THESIS
2014
xii, 186 pages : illustrations ; 30 cm
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: Fix...[
Read more ]
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.
Post a Comment