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

A hybrid algorithm for Urban transit schedule optimization

Author

Listed:
  • Tang, Jinjun
  • Yang, Yifan
  • Qi, Yong

Abstract

Designing reasonable departure schedule is the key step to realize the urban transit priority. It can not only reduce the operating cost of bus company, but also guarantee convenience for passengers. This paper estimates the travel time between bus stations based on the historical trajectory data of the bus, and then combines the number of passengers get on and off at each station to optimize the departure timetable. In addition, several constraints including actual travel time, limited capacity and arrival time distribution type are considered in the optimization models to effectively and comprehensively estimate the passenger waiting time. Finally, a hybrid algorithm combining Genetic Algorithm (GA) and Simulated Annealing Algorithm (SAA) is proposed to search optimal solution in scheduling model. A case study is applied to testify the effectiveness of proposed models. In the experiments, we compare optimization results of proposed method to traditional genetic algorithms, and the results show the superiority and feasibility of the hybrid optimization approach.

Suggested Citation

  • Tang, Jinjun & Yang, Yifan & Qi, Yong, 2018. "A hybrid algorithm for Urban transit schedule optimization," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 512(C), pages 745-755.
    • Handle: RePEc:eee:phsmap:v:512:y:2018:i:c:p:745-755
    DOI: 10.1016/j.physa.2018.08.017
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378437118309610
    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.2018.08.017?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. Sun, Xiuqiao & Wang, Jian, 2018. "Routing design and fleet allocation optimization of freeway service patrol: Improved results using genetic algorithm," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 501(C), pages 205-216.
    2. Nagatani, Takashi, 2012. "Delay effect on schedule in shuttle bus transportation controlled by capacity," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 391(11), pages 3266-3276.
    3. Tang, Jinjun & Zhang, Shen & Chen, Xinqiang & Liu, Fang & Zou, Yajie, 2018. "Taxi trips distribution modeling based on Entropy-Maximizing theory: A case study in Harbin city—China," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 493(C), pages 430-443.
    4. Herbon, Avi & Hadas, Yuval, 2015. "Determining optimal frequency and vehicle capacity for public transit routes: A generalized newsvendor model," Transportation Research Part B: Methodological, Elsevier, vol. 71(C), pages 85-99.
    5. Yan, Ying & Zhang, Shen & Tang, Jinjun & Wang, Xiaofei, 2017. "Understanding characteristics in multivariate traffic flow time series from complex network structure," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 477(C), pages 149-160.
    6. Laporte, Gilbert & Ortega, Francisco A. & Pozo, Miguel A. & Puerto, Justo, 2017. "Multi-objective integration of timetables, vehicle schedules and user routings in a transit network," Transportation Research Part B: Methodological, Elsevier, vol. 98(C), pages 94-112.
    7. Tang, Jinjun & Liang, Jian & Zhang, Shen & Huang, Helai & Liu, Fang, 2018. "Inferring driving trajectories based on probabilistic model from large scale taxi GPS data," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 506(C), pages 566-577.
    8. Ibarra-Rojas, Omar J. & Rios-Solis, Yasmin A., 2012. "Synchronization of bus timetabling," Transportation Research Part B: Methodological, Elsevier, vol. 46(5), pages 599-614.
    9. Nagatani, Takashi, 2017. "Effect of periodic inflow on speed-controlled shuttle bus," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 469(C), pages 224-231.
    10. Fouilhoux, P. & Ibarra-Rojas, O.J. & Kedad-Sidhoum, S. & Rios-Solis, Y.A., 2016. "Valid inequalities for the synchronization bus timetabling problem," European Journal of Operational Research, Elsevier, vol. 251(2), pages 442-450.
    11. Nagatani, Takashi, 2016. "Effect of speedup delay on shuttle bus schedule," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 460(C), pages 121-130.
    12. Zhou, Xuemei & Huang, Huang & Jia, Xinchang & Jiang, Nan, 2014. "Integrated passenger terminal capacity analysis under the capacity constraints of surrounding road network," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 414(C), pages 194-203.
    13. Feng, Jia & Li, Xiamiao & Mao, Baohua & Xu, Qi & Bai, Yun, 2017. "Weighted complex network analysis of the Beijing subway system: Train and passenger flows," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 474(C), pages 213-223.
    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. Cong, Yuan & Bie, Yiming & Liu, Ziyan & Zhu, Aoze, 2024. "Collaborative vehicle-crew scheduling for multiple routes with a mixed fleet of electric and fuel buses," Energy, Elsevier, vol. 298(C).
    2. Zong, Fang & Yu, Ping & Tang, Jinjun & Sun, Xiao, 2019. "Understanding parking decisions with structural equation modeling," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 523(C), pages 408-417.
    3. Hao, Jingjing & Zhang, Ling & Ji, Xiaofeng & Tang, Jinjun, 2020. "Modeling and analyzing of family intention for the customized student routes: A case study in China," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 542(C).
    4. Li, Jiawei & Wen, Xiangxi & Wu, Minggong & Liu, Fei & Li, Shuangfeng, 2020. "Identification of key nodes and vital edges in aviation network based on minimum connected dominating set," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 541(C).
    5. Vee-Liem Saw & Lock Yue Chew, 2020. "No-boarding buses: Synchronisation for efficiency," PLOS ONE, Public Library of Science, vol. 15(3), pages 1-34, March.
    6. Gao, Yuhong & Qu, Zhaowei & Song, Xianmin & Yun, Zhenyu & Xia, Yingji, 2021. "A novel relationship model between signal timing, queue length and travel speed," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 583(C).
    7. Wang, Chao & Ma, Changxi & Xu, Xuecai(Daniel), 2020. "Multi-objective optimization of real-time customized bus routes based on two-stage method," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 537(C).
    8. Dalong Li & Benxing Liu & Fangtong Jiao & Ziwen Song & Pengsheng Zhao & Xiaoqing Wang & Feng Sun, 2022. "Optimization Method of Combined Multi-Mode Bus Scheduling under Unbalanced Conditions," Sustainability, MDPI, vol. 14(23), pages 1-17, November.
    9. Xiaoyong Tang & Xiaoyi Liao, 2018. "Application-aware deadline constraint job scheduling mechanism on large-scale computational grid," PLOS ONE, Public Library of Science, vol. 13(11), pages 1-19, November.
    10. Jianglong Yang & Li Zhou & Huwei Liu, 2021. "Hybrid genetic algorithm-based optimisation of the batch order picking in a dense mobile rack warehouse," PLOS ONE, Public Library of Science, vol. 16(4), pages 1-25, April.
    11. Tang, Jinjun & Chen, Xinqiang & Hu, Zheng & Zong, Fang & Han, Chunyang & Li, Leixiao, 2019. "Traffic flow prediction based on combination of support vector machine and data denoising schemes," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 534(C).
    12. Tang, Jinjun & Hu, Jin & Hao, Wei & Chen, Xinqiang & Qi, Yong, 2020. "Markov Chains based route travel time estimation considering link spatio-temporal correlation," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 545(C).
    13. Lingyu Zheng & Hao Ma & Zhongyu Wang, 2024. "Travel Time Estimation for Urban Arterials Based on the Multi-Source Data," Sustainability, MDPI, vol. 16(17), pages 1-15, September.
    14. Büchel, Beda & Corman, Francesco, 2022. "Modeling conditional dependencies for bus travel time estimation," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 592(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. Zhang, Shen & Liu, Xin & Tang, Jinjun & Cheng, Shaowu & Qi, Yong & Wang, Yinhai, 2018. "Spatio-temporal modeling of destination choice behavior through the Bayesian hierarchical approach," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 512(C), pages 537-551.
    2. Du, Zhouyang & Tang, Jinjun & Qi, Yong & Wang, Yiwei & Han, Chunyang & Yang, Yifan, 2020. "Identifying critical nodes in metro network considering topological potential: A case study in Shenzhen city—China," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 539(C).
    3. Guo, Yajuan & Yang, Licai & Hao, Shenxue & Gao, Jun, 2019. "Dynamic identification of urban traffic congestion warning communities in heterogeneous networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 522(C), pages 98-111.
    4. Jiang, Xurui & Wen, Xiangxi & Wu, Minggong & Song, Min & Tu, Congliang, 2019. "A complex network analysis approach for identifying air traffic congestion based on independent component analysis," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 523(C), pages 364-381.
    5. Tang, Jinjun & Chen, Xinqiang & Hu, Zheng & Zong, Fang & Han, Chunyang & Li, Leixiao, 2019. "Traffic flow prediction based on combination of support vector machine and data denoising schemes," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 534(C).
    6. Zong, Fang & Tian, Yongda & He, Yanan & Tang, Jinjun & Lv, Jianyu, 2019. "Trip destination prediction based on multi-day GPS data," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 515(C), pages 258-269.
    7. Zong, Fang & Yu, Ping & Tang, Jinjun & Sun, Xiao, 2019. "Understanding parking decisions with structural equation modeling," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 523(C), pages 408-417.
    8. Helai Huang & Jialing Wu & Fang Liu & Yiwei Wang, 2020. "Measuring Accessibility Based on Improved Impedance and Attractive Functions Using Taxi Trajectory Data," Sustainability, MDPI, vol. 13(1), pages 1-23, December.
    9. Tang, Jinjun & Bi, Wei & Liu, Fang & Zhang, Wenhui, 2021. "Exploring urban travel patterns using density-based clustering with multi-attributes from large-scaled vehicle trajectories," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 561(C).
    10. Changxi Ma & Ruichun He & Wei Zhang, 2018. "Path optimization of taxi carpooling," PLOS ONE, Public Library of Science, vol. 13(8), pages 1-15, August.
    11. Jinjun Tang & Fan Gao & Fang Liu & Wenhui Zhang & Yong Qi, 2019. "Understanding Spatio-Temporal Characteristics of Urban Travel Demand Based on the Combination of GWR and GLM," Sustainability, MDPI, vol. 11(19), pages 1-19, October.
    12. Ci, Yusheng & Wu, Lina & Zhao, Jiafa & Sun, Yichen & Zhang, Guohui, 2019. "V2I-based car-following modeling and simulation of signalized intersection," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 525(C), pages 672-679.
    13. Ramli, Muhamad Azfar & Jayaraman, Vasundhara & Kwek, Hyen Chee & Tan, Kian Heong & Lee Kee Khoon, Gary & Monterola, Christopher, 2018. "Improved estimation of commuter waiting times using headway and commuter boarding information," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 501(C), pages 217-226.
    14. Yichuan Peng & Yuming Jiang & Jian Lu & Yajie Zou, 2018. "Examining the effect of adverse weather on road transportation using weather and traffic sensors," PLOS ONE, Public Library of Science, vol. 13(10), pages 1-14, October.
    15. Kuo, Yong-Hong & Leung, Janny M.Y. & Yan, Yimo, 2023. "Public transport for smart cities: Recent innovations and future challenges," European Journal of Operational Research, Elsevier, vol. 306(3), pages 1001-1026.
    16. Ansarilari, Zahra & Bodur, Merve & Shalaby, Amer, 2024. "A novel model for transfer synchronization in transit networks and a Lagrangian-based heuristic solution method," European Journal of Operational Research, Elsevier, vol. 317(1), pages 76-91.
    17. Abdolmaleki, Mojtaba & Masoud, Neda & Yin, Yafeng, 2020. "Transit timetable synchronization for transfer time minimization," Transportation Research Part B: Methodological, Elsevier, vol. 131(C), pages 143-159.
    18. Yin, Jiateng & D’Ariano, Andrea & Wang, Yihui & Yang, Lixing & Tang, Tao, 2021. "Timetable coordination in a rail transit network with time-dependent passenger demand," European Journal of Operational Research, Elsevier, vol. 295(1), pages 183-202.
    19. Cortés, Cristián E. & Gil, Cristiam & Gschwender, Antonio & Rey, Pablo A., 2023. "The bus synchronization timetabling problem with dwelling times," Transportation Research Part B: Methodological, Elsevier, vol. 174(C).
    20. Dalong Li & Benxing Liu & Fangtong Jiao & Ziwen Song & Pengsheng Zhao & Xiaoqing Wang & Feng Sun, 2022. "Optimization Method of Combined Multi-Mode Bus Scheduling under Unbalanced Conditions," Sustainability, MDPI, vol. 14(23), pages 1-17, November.

    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:512:y:2018:i:c:p:745-755. 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.