{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T16:28:28Z","timestamp":1778516908904,"version":"3.51.4"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,11,29]],"date-time":"2022-11-29T00:00:00Z","timestamp":1669680000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,11,29]],"date-time":"2022-11-29T00:00:00Z","timestamp":1669680000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Tertiary Education Scholarships Scheme"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["SN COMPUT. SCI."],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This paper addresses a school bus routing problem formulated as a capacitated and time-constrained open vehicle routing problem with a heterogeneous fleet and single loads. This problem incorporates several realistic features, such as student eligibility, maximum walking distances, bus stop selection, maximum riding times, different types of buses, multistops, and bus dwell times. A heuristic algorithm based on an iterated local search approach is proposed for this problem. It determines the selection of bus stops from a set of potential stops, the assignment of students to the selected bus stops, and the routes along the selected bus stops. The main objectives are minimizing the number of buses used, the total student walking distance, and the total route journey time. Other aims are balancing route journey times between buses and minimizing the total number of empty seats. A set of 20 real-world problem instances are used to evaluate the performance of the algorithm. Results indicate that the algorithm finds high-quality solutions in very short amounts of computational time.<\/jats:p>","DOI":"10.1007\/s42979-022-01466-6","type":"journal-article","created":{"date-parts":[[2022,11,29]],"date-time":"2022-11-29T14:04:37Z","timestamp":1669730677000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["A School Bus Routing Heuristic Algorithm Allowing Heterogeneous Fleets and Bus Stop Selection"],"prefix":"10.1007","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8968-9101","authenticated-orcid":false,"given":"Monique","family":"Sciortino","sequence":"first","affiliation":[]},{"given":"Rhyd","family":"Lewis","sequence":"additional","affiliation":[]},{"given":"Jonathan","family":"Thompson","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,11,29]]},"reference":[{"key":"1466_CR1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cie.2019.106125","volume":"138","author":"M Babaei","year":"2019","unstructured":"Babaei M, Rajabi-Bahaabadi M. School bus routing and scheduling with stochastic time-dependent travel times considering on-time arrival reliability. Comput Ind Eng. 2019;138: 106125.","journal-title":"Comput Ind Eng"},{"issue":"12","key":"1466_CR2","doi-asserted-by":"publisher","first-page":"1599","DOI":"10.1057\/palgrave.jors.2602305","volume":"58","author":"T Bekta\u015f","year":"2007","unstructured":"Bekta\u015f T, Elmasta\u015f S. Solving school bus routing problems through integer programming. J Oper Res Soc. 2007;58(12):1599\u2013604.","journal-title":"J Oper Res Soc"},{"key":"1466_CR3","unstructured":"Bertsimas D, Delarue A, Martin S. From school buses to start times: driving policy with optimization. 2019."},{"issue":"2","key":"1466_CR4","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1287\/trsc.13.2.113","volume":"13","author":"LD Bodin","year":"1979","unstructured":"Bodin LD, Berman L. Routing and scheduling of school buses by computer. Transp Sci. 1979;13(2):113\u201329.","journal-title":"Transp Sci"},{"issue":"2","key":"1466_CR5","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1002\/net.21589","volume":"65","author":"M B\u00f6gl","year":"2015","unstructured":"B\u00f6gl M, Doerner KF, Parragh SN. The school bus routing and scheduling problem with transfers. Networks. 2015;65(2):180\u2013203.","journal-title":"Networks"},{"issue":"2","key":"1466_CR6","first-page":"107","volume":"29","author":"R Bowerman","year":"1995","unstructured":"Bowerman R, Hall B, Calamai P. A multi-objective optimization approach to urban school bus routing: formulation and solution method. Transport Res Part A. 1995;29(2):107\u201323.","journal-title":"Transport Res Part A"},{"issue":"8","key":"1466_CR7","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1080\/07408179708966379","volume":"29","author":"J Braca","year":"1997","unstructured":"Braca J, Bramel J, Posner B, Simchi-Levi D. A computerized approach to the New York City School Bus Routing Problem. IIE Trans. 1997;29(8):693\u2013702.","journal-title":"IIE Trans"},{"key":"1466_CR8","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1016\/j.cie.2015.12.007","volume":"99","author":"K Braekers","year":"2016","unstructured":"Braekers K, Ramaekers K, Nieuwenhuyse IV. The vehicle routing problem: state of the art classification and review. Comput Ind Eng. 2016;99:300\u201313.","journal-title":"Comput Ind Eng"},{"key":"1466_CR9","unstructured":"busprobs. 2018."},{"issue":"4","key":"1466_CR10","doi-asserted-by":"publisher","first-page":"1349","DOI":"10.1287\/trsc.2016.0721","volume":"51","author":"H Caceres","year":"2017","unstructured":"Caceres H, Batta R, He Q. School bus routing with stochastic demand and duration constraints. Transp Sci. 2017;51(4):1349\u201364.","journal-title":"Transp Sci"},{"key":"1466_CR11","doi-asserted-by":"crossref","unstructured":"Campbell JF, North JW, Ellegood WA. Modeling mixed load school bus routing. Quant Approach Logistic Supply Chain Manage. 2015;3\u201330.","DOI":"10.1007\/978-3-319-12856-6_1"},{"issue":"4","key":"1466_CR12","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0153614","volume":"11","author":"X Chen","year":"2015","unstructured":"Chen X, Kong Y, Dang L, Hou Y, Ye X. Exact and metaheuristic approaches for a bi-objective school bus scheduling problem. PLoS One. 2015;11(4): e0153614.","journal-title":"PLoS One"},{"issue":"4","key":"1466_CR13","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1057\/palgrave.jors.2601324","volume":"53","author":"A Corber\u00e1n","year":"2002","unstructured":"Corber\u00e1n A, Fern\u00e1ndez E, Laguna M, Mart\u00ed R. Heuristic solutions to the problem of routing school buses with multiple objectives. J Oper Res Soc. 2002;53(4):427\u201335.","journal-title":"J Oper Res Soc"},{"issue":"1","key":"1466_CR14","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1287\/mnsc.6.1.80","volume":"6","author":"GB Dantzig","year":"1959","unstructured":"Dantzig GB, Ramser JH. The truck dispatching problem. Manage Sci. 1959;6(1):80\u201391.","journal-title":"Manage Sci"},{"key":"1466_CR15","unstructured":"Desrosiers J, Ferland JA, Rousseau JM, Lapalme G, Chapleau L. An overview of a school busing system. Sci Manage Transp Syst. 1981;235\u201343."},{"issue":"2","key":"1466_CR16","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1287\/trsc.23.2.141","volume":"23","author":"M Dror","year":"1989","unstructured":"Dror M, Trudeau P. Savings by split delivery routing. Transp Sci. 1989;23(2):141\u20135.","journal-title":"Transp Sci"},{"issue":"3","key":"1466_CR17","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1002\/nav.3800370304","volume":"37","author":"M Dror","year":"1990","unstructured":"Dror M, Trudeau P. Split delivery routing. Nav Res Logist. 1990;37(3):383\u2013402.","journal-title":"Nav Res Logist"},{"issue":"3","key":"1466_CR18","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/0305-0548(80)90006-4","volume":"7","author":"G Dulac","year":"1980","unstructured":"Dulac G, Ferland JA, Forgues PA. School bus routes generator in urban surroundings. Comput Oper Res. 1980;7(3):199\u2013213.","journal-title":"Comput Oper Res"},{"key":"1466_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.omega.2019.03.014","volume":"95","author":"WA Ellegood","year":"2020","unstructured":"Ellegood WA, Solomon S, North J, Campbell JF. School bus routing problem: contemporary trends and research directions. Omega. 2020;95:1\u201318.","journal-title":"Omega"},{"issue":"1\u20132","key":"1466_CR20","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1016\/j.mcm.2007.02.007","volume":"47","author":"AGH Kek","year":"2008","unstructured":"Kek AGH, Cheu RL, Meng Q. Distance-constrained capacitated vehicle routing problems with flexible assignment of start and end depots. Math Comput Model. 2008;47(1\u20132):140\u201352.","journal-title":"Math Comput Model"},{"issue":"3","key":"1466_CR21","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1287\/trsc.22.3.161","volume":"22","author":"G Laporte","year":"1988","unstructured":"Laporte G, Nobert Y, Taillefer S. Solving a family of multi-depot vehicle routing and location-routing problems. Transp Sci. 1988;22(3):161\u201372.","journal-title":"Transp Sci"},{"key":"1466_CR22","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.jda.2018.11.001","volume":"52\u201353","author":"R Lewis","year":"2018","unstructured":"Lewis R, Smith-Miles K. A heuristic algorithm for finding cost-effective solutions to real-world school bus routing problems. J Discrete Algor. 2018;52\u201353:2\u201317.","journal-title":"J Discrete Algor"},{"issue":"5","key":"1466_CR23","doi-asserted-by":"publisher","first-page":"552","DOI":"10.1057\/palgrave.jors.2601341","volume":"53","author":"LY Li","year":"2002","unstructured":"Li LY, Fu Z. The school bus routing problem: a case study. J Oper Res Soc. 2002;53(5):552\u20138.","journal-title":"J Oper Res Soc"},{"key":"1466_CR24","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1016\/j.eswa.2016.03.005","volume":"56","author":"FM Lima","year":"2016","unstructured":"Lima FM, Pereira DS, Concei\u00e7\u00e3o SV, Ramos Nunes NT. A mixed load capacitated rural school bus routing problem with heterogeneous fleet: algorithms for the Brazilian context. Expert Syst Appl. 2016;56:320\u201334.","journal-title":"Expert Syst Appl"},{"key":"1466_CR25","doi-asserted-by":"crossref","unstructured":"Newton RM, Thomas WH. Design of school bus routes by computer. Socio Econ Plann Sci.1969; 75\u201385.","DOI":"10.1016\/0038-0121(69)90051-2"},{"key":"1466_CR26","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/j.ejor.2009.05.017","volume":"202","author":"J Park","year":"2010","unstructured":"Park J, Kim BI. The school bus routing problem: a review. Eur J Oper Res. 2010;202:311\u20139.","journal-title":"Eur J Oper Res"},{"issue":"1","key":"1466_CR27","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1016\/j.ejor.2011.08.022","volume":"217","author":"J Park","year":"2012","unstructured":"Park J, Tae H, Kim B-I. A post-improvement procedure for the mixed load school bus routing problem. Eur J Oper Res. 2012;217(1):204\u201313.","journal-title":"Eur J Oper Res"},{"issue":"2","key":"1466_CR28","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1016\/j.cor.2011.04.015","volume":"39","author":"J Riera-Ledesma","year":"2012","unstructured":"Riera-Ledesma J, Salazar-Gonz\u00e1lez J-J. Solving school bus routing using the multiple vehicle traveling purchaser problem: a branch-and-cut approach. Comput Oper Res. 2012;39(2):391\u2013404.","journal-title":"Comput Oper Res"},{"issue":"2","key":"1466_CR29","doi-asserted-by":"publisher","first-page":"04018018","DOI":"10.1061\/(ASCE)UP.1943-5444.0000454","volume":"144","author":"LD Sales","year":"2018","unstructured":"Sales LD, Melo CS, Bonates TD, Prata BD. Memetic algorithm for the heterogeneous fleet school bus routing problem. J Urban Plann Dev. 2018;144(2):04018018.","journal-title":"J Urban Plann Dev"},{"key":"1466_CR30","unstructured":"Sansone K. No free school transport for 1,000 students in church and independent schools. MaltaToday. 2018. https:\/\/www.maltatoday.com.mt\/news\/national\/89608\/no_free_school_transport_for_1000_students_in_church_and_independent_schools#.YuO46i0RqCg."},{"issue":"5","key":"1466_CR31","doi-asserted-by":"publisher","first-page":"564","DOI":"10.1057\/palgrave.jors.2600924","volume":"51","author":"D Sariklis","year":"2000","unstructured":"Sariklis D, Powell S. A heuristic method for the open vehicle routing problem. J Oper Res Soc. 2000;51(5):564\u201373.","journal-title":"J Oper Res Soc"},{"key":"1466_CR32","unstructured":"sbrpMaltaHeterogeneousFleets. 2021."},{"issue":"2","key":"1466_CR33","doi-asserted-by":"publisher","first-page":"518","DOI":"10.1016\/j.ejor.2013.02.025","volume":"229","author":"P Schittekat","year":"2013","unstructured":"Schittekat P, Kinable J, S\u00f6rensen K, Sevaux M, Spieksma F, Springael J. A metaheuristic for the school bus routing problem with bus stop selection. Eur J Oper Res. 2013;229(2):518\u201328.","journal-title":"Eur J Oper Res"},{"key":"1466_CR34","doi-asserted-by":"crossref","unstructured":"Schittekat P, Sevaux M, Sorensen K. A mathematical formulation for a school bus routing problem. In: 2006 international conference on service systems and service management. 2006. p. 1552\u20137.","DOI":"10.1109\/ICSSSM.2006.320767"},{"key":"1466_CR35","doi-asserted-by":"crossref","unstructured":"Sciortino M, Lewis R, Thompson J. A heuristic algorithm for school bus routing with bus stop selection. Evolutionary Computation in Combinatorial Optimization, Springer Lecture Notes in Computer Science. 2021;12692:202\u201318.","DOI":"10.1007\/978-3-030-72904-2_13"},{"issue":"2","key":"1466_CR36","first-page":"137","volume":"6","author":"VS Siqueira","year":"2016","unstructured":"Siqueira VS, Silva EN, Silva RV, Rocha ML. Implementation of the metaheuristic GRASP applied to the school bus routing problem. Int J E-Educ E-Bus E-Manage E-Learn. 2016;6(2):137\u201345.","journal-title":"Int J E-Educ E-Bus E-Manage E-Learn"},{"issue":"4","key":"1466_CR37","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1287\/trsc.1040.0096","volume":"39","author":"M Spada","year":"2005","unstructured":"Spada M, Bierlaire M, Liebling TM. Decision-aiding methodology for the school bus routing and scheduling problem. Transp Sci. 2005;39(4):477\u201390.","journal-title":"Transp Sci"},{"issue":"8","key":"1466_CR38","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0202618","volume":"13","author":"S Sun","year":"2018","unstructured":"Sun S, Duan Z, Xu Q. School bus routing problem in the stochastic and time-dependent transportation network. PLoS One. 2018;13(8): e0202618.","journal-title":"PLoS One"}],"container-title":["SN Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-022-01466-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s42979-022-01466-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42979-022-01466-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,7]],"date-time":"2023-01-07T22:28:24Z","timestamp":1673130504000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s42979-022-01466-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,29]]},"references-count":38,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2023,1]]}},"alternative-id":["1466"],"URL":"https:\/\/doi.org\/10.1007\/s42979-022-01466-6","relation":{},"ISSN":["2661-8907"],"issn-type":[{"value":"2661-8907","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,11,29]]},"assertion":[{"value":"17 July 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 October 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 November 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"On behalf of all authors, the corresponding author states that there is no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of Interest"}}],"article-number":"74"}}