Our Latest Performance Improvement: Solving Traveling Salesman Problems Up To 50% Faster

We are constantly working to improve our software to better serve our customers. We solve millions of vehicle routing problems every day. Over 90% of these problems are actually variations of the famous traveling salesman problem, which requires finding the shortest possible route that visits all the locations exactly once. As we see these problems being solved in the mobile context more often, just like ordinary shortest path problems (from an origin to a destination), we also see the need to solve these problems faster and faster. We are excited to announce our latest performance improvement: we can now solve traveling salesman problems up to 50% faster!

To solve real world Traveling Salesman problems, we essentially need to solve 2 main sub-problems which have to be solved one after the other: the shortest path problem to calculate all travel times and distances between all locations and the actual Traveling Salesman problem to determine the best sequence of these locations.

We have already written a detailed article about our incredible fast Matrix API and how we solve the first subproblem, i.e. the shortest path problem. It can be read here. The improvements made on the second subproblem can be summarized as follows:

Firstly, we have optimized our software and hardware to take even more advantage of parallel processing, which means that we can now solve multiple parts of the problem simultaneously (on hardware that is suited best for these kind of tasks). This has dramatically reduced the time required to find a solution.

In addition, we have developed new heuristics that enable us to quickly eliminate non-optimal routes and focus on the most promising paths. This helps us to converge on a solution more quickly and with greater accuracy.

These enhancements enable us to solve traveling salesman problems as quickly as it is illustrated in the following figure. The traveling salesman problems used here are typical last mile delivery problems with random stops in Munich.

The figure shows the computation times in milliseconds (y-axis) for 5 traveling salesman problems varying in size (x-axis). The travel times are calculated based on OpenStreetMap. Furthermore, it differentiates between the computation time of the matrix (all travel times and distances between all locations, e.g. 40×40 or 120×120 travel times) and of the traveling salesman problem (tsp). As you can see, a traveling salesman problem with 120 stops can now be solved in 380ms. The matrix takes 120ms and searching for the best sequence 260ms*.

It takes slightly more time if you solve these traveling salesman problems with (day)time-dependent travel times from TomTom. To solve this type of problem, we compute multiple matrices to account for traffic and peak and off-peak travel times (see here for an article describing how we derive time-dependent travel times).

As illustrated in the figure above a traveling salesman problem with 120 stops takes 825ms in total (209ms for the matrix, 616ms for the sequence)*.

These improvements mean that our customers now get faster results enabling them to optimize their operations more effectively. At the same time, we – for our part – can solve these problems even more efficiently and thus more problems with the same computing capacity, which in turn allows us to offer our service at attractive prices.

We are committed to continuously improving our software and providing our customers with the best possible service and are excited to see the impact our latest performance improvement will have on our customers’ businesses. If you have any questions or would like to learn more about our software, please don’t hesitate to get in touch. If you are new to GraphHopper and just want to try our service without contacting us and without any further obligations, you are welcome to register here. Then you will get a free Standard plan for two weeks.

Happy Routing!

Your GraphHopper Team

*_{All computation times shown above are average numbers (from 100 runs). The traveling salesman problems are solved on our fastest dedicated setup, i.e. if you register here to try out our service, it takes slightly more time.}