Prof. Dr. Remy Spliet
Period: Jan 2025 – dec 2029
Funded by: NWO
The vehicle routing problem (VRP) is an optimization problem in which it has to be decided in what order locations (such as customers’ homes, shops or ports) are visited by vehicles (such as vans, trucks or ships). This is a central optimization problem in the field of Operations Research. Using modern computer technology and sophisticated algorithms, we are able to find the optimal solution for instances of the VRP with about 100 locations, within a reasonable computation time (say a few hours).
Although this is respectable, this scale is not close to instances observed in practice, where e.g. a postal service schedules deliveries at thousands of homes. Therefore, in practice, optimality is abandoned and schedules are used that are not too bad. This leaves the opportunity to reduce costs, energy, emission, congestion, noise, etc., on a large scale. State-of-the-art methods for solving the VRP rely on mathematical models, in which the modeler decides on how to encode a solution.
For example, for every two locations, we can introduce a binary variable that is either one if a vehicle travels between those locations, or zero if it does not. Another type of encoding is to introduce a binary variable for every potential route that a vehicle may traverse, which is one if the route is used, and zero if it is not. The chosen encoding has a fundamental impact on our ability to solve the VRP. For example, the size of the mathematical model is affected (the smaller the better). Therefore, a natural question that we study in our research is: What is the smallest possible encoding for the VRP? In this research project, we explore encodings and their properties, in a pursuit to discover new methods for solving the VRP on a larger scale.
