Han Hoogeveen

Date: 16:00 – 16:30, Thursday, 03.12.2020
Location: Teams ICS Colloquium

Title: Local Search meets ILP: Finding schedules for electric buses
Abstract: One of the typical problems in Public Transport is the Vehicle Scheduling problem. Here we are given a set of trips that must be driven according to a given timetable. The introduction of electric buses has made this problem much more complex (both from a practical and a computational point of view), since for each bus we must not only find the trips that it has to drive, but we have to come up with a charging schedule as well.
We want to find a solution to this problem using integer linear programming (ILP). Basically, we want to find the best combination from a set of vehicle schedules, where each vehicle schedule describes for a single bus which trips to serve and when to charge. Since it is impossible to enumerate all possible vehicle schedules, we must find the `right subset’ of vehicle schedules to use as input to the ILP.
In an earlier paper we have applied an approach based on column generation. In this presentation I will discuss a new method  to find a good subset of vehicle schedules that is based on using multi-start local search. We have tested both methods on instances from Qbuzz (which serves the public transport in Utrecht under the name U-OV). This new approach finds solutions that are much closer to the theoretical lower bound, which implies a saving of several million euros for the area of Utrecht alone.  The new method has immediately been incorporated by Qbuzz, and it seems promising for other applications in transportation and logistics.