Traveling salesman problem applied to logistics

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

What is the traveling salesman problem?

The traveling 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 traveling salesman problem to manage routes and optimize delivery services. This is due to their potential to increase profitability and sustainability by covering less distance and reducing greenhouse gas emissions.

The traveling 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 traveling salesman problem

The modern study of the traveling 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 NJ.

How do you solve the traveling salesman problem?

There are two main ways to address the question posed by the traveling 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 analyzes variations. Every time a node is added to the path, the algorithm calculates the distance to be traveled 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 transportation company or sales team. The process continues until all routes are explored, and the shortest one is designated optimal.

Nearest neighbor

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 traveling salesman problem, it isn’t always the most suitable.

Applications of the traveling salesman problem

Although finding the most suitable traveling 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 minimize execution times and increase battery life.
2. Production planning. This technique can also be applied in manufacturing environments to optimize maintenance routes. Finding the shortest path to check all machines helps prevent disruptions to the production plan.
3. Logistics and transportation. The traveling salesman problem has multiple applications in logistics:
   • Freight delivery. Transportation companies leverage the traveling salesman problem to determine the shortest route for a truck to deliver to all cities. This frees up the vehicle sooner, enabling it to handle more orders.
   • Passenger transportation. Similarly, bus companies and other transportation providers can find the fastest trip options, thus satisfying customer expectations.
   • Technical assistance. Service companies can create optimized routes to cover all facilities that need to be checked, improving their technicians’ efficiency.

Other factors impacting the traveling salesman problem

Finding an algorithm that solves the traveling 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 traveling salesman problem in warehousing

In addition to streamlining road routes, the traveling salesman problem also applies to warehouses and distribution centers. 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 maximize efficiency.

If you’re looking to streamline your intralogistics processes, at Interlake Mecalux, we’re here to help. Our company 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.