What is the TSP (travelling salesman problem)?

How do you determine the best itinerary to visit multiple customers while covering the fewest possible kilometres? Behind this question, which mobile sales reps face every day, lies a mathematical problem studied for decades: the Travelling Salesperson Problem, or TSP.

Its principle is simple: find the shortest path connecting several destinations. However, solving it quickly becomes complex as the number of points to visit increases.

And in reality, organising a sales route is not just about calculating distances. You also have to respect customers' opening hours, pre-scheduled appointments, visit durations, and working days.

So, how does the TSP work? Why is it so difficult to solve? And how can its principles help build more effective sales routes?

What is the Travelling Salesperson Problem (TSP)?

The Travelling Salesperson Problem (TSP) is a classic combinatorial optimisation problem.

It consists of determining the shortest route that visits a set of destinations, stopping at each of them exactly once, before returning to the starting point.

Let's take an example.

A sales rep needs to visit five stores across their territory. They know their addresses, but must determine the order in which to visit them to minimise the distance travelled.

They could start with store A, proceed to B, then C, D, and E. But they could also visit these stores in a completely different order.

Each combination produces an itinerary whose total distance may vary.

The goal of the TSP is to find the sequence of stops that results in the shortest total distance travelled.

This challenge extends far beyond sales teams. It is found in logistics, delivery, transport, and even certain industrial processes.

Why is the TSP so complex to solve?

When the number of destinations is limited, comparing several itineraries is relatively straightforward.

However, each new destination considerably increases the number of possible combinations.

By fixing a starting point and considering all possible visit sequences:

• With 5 destinations, there are 24 possible sequences.

• With 10 destinations, there are 362,880.

• With 15 destinations, that number exceeds 87 billion.

These figures illustrate what is known as a combinatorial explosion: the number of possible solutions increases extremely rapidly with the size of the problem.

In computer science, the TSP belongs to the family of NP-hard problems. In other words, no known general method can guarantee the exact solution of all instances in a computing time that scales polynomially with their size.

This does not mean that finding the optimal solution is impossible. Exact methods exist and can solve many instances.

However, when the number of destinations and constraints increases, systematically searching for the perfect solution can require substantial computing resources.

This is why optimisation tools use various methods to find effective itineraries within a reasonable timeframe.

How does a TSP algorithm work?

In its classic formulation, the Travelling Salesperson Problem relies mainly on two elements:

1. The destinations to visit, represented by geographic points.

2. The travel distance or cost between these destinations, allowing itineraries to be compared.

The problem also defines a loop, with a starting point and a return to that same point.

Based on this information, the algorithm searches for the visit order that minimises the total distance.

The different solving methods

Several approaches can be used to solve a TSP problem.

Exact methods explore solutions in a structured way to identify and prove the best possible itinerary. They can become computationally expensive as the problem grows more complex.

Heuristics aim to quickly obtain a satisfactory solution, without guaranteeing that it is optimal. A simple approach, for example, consists of travelling to the nearest unvisited destination at each step.

Metaheuristics use more sophisticated search strategies to explore and improve various solutions. They are particularly valuable for large-scale problems.

The choice of method depends on the number of destinations, the available computing time, and the required level of accuracy.

However, in the context of sales routes, another factor comes into play: distance is not the only constraint to satisfy.

From the TSP to route optimisation: why the shortest path is not enough

The classic TSP answers one question: what is the shortest route to visit all destinations?

A field sales rep must answer a much more complex question: how do I organise my visits to meet the right customers, at the right times, while limiting my travel and respecting my daily constraints?

The difference is significant.

Imagine a Field Sales Representative who needs to visit fifteen stores over three days.

An algorithm that solely aims to reduce distance might propose an itinerary that looks very short on paper. Yet that schedule could be impossible to carry out:

• A store might be closed when they arrive.

• A visit might take longer than the available time slot.

• Two appointments could overlap.

• The sales rep might finish their day well past their working hours.

• An already confirmed appointment might have to be rescheduled.

