PhD candidate: Maurice de Kort
Start: Spring 2025
Designing routes for vehicles is an important task in many logistical processes, such as parcel delivery, store resupply, public transport and waste collection. In essence, the task is to find the shortest routes visiting all customers. Many companies offer software which design vehicle routes, like ORTEC, Route4Me, and Google. However, such software typically does not provide optimal routes. Instead, it makes use of heuristic algorithms which provide routes that may outperform manual planners, but for which it is not clear how far away from the optimum they are. Great opportunities remain for reducing costs, energy, emission, congestion, noise, etc., on a large scale.
To find the optimal solution, a common approach is to model the problem as a Mixed Integer Linear Program (MILP) and use MILP algorithms to solve it. However, there are many different ways to formulate an optimization problem as a MILP, and the choice of formulation can have a significant impact on computational performance. In this PhD project, I derive theoretical bounds on the sizes and strengths of formulations, which determine their efficiency. Using these insights, I develop novel formulations, in particular for routing problems.
With this research, I aim to obtain new theoretical and computational insights on vehicle routing problems, providing new research directions for the scientific community. The ambition is to take a step towards faster algorithms to solve routing problems to optimality, closing the gap between the current scientific state-of-the-art and industry-ready algorithms.
