IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v217y2012i1p204-213.html
   My bibliography  Save this article

A post-improvement procedure for the mixed load school bus routing problem

Author

Listed:
  • Park, Junhyuk
  • Tae, Hyunchul
  • Kim, Byung-In

Abstract

This paper aims to develop a mixed load algorithm for the school bus routing problem (SBRP) and measure its effects on the number of required vehicles. SBRP seeks to find optimal routes for a fleet of vehicles, where each vehicle transports students from their homes and to their schools while satisfying various constraints. When mixed load is allowed, students of different schools can get on the same bus at the same time. Although many of real world SBRP allow mixed load, only a few studies have considered these cases. In this paper, we present a new mixed load improvement algorithm and compare it with the only existing algorithm from the literature. Benchmark problems are proposed to compare the performances of algorithms and to stimulate other researchers’ further study. The proposed algorithm outperforms the existing algorithm on the benchmark problem instances. It has also been successfully applied to some of real-world SBRP and could reduce the required number of vehicles compared with the current practice.

Suggested Citation

  • Park, Junhyuk & Tae, Hyunchul & Kim, Byung-In, 2012. "A post-improvement procedure for the mixed load school bus routing problem," European Journal of Operational Research, Elsevier, vol. 217(1), pages 204-213.
    • Handle: RePEc:eee:ejores:v:217:y:2012:i:1:p:204-213
    DOI: 10.1016/j.ejor.2011.08.022
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221711007636
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2011.08.022?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. Dumas, Yvan & Desrosiers, Jacques & Soumis, Francois, 1991. "The pickup and delivery problem with time windows," European Journal of Operational Research, Elsevier, vol. 54(1), pages 7-22, September.
    2. Cortés, Cristián E. & Matamala, Martín & Contardo, Claudio, 2010. "The pickup and delivery problem with transfers: Formulation and a branch-and-cut solution method," European Journal of Operational Research, Elsevier, vol. 200(3), pages 711-724, February.
    3. Park, Junhyuk & Kim, Byung-In, 2010. "The school bus routing problem: A review," European Journal of Operational Research, Elsevier, vol. 202(2), pages 311-319, April.
    4. Lawrence D. Bodin & Lon Berman, 1979. "Routing and Scheduling of School Buses by Computer," Transportation Science, INFORMS, vol. 13(2), pages 113-129, May.
    5. Julien Bramel & David Simchi-Levi, 1995. "A Location Based Heuristic for General Routing Problems," Operations Research, INFORMS, vol. 43(4), pages 649-660, August.
    6. M. Spada & M. Bierlaire & Th. M. Liebling, 2005. "Decision-Aiding Methodology for the School Bus Routing and Scheduling Problem," Transportation Science, INFORMS, vol. 39(4), pages 477-490, November.
    7. Fügenschuh, Armin, 2009. "Solving a school bus scheduling problem with integer programming," European Journal of Operational Research, Elsevier, vol. 193(3), pages 867-884, March.
    8. Belfiore, PatrI´cia & Yoshida Yoshizaki, Hugo Tsugunobu, 2009. "Scatter search for a real-life heterogeneous fleet vehicle routing problem with time windows and split deliveries in Brazil," European Journal of Operational Research, Elsevier, vol. 199(3), pages 750-758, December.
    9. Billy E. Gillett & Leland R. Miller, 1974. "A Heuristic Algorithm for the Vehicle-Dispatch Problem," Operations Research, INFORMS, vol. 22(2), pages 340-349, April.
    10. Marius M. Solomon, 1987. "Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints," Operations Research, INFORMS, vol. 35(2), pages 254-265, April.
    11. Fleszar, Krzysztof & Osman, Ibrahim H. & Hindi, Khalil S., 2009. "A variable neighbourhood search algorithm for the open vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 195(3), pages 803-809, June.
    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. Shafahi, Ali & Wang, Zhongxiang & Haghani, Ali, 2018. "SpeedRoute: Fast, efficient solutions for school bus routing problems," Transportation Research Part B: Methodological, Elsevier, vol. 117(PA), pages 473-493.
    2. Dimitris Bertsimas & Arthur Delarue & William Eger & John Hanlon & Sebastien Martin, 2020. "Bus Routing Optimization Helps Boston Public Schools Design Better Policies," Interfaces, INFORMS, vol. 50(1), pages 37-49, January.
    3. Wang, Zhongxiang & Haghani, Ali, 2020. "Column generation-based stochastic school bell time and bus scheduling optimization," European Journal of Operational Research, Elsevier, vol. 286(3), pages 1087-1102.
    4. Shichao Sun & Zhengyu Duan & Qi Xu, 2018. "School bus routing problem in the stochastic and time-dependent transportation network," PLOS ONE, Public Library of Science, vol. 13(8), pages 1-17, August.
    5. Huasheng Liu & Yuqi Zhao & Jin Li & Yu Li & Xiaowen Li & Sha Yang, 2022. "A Two-Phase, Joint-Commuting Model for Primary and Secondary Schools Considering Parking Sharing," IJERPH, MDPI, vol. 19(11), pages 1-25, May.
    6. Dasdemir, Erdi & Testik, Murat Caner & Öztürk, Diclehan Tezcaner & Şakar, Ceren Tuncer & Güleryüz, Güldal & Testik, Özlem Müge, 2022. "A multi-objective open vehicle routing problem with overbooking: Exact and heuristic solution approaches for an employee transportation problem," Omega, Elsevier, vol. 108(C).
    7. Amanda Chu & Pinar Keskinocak & Monica C. Villarreal, 2020. "Introduction: Empowering Denver Public Schools to Optimize School Bus Operations," Interfaces, INFORMS, vol. 50(5), pages 298-312, September.
    8. Hernan Caceres & Rajan Batta & Qing He, 2017. "School Bus Routing with Stochastic Demand and Duration Constraints," Transportation Science, INFORMS, vol. 51(4), pages 1349-1364, November.
    9. Ezquerro Eguizábal, Sara & Moura Berodia, José Luis & Ibeas Portilla, Ángel & Benavente Ponce, Juan, 2018. "Optimization model for school transportation design based on economic and social efficiency," Transport Policy, Elsevier, vol. 67(C), pages 93-101.
    10. Fátima M. Souza Lima & Davi S. D. Pereira & Samuel V. Conceição & Ricardo S. Camargo, 2017. "A multi-objective capacitated rural school bus routing problem with heterogeneous fleet and mixed loads," 4OR, Springer, vol. 15(4), pages 359-386, December.
    11. Schittekat, Patrick & Kinable, Joris & Sörensen, Kenneth & Sevaux, Marc & Spieksma, Frits & Springael, Johan, 2013. "A metaheuristic for the school bus routing problem with bus stop selection," European Journal of Operational Research, Elsevier, vol. 229(2), pages 518-528.
    12. Ellegood, William A. & Solomon, Stanislaus & North, Jeremy & Campbell, James F., 2020. "School bus routing problem: Contemporary trends and research directions," Omega, Elsevier, vol. 95(C).
    13. Ansari, Azadeh & Farrokhvar, Leily & Kamali, Behrooz, 2021. "Integrated student to school assignment and school bus routing problem for special needs students," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 152(C).
    14. Xiaopan Chen & Yunfeng Kong & Lanxue Dang & Yane Hou & Xinyue Ye, 2015. "Exact and Metaheuristic Approaches for a Bi-Objective School Bus Scheduling Problem," PLOS ONE, Public Library of Science, vol. 10(7), pages 1-20, July.
    15. Monnerat, Filipe & Dias, Joana & Alves, Maria João, 2019. "Fleet management: A vehicle and driver assignment model," European Journal of Operational Research, Elsevier, vol. 278(1), pages 64-75.
    16. Caceres, Hernan & Batta, Rajan & He, Qing, 2019. "Special need students school bus routing: Consideration for mixed load and heterogeneous fleet," Socio-Economic Planning Sciences, Elsevier, vol. 65(C), pages 10-19.
    17. 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.

    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. Park, Junhyuk & Kim, Byung-In, 2010. "The school bus routing problem: A review," European Journal of Operational Research, Elsevier, vol. 202(2), pages 311-319, April.
    2. Ellegood, William A. & Solomon, Stanislaus & North, Jeremy & Campbell, James F., 2020. "School bus routing problem: Contemporary trends and research directions," Omega, Elsevier, vol. 95(C).
    3. Vidal, Thibaut & Crainic, Teodor Gabriel & Gendreau, Michel & Prins, Christian, 2013. "Heuristics for multi-attribute vehicle routing problems: A survey and synthesis," European Journal of Operational Research, Elsevier, vol. 231(1), pages 1-21.
    4. 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.
    5. Kim, Byung-In & Kim, Seongbae & Park, Junhyuk, 2012. "A school bus scheduling problem," European Journal of Operational Research, Elsevier, vol. 218(2), pages 577-585.
    6. Sepehr Nemati & Oleg V. Shylo & Oleg A. Prokopyev & Andrew J. Schaefer, 2016. "The Surgical Patient Routing Problem: A Central Planner Approach," INFORMS Journal on Computing, INFORMS, vol. 28(4), pages 657-673, November.
    7. Dimitris Bertsimas & Arthur Delarue & William Eger & John Hanlon & Sebastien Martin, 2020. "Bus Routing Optimization Helps Boston Public Schools Design Better Policies," Interfaces, INFORMS, vol. 50(1), pages 37-49, January.
    8. Amanda Chu & Pinar Keskinocak & Monica C. Villarreal, 2020. "Introduction: Empowering Denver Public Schools to Optimize School Bus Operations," Interfaces, INFORMS, vol. 50(5), pages 298-312, September.
    9. J Faulin & A García del Valle, 2008. "Solving the capacitated vehicle routing problem using the ALGELECT electrostatic algorithm," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(12), pages 1685-1695, December.
    10. Shafahi, Ali & Wang, Zhongxiang & Haghani, Ali, 2018. "SpeedRoute: Fast, efficient solutions for school bus routing problems," Transportation Research Part B: Methodological, Elsevier, vol. 117(PA), pages 473-493.
    11. Fátima M. Souza Lima & Davi S. D. Pereira & Samuel V. Conceição & Ricardo S. Camargo, 2017. "A multi-objective capacitated rural school bus routing problem with heterogeneous fleet and mixed loads," 4OR, Springer, vol. 15(4), pages 359-386, December.
    12. Perugia, Alessandro & Moccia, Luigi & Cordeau, Jean-François & Laporte, Gilbert, 2011. "Designing a home-to-work bus service in a metropolitan area," Transportation Research Part B: Methodological, Elsevier, vol. 45(10), pages 1710-1726.
    13. Liwei Zeng & Sunil Chopra & Karen Smilowitz, 2019. "The Covering Path Problem on a Grid," Transportation Science, INFORMS, vol. 53(6), pages 1656-1672, November.
    14. Gronalt, Manfred & Hartl, Richard F. & Reimann, Marc, 2003. "New savings based algorithms for time constrained pickup and delivery of full truckloads," European Journal of Operational Research, Elsevier, vol. 151(3), pages 520-535, December.
    15. Qi, Mingyao & Lin, Wei-Hua & Li, Nan & Miao, Lixin, 2012. "A spatiotemporal partitioning approach for large-scale vehicle routing problems with time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(1), pages 248-257.
    16. Xiang, Zhihai & Chu, Chengbin & Chen, Haoxun, 2006. "A fast heuristic for solving a large-scale static dial-a-ride problem under complex constraints," European Journal of Operational Research, Elsevier, vol. 174(2), pages 1117-1139, October.
    17. César Rego, 1998. "A Subpath Ejection Method for the Vehicle Routing Problem," Management Science, INFORMS, vol. 44(10), pages 1447-1459, October.
    18. Liu, Fuh-Hwa Franklin & Shen, Sheng-Yuan, 1999. "A route-neighborhood-based metaheuristic for vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 118(3), pages 485-504, November.
    19. Stacy A. Voccia & Ann Melissa Campbell & Barrett W. Thomas, 2019. "The Same-Day Delivery Problem for Online Purchases," Service Science, INFORMS, vol. 53(1), pages 167-184, February.
    20. Hernan Caceres & Rajan Batta & Qing He, 2017. "School Bus Routing with Stochastic Demand and Duration Constraints," Transportation Science, INFORMS, vol. 51(4), pages 1349-1364, 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:ejores:v:217:y:2012:i:1:p:204-213. 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.elsevier.com/locate/eor .

    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.