The shortest path is therefore not necessarily the most efficient sales route, nor even a feasible one.

To tackle these challenges, route optimisation software uses more advanced mathematical models than the classic TSP.

In particular, they resemble Vehicle Routing Problems (VRP) and their variants that incorporate time windows or scheduling constraints.

These models make it possible to determine not only the visiting order, but also a coherent distribution of visits over time.

What constraints must a sales route optimiser take into account?

To build a sales route tailored to real-world conditions, several parameters can be integrated.

The starting address

This defines the point from which the sales rep begins travelling: home, the office, or another reference address.

Working hours

They define the window during which travel and visits must be organised. A sales rep working from 8:00 to 17:00 does not have the same available time as one finishing their day at 19:00.

The maximum number of visits per day

This caps the number of appointments scheduled each day, particularly to avoid overloading working days.

Visit duration

Not all sales visits require the same amount of time. A fifteen-minute prospecting meeting is not organised in the same way as a forty-five-minute visit in grocery retail.

Opening hours of establishments

A pharmacy, a restaurant, or a shop cannot necessarily be visited at any time. Optimisation must account for their opening times whenever they are specified.

The lunch break

It can be integrated into the schedule to reserve break time during the day.

Active days and excluded days

A sales rep may work across several days while excluding specific days dedicated to other activities, meetings, or leave.

The planning period

Optimisation can cover a single day, a week, or a longer period, depending on portfolio coverage requirements.

Pre-scheduled appointments

This is a particularly crucial constraint. When a sales rep has confirmed appointments, the optimisation must be able to organise the other visits around these commitments.

Taken together, these parameters transform a simple distance problem into a genuine sales planning problem.

Discover how to help your sales reps plan their sales routes.

Why can an optimised route sometimes seem counter-intuitive?

Let's look at a concrete example.

A sales rep visits a store in Toulouse. Just 200 metres away lies another point of sale belonging to their portfolio.

Yet the optimiser does not schedule this second store on the same day. It places it on the following day.

At first glance, this choice seems counter-intuitive. Why return to the same neighbourhood when the two locations are so close?

Several constraints can explain this outcome.

The store might be closed at the time of the visit. The planned visit duration might prevent the sales rep from arriving on time for their next appointment. The maximum number of visits might also have been reached.

The optimiser searches for a solution that complies with all defined constraints. Geographic proximity alone is therefore not always sufficient to justify adding an establishment to a sales route.

This example illustrates a fundamental difference between the TSP and its commercial application.

An optimised sales route does not necessarily correspond to the shortest path between customers, but to an organisation that seeks the best trade-off between travel, available time, and visit constraints.

How do you transition from the TSP to an optimised sales route?

The Travelling Salesperson Problem helps illustrate the mathematical challenge of finding the best route. But to organise the travel of a mobile sales rep, software must go further.

It must incorporate customer data, working hours, visit durations, and existing appointments, and then identify a coherent organisation based on these constraints.

This is the role of a route optimisation engine: transforming a selection of customers and planning parameters into an actionable sales route proposal.

With Sidely, this engine is directly integrated into the field CRM. Sales reps can run an optimisation from their map or their calendar, taking already scheduled appointments into account.

To understand the various calculation steps, the methods used, and how Sidely organises visits, check out our article: How does a route optimisation engine work?

TSP and route optimisation: key takeaways

The Travelling Salesperson Problem is one of the most famous problems in mathematical optimisation. It seeks to identify the shortest circuit that visits a set of destinations before returning to the starting point.

However, in the day-to-day life of mobile sales reps, distance is only one part of the equation.

Opening hours, visit durations, confirmed appointments, working days, and sales priorities must also be taken into account.

This is why professional route optimisers rely on more complex planning models than the classic TSP.

Their goal is not simply to minimise the kilometres driven by sales reps, but to help them organise realistic, coherent, and commercially effective days.

By embedding this logic directly within the CRM, Sidely enables field teams to move seamlessly from selecting the customers to visit to the practical organisation of their journeys.