چکیده:
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
خلاصه ماشینی:
"Allocation Heuristic Sub-Problem We consider student allocation in two positions: first, in the constructive phase when the stops are selected, the routes are built and the feasibility of the solution in term of student allocation is preserved; second, during the second level of the oscillating strategy stage where the current solution is re-optimized.
Best parameter settings for both metaheuristics رجوع شود به تصویر صفحه Based on P-value, it seems that all local search operators, percentage number of routes to be destroyed ( ) , as well as the value of initial penalty (0 ) are important parameters that influence both the solution quality and the computing time.
Each table presents details on the problem instances and also results of each metaheuristics in 10 columns: Number of stops (column stop), number of students (column stud), bus capacity (column cap), maximum walking distance (column wd), The best know solutions obtained by the metaheuristic in Schittekat et al (column Best known sol), Exact solution found by GAMS software (column GAMS ),best solutions calculated after 10 runs (column Best sol), average cost of the solutions calculated after 10 runs (column Avg sol), Best gap from best known solutions (column % Best Gap) , Average gap from best known solutions (column percentage % Avg Gap) and average computing time (column Avg time in seconds)."