Martin Grötschel (Zuse Institute Berlin)
Title
Routing problems: Standard and unusual cases
Abstract
Shortest path, Chinese postman and symmetric travelling salesman problems are combinatorial optimization problems with a rich theory. They have undergone extensive computational studies and can be viewed as “solved” for the majority of their practical applications. However, most routing problems are not so nicely structured. They often come with various combinations of side constraints such as capacity, depot and ordering constraints as well as time windows, with online or real-time requirements and possibly multiple objective functions. Such routing problems are notoriously difficult and a typical playground for heuristics.
In the last 30 years my research group has covered a large variety of routing problems in public transport, logistics, general transportation, machine and emergency scheduling, etc.
I plan to give a broad survey on these problems as well as on successful solution approaches, and I will concentrate on particular cases that we are currently working on. These include train scheduling (high-speed trains ICE in Germany with uncommon “regularity requirements”) and a quite unusual routing problem where vehicles have to be routed “optimally” to catch trucks on the German Autobahn that try to avoid the payment of road tolls. Needless to say, that these inspection vehicles have to satisfy several nonstandard legal requirements.