Iterated Local Search Algorithm with Strategic Oscillation for School Bus Routing Problem with Bus Stop Selection

Document Type : Research Paper

Authors

1 Department of Engineering Management, Faculty of Applied Economics, University of Antwerp, Belgium

2 Department of Engineering Management, Faculty of Applied Economics, University Antwerp, Belgium

3 Department of Industrial Engineering, University of Science and Culture, Tehran, Iran

Abstract

The school bus routing problem (SBRP) represents a variant of the well-known vehicle routing problem. The main goal of this study is to pick up students allocated to some bus stops and generate routes, including the selected stops, in order to carry students to school. In this paper, we have proposed a simple but effective metaheuristic approach that employs two features: first, it utilizes large neighborhood structures for a deeper exploration of the search space; second, the proposed heuristic executes an efficient transition between the feasible and infeasible portions of the search space. Exploration of the infeasible area is controlled by a dynamic penalty function to convert the unfeasible solution into a feasible one. Two metaheuristics, called N-ILS (a variant of the Nearest Neighbourhood with Iterated Local Search algorithm) and I-ILS (a variant of Insertion with Iterated Local Search algorithm) are proposed to solve SBRP. Our experimental procedure is based on the two data sets. The results show that N-ILS is able to obtain better solutions in shorter computing times. Additionally, N-ILS appears to be very competitive in comparison with the best existing metaheuristics suggested for SBRP

Keywords

Main Subjects

References

Angel R., Caudle W., Noonan R. and Whinston A. (1972). Computer-assisted school bus scheduling. Management Science, Vol. 18, pp. 279-288.
Baldacci R., Dell'amico M. and González J. S. (2007). The capacitated m-ring-star problem. Operations Research, Vol. 55, pp. 1147-1162.
Bock A., Grant E., Könemann J. and Sanità, L. (2011).The school bus problem on trees. International Symposium on Algorithms and Computation, Springer, pp. 10-19.
Bodin L. D. and Berman L. (1979). Routing and scheduling of school buses by computer. Transportation Science, Vol. 13, pp. 113-129.
Bowerman R., Hall B. and Calamai P. (1995). A multi-objective optimization approach to urban school bus routing: Formulation and solution method. Transportation Research Part A: Policy and Practice, Vol. 29, pp. 107-123.
Brandao J. (2006). A new tabu search algorithm for the vehicle routing problem with backhauls. European Journal of Operational Research, Vol. 173, pp. 540-555.
Campbell A. M. and Savelsbergh M. (2004). Efficient insertion heuristics for vehicle routing and scheduling problems. Transportation science, Vol. 38, pp. 369-378.
Chapleau L., Ferland J. A. and Rousseau J. M. (1985). Clustering for routing in densely populated areas. European Journal of Operational Research, Vol. 20, pp. 48-57.
Desrosiers J., Commerciales É. D. H. É. Transports, U. D. M. C. D. R. S. L. and Opérationnelle, U. D. M. D. D. I. E. D. R. (1986a). TRANSCOL: A multi-period school bus routing and scheduling system, Montréal: Université de Montréal, Centre de recherche sur les tranports.
Desrosiers J., Transports U. D. M. C. D. R. S. L. and Opérationnelle, U. D. M. D. D. I. E. D. R. (1980). An Overview of School Busing System, Montréal: Université de Montréal, Centre de recherche sur les transports.
Dulac G., Ferland J. A. and Forgues P. A.( 1980). School bus routes generator in urban surroundings. Computers & Operations Research, Vol. 7, pp. 199-213.
Gavish B. and Shlifer E. (1979). An approach for solving a class of transportation scheduling problems. European Journal of Operational Research, Vol. 3, pp. 122-134.
Hansen P. and Mladenović N. (1999). An introduction to variable neighborhood search. In Meta-heuristics, pp. 433-458. Springer US.
Hachicha M., Hodgson M. J., Laporte G. and SEMET F. (2000). Heuristics for the multi-vehicle covering tour problem. Computers & Operations Research, Vol. 27, pp. 29-42.
Kinable J., Spieksma F. and Vanden berghe G.( 2014). School bus routing—a column generation approach. International Transactions in Operational Research, Vol. 21, pp. 453-478.
Lourenço H. R., Martin O. C. and Stützle T.( 2010). Iterated local search: Framework and applications. Hand book of Metaheuristics. Springer.
Newton R. M. and Thomas W. H. (1974). Bus routing in a multi-school system. Computers & Operations Research, Vol. 1, pp. 213-222.
Pacheco J., Caballero R., Laguna M. and Molina J. (2013). Bi-objective bus routing: an application to school buses in rural areas. Transportation Science, Vol.  47, pp. 397-411.
Park J. and Kim B. I.( 2010). The school bus routing problem: A review. European Journal of operational research, Vol.  202, pp. 311-319.
Riera-ledesma J., Salazar-gonzález J. J. (2013). A column generation approach for a school bus routing problem with resource constraints. Computers & Operations Research, Vol.  40, pp. 566-583.
Schittekat P., Kinable J., Sörensen K., Sevaux M., Spieksma F. and Springael J.( 2013). A metaheuristic for the school bus routing problem with bus stop selection. European Journal of Operational Research, Vol. 229, pp. 518-528.
Subramanian A., Drummond L. M. D. A., Bentes C., Ochi L. S. and Farias R.(2010). A parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery. Computers & Operations Research, Vol. 37, pp. 1899-1911.
Swersey A. J. and Ballard W.( 1984). Scheduling school buses. Management Science, 30, 844-853. Talarico L., Sörensen K.and Springael J. (2015). Metaheuristics for the risk-constrained cash-in-transit vehicle routing problem. European Journal of Operational Research, Vol.  244, pp. 457-470.
Toth P. and Vigo D.( 2002). Vehicle Routing Problem SIAM Monographs on Discrete Mathematics and Applications, Vol. 9. SIAM: Philadelphia, PA.
Toth P. and Vigo D.( 2003). The granular tabu search and its application to the vehicle-routing problem. Informs Journal on computing, Vol.  15, pp. 333-346.
Verderber W. J. (1974). Automated pupil transportation. Computers & Operations Research, Vol. 1, pp. 235-245.
International Journal of Supply and Operations Management
Volume 4, Issue 1 - Serial Number 1
February 2016
Pages 1-14

Files

Share

How to cite

Statistics