IDEAS home Printed from https://ideas.repec.org/a/pal/jorsoc/v58y2007i12d10.1057_palgrave.jors.2602305.html
   My bibliography  Save this article

Solving school bus routing problems through integer programming

Author

Listed:
  • T Bektaş

    (Université de Montréal, HEC Montréal
    Başkent University)

  • Seda Elmastaş

    (Başkent University
    Bilkent University)

Abstract

In this paper, an exact solution approach is described for solving a real-life school bus routing problem (SBRP) for transporting the students of an elementary school throughout central Ankara, Turkey. The problem is modelled as a capacitated and distance constrained open vehicle routing problem and an associated integer linear program is presented. The integer program borrows some well-known inequalities from the vehicle routing problem, which are also shown to be valid for the SBRP under consideration. The optimal solution of the problem is computed using the proposed formulation, resulting in a saving of up to 28.6% in total travelling cost as compared to the current implementation.

Suggested Citation

  • T Bektaş & Seda Elmastaş, 2007. "Solving school bus routing problems through integer programming," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(12), pages 1599-1604, December.
    • Handle: RePEc:pal:jorsoc:v:58:y:2007:i:12:d:10.1057_palgrave.jors.2602305
    DOI: 10.1057/palgrave.jors.2602305
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1057/palgrave.jors.2602305
    File Function: Abstract
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1057/palgrave.jors.2602305?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. L Y O Li & Z Fu, 2002. "The school bus routing problem: a case study," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 53(5), pages 552-558, May.
    2. Letchford, Adam N. & Lysgaard, Jens & Eglese, Richard W., 2006. "A Branch-and-Cut Algorithm for the Capacitated Open Vehicle Routing Problem," CORAL Working Papers L-2006-06, University of Aarhus, Aarhus School of Business, Department of Business Studies.
    3. D Sariklis & S Powell, 2000. "A heuristic method for the open vehicle routing problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 51(5), pages 564-573, May.
    4. R. D. Angel & W. L. Caudle & R. Noonan & A. Whinston, 1972. "Computer-Assisted School Bus Scheduling," Management Science, INFORMS, vol. 18(6), pages 279-288, February.
    5. Naddef, Denis, 1994. "A remark on "Integer linear programming formulation for a Vehicle Routing Problem" by N.R. Achutan and L. Caccetta, or how to use the Clark & Wright savings to write such integer linear prog," European Journal of Operational Research, Elsevier, vol. 75(1), pages 238-241, May.
    6. Kara, Imdat & Laporte, Gilbert & Bektas, Tolga, 2004. "A note on the lifted Miller-Tucker-Zemlin subtour elimination constraints for the capacitated vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 158(3), pages 793-795, November.
    7. Z Fu & R Eglese & L Y O Li, 2005. "A new tabu search heuristic for the open vehicle routing problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(3), pages 267-274, March.
    8. C D Tarantilis & G Ioannou & C T Kiranoudis & G P Prastacos, 2005. "Solving the open vehicle routeing problem via a single parameter metaheuristic algorithm," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(5), pages 588-596, May.
    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. Joon Moon & Young Joo Kim & Taesu Cheong & Sang Hwa Song, 2020. "Locating Battery Swapping Stations for a Smart e-Bus System," Sustainability, MDPI, vol. 12(3), pages 1-21, February.
    3. 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.
    4. 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).
    5. 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.
    6. 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).
    7. 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.
    8. Agyeman, Stephen & Cheng, Lin, 2020. "Analysis of barriers to perceived service quality in Ghana: Students’ perspectives on bus mobility attributes," Transport Policy, Elsevier, vol. 99(C), pages 63-85.
    9. 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. D Aksen & Z Özyurt & N Aras, 2007. "Open vehicle routing problem with driver nodes and time deadlines," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(9), pages 1223-1234, September.
    2. Fung, Richard Y.K. & Liu, Ran & Jiang, Zhibin, 2013. "A memetic algorithm for the open capacitated arc routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 50(C), pages 53-67.
    3. P P Repoussis & C D Tarantilis & G Ioannou, 2007. "The open vehicle routing problem with time windows," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(3), pages 355-367, March.
    4. U Derigs & K Reuter, 2009. "A simple and efficient tabu search heuristic for solving the open vehicle routing problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(12), pages 1658-1669, December.
    5. 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.
    6. Letchford, Adam N. & Lysgaard, Jens & Eglese, Richard W., 2006. "A Branch-and-Cut Algorithm for the Capacitated Open Vehicle Routing Problem," CORAL Working Papers L-2006-06, University of Aarhus, Aarhus School of Business, Department of Business Studies.
    7. 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).
    8. Atefi, Reza & Salari, Majid & C. Coelho, Leandro & Renaud, Jacques, 2018. "The open vehicle routing problem with decoupling points," European Journal of Operational Research, Elsevier, vol. 265(1), pages 316-327.
    9. X-Y Li & P Tian & S C H Leung, 2009. "An ant colony optimization metaheuristic hybridized with tabu search for open vehicle routing problems," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(7), pages 1012-1025, July.
    10. Liu, Ran & Jiang, Zhibin, 2012. "The close–open mixed vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 220(2), pages 349-360.
    11. Eduardo Lalla-Ruiz & Christopher Expósito-Izquierdo & Shervin Taheripour & Stefan Voß, 2016. "An improved formulation for the multi-depot open vehicle routing problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 38(1), pages 175-187, January.
    12. Furkan Uzar, M. & Çatay, Bülent, 2012. "Distribution planning of bulk lubricants at BP Turkey," Omega, Elsevier, vol. 40(6), pages 870-881.
    13. A N Letchford & J Lysgaard & R W Eglese, 2007. "A branch-and-cut algorithm for the capacitated open vehicle routing problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(12), pages 1642-1651, December.
    14. 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).
    15. Z Fu & R Eglese & L Y O Li, 2005. "A new tabu search heuristic for the open vehicle routing problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(3), pages 267-274, March.
    16. Jesús Sánchez-Oro & Ana D. López-Sánchez & J. Manuel Colmenar, 2020. "A general variable neighborhood search for solving the multi-objective open vehicle routing problem," Journal of Heuristics, Springer, vol. 26(3), pages 423-452, June.
    17. N. Norouzi & R. Tavakkoli-Moghaddam & M. Ghazanfari & M. Alinaghian & A. Salamatbakhsh, 2012. "A New Multi-objective Competitive Open Vehicle Routing Problem Solved by Particle Swarm Optimization," Networks and Spatial Economics, Springer, vol. 12(4), pages 609-633, December.
    18. Zhen, Lu & Tan, Zheyi & Wang, Shuaian & Yi, Wen & Lyu, Junyan, 2021. "Shared mobility oriented open vehicle routing with order radius decision," Transportation Research Part A: Policy and Practice, Elsevier, vol. 144(C), pages 19-33.
    19. 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.
    20. Chiang, Wen-Chyuan & Russell, Robert & Xu, Xiaojing & Zepeda, David, 2009. "A simulation/metaheuristic approach to newspaper production and distribution supply chain problems," International Journal of Production Economics, Elsevier, vol. 121(2), pages 752-767, October.

    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:pal:jorsoc:v:58:y:2007:i:12:d:10.1057_palgrave.jors.2602305. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.palgrave-journals.com/ .

    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.