A framework is proposed for determining the least expected cost path in a schedule-based time-expanded public transit network where travel times, and thus bus arrival and departure times at stops, are stochastic. Transfer reliability is incorporated in a label-correcting algorithm with a penalty function for the expected waiting time when transferring that reflects the likelihood of making a successful transfer. The algorithm is implemented in transit assignment on an Austin, Texas test network, using actual bus arrival and departure time distributions from vehicle location data. Assignment results are compared with those of a deterministic shortest path based on the schedule and from a calibrated transit assignment model. Simulations of the network and passenger paths are also conducted to evaluate the overall path reliability. The reliable shortest path algorithm is found to penalize transferring and provide paths with improved transfer and overall reliability. The proposed model is realistic, incorporating reliability measures from vehicle location data, and practical, given the efficient shortest path approach and application to transit assignment. / text

Schedule-based transit assignment models have been studied extensively from 2000, considering more time-dependent transit passenger behavior associated with the transit schedule. Currently, transit schedule information is more easily accessed using new telecommunications systems, such as mobile devices and the internet. One critical example of information sharing is Google's General Transit Feed Specification (GTFS). The information of the schedule per se, however, is not enough to explain the transit passenger's behavior, especially in a congested transit system. Regarding the congestion issues on a transit system, numerous researches have studied a transit schedule network (Nguyen et al., 2001; Nuzzolo et al., 2001; Poon et al., 2004; Hamdouch and Lawphonpanich, 2008, 2010).Along the stream toward understanding transit passenger behavior in the capacitated transit schedule network, we propose solution models for solving the deterministic and stochastic user equilibrium (SUE) problems on a capacitated transit schedule network. Nguyen et al. (2001) introduced how the capacitated user equilibrium (UE) on a transit schedule network is different from the auto user equilibrium. For the foundation of the study, we utilize the link-based and time-expanded (LBTE) transit schedule network introduced by Noh et al. (2012a) which effectively captures turning movements like transfers easily as well as maintaining the efficient size of a schedule-based network. In the LBTE transit network, time points are assigned to each link connecting two stops by each run (or route). Utilizing the "link-based" structure, a link-based shortest path (LBSP) and hyperpath search (LBHP) models (Noh et al., 2012a) are introduced. Especially, the hyperpath employs a log-sum weighting function for incorporating multiple schedule alternatives at each stop node considering passenger's stochastic behavior. One distinctive transit passenger behavior over a congested transit system is a first-in-first-out (FIFO) priority on boarding. A passenger already on board has the higher priority than passengers who are about to boarding, and the passengers arriving earlier at a stop will have higher priority than the passengers arriving later at the stop. To consider the capacitated UE considering the relation between the FIFO boarding priority and vehicle capacity constraint, we apply a "soft-capacity" cost (Nguyen et al., 2001). This soft capacity cost function allows some violation of the predefined vehicle capacity, but the violation will be penalized and affect the cost of the path in the next iteration. The penalty of the soft capacity cost function allows not to assigning passengers on the alternatives having the lower priority of boarding, which finally leads to the solution of the capacitated transit deterministic user equilibrium (DUE) or SUE problems. For the main transit assignment models, we proposed path- and hyperpath-based methods and a self-adaptive method considering deterministic and stochastic passenger behaviors. First, we developed the hyperpath-based assignment method by Noh et al. (2012b). For the FIFO transit passenger behavior, typically accompanying asymmetric (non-separable) cost relation, we also introduce a diagonalization technique (Sheffi, 1985) with the method of successive average (MSA) assignment technique. As expecting a better performance, second, we introduced the path-based assignment models using gradient projection. For the FIFO passenger behavior on boarding, we considered the same diagonalization approach used in the hyperpath-based assignment model and a full-Hessian scaling matrix in the gradient projection. By utilizing a full path set for each O-D pair, a better performance is guaranteed with the path-based model but the diagonalization technique may result in longer iterations. For improving the diagonalization steps, third, we explored several other possible methods. Above all, we proposed the better initial solution (BIS) model which assigns the initial flows on the priority path over congested links and also maintains feasible flows below the capacity constraint. On the other hand, we also added two additional assignment models to improve the diagonalization technique. One utilizes a full Hessian scaling matrix in the proposed path-based assignment model instead of diagonalization and the other is the self-adaptive gradient projection (SAGP) model introduced by Chen et al. (2012) which does not require a scaling matrix by optimizing the step-size in the path-based projection model. For improving the SAGP model, we modified the SAGP model. First, we applied the SAGP at a disaggregate level for each O-D pair as expecting a compact set of path alternatives limited by each O-D pair, called disaggregate self-adaptive gradient projection (DSAGP). Second, we applied a type of diagonalization technique in the SAGP model by maintaining the residual capacities for the estimated flows in the next iteration. Beyond just a single model development, the proposed transit assignment models not only showed various possibilities of the transit assignment, but also showed which model is more efficient and practical in terms of a real application. A computational model structure using the proposed models was mainly designed for an effective model development by sharing numerous components as well as maintaining the efficient data structure. The nine combination models based on the proposed three main models (hyperpath- and path-based and DSAGP assignment models) and the efficient BIS technique for solving the problems were tested and analyzed on a sample network and a partial Sacramento regional transit network.

[Truncated abstract] This thesis develops a scheduled protocol (time division multiple access, TDMA) called flexible-schedule-based TDMA Protocol (FlexiTP), to address the problem of providing end-to-end guarantees on data delivery, whilst also respecting severe resource constraints of wireless sensor networks. FlexiTP achieves this balance through a distributed, synchronised, and loose slot structure in which sensor nodes can build, modify, or extend their schedules based on their local information. In FlexiTP, it is not necessary to predetermine the number of slots required for a network. FlexiTP's local repair scheme allows nodes to adjust their schedules dynamically and autonomously to recover from node and communication faults. Hence, it maintains a reliable and selforganising multihop network. Most sensor network protocols designed for data gathering applications implicitly assume a periodic rate of data collection from all nodes in the network to the base station. However, nodes may want to report their data more rapidly or slowly depending on the significance and importance of their data to the end-user. The problem is that traditional TDMA-based protocols are not flexible to changes in traffic patterns because of their rigid slot structure schemes. This thesis aims to solve this problem by developing an ondemand TDMA slot transfer method that leverages the flexible-slot structure algorithm of FlexiTP to transfer time slots from one part of the network to another part. ... While these communication patterns are sufficient for monitoring applications, individual sensor nodes may need to send their data to multiple destination nodes across the network in order to execute a distributed cooperative-function based on their local environment. This peer-to-peer communication pattern makes sensor networks more reactive to triggers from the environment. This thesis attempts to solve the problem of lack of peer-to-peer communication in the design of a TDMA-driven protocol by extending the idea of on-demand TDMA slot transfer method to allow each sensor node in the network to claim extra time slots to communicate with any other nodes (peers) in the network, without going through the base station. Nodes in the network may have different priorities of data because of event-triggering sensor readings or various types of sensor readings (e.g., light, temperature, and humidity) they provide. When nodes with high priority packets increase the frequency of their data collections, the network bandwidth may be dominated by these nodes. It is desirable to allow nodes with low priority packets to aggregate their packets and so enabling these nodes to send their data to the base station under the current available network bandwidth. This thesis proposes an on-demand data aggregation algorithm that enables sensor nodes to perform an in-network-aggregation based on their current sensing requirements and network capacity constraints. In summary, this thesis describes the design, implementation, and evaluation of protocols for wireless sensor networks that focus on achieving energy-efficiency, provisioning performance assurances, and supporting reactivity and adaptability in constantly changing environment.