Scheduling electric vehicles by simulated annealing with recombination through ILP

In this paper, we consider the electric vehicle scheduling problem (e-VSP): a set of trips corresponding to a given timetable have to be driven by a set of electric buses with limited capacity. This problem, like many other planning problems, boils down to assigning to each bus a subset of the trips with the obvious side constraint that the selected subset can be feasibly driven by this single bus; such a feasible subset is called a vehicle schedule. If we know all possible vehicle schedules, we can select the best set of these by solving an integer linear program (ILP). This idea has inspired many researchers to the heuristic of finding a decent subset of all vehicle schedules using the technique of column generation and then solve the ILP. For the e-VSP, this approach leads to good solutions, but there is still room for improvement. Instead of using column generation, we apply simulated annealing to find the subset of vehicle schedules that we use as input for the ILP. For the e-VSP, this leads to better solutions. Moreover, this approach, which we call simulated annealing with recombination through ILP, is generally applicable and has as a clear advantage that we do not have to solve the pricing problem, because this approach increases the application possibilities and takes far less time.