Travelling salesman problem applied to logistics

The travelling salesman problem — also known as the travelling salesperson problem — is one of the most common issues in logistics. But how can it be solved?

What is the travelling salesman problem?

The travelling salesman problem is part of the operations research and computer science fields. It aims to select the most efficient route for visiting a series of locations only once. This results in the greatest resource savings when performing tasks such as delivering goods and visiting clients.

Companies use algorithms for the travelling salesman problem to manage routes and optimise delivery services. This is due to their potential to increase profitability and sustainability by covering less distance and reducing greenhouse gas emissions.

The travelling salesman problem has garnered significant attention in theoretical computer science over the years. Although it’s easy to describe, it’s difficult to solve. The number of possible sequences that could crack it grows exponentially with the number of cities or delivery points to visit. Therefore, computer scientists employ approximation algorithms to find the shortest and least costly route. Later, we’ll discuss some of the most common methods.

Origins of the travelling salesman problem

The modern study of the travelling salesman problem dates back to the 20th century with Karl Menger. The Austrian economist introduced the problem to Hassler Whitney, who later presented it at Princeton University. There, A.W. Tucker and Merril Flood explored its applicability in the context of school bus routing in New Jersey (US).

How do you solve the travelling salesman problem?

There are two main ways to address the question posed by the travelling salesman problem. Both involve algorithms:

1. Exact algorithms. This approach seeks solutions through exhaustive methods. However, it’s often not feasible because of the extensive computation time required.
2. Heuristic algorithms. These methods can provide approximate answers in less time.

Heuristic algorithms are detailed below.

Brute-force

This method consists of calculating and comparing all possible routes to select the shortest and most convenient one. It’s only helpful in simple scenarios.

Branch and bound

This system starts with the selection of an initial route. It then systematically analyses variations. Every time a node is added to the path, the algorithm calculates the distance to be travelled and compares it with the previous option. If the total distance increases, that alternative is removed from the branching system and no longer considered a viable solution.

This way, the algorithm discards several possibilities and gets closer to the most cost-effective option for the transport company or sales team. The process continues until all routes are explored and the shortest one is designated optimal.

Nearest neighbour

This algorithm starts at a random location. From there, it finds the closest node and adds it to the sequence. This action is repeated from the next node until all cities or destinations are included in the itinerary. Finally, the algorithm returns to the starting point to complete the cycle. Although this may seem like the simplest way to solve the travelling salesman problem, it isn’t always the most suitable.

Applications of the travelling salesman problem

Although finding the most suitable travelling salesman solution can be challenging, approaches to this problem are employed across various sectors:

1. Robotics and automation. Streamlining the movements of robots and machines helps reduce battery consumption and improve efficiency. For instance, the fleet management software that controls autonomous mobile robots (AMRs) detects which robot is closest to the starting point of a task to minimise execution times and increase battery life.
2. Production planning. This technique can also be applied in manufacturing environments to optimise maintenance routes. Finding the shortest path to check all machines helps prevent disruptions to the production plan.
3. Logistics and transport. The travelling salesman problem has multiple applications in logistics:
   • Freight delivery. Transport companies leverage the travelling salesman problem to determine the shortest route for a lorry to deliver to all cities. This frees up the vehicle sooner, enabling it to handle more orders.
   • Passenger transport. Similarly, bus companies and other transport providers can find the fastest trip options, thus satisfying customer expectations.
   • Technical assistance. Service companies can create optimised routes to cover all facilities that need to be checked, improving their technicians’ efficiency.

Other factors impacting the travelling salesman problem

Finding an algorithm that solves the travelling salesman problem overall is complicated due to certain constraints. For example, the methods employed don’t account for unexpected events such as:

• Scheduled visits or last-minute appointments
• Traffic delays
• Restrictive hours at some destinations
• Route changes due to force majeure

The travelling salesman problem in warehousing

In addition to streamlining road routes, the travelling salesman problem also applies to warehouses and distribution centres. It can be leveraged to fine-tune picking operations, allowing workers to make fewer trips and thus fill more orders. Warehouse management systems (WMSs) oversee and coordinate movements and processes to maximise efficiency.

If you’re looking to streamline your intralogistics processes, at Mecalux, we’re here to help. We developed Easy WMS to enhance the throughput of both manual and automated warehouses. Hundreds of clients use it every day to boost their operations. Easy WMS’s functionalities are vital for intralogistics processes. Contact us for advice on this and other warehousing solutions.