IDEAS home Printed from https://ideas.repec.org/a/eee/phsmap/v571y2021ics0378437121001084.html
   My bibliography  Save this article

Real-time customized bus routes design with optimal passenger and vehicle matching based on column generation algorithm

Author

Listed:
  • Shen, Chan
  • Sun, Yao
  • Bai, Zijian
  • Cui, Hongjun

Abstract

With the popularity and development of mobile Internet, new transportation network services such as customized buses are expected to become a new way of popular transportation in crowded metropolises. In this paper, we propose a real-time customized bus routes design model. We divide the proposed model into two-stage problem to solve. The first stage problem is the vehicle route problem with time window (VRPTW), and the second stage problem is bilateral matching problem. For the first stage, the column generation algorithm is used to solve the problem. For the second stage, we solve it by the improved H-R bilateral matching algorithm. Finally, data on customized bus in Tianjin city of China are used to verify the accuracy of the real-time customized bus routes design model. The optimized results show that the average attendance rate has reached 70.8%, and the service rate of passenger has reached 88.5%. The results have proved that the real-time customized bus routes design model has a practical applicability in operation.

Suggested Citation

  • Shen, Chan & Sun, Yao & Bai, Zijian & Cui, Hongjun, 2021. "Real-time customized bus routes design with optimal passenger and vehicle matching based on column generation algorithm," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 571(C).
    • Handle: RePEc:eee:phsmap:v:571:y:2021:i:c:s0378437121001084
    DOI: 10.1016/j.physa.2021.125836
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378437121001084
    Download Restriction: Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000
    File URL: https://libkey.io/10.1016/j.physa.2021.125836?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Harilaos N. Psaraftis, 1980. "A Dynamic Programming Solution to the Single Vehicle Many-to-Many Immediate Request Dial-a-Ride Problem," Transportation Science, INFORMS, vol. 14(2), pages 130-154, May.
    2. Luathep, Paramet & Sumalee, Agachai & Lam, William H.K. & Li, Zhi-Chun & Lo, Hong K., 2011. "Global optimization method for mixed transportation network design problem: A mixed-integer linear programming approach," Transportation Research Part B: Methodological, Elsevier, vol. 45(5), pages 808-827, June.
    3. Wenxuan Shan & Qianqian Yan & Chao Chen & Mengjie Zhang & Baozhen Yao & Xuemei Fu, 2019. "Optimization of competitive facility location for chain stores," Annals of Operations Research, Springer, vol. 273(1), pages 187-205, February.
    4. Shaheen, Susan & Sperling, Daniel & Wagner, Conrad, 1998. "Carsharing in Europe and North American: Past, Present, and Future," University of California Transportation Center, Working Papers qt4gx4m05b, University of California Transportation Center.
    5. Jeffery L. Kennington & Charles D. Nicholson, 2010. "The Uncapacitated Time-Space Fixed-Charge Network Flow Problem: An Empirical Investigation of Procedures for Arc Capacity Assignment," INFORMS Journal on Computing, INFORMS, vol. 22(2), pages 326-337, May.
    6. George B. Dantzig & Philip Wolfe, 1960. "Decomposition Principle for Linear Programs," Operations Research, INFORMS, vol. 8(1), pages 101-111, February.
    7. Baozhen Yao & Bin Yu & Ping Hu & Junjie Gao & Mingheng Zhang, 2016. "An improved particle swarm optimization for carton heterogeneous vehicle routing problem with a collection depot," Annals of Operations Research, Springer, vol. 242(2), pages 303-320, July.
    8. Yu, Bin & Yang, Zhong-Zhen & Yao, Baozhen, 2009. "An improved ant colony optimization for vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 196(1), pages 171-176, July.
    9. Bin Yu & Zixuan Peng & Zhihui Tian & Baozhen Yao, 2019. "Sailing speed optimization for tramp ships with fuzzy time window," Flexible Services and Manufacturing Journal, Springer, vol. 31(2), pages 308-330, June.
    10. Nelson, John D. & Wright, Steve & Masson, Brian & Ambrosino, Giorgio & Naniopoulos, Aristotelis, 2010. "Recent developments in Flexible Transport Services," Research in Transportation Economics, Elsevier, vol. 29(1), pages 243-248.
    11. Farahani, Reza Zanjirani & Miandoabchi, Elnaz & Szeto, W.Y. & Rashidi, Hannaneh, 2013. "A review of urban transportation network design problems," European Journal of Operational Research, Elsevier, vol. 229(2), pages 281-302.
    12. W. Szeto & Y. Jiang & D. Wang & A. Sumalee, 2015. "A Sustainable Road Network Design Problem with Land Use Transportation Interaction over Time," Networks and Spatial Economics, Springer, vol. 15(3), pages 791-822, September.
    13. Natalia Kliewer & Vitali Gintner & Leena Suhl, 2008. "Line Change Considerations Within a Time-Space Network Based Multi-Depot Bus Scheduling Model," Lecture Notes in Economics and Mathematical Systems, in: Mark Hickman & Pitu Mirchandani & Stefan Voß (ed.), Computer-aided Systems in Public Transport, pages 57-70, Springer.
    14. Víctor M. Albornoz & Linco J. Ñanco, 2016. "An Empirical Design of a Column Generation Algorithm Applied to a Management Zone Delineation Problem," Lecture Notes in Economics and Mathematical Systems, in: Raquel J. Fonseca & Gerhard-Wilhelm Weber & João Telhada (ed.), Computational Management Science, edition 1, pages 201-208, Springer.
    15. Liu, Tao & Ceder, Avishai (Avi), 2015. "Analysis of a new public-transport-service concept: Customized bus in China," Transport Policy, Elsevier, vol. 39(C), pages 63-76.
    16. Kang, Jee Eun & Chow, Joseph Y.J. & Recker, Will W., 2013. "On activity-based network design problems," Transportation Research Part B: Methodological, Elsevier, vol. 57(C), pages 398-418.
    17. Ryley, Tim J. & A. Stanley, Peter & P. Enoch, Marcus & M. Zanni, Alberto & A. Quddus, Mohammed, 2014. "Investigating the contribution of Demand Responsive Transport to a sustainable local public transport system," Research in Transportation Economics, Elsevier, vol. 48(C), pages 364-372.
    18. Shaheen, Susan & Sperling, Daniel & Wagner, Conrad, 1998. "Carsharing in Europe and North American: Past, Present, and Future," Institute of Transportation Studies, Research Reports, Working Papers, Proceedings qt4gx4m05b, Institute of Transportation Studies, UC Berkeley.
    19. Hu Shao & William Lam & Mei Tam, 2006. "A Reliability-Based Stochastic Traffic Assignment Model for Network with Multiple User Classes under Uncertainty in Demand," Networks and Spatial Economics, Springer, vol. 6(3), pages 173-204, September.
    20. Jesús Sáez Aguado, 2009. "Fixed Charge Transportation Problems: a new heuristic approach based on Lagrangean relaxation and the solving of core problems," Annals of Operations Research, Springer, vol. 172(1), pages 45-69, November.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Chen, Feng & Peng, Haorong & Ding, Wenlong & Ma, Xiaoxiang & Tang, Daizhong & Ye, Yipeng, 2021. "Customized bus passenger boarding and deboarding planning optimization model with the least number of contacts between passengers during COVID-19," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 582(C).
    2. Guan, Yunlin & Xiang, Wang & Wang, Yun & Yan, Xuedong & Zhao, Yi, 2023. "Bi-level optimization for customized bus routing serving passengers with multiple-trips based on state–space–time network," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 614(C).
    3. Maela Madel L. Cahigas & Ferani E. Zulvia & Ardvin Kester S. Ong & Yogi Tri Prasetyo, 2023. "A Comprehensive Analysis of Clustering Public Utility Bus Passenger’s Behavior during the COVID-19 Pandemic: Utilization of Machine Learning with Metaheuristic Algorithm," Sustainability, MDPI, vol. 15(9), pages 1-31, April.
    4. Zhen, Lu & Baldacci, Roberto & Tan, Zheyi & Wang, Shuaian & Lyu, Junyan, 2022. "Scheduling heterogeneous delivery tasks on a mixed logistics platform," European Journal of Operational Research, Elsevier, vol. 298(2), pages 680-698.
    5. Shang, Huayan & Chang, Yi & Huang, Haijun & Zhao, Fangxia, 2022. "Integration of conventional and customized bus services: An empirical study in Beijing," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 605(C).

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Tong, Lu & Zhou, Xuesong & Miller, Harvey J., 2015. "Transportation network design for maximizing space–time accessibility," Transportation Research Part B: Methodological, Elsevier, vol. 81(P2), pages 555-576.
    2. Jing Li & Yongbo Lv & Jihui Ma & Yuan Ren, 2019. "Factor Analysis of Customized Bus Attraction to Commuters with Different Travel Modes," Sustainability, MDPI, vol. 11(24), pages 1-13, December.
    3. Gong, Manlin & Hu, Yucong & Chen, Zhiwei & Li, Xiaopeng, 2021. "Transfer-based customized modular bus system design with passenger-route assignment optimization," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 153(C).
    4. Liu, Haoxiang & Wang, David Z.W., 2015. "Global optimization method for network design problem with stochastic user equilibrium," Transportation Research Part B: Methodological, Elsevier, vol. 72(C), pages 20-39.
    5. Sharif Azadeh, Shadi & van der Zee, J. & Wagenvoort, M., 2022. "Choice-driven service network design for an integrated fixed line and demand responsive mobility system," Transportation Research Part A: Policy and Practice, Elsevier, vol. 166(C), pages 557-574.
    6. Li, Qing & Liao, Feixiong, 2020. "Incorporating vehicle self-relocations and traveler activity chains in a bi-level model of optimal deployment of shared autonomous vehicles," Transportation Research Part B: Methodological, Elsevier, vol. 140(C), pages 151-175.
    7. Liu, Haoxiang & Szeto, W.Y. & Long, Jiancheng, 2019. "Bike network design problem with a path-size logit-based equilibrium constraint: Formulation, global optimization, and matheuristic," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 127(C), pages 284-307.
    8. Virginie Boutueil, 2018. "New Mobility Services," Post-Print hal-01981277, HAL.
    9. Liang, Jinpeng & Wu, Jianjun & Gao, Ziyou & Sun, Huijun & Yang, Xin & Lo, Hong K., 2019. "Bus transit network design with uncertainties on the basis of a metro network: A two-step model framework," Transportation Research Part B: Methodological, Elsevier, vol. 126(C), pages 115-138.
    10. Zhang, Fang & Lu, Jian & Hu, Xiaojian & Meng, Qiang, 2023. "Integrated deployment of dedicated lane and roadside unit considering uncertain road capacity under the mixed-autonomy traffic environment," Transportation Research Part B: Methodological, Elsevier, vol. 174(C).
    11. Wang, Jian & He, Xiaozheng & Peeta, Srinivas & Wang, Wei, 2022. "Globally convergent line search algorithm with Euler-based step size-determination method for continuous network design problem," Transportation Research Part B: Methodological, Elsevier, vol. 163(C), pages 119-144.
    12. Frans Sengers & Bruno Turnheim & Frans Berkhout, 2021. "Beyond experiments: Embedding outcomes in climate governance," Environment and Planning C, , vol. 39(6), pages 1148-1171, September.
    13. Mariana de Oliveira Lage & Cláudia Aparecida Soares Machado & Cristiano Martins Monteiro & Clodoveu Augusto Davis & Charles Lincoln Kenji Yamamura & Fernando Tobal Berssaneti & José Alberto Quintanilh, 2021. "Using Hierarchical Facility Location, Single Facility Approach, and GIS in Carsharing Services," Sustainability, MDPI, vol. 13(22), pages 1-13, November.
    14. Luca Nitschke, 2020. "Reconstituting Automobility: The Influence of Non-Commercial Carsharing on the Meanings of Automobility and the Car," Sustainability, MDPI, vol. 12(17), pages 1-20, August.
    15. Garijo, Delia & Márquez, Alberto & Rodríguez, Natalia & Silveira, Rodrigo I., 2019. "Computing optimal shortcuts for networks," European Journal of Operational Research, Elsevier, vol. 279(1), pages 26-37.
    16. Khooban, Zohreh & Farahani, Reza Zanjirani & Miandoabchi, Elnaz & Szeto, W.Y., 2015. "Mixed network design using hybrid scatter search," European Journal of Operational Research, Elsevier, vol. 247(3), pages 699-710.
    17. Sun, Yanshuo & Schonfeld, Paul, 2015. "Stochastic capacity expansion models for airport facilities," Transportation Research Part B: Methodological, Elsevier, vol. 80(C), pages 1-18.
    18. Alfred Benedikt Brendel & Sascha Lichtenberg & Christoph Prinz & Bernd Herrenkind, 2020. "Increasing the Value of Shared Vehicles: Insights from an Implementation of User-Based Relocation in Station-Based One-Way Carsharing," Sustainability, MDPI, vol. 12(21), pages 1-15, October.
    19. Hosseininasab, Seyyed-Mohammadreza & Shetab-Boushehri, Seyyed-Nader & Hejazi, Seyed Reza & Karimi, Hadi, 2018. "A multi-objective integrated model for selecting, scheduling, and budgeting road construction projects," European Journal of Operational Research, Elsevier, vol. 271(1), pages 262-277.
    20. Sohani Liyanage & Hussein Dia & Rusul Abduljabbar & Saeed Asadi Bagloee, 2019. "Flexible Mobility On-Demand: An Environmental Scan," Sustainability, MDPI, vol. 11(5), pages 1-39, February.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:phsmap:v:571:y:2021:i:c:s0378437121001084. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.journals.elsevier.com/physica-a-statistical-mechpplications/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.