Greenplan talked to Prof. Dr. Jens Vygen from the Research Institute for Discrete Mathematics and the Hausdorff Center of Mathematics about the cooperation with the tour planning startup. The interview provides interesting insights about how discrete mathematics benefits tour planning approaches.
Professor Vygen, you are a Professor of Mathematics at the University of Bonn and work at the Research Institute for Discrete Mathematics and the Hausdorff Center of Mathematics, also located in Bonn. You specialize in combinatorial optimization and, together with Professor Korte, head the “Combinatorial Optimization in Chip Design” cooperation with IBM that exists for over 30 years. You also manage the “Combinatorial Optimization for Applications in Pickup and Delivery Services” cooperation with Deutsche Post DHL, initiated in 2016.
What was it about logistics that attracted your interest?
The core problems that we see in this area – starting with the well-known Traveling Salesman Problem (TSP) – are classic combinatorial optimization problems that I had studied previously on a more theoretical level. There is still a lot to discover here. The TSP gets even more interesting when you have to account for additional real-life requirements for which mathematical models and algorithms do not yet exist. It is always satisfying when we can apply innovative mathematics to help generate real-world solutions that actually improve efficiency and save resources. In our cooperation with Greenplan, we enjoy a very direct route between theory and practice; we are able to test and apply our mathematical ideas right away in the real world of logistics.
What is discrete mathematics and how does the route planning algorithm benefit from the expertise of your institute in this area?
Discrete mathematics analyzes systems in which the number of choices or alternatives is finite, but still large enough so that it would be impossible to simply try them all out. A good example is the TSP. If you need to deliver to three different places from a single warehouse, you can simply try out all the possible sequences: ABC, ACB, BAC, BCA, CAB, CBA. But if you have 30 places instead of three, the number of alternatives is astronomical; even all the computers on the planet working together would take years to compute them. Discrete mathematics provides a way to quickly find the optimal sequence of these 30 places; we call this combinatorial optimization. Our institute is a leader in the field. We also have decades of experience with industrial applications and write software that meets the highest standards and requirements.
What are some of the unique features of the algorithm you have developed in cooperation with DHL/Greenplan?
We have conceived our algorithm so that it is flexible and guarantees to always find a solution in a short amount of time that takes into account all constraints. For very large or complex problems, a few minutes is not enough to compute an optimum solution, but we can get very close to it. We work with a very carefully designed general model that can be used for very different real-world applications and scenarios. We also work with realistic travel times, which vary depending not only on the type of vehicle and route but also time of day. This makes some of the algorithms more complex, but not necessarily much slower, and it pays off in the form of much more realistic and robust solutions, especially when deadlines need to be met.
How do you see this area developing in the future?
We are constantly coming up with new ideas, and continuously improving on the algorithm – making it better and faster, but also responding to new real-world conditions and requirements. We were recently able to prove a better approximation guarantee, for example, and now want to see how this translates into real-world benefits. Other focus areas include planning with incomplete data and making on-the-fly route adjustments based on changing requirements. And we have many more ideas, so no risk of boredom here!
What makes the cooperation with Deutsche Post DHL such a success?
It is an excellent collaboration; we cooperate very closely and communicate on almost a daily basis. Because we are all located in Bonn, we have the luxury of being able to meet in person often. So we can move quickly – from the time of a new mathematical idea to the real-world application, or from a new real-world requirement to an updated algorithm. Another important factor is that we, as part of the Hausdorff Center for Mathematics excellence cluster, are able to recruit outstanding students to our team on a regular basis. One of our former doctoral students, for example, is already working for Greenplan, and more are sure to follow.
Thank you for your time!