Iterated Local Search Algorithm with Strategic Oscillation for School Bus Routing Problem with Bus Stop Selection
he 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...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Kharazmi University
2017-02-01
|
| Series: | International Journal of Supply and Operations Management |
| Subjects: | |
| Online Access: | http://www.ijsom.com/article_2716_506.html |
| _version_ | 1819073082392838144 |
|---|---|
| author | Mohammad Saied Fallah Niasar Luca Talarico Mehdi Sajadifar Amir Hosein Tayebi |
| author_facet | Mohammad Saied Fallah Niasar Luca Talarico Mehdi Sajadifar Amir Hosein Tayebi |
| author_sort | Mohammad Saied Fallah Niasar |
| collection | DOAJ |
| description | he 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 |
| first_indexed | 2024-12-21T17:47:58Z |
| format | Article |
| id | doaj.art-532500570458418a931afbcf3e17a7e8 |
| institution | Directory Open Access Journal |
| issn | 2383-1359 2383-2525 |
| language | English |
| last_indexed | 2024-12-21T17:47:58Z |
| publishDate | 2017-02-01 |
| publisher | Kharazmi University |
| record_format | Article |
| series | International Journal of Supply and Operations Management |
| spelling | doaj.art-532500570458418a931afbcf3e17a7e82022-12-21T18:55:27ZengKharazmi UniversityInternational Journal of Supply and Operations Management2383-13592383-25252017-02-0141124Iterated Local Search Algorithm with Strategic Oscillation for School Bus Routing Problem with Bus Stop Selection Mohammad Saied Fallah Niasar0Luca Talarico1 Mehdi Sajadifar2Amir Hosein Tayebi3Department of Engineering Management, Faculty of Applied Economics, University of Antwerp, BelgiumDepartment of Engineering Management, Faculty of Applied Economics, University Antwerp, BelgiumDepartment of Industrial Engineering, University of Science and Culture, Tehran, IranDepartment of Engineering Management, Faculty of Applied Economics, University Antwerp, Belgiumhe 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 SBRPhttp://www.ijsom.com/article_2716_506.htmlSchool bus routing problemCombinatorial optimizationIterated local search algorithmStrategic oscillation |
| spellingShingle | Mohammad Saied Fallah Niasar Luca Talarico Mehdi Sajadifar Amir Hosein Tayebi Iterated Local Search Algorithm with Strategic Oscillation for School Bus Routing Problem with Bus Stop Selection International Journal of Supply and Operations Management School bus routing problem Combinatorial optimization Iterated local search algorithm Strategic oscillation |
| title | Iterated Local Search Algorithm with Strategic Oscillation for School Bus Routing Problem with Bus Stop Selection |
| title_full | Iterated Local Search Algorithm with Strategic Oscillation for School Bus Routing Problem with Bus Stop Selection |
| title_fullStr | Iterated Local Search Algorithm with Strategic Oscillation for School Bus Routing Problem with Bus Stop Selection |
| title_full_unstemmed | Iterated Local Search Algorithm with Strategic Oscillation for School Bus Routing Problem with Bus Stop Selection |
| title_short | Iterated Local Search Algorithm with Strategic Oscillation for School Bus Routing Problem with Bus Stop Selection |
| title_sort | iterated local search algorithm with strategic oscillation for school bus routing problem with bus stop selection |
| topic | School bus routing problem Combinatorial optimization Iterated local search algorithm Strategic oscillation |
| url | http://www.ijsom.com/article_2716_506.html |
| work_keys_str_mv | AT mohammadsaiedfallahniasar iteratedlocalsearchalgorithmwithstrategicoscillationforschoolbusroutingproblemwithbusstopselection AT lucatalarico iteratedlocalsearchalgorithmwithstrategicoscillationforschoolbusroutingproblemwithbusstopselection AT mehdisajadifar iteratedlocalsearchalgorithmwithstrategicoscillationforschoolbusroutingproblemwithbusstopselection AT amirhoseintayebi iteratedlocalsearchalgorithmwithstrategicoscillationforschoolbusroutingproblemwithbusstopselection |