Discrete Mathematics for Green Route Planning

University of Bonn and Deutsche Post DHL Group Perpetuate their Cooperation. Various Awards

Bonn, 23.03.2021. How can parcels and freight be delivered in a more resource-saving and sustainable way? Since 2017, the University of Bonn and the Deutsche Post DHL Group cooperate in the area of route planning. The Research Institute for Discrete Mathematics has developed an algorithm that exploits the considerable optimization potential and is already being used successfully in practice. Therefore, the Deutsche Post DHL has founded the subsidiary company Greenplan that aims at using the algorithm for a wide variety of applications. The cooperation will now be continued for an unlimited period.

“The collaboration with the logistic experts at Greenplan was very fruitful from the start”, Jens Vygen, Professor at the Research Institute for Discrete Mathematics, says. “We developed an algorithm that is not only flexibly applicable but also delivers excellent results after only a short computation time.” A novelty is that the algorithm considers travel times that do not only depend on the distance, but also on the time of day. The routes can, for example, avoid traffic jams and can facilitate considerable savings in cost and emission. For this, Greenplan received the PostEurop Innovation Award last year.

Dr. Dirk Müller, who leads the software development at the Research Institute for Discrete Mathematics, explains the difficulties: "Even the calculation of the best route from A to B is difficult when the travel time and cost depend on traffic situations.” The question how much the cost of a tour increases if a new assignment is added at the optimal position is much more difficult and must be answered millions of times by the program. ”And this with a total computation time of only a few minutes."

Dr. Clemens Beckmann, CEO of Greenplan, studied mathematics himself and is delighted by the close cooperation with the university: “The great professionalism in the collaboration, as well as the geographical proximity, have been the basis for the extremely fast development, during which the logistic and scientific expertise complemented each other optimally.” Today, the young company can therefore offer their customers from logistics, external work planning (for example technicians, installers), and e-commerce a route planning tool that is efficient as well as sustainable and that can be used quickly and flexibly for a variety of applications. “With the new contract we have further strengthened our cooperation and we are looking forward to our future collaboration."

With the number of cities, the number of routes increases extremely

The Discrete Mathematics group led by Professor Jens Vygen are experts for Combinatorial Optimization. In recent years, they have developed better and better algorithms, especially for the Traveling Salesman Problem. Here the aim is to find the shortest round trip through different cities. For 15 cities there are already more than 87 billion different round trips, and for 20 cities, even a computer can no longer try out all the options.

Award for the research team

Now the scientists even succeeded in finding a better approximation ratio for the Capacitated Vehicle Routing; the first one in 30 years. The authors Jannis Blauth, Vera Traub, and Jens Vygen will receive the Best Paper Award at IPCO 2021, which will be held in May and which is the worldwide leading conference on Integer Programming and Combinatorial Optimization.

The tour planning team at the Research Institute for Discrete Mathematics. Clockwise, starting at 12 o'clock: Professor Jens Vygen, Antonia Ellerbrock, Felix Rosebrock, Dr. Dirk Müller, Professor Stephan Held, Jannis Blauth (Doktorand), Silas Rathke, Vanessa Ryborz and in the middle Luise Puhlmann. © Jens Vygen/HCM/Uni Bonn