Traveling salesman problem: finding the optimal route

By December 16, 2020Mobile, WorkForce Management
traveling salesman problem

Finding the shortest yet most efficient route for delivery drivers and fieldworkers is the biggest challenge for logistic centers, warehouses, and companies providing field services and deliveries. Route optimization is so complicated that it requires mathematical algorithms. One of them is the classic “Traveling salesman problem”, famous for its simple description and a difficult calculational process.

What is the traveling salesman problem?

The traveling salesman (in our case it’s the courier, deliveryman, driver, field service employee) has to visit several cities and return to his starting point. We know the distance between each city. What is the shortest possible route for the traveling salesman? This route can be expressed in kilometers, the time needed to complete it, or its cost. Therefore, we can search for the shortest, faster, or cheapest route. We also have to assume, that the distance between any two cities isn’t longer than the length of any of the roads connecting those cities that leads through different cities.

Let’s see this problem on the example of a delivery logistics company. They plan deliveries to tens or even hundreds of recipients every day and that requires loading tens or hundreds of vehicles. Rules of combinatorics tell us that having many recipients and a large fleet, there are more ways to plan the routes than number combinations on the lottery tickets. How can the delivery company managers tackle the mathematicians’ daunting challenge? 

Support of the algorithms

Until now, the logisticians and dispatchers spent most of their time planning the routes. However, comparing all of the optimal options wasn’t possible. The calculations were simplified and time-consuming and the final result, coming from Excel spreadsheets, wasn’t satisfying. Don’t get rid of those spreadsheets though! Fill them out with data about tasks, employees, and destinations, and then use a more sophisticated tool. A tool that can calculate all the times, distances, and other parameters within a few minutes. This tool is GeoTask Planner Portal, Google Maps based application for automated route and task planning. If you want to build your own application for managing deliveries, you can use a Cloud API offered with GeoTask Planner.

Why are tools for route optimization worth using? 

We already know that even qualified specialists may struggle with planning routes between many dispersed places. This is why the benefits of using IT tools for automated route optimization are worth looking at. It’s best to illustrate it with a real analysis performed by our team at one of the logistics centers using the GeoTask Planner application. 

What’s it like in the reality? 

The logistics center mentioned above is a big company with an area of 20 000 m2 which delivers products to about 300-400 stores every day. The list of the recipients depends on supply needs, time of the year, and day of the week. We analyzed a five-day sample. 

The center’s logisticians have to match the deliveries to particular vehicles and start the completion process fast so that the trucks can start the journey in the morning of the next day. The loading is performed according to LIFO (Last In First Out), the first loaded parcel goes to the last visited store, and the last loaded parcel goes to the first store. The route has to be planned according to this order. 

Using the GeoTask Planner application significantly shortened the route. The diagram below shows the reduction of the number of driven kilometers by the whole fleet. 

Pic. 1. Number of kilometers for routes that include the same stops, planned by the logistician and the GeoTask Planner optimizer on a particular day. 

Based on the analyzed case we can see that GeoTask Planner allows us to shorten the routes by 19% on average. This is how much you save on the route length alone. 

route optimizing

Pic 2. How many percent of the routes planned by the GeoTask Planner optimizer are shorter than those planned by the logistician.

Since the application plans the routes in a way that uses the cargo space to the maximum, the center got the additional benefits of optimal loading. This allowed them to limit the number of the vehicles needed to complete deliveries by 1-2 vehicles on average compared to the planning without the optimization tool. The table below shows the number of stores that are awaiting deliveries on particular days and the number of vehicles needed to perform this task when planned by the logistician versus planned by GeoTask Planner. 

optimized route

What are the benefits of automated optimization?

  • You get the best route out of thousands of options. Planning routes takes few minutes instead of hours so logisticians can save up to 80% of their time.
  • Routes are planned according to data from map services such as the length of the route and the driving time. This provides accurate information for the drivers.
  • Routes planned with the optimizer are reduced by as much as 20%.
  • Planned routes consider vehicle capacity, reducing the number of delivery trucks needed.
  • Automated delivery scheduling saves up to 80% of the dispatcher’s time devoted to planning.

Sound interesting? Try GeoTaskPlanner out!

You can try GeoTaskPlanner out and test it for free for 2 weeks. Test the system and see how automated route and schedule planning will improve the effectiveness of your operations and quality of customer service.