Fast and useful - Efficient routing and its application in practice

Routing problems are among the most-studied and practical-relevant problems in combinatorial optimization. To tackle their complexity, a plethora of heuristics has been developed in the last decades to compute better and better solutions in a feasible time. However, this race for better solutions has caused heuristics to become extremely intricate and difficult to study or to apply in practice. Furthermore, almost all research has been targeted to solve problems of several hundred customers, even though some applications like waste collection and parcel distributions can involve thousands or even tens of thousands of customers.

In this talk, I will demonstrate that complexity is not the only way to obtain successful heuristics. We developed a well-implemented local search which - guided by problem knowledge, obtained through data mining - is among the most efficient heuristics for the Vehicle Routing Problem. Moreover, its linear scaling can be used to solve very large scale routing problems with 10,000 and more customers in a feasible time. Such a fast routing algorithm can be used to tackle real-world problems, for instance, to simulate whether parcel deliveries via cargo bikes are a decent alternative to classical home deliveries via vans. Finally, efficient solution techniques for routing problems can be used to address more advanced problems, especially when it comes to integrating different decisions along the supply-chain in one optimisation framework. As an example, I will outline the idea of optimising the inventory strategy as well as the distribution jointly.

Registration to Remy Spliet, spliet@ese.eur.nl is required for availability of lunch.