Hybrid Variable Neighborhood Search for solving school bus-driver problem with resource constraints

Abstract

The school bus-priver problem with resource constraints (SBDP-RC) is an optimization problem with many practical applications. In the problem, several vehicles are prepared to pick a number of pupils in which the total resources of all vehicles are lower than a predefined value. The aim is to find a schedule that minimizes the sum of the pupils’ waiting times. The problem is NP-hard in the general case. In this paper, to solve the problem. After this, the post phase improves the solution by a general variable neighborhood search (GVNS) with a random neighborhood search combined with shaking technique. The proposed metaheuristic hybridization algorithm is tested on a benchmark to show its efficiency. The results show that the algorithm receives good feasible solutions fast. In many cases, better solutions can be found compared to previous metaheuristic algorithms.