Optimization of transit route network, vehicle headways and timetables for large-scale transit networks. (English) Zbl 1138.90350

Zhao, Fang; Zeng, Xiaogang

Eur. J. Oper. Res. 186, No. 2, 841-855 (2008).

Summary: This paper presents a metaheuristic method for optimizing transit networks, including route network design, vehicle headway, and timetable assignment. Given information on transit demand, the street network of the transit service area, and total fleet size, the goal is to identify a transit network that minimizes a passenger cost function. Transit network optimization is a complex combinatorial problem due to huge search spaces of route network, vehicle headways, and timetables. The methodology described in this paper includes a representation of transit network variable search spaces (route network, headway, and timetable); a user cost function based on passenger random arrival times, route network, vehicle headways, and timetables; and a metaheuristic search scheme that combines simulated annealing, tabu, and greedy search methods. This methodology has been tested with problems reported in the existing literature, and applied to a large-scale realistic network optimization problem. The results show that the methodology is capable of producing improved solutions to large-scale transit network design problems in reasonable amounts of time and computing resources.

MSC:

90B10	Deterministic network models in operations research
90B06	Transportation, logistics and supply chain management
90C27	Combinatorial optimization

Keywords:

metaheuristics; routing/timetable

References:

[1]	Baaj, M. H.; Mahmassani, H. S., An AI-based approach for transit route system planning and design, Journal of Advanced Transportation, 25, 2, 187-210 (1991)
[2]	Bertsekas, D. P., Network Optimization: Continuous and Discrete Models (1998), Athena Scientific: Athena Scientific Belmont, Mass · Zbl 0997.90505
[3]	Bowerman, R.; Hall, B.; Calamai, P., A multi-objective optimization approach to urban school bus-routing: Formulations and solution methods, Transportation Research - Part A, 29, 2, 107-123 (1995)
[4]	Ceder, A.; Wilson, N. H.M., Bus network design, Transportation Research - Part B, 20, 331-344 (1986)
[6]	Gao, Z.; Sun, H.; Shan, L. L., A continuous equilibrium network design model and algorithm for transit systems, Transportation Research - Part B, 38, 235-250 (2002)
[7]	Hajek, B., Cooling schedules for optimal annealing, Mathematical Methods of Operations Research, 13, 311-329 (1988) · Zbl 0652.65050
[8]	Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M. P., Optimization by simulated annealing, Science, 4598, 220, 671-680 (1983) · Zbl 1225.90162
[10]	Matisziw, T. C.; Murray, A. T.; Kim, C., Strategic route extension in transit networks, European Journal of Operational Research, 171, 661-673 (2006) · Zbl 1090.90010
[11]	Ramirez, A. I.; Seneviratne, P. N., Transit route design applications using GIS, Transportation Research Record, 1557, 10-14 (1996)
[13]	Wirasinghe, S. C.; Ghoneim, N. S., Spacing of bus-stops for many-to-many travel demand, Transportation Science, 15, 3, 210-221 (1981)
[14]	Wu, C.; Murray, A., Optimizing public transit quality and access: The multiple-route maximal covering/shortest path problem, Environment and Planning B: Planning and Design, 32, 163-178 (2005)
[15]	Zhao, F., Large-scale transit network optimization by minimizing transfers and user cost, Journal of Public Transportation, 9, 2, 107-129 (2006)
[17]	Zhao, F.; Zeng, X., Optimization of transit network layout and headway with a combined genetic algorithm and simulated annealing method, Journal of Engineering Optimization, 38, 6, 701-722 (2006)