Why Routing? In an increasingly interconnected world, many applications share one common feature: Several destinations have to be visited from a point of origin. Consider the distribution of parcels as an example. The delivery company employs several drivers, each of which can visit customers on a route. A driver starts a route in the morning from a distribution center, delivers all parcels to the respective customers and returns after the work is done. Having better planned routes can significantly decrease the costs of the companys, but it also reduces emissions and congestion. The efficient planning of these routes is the essence of the Vehicle Routing Problem (VRP).

Computing routes. Routing problems are among the most intensively studied problems in the field of combinatorial optimization; largely because the underlying models are simple, yet challenging to solve. If we have to plan the routing for 20 customers there are already more possible solutions than there are cells in the human body, and for 60 customers the number of solutions is larger than the number of observable atoms in the universe. RoutingSolver has been applied to problems with up to 30.000 customers and the sheer magnitudes of the resulting problem complexity are beyond any physical comparison in the real-world.

Heuristics. Rather than looking at every possible solution, heuristics try to take a shortcut and find a solution that is not necessarily the best one, but good enough. This idea is so fundamental that it is even wired in the human brain. Many decisions that we take in our daily life are not the product of a detailed rational analysis and comparison between all available options, but rather based on past experience and current emotion. In the domain of routing, a variety of impressive heuristics have been developed in the last decade, that solve routing problems with several hundred customers to near-optimality in a few minutes.

  • Scholar Florian Arnold
  • LinkedIn Florian Arnold

© 2018 by Florian Arnold