Transit network design with stochastic demand

Abstract

The transit network design problem (TNDP) arises in the rail, bus and ferry industries. It requires the joint determination of the service or carrier network and the commodity flows to achieve certain objective, such as minimum cost, maximum revenue, etc. It has been well recognized that the stochastic nature of demand has a substantial impact on the service design patterns. Integrating the consideration of uncertain demand into the TNDP can lead to robust and cost-effective service network designs which not only provide reliable services to passengers, but also reduce the expected cost for the operating companies. This thesis focuses on the tactical planning methodology for the TNDP with stochastic demand. To address demand uncertainty, two types of services are introduced: Fixed Route Transit (FRT) and Demand Responsive Transit (DRT). FRT is operated with a fixed schedule, while DRT is only called upon to accommodate demand overflow, which typically has a higher unit cost. In this research, the TNDP is formulated as a two stage mixed-integer stochastic problem with capacity constraints. This thesis draws upon the concept of regular service reliability (SR); i.e. the FRT is designed to be sufficient to cover the demand up to a certain specified SR. This approach reduces the otherwise difficult 2-stage stochastic problem into two phases that can be solved iteratively. For a specific SR, Phase-1 determines the deployment of FRT which covers the demand up to a specific SR, and Phase-2 determines the DRT capacity to accommodate the realized demand that exceeds the capacity of the FRT. In determining the SR, the expected cost arising from the DRT must be duly considered. The key is to determine the SR of the FRT in order to minimize the expected system cost under stochastic demand. The level of SR internalizes the tradeoff between these two types of services. The final optimal solution is obtained by conducting a gradient search to obtain the optimal SR. Other than providing a performance characterization for the FRT, the term SR allows decoupling the computations of the FRT schedule and DRT deployment, leading to substantial gains in computational efficiency. Two passenger flow patterns, system optimal (SO) and user equilibrium (UE) are investigated separately. With the notion of SR, a linear programming (LP) approach is formulated to deal with the great challenges in the encapsulation of stochastic demand, equilibrium constraints and hard capacity constraints simultaneously, through treating the negative Lagrange multiplier associated with the capacity constraint as the extra delay caused by passenger overload. The SR-based formulation and the gradient algorithm are then applied to one actual ferry network scheduling problem in Hong Kong with promising results. Compared to existing stochastic methods, this approach leads to substantial computation time savings. To evaluate the benefits of passenger reservation, two DRT provision schemes are investigated based on whether the demand information is acquired in advance by passenger reservation to facilitate the company to plan for DRT. In addition to the great computation efficiency brought by the reformulation, service reliability also conveys a level of robustness in the context of robust rapid TNDP under demand uncertainty. Two types of services, rapid transit services and dial-or-ride services are introduced, which work as FRT and DRT respectively. The network topology and frequencies of rapid transit services and the deployment of dial-a-ride services are determined to minimize system cost, which takes into account passenger waiting and transfer time cost. A hybrid solution algorithm combining the improved gradient method and neighborhood search is developed to further improve the algorithm efficiency. The algorithm confines the computation time to within minutes for a 10-node 19-link network, which may pave its way for larger-scale network applications. The level of robustness represented by SR can be optimized endogenously, whereas in traditional robust formulations, the level of robustness is typically set arbitrarily without cost justifications. The case study demonstrates that the utilization of the two-phase formulation can lead to an utterly different transit lines alignment and reduced transfer times of passengers as compared with the traditional robust method. Due to the high construction and operating costs of rapid transit lines, some existing lines may require government subsidy to maintain operation. On the other hand, dial-a-ride services can make use of the existing roadways hence are much more economical to implement. It is well known that public transport usage, i.e. FRT and DRT combined, is positively related to urban development density. This thesis extends the TNDP by considering the development density. Instead of assuming exogenous OD demand, we relate the development demand density in each station and apply the gravity trip distribution model to obtain the OD demand. The robust optimization approach is applied to address the uncertainty demand as a polyhedral uncertainty set. It is reformulated as a mixed integer linear program through replacing the uncertainty affected constraints by its dual problem. A novel formulation to relate rapid transit construction as a function of the development density with stochastic demand is developed. The minimum development density to allow for financially viable rapid transit is studied.

Date of Award	2014
Original language	English
Awarding Institution	The Hong Kong University of Science and Technology