Route Design Problem of Customized Buses: Mixed Integer Programming Model and Case Study
Publication: Journal of Transportation Engineering, Part A: Systems
Volume 144, Issue 11
Abstract
In recent years, the customized bus (CB) has been introduced and popularized in China to improve the attraction and service level of public transportation. A key point of the CB system, the route design problem, is always formulated as a vehicle routing problem with pickup and delivery (VRPPD). However, VRPPD cannot sufficiently describe the in-vehicle passengers of multiple vehicles involved. In this paper, a mixed integer programming model is developed to formulate a multivehicle routing problem, with suggestions for bus stop locations and routes. Meanwhile, the model can determine passenger-to-vehicle assignment based on a series of constraints, like operation standard and number of stations. In solving the problem, a numerical example is used to compare a genetic algorithm (GA) and branch-and-cut algorithm. The comparison results illustrate that GA is more efficient with lower complexity. Finally, in order to apply and evaluate the proposed model, a real-world case study using smartcard data is conducted to compare the approach with the current CB route design method in Beijing.
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 (Nos. 71621001, 91746201, 71601015).
References
Abdulkader, M. M., Y. Gajpal, and T. Y. ElMekkawy. 2015. “Hybridized ant colony algorithm for the multi compartment vehicle routing problem.” Appl. Soft Comput. 37: 196–203. https://doi.org/10.1016/j.asoc.2015.08.020.
Amirgholy, M., and E. J. Gonzales. 2016. “Demand responsive transit systems with time-dependent demand: User equilibrium, system optimum, and management strategy.” Transp. Res. Part B: Methodol. 92: 234–252. https://doi.org/10.1016/j.trb.2015.11.006.
Amiripour, S. M. M., A. S. Mohaymany, and A. Ceder. 2015. “Optimal modification of urban bus network routes using a genetic algorithm.” J. Transp. Eng. 141 (3): 04014081. https://doi.org/10.1061/(ASCE)TE.1943-5436.0000741.
Arbex, R. O., and C. B. da Cunha. 2015. “Efficient transit network design and frequencies setting multi-objective optimization by alternating objective genetic algorithm.” Transp. Res. Part B: Methodol. 81: 355–376. https://doi.org/10.1016/j.trb.2015.06.014.
Bin, L. I., M. Yang, R. Xiao, S. O. Automobile, and C. University. 2016. “The study on factors affecting customized city bus service fares base on logistic model.” China Sciencepaper 11 (7): 786–792.
Cao, Y., and J. Wang. 2016. “The key contributing factors of customized shuttle bus in rush hour: A case study in Harbin city.” Procedia Eng. 137: 478–486. https://doi.org/10.1016/j.proeng.2016.01.283.
Chakroborty, P. 2010. “Genetic algorithms for optimal urban transit network design.” Comput. Aided Civ. Infrastruct. Eng. 18 (3): 184–200.
Chen, X., Z. Liu, D. Hua, and I. Kim. 2017. “A new model for rail-based park-and-ride with feeder bus services.” Transp. Res. Procedia. 21: 79–86. https://doi.org/10.1016/j.trpro.2017.03.079.
Chevrier, R., A. Liefooghe, L. Jourdan, and C. Dhaenens. 2012. “Solving a dial-a-ride problem with a hybrid evolutionary multi-objective approach: Application to demand responsive transport.” Appl. Soft Comput. 12 (4): 1247–1258. https://doi.org/10.1016/j.asoc.2011.12.014.
Cipriani, E., S. Gori, and M. Petrelli. 2012. “Transit network design: A procedure and an application to a large urban area.” Transp. Res. Part C: Emerging 20 (1): 3–14. https://doi.org/10.1016/j.trc.2010.09.003.
Cordeau, J. F. 2006. “A branch-and-cut algorithm for the dial-a-ride problem.” Oper. Res. 54 (3): 573–586. https://doi.org/10.1287/opre.1060.0283.
Cordeau, J. F., and G. Laporte. 2007. “The dial-a-ride problem: Models and algorithms.” Ann. Oper. Res. 153 (1): 29–46. https://doi.org/10.1007/s10479-007-0170-8.
Deng, L. B., W. Gao, W. L. Zhou, and T. Z. Lai. 2013. “Optimal design of feeder-bus network related to urban rail line based on transfer system.” Procedia-Social Behav. Sci. 96: 2383–2394. https://doi.org/10.1016/j.sbspro.2013.08.267.
Fan, W. 2004. “Optimal transit route network design problem: Algorithms, implementations, and numerical results.” Ph.D. dissertation, Center for Transportation Research, Univ. of Texas at Austin.
Fan, W., and R. B. Machemehl. 2006. “Optimal transit route network design problem with variable transit demand: Genetic algorithm approach.” J. Transp. Eng. 132 (1): 40–51. https://doi.org/10.1061/(ASCE)0733-947X(2006)132:1(40).
Fan, W., and R. B. Machemehl. 2008. “Tabu search strategies for the public transportation network optimizations with variable transit demand.” Comput. Civ. Infrastruct. Eng. 23 (7): 502–520. https://doi.org/10.1111/j.1467-8667.2008.00556.x.
Fatnassi, E., O. Chebbi, and J. C. Siala. 2014. “Bee colony algorithm for the routing of guided automated battery-operated electric vehicles in personal rapid transit systems.” In Proc., IEEE Congress on Evolutionary Computation, 536–543. New York: IEEE.
Gribkovskaia, I., Ø. Halskau, G. Laporte, and M. Vlček. 2007. “General solutions to the single vehicle routing problem with pickups and deliveries.” Eur. J. Oper. Res. 180 (2): 568–584. https://doi.org/10.1016/j.ejor.2006.05.009.
Harms, S., and B. Truffer. 1998. “The emergence of a nationwide carsharing cooperative in Switzerland.” In A case-study for the EC-supported research project “Strategic Niche Management as a tool for transition to a sustainable transport system”. Zürich: EAWAG.
Kuan, S. N., H. L. Ong, and K. M. Ng. 2006. “Solving the feeder bus network design problem by genetic algorithms and ant colony optimization.” Adv. Eng. Software 37 (6): 351–359. https://doi.org/10.1016/j.advengsoft.2005.10.003.
Kusakabe, T., and Y. Asakura. 2014. “Behavioural data mining of transit smart card data: A data fusion approach.” Transp. Res. Part C: Emerging 46: 179–191. https://doi.org/10.1016/j.trc.2014.05.012.
Langlois, G. G., H. N. Koutsopoulos, and J. Zhao. 2016. “Inferring patterns in the multi-week activity sequences of public transport users.” Transp. Res. Part C: Emerging 64: 1–16. https://doi.org/10.1016/j.trc.2015.12.012.
Li, X., and L. Quadrifoglio. 2010. “Feeder transit services: Choosing between fixed and demand responsive policy.” Transp. Res. Part C: Emerging 18 (5): 770–780. https://doi.org/10.1016/j.trc.2009.05.015.
Liu, T., and A. Ceder. 2015. “Analysis of a new public-transport-service concept: Customized bus in China.” Transp. Policy 39: 63–76. https://doi.org/10.1016/j.tranpol.2015.02.004.
Liu, T., A. Ceder, R. Bologna, and B. Cabantous. 2016. “Commuting by customized bus: A comparative analysis with private car and conventional public transport in two cities.” Public J. Transp. 19 (2): 55–74. https://doi.org/10.5038/2375-0901.19.2.4.
Long, Y., and J. C. Thill. 2015. “Combining smart card data and household travel survey to analyze jobs-housing relationships in Beijing.” Comput. Environ. Urban Syst. 53: 19–35. https://doi.org/10.1016/j.compenvurbsys.2015.02.005.
Lysgaard, J., A. N. Letchford, and R. W. Eglese. 2004. “A new branch-and-cut algorithm for the capacitated vehicle routing problem.” Math. Program. 100 (2): 423–445. https://doi.org/10.1007/s10107-003-0481-8.
Ma, J., Y. Yang, W. Guan, F. Wang, T. Liu, W. Tu, and C. Song. 2017a. “Large-scale demand driven design of a customized bus network: A methodological framework and Beijing case study.” J. Adv. Transp. 2017 (3): 1–14. https://doi.org/10.1155/2017/3865701.
Ma, X., C. Liu, H. Wen, Y. Wang, and Y. J. Wu. 2017b. “Understanding commuting patterns using transit smart card data.” J. Transp. Geogr. 58: 135–145. https://doi.org/10.1016/j.jtrangeo.2016.12.001.
Ma, X., Y. J. Wu, Y. Wang, F. Chen, and J. Liu. 2013. “Mining smart card data for transit riders’ travel patterns.” Transp. Res. Part C: Emerging 36: 1–12. https://doi.org/10.1016/j.trc.2013.07.010.
Mahdi Amiripour, S. M., A. S. Mohaymany, and A. Ceder. 2014. “Optimal modification of urban bus network routes using a genetic algorithm.” J. Transp. Eng. 141 (3): 04014081. https://doi.org/10.1061/(ASCE)TE.1943-5436.0000741.
Martí, R., and G. Reinelt. 2011. “Branch-and-cut.” Appl. Math. Sci. 175: 95–116. https://doi.org/10.1137/1033004.
Mitchell, J. E. 2011. “Branch and cut.” In Wiley encyclopedia of operations research and management science. Hoboken, NJ: Wiley.
Montané, F. A. T., and R. D. Galvao. 2006. “A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service.” Comput. Oper. Res. 33 (3): 595–619. https://doi.org/10.1016/j.cor.2004.07.009.
Nayeem, M. A., M. K. Rahman, and M. S. Rahman. 2014. “Transit network design by genetic algorithm with elitism.” Transp. Res. Part C: Emerging 46: 30–45. https://doi.org/10.1016/j.trc.2014.05.002.
Padberg, M. W., and G. Rinaldi. 1990. “Facet identification for the symmetric traveling salesman polytope.” Math. Program. 47 (1–3): 219–257. https://doi.org/10.1007/BF01580861.
Padberg, M. W., and G. Rinaldi. 1991. “A branch-and-cut algorithm for the resolution of large-scale symmetric travelling salesman problems.” SIAM Rev. 33 (1): 60–100. https://doi.org/10.1137/1033004.
Tabassum, S., S. Tanaka, F. Nakamura, and A. Ryo. 2017. “Feeder network design for mass transit system in developing countries (case study of Lahore, Pakistan).” Transp. Res. Procedia. 25: 3129–3146. https://doi.org/10.1016/j.trpro.2017.05.343.
Tao, S., J. Corcoran, I. Mateo-Babiano, and D. Rohde. 2014a. “Exploring bus rapid transit passenger travel behavior using big data.” Appl. Geogr. 53 (53): 90–104. https://doi.org/10.1016/j.apgeog.2014.06.008.
Tao, S., D. Rohde, and J. Corcoran. 2014b. “Examining the spatial-temporal dynamics of bus passenger travel behavior using smart card data and the flow-comap.” J. Transp. Geogr. 41 (41): 21–36. https://doi.org/10.1016/j.jtrangeo.2014.08.006.
Tong, L. C., L. Zhou, J. Liu, and X. Zhou. 2017. “Customized bus service design for jointly optimizing passenger-to-vehicle assignment and vehicle routing.” Transp. Res. Part C: Emerging 85: 451–475. https://doi.org/10.1016/j.trc.2017.09.022.
Viggiano, C., H. N. Koutsopoulos, N. H. Wilson, and J. Attanucci. 2017. “Journey-based characterization of multi-modal public transportation networks.” Public Transp. 9 (1–2): 437–461. https://doi.org/10.1007/s12469-016-0145-8.
Wang, C., X. Li, X. Zhou, A. Wang, and N. Nedjah. 2016. “Soft computing in big data intelligent transportation systems.” Appl. Soft Comput. 38: 1099–1108. https://doi.org/10.1016/j.asoc.2015.06.006.
Xiong, J., W. Guan, L. Song, A. Huang, and C. Shao. 2013. “Optimal routing design of a community shuttle for metro stops.” J. Transp. Eng. 139 (12): 1211–1223. https://doi.org/10.1061/(ASCE)TE.1943-5436.0000608.
Yang, X., and H. Liu. 2007. “Transit route network optimal design based on routes optimal choice.” Comput. Commun. 25 (2): 14–18. https://doi.org/10.3963/j.issn.1674-4861.2007.02.004.
Zachariadis, E. E., C. D. Tarantilis, and C. T. Kiranoudis. 2009. “A hybrid metaheuristic algorithm for the vehicle routing problem with simultaneous delivery and pick-up service.” Expert. Syst. Appl. 36 (2): 1070–1081. https://doi.org/10.1016/j.eswa.2007.11.005.
Zachariadis, E. E., C. D. Tarantilis, and C. T. Kiranoudis. 2015. “The load-dependent vehicle routing problem and its pick-up and delivery extension.” Transp. Res. Part B: Methodol. 71: 158–181. https://doi.org/10.1016/j.trb.2014.11.004.
Zhao, F. 2006. “Large-scale transit network optimization by minimizing transfers and user cost.” Public J. Transp. 9 (2): 107–129. https://doi.org/10.5038/2375-0901.9.2.6.
Zhao, F., and X. Zeng. 2006. “Optimization of transit network layout and headway with a combined genetic algorithm and simulated annealing method.” Eng. Optimiz. 38 (6): 701–722. https://doi.org/10.1080/03052150600608917.
Zhao, F., and X. Zeng. 2007. “Optimization of user and operator cost for large-scale transit network.” J. Transp. Eng. 133 (4): 240–251. https://doi.org/10.1061/(ASCE)0733-947X(2007)133:4(240).
Zhao, F., and X. Zeng. 2008. “Optimization of transit route network, vehicle headways and timetable for large-scale transit networks.” Eur. J. Oper. Res. 186 (2): 841–855. https://doi.org/10.1016/j.ejor.2007.02.005.
Zhao, H., W. Xu, and R. Jiang. 2015. “The memetic algorithm for the optimization of urban transit network.” Expert. Syst. Appl. 42 (7): 3760–3773. https://doi.org/10.1016/j.eswa.2014.11.056.
Zhong, C., E. Manley, S. M. Arisona, M. Batty, and G. Schmitt. 2015. “Measuring variability of mobility patterns from multiday smart-card data.” J. Comput. Sci. 9: 125–130. https://doi.org/10.1016/j.jocs.2015.04.021.
Zhong, S., and S. Ma. 2009. “Improved branch and cut algorithm for vehicle routing problem.” [In Chinese.] Syst. Eng. -Theory Pract. 29 (10): 152–158.
Zhou, J., E. Murphy, and Y. Long. 2014. “Commuting efficiency in the Beijing metropolitan area: An exploration combining smartcard and travel survey data.” J. Transp. Geogr. 41 (41): 175–183. https://doi.org/10.1016/j.jtrangeo.2014.09.006.
Zhou, J., N. Sipe, Z. Ma, D. Mateo-Babiano, and S. Darchen. 2017. “Monitoring transit-served areas with smartcard data: A Brisbane case study.” J. Transp. Geogr., in press. https://doi.org/10.1016/j.jtrangeo.2017.07.005.
Information & Authors
Information
Published In
Journal of Transportation Engineering, Part A: Systems
Volume 144 • Issue 11 • November 2018
Copyright
©2018 American Society of Civil Engineers.
History
Received: Aug 25, 2017
Accepted: May 9, 2018
Published online: Aug 28, 2018
Published in print: Nov 1, 2018
Discussion open until: Jan 28, 2019
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.