The Traveling Salesman Problem Solution for Delivery and Service Businesses

Swadesh Behera
Sep 16, 2020, 03:48 AM

Image Source


Calculating the most efficient route between a number of cities is a major challenge. There are hundreds of possible options which change based on hundreds of different variables.

For instance, in just 15 cities there are over 87 billion possible round trips. 

This is the traveling salesman problem. 

And it’s an incredibly costly one for any delivery, service, or trucking business.

To solve the traveling salesman problem, you need robust algorithms and some serious computational power.

If you don’t want to invest money in an internal team of expert mathematicians and engineers, you need a third-party solution.

In this article, we’ll explore what makes the traveling salesman problem (TSP) so hard and how business owners can use smart software solutions to solve it, reduce mileage, and improve fleet efficiency.


To navigate to the section which interests you the most, click below:

  • What is The Traveling Salesman Problem?
  • Why the Traveling Salesman Problem Is Still Hard to Solve in 2020
  • How The Little Posy Co. Plans Routes for 1,000 Destinations in Minutes


What Is the Traveling Salesman Problem?


The traveling salesman problem (TSP) is a problem that asks, with a list of stops and the distances between each of them, what is the shortest path/possible route that visits each location and returns to the origin?

For decades the TSP has been a challenge for many businesses that rely on route planning — for example, field service, shipping, and delivery companies.

With just a starting point and a few stops, planning a route can seem complicated enough.

But once you start planning routes throughout the country, it reaches an almost unthinkable level of complexity.

This is what a route would look like if planned to every city in the US with over 500 inhabitants:

Just imagine the number of possible routes you could take when a single possible solution is this complex.


Why the Traveling Salesman Problem Is Still Hard to Solve in 2020

Mathematician Karl Menger discovered the TSP in 1930, over 90 years ago.

Since then, there have been many suggested solutions and algorithms. But they often struggle with the sheer scale, since the number of possible routes increases exponentially with each new stop.

And the truth is, real route planning in 2020 for real businesses is more complex than just a list of stops — making things even more complicated.

In the real world, it’s not as easy as simply finding the shortest route.

It’s not just about destinations and distance, there are many other factors in play.

It’s not as easy as just taking a list of addresses and creating a route. 

A field sales rep, delivery driver, or technician also has to consider a lot of other factors, like time windows, vehicle capacities, and more.


Delivery time windows and planned sales meetings

What if your delivery drivers or salesmen have planned delivery times or sales meetings? Then it’s not enough to just consider the distance, you also have to factor in when they should be at each location.

This adds a whole new level of complexity, and is a challenge that most route planners simply can’t handle.

This particular instance of the problem is also known as the Vehicle Routing Problem with Time Windows (VRPTW). 


Required vehicle capacities or technician qualifications

For deliveries, each package that you plan for can have specific requirements in terms of shipping and handling, from refrigeration to unloading dimensions.

You also have to consider the overall loading capacity of each vehicle.

But even for maintenance and field service businesses, you have to consider the unique qualifications of each technician, and whether they match a job.

This is also known as the Capacitated Vehicle Routing Problem (CVRP)


Planning efficient routes that include both pickups and deliveries

If your business delivers any sort of reusable packaging or recyclable materials to your customers, chances are that reverse logistics are a huge priority.

To maximize the efficiency of your business, you want to integrate both pickup and delivery into all planned routes.

This adds another dimension and a level of complexity that most route optimization tools can’t handle.

This is also referred to as the Pick-up and Delivery Vehicle Routing Problem (PDVRP)


Considering priority of leads, existing clients, and deliveries

To run a business efficiently and keep VIP customers satisfied, you also need to make sure your staff prioritize things the right way.

If your routes don’t consider priority, every customer will be treated the same. So you risk alienating loyal customers if you suddenly switch to an automated solution that can’t handle that.


Balancing workloads between multiple drivers

Of course, when planning routes for multiple drivers, you also have to consider their workloads.

Drivers are only human, and have a maximum shift length of 14 hours and mandatory breaks.

What good is an “efficient route” if it’s not possible for a driver to handle it within the allotted time?

Good workload balancing tools will help you reduce overtime and cut driver costs, and make sure all drivers are HOS-compliant at all times.


How The Little Posy Co. Plans Routes for 1,000 Destinations in Minutes with a Route Optimization Software

The Little Posy Co. is an Australian flower delivery business, with hundreds of unique flowers and posies (bouquets) on offer every single day.

Like any flower delivery business or florist, they face huge fluctuations in demand in relation to different holidays.

On Valentine’s Day in 2019, the order volume exploded to over 1,000 orders in a day, the same volume as a regular week.

Normally, this would be an impossible task for Posy’s small team, but OptimoRoute helped streamline the entire process.

“OptimoRoute has changed the impossible to the absolutely possible on Valentine’s Day. It takes the pressure off – I could not fathom how the workflow could function so smoothly without this piece of software.” – Gabby Maynard, The Little Posy Co.


Bulk Import of Orders and Fast Automatic Route Planning

With a route optimization software, there’s no need to individually add stops or addresses, or plan routes for a single driver at a time.

You can simply import your order list in an Excel spreadsheet or a CSV file.

From there, the software plans routes automatically, adjusting for real-world restrictions like delivery times, driver service areas, driver schedules, and more.

“I couldn’t even imagine having to dispatch 1,000 orders without OptimoRoute because it’s literally a few clicks of a mouse and the routes are perfectly mapped.” Gabby Maynard, The Little Posy Co.


Historical Data and Analytics Help Forecast Demand

The historical route data and detailed analytics helped Maynard forecast the demand for, and scale the fleet accordingly.

“We rely heavily on historical data – knowing how many drivers I need to recruit for the day, how many orders each driver can take, how long those deliveries would take, and how many drivers were dispatched.” Gabby Maynard, The Little Posy Co.


Final Thoughts

As a business owner, the last thing you want to do is waste unnecessary time sitting in Google Maps trying to plan routes and not getting optimal solutions.

The TSP affects businesses because planning routes manually requires so much work, ballooning the man hours and total costs of your logistics.

This can often mean oversized dispatching and scheduling departments, and a fleet that is slow to respond to cancellations and last-minute orders.


This article was originally published at


Latest Posts

  • Latest Posts