Optimal transit route network design problem: Algorithms, implementations, and numerical results.

摘要

Previous approaches used to solve the transit route network design problem (TRNDP) can be classified into three categories: (1) Practical guidelines and ad hoc procedures; (2) Analytical optimization models for idealized situations; and (3) Meta-heuristic approaches for more practical problems. When the TRNDP is solved for a network of realistic size in which many parameters need to be determined, it is a combinatorial and NP-hard problem in nature and several sources of non-linearities and non-convexities involved preclude guaranteed globally optimal solution algorithms. As a result, the meta-heuristic approaches, which are able to pursue reasonably good local (possibly global) optimal solutions and deal with simultaneous design of the transit route network and determination of its associated service frequencies, become necessary. The objective of this dissertation is to systematically study the optimal TRNDP using hybrid heuristic algorithms at the distribution node level without aggregating the travel demand zones into a single node. A multi-objective nonlinear mixed integer model is formulated for the TRNDP. The proposed solution framework consists of three main components: an Initial Candidate Route Set Generation Procedure (ICRSGP) that generates all feasible routes incorporating practical bus transit industry guidelines; a Network Analysis Procedure (NAP) that determines transit trips for the TRNDP with variable demand, assigns these transit trips, determines service frequencies and computes performance measures; and a Heuristic Search Procedure (HSP) that guides the search techniques. Five heuristic algorithms, including the genetic algorithm, local search, simulated annealing, random search and tabu search, are employed as the solution methods for finding an optimal set of routes from the huge solution space. For the TRNDP with small network, the exhaustive search method is also used as a benchmark to examine the efficiency and measure the quality of the solutions obtained by using these heuristic algorithms. Several C++ program codes are developed to implement these algorithms for the TRNDP both with fixed and variable transit demand. Comprehensive experimental networks are used and successfully tested. Sensitivity analyses for each algorithm are conducted and model comparisons are performed. Numerical results are presented and the multi-objective decision making nature of the TRNDP is explored. Related characteristics underlying the TRNDP are identified, inherent tradeoffs are described and the redesign of the existing transit network is also discussed.