Optimal Routing Design of a Community Shuttle for Metro Stations
Publication: Journal of Transportation Engineering
Volume 139, Issue 12
Abstract
The optimization of a community shuttle route plays an important role in the efficient operation of public transit microcirculation. This paper develops a solution for the optimal routing design problem with the objective of minimizing the total cost, including user and supplier costs, considering passenger traffic demand and budget constraints. The optimization variables include route and headway. To calculate the user cost, a heuristic algorithm for locating stops is presented. Then the optimized headway corresponding to a given bus route is confirmed by minimizing the total cost function. In solving the problem, a depth-first search algorithm (DFS) and a genetic algorithm (GA) are both presented. By comparing the results and the CPU time of the two algorithms, this paper demonstrated that GA is reliable and more efficient than DFS. The impacts of route length and the maximum tolerable walking distance on the cost and headway are also analyzed.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
This paper is sponsored by NSFC Project (No. 71131001-2) and National Basic Research Program of China (No. 2012CB725403-5) and the Foundation Research Funds for the Central Universities (2013YJS045).
References
Braysy, O., and Gendreau, M. (2005). “Vehicle routing problem with time windows. Part 1: Routing construction and local search algorithms.” Transp. Sci., 39(1), 104–118.
Ceder, A. (2009). “Stepwise multi-criteria and multi-strategy design of public transit shuttles.” J. Multi-Criteria Decis. Anal., 16(1–2), 21–38.
Ceder, A., and Yim, Y. B. (2002). “Integrated smart feeder/shuttle bus service.” California Path Program, Institute of Transportation Studies, Univ. of California at Berkeley, Berkeley, CA.
Chang, S. K., and Lee, C. J. (1993). “Welfare comparison of fixed- and flexible-route bus systems.”, Transportation Research Board, Washington, DC, 16–22.
Chang, S. K., and Schonfeld, P. M. (1991). “Multiple period optimization of bus transit systems.” Transp. Res. B, 25(6), 453–478.
Chang, S. K., and Yu, W. J. (1996). “Comparison of subsidized fixed- and flexible-route bus system.”, Transportation Research Board, Washington, DC, 15–20.
Chien, S. (2000). “Optimal feeder bus routes on irregular street networks.” J. Adv. Transp., 34(2), 213–248.
Chien, S. (2005). “Optimization of headway, vehicle size and route choice for minimum cost feeder service.” Transp. Plann. Technol., 28(5), 359–380.
Chien, S., and Schonfeld, P. M. (1997). “Optimization of grid transit system in heterogeneous urban environment.” J. Transp. Eng., 28–35.
Chien, S., and Schonfeld, P. M. (1998). “Joint optimization of a rail transit line and its feeder bus system.” J. Adv. Transp., 32(3), 253–282.
Chien, S., Spasovic, L. N., Elefsiniotis, S. S., and Chhonkar, R. S. (2001a). “Evaluation of feeder bus systems with probabilistic time-varying demands and non-additive time costs.”, Transportation Research Board, Washington, DC, 47–55.
Chien, S., Yang, Z., and Hou, E. (2001b). “Genetic algorithm approach for transit route planning and design.” J. Transp. Eng., 200–207.
Cordeau, J. F., Gendreau, M., Laporte, G., Potvin, J. Y., and Semet, F. (2002). “A guide to vehicle routing heuristics.” J. Oper. Res. Soc., 53(5), 512–522.
Fan, W., and Machemehl, R. B. (2006a). “Optimal transit route network design problem with variable transit demand: genetic algorithm approach.” J. Transp. Eng., 40–51.
Fan, W., and Machemehl, R. B. (2006b). “Using a simulated annealing algorithm to solve the transit route network design problem.” J. Transp. Eng., 122–132.
Ibaraki, T., Imahori, S., Kubo, M., Masuda, T., Uno, T., and Yagiura, M. (2005). “Effective local search algorithms for routing and scheduling problems with general time-window constraints.” Transp. Sci., 39(2), 206–232.
Imam, M. O. (1998). “Optimal design of public bus service with demand equilibrium.” J. Transp. Eng., 431–436.
Jerby, S., and Ceder, A. (2006). “Optimal routing design for shuttle bus service.”, Transportation Research Board, Washington, DC, 14–22.
Kuah, G. K., and Perl, J. (1988). “Optimization of feeder bus routes and bus-stop spacing.” J. Transp. Eng., 341–354.
Lee, Y. J., and Vuchic, V. R. (2005). “Transit network design with variable demand.” J. Transp. Eng., 1–10.
Mohaymany, A. S., and Gholami, A. (2010). “Multimodal feeder network design problem: ant colony optimization approach.” J. Transp. Eng., 323–331.
Ngamchai, S., and Lovell, D. J. (2003). “Optimal time transfer in bus transit route network design using a genetic algorithm.” J. Transp. Eng., 510–521.
Pattnaik, S. B., Mohan, S., and Tom, V. M. (1998). “Urban bus transit route network design using genetic algorithm.” J. Transp. Eng., 368–375.
Shi, F., Wang, H., Yu, L., and Hu, F. (2011). MATLAB intelligent algorithm and analysis of 30 cases, Beijing University of Aeronautics and Astronautics Press, Beijing (in Chinese).
Shrivastava, P., and Dhingra, S. L. (2001). “Development of feeder routes for suburban railway stations using a heuristic approach.” J. Transp. Eng., 334–341.
Shrivastava, P., and Dhingra, S. L. (2002). “Development of coordinated schedules using genetic algorithms.” J. Transp. Eng., 89–96.
Shrivastava, P., and Mahony, M. O. (2006). “A model for development of optimized feeder routes and coordinated schedules-A genetic algorithms approach.” Transp. Policy, 13(5), 413–425.
Solomon, M. M., and Desrosiers, J. (1988). “Time window constrained routing and scheduling problems.” Trans. Sci., 22(1), 1–13.
Tom, V. M., and Mohan, S. (2003). “Transit route network design using frequency coded genetic algorithm.” J. Transp. Eng., 186–195.
Tsao, S., and Schonfeld, P. (1983). “Optimization of zonal transit service.” J. Transp. Eng., 257–272.
Verma, A., and Dhingra, S. L. (2005). “Feeder bus routes generation within integrated mass transit planning framework.” J. Transp. Eng., 822–834.
Wang, H. Y., Huang, Q., Li, C. T., and Chu, B. Z. (2010). Graph theory algorithms based on MATLAB, Beijing University of Aeronautics and Astronautics Press, Beijing (in Chinese).
Xu, W. T., He, S. W., Song, R., Li, J., and Yuan, R. W. (2009). “Route generation optimization model for feeder bus based on advanced genetic algorithm.” J. Beijing Jiaotong Univ., 33(3), 40–44 (in Chinese).
Yim, Y. B., and Ceder, A. (2006). “Smart feeder/shuttle bus service: Consumer research and design.” J. Publ. Transp., 9(1), 19–43.
Zhao, F., and Zeng, X. (2007). “Optimization of user and operator cost for large-scale transit network.” J. Transp. Eng., 240–251.
Information & Authors
Information
Published In
Journal of Transportation Engineering
Volume 139 • Issue 12 • December 2013
Pages: 1211 - 1223
Copyright
© 2013 American Society of Civil Engineers.
History
Received: Nov 30, 2012
Accepted: Jul 26, 2013
Published online: Jul 27, 2013
Published ahead of production: Jul 29, 2013
Published in print: Dec 1, 2013
Discussion open until: Dec 27, 2013
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.