Four Heuristic Solutions to the Traveling Salesperson Problem

Four Heuristic Solutions to the Traveling Salesperson Problem

ompanies with big fleets of vehicles track fuel prices with manic single-mindedness?and for good reason! Drivers for Federal Express, UPS, DHL, and other delivery companies drive hundreds of millions of miles per year. The United States Postal Service (USPS) alone drives around 1.1 billion miles and uses about 125 million gallons of fuel per year. If you multiply those numbers by the current cost of fuel, you can see that the stakes are enormous.

A fuel price increase of only a few cents per gallon can mean millions of dollars in added expense. Conversely, reducing fuel use by even 1 or 2 percent can save millions. Changing technologies and educating drivers to save fuel can help. For example, the USPS is replacing older vehicles to attain better mileage, moving to bigger vehicles to reduce the number of trips they must drive, and improving infrastructure to reduce the number of trips back to refueling centers.

But another way to reduce fleet costs is to optimize routes so vehicles travel as few miles as possible. That not only reduces fuel consumption, but it also reduces wear and tear on vehicles and lets drivers visit more stops in the same amount of time.

The Traveling Salesperson Problem
The goal of the Traveling Salesperson Problem (TSP) is to find the shortest possible route through a network that visits a given set of stops and then returns to its starting point. That’s exactly the problem that shipping companies such as Federal Express, UPS, and DHL face every day. A carrier must drive from a central collection point to a bunch of delivery stops and then back by the shortest route possible.

Unfortunately TSP is a very hard problem and there is no known algorithm for solving it exactly for larger problems.

Any solution to TSP provides the order in which the stops should be visited. One sure-fire approach to solving TSP is to examine every possible solution exhaustively. If there are N stops to visit, there are N! possible arrangements of the stops; therefore there are N! possible solutions. The function N! (pronounced “N Factorial”) equals N * (N-1) * (N-2) * … * 1. As you can imagine, the number of calculations grows extremely quickly as N increases, which unfortunately means that using an exhaustive approach to examine every possible solution is impractical for all but the smallest problems.

Table 1 shows the values of N! for several values of N. A TSP problem that visits only 10 stops has more than 3 million possible solutions and larger problems are completely out of reach. Even if you have a blazingly fast computer that can examine 1 billion possible solutions per second, to solve a 30-stop TSP you would need more than 8×1015 years (that’s 8 quadrillion years) to solve the problem exhaustively! While cutting back on fuel would be nice, you’re going to have to find a faster method if you want to claim the savings in the current fiscal year.

Table 1. The factorial function grows extremely quickly as N increases.

N 5 10 15 20 25 30
N! 120 3.63×106 1.30×1012 2.43×1018 1.55×1025 2.65×1032

But a 30-stop route is not uncommon in real-world situations. To make matters even worse, companies such as UPS and Federal Express must build different routes every day (in fact, several times every day) so they don’t have much time to wait for good solutions.

For TSP problems with more than a dozen or so stops, you must turn to heuristics. A heuristic is an algorithm that doesn’t guarantee the best possible solution but that should produce a usable result. While you may not be able to achieve the full 6.7 percent possible savings for a route, you may be able to find a solution that saves 6.1 percent?and do it before your retirement party.

Divide and Conquer
One approach that many fleet companies take is to divide the stops into smaller groups and then build routes for the groups separately. Street networks often subdivide into regions naturally and that makes dividing up the stops easier. For example, a river, canyon, or highway may divide a city so roads cross over it at only a few places. It would usually be inefficient to make a route that jumps back and forth across the divide, so it probably makes sense to divide the stops into two groups, one for each side of the obstacle, and then plan routes for the groups separately.

Many companies carefully plan out delivery areas and then assign all the stops in a particular area to a single driver. That not only lets them plan routes one area at a time, but it also gives drivers time to become familiar with an area so they learn the shortcuts and don’t get lost as often.

While dividing stops into delivery areas helps, it still leaves you short of a full solution. Suppose delivery people drive four-hour shifts and can deliver about four packages per hour. Because that’s 16 packages per shift, it would be nice if you could solve at least 16-stop TSP problems. Even with the super computer described earlier flashing through 1 billion solutions per second, it would take you almost 6 hours to solve this problem exhaustively.

This still isn’t good enough, particularly if deliveries are faster than four per hour. Dividing the stops helps but you need more heuristics to avoid an exhaustive search.

The Random Approach
A very straightforward approach to solving TSP is to simply pick a bunch of random orderings for the stops and then see which one is best. This may seem like a stupid approach. After all, the chances of guessing the best solution for a 30-stop TSP are almost indistinguishable from zero?almost as bad as those of winning the lottery. However, picking random solutions is very quick and easy. If you examine a few thousand random solutions, you almost certainly won’t find the best solution but you may find one that’s pretty good.

Figure 1. Random Route Strategy: Testing random routes is quick but doesn’t always lead to great solutions.

Testing random solutions is quick and easy but it’s, well, random. There’s no notion of working towards a better solution. You just make a bunch of haphazard guesses and see which one is best.

Figure 1 shows the downloadable TSP example program that accompanies this article (in both Visual Basic and C# versions) displaying a randomly generated solution to a 35-stop TSP. The program generated 10,000 random routes and picked the one shown in Figure 1 as the best. It’s not a great solution?after a few minutes with pencil and paper, you could probably improve on this route considerably.

Instead of just making a bunch of random solutions, you improve this algorithm significantly if you try to improve the random solution. Rather than testing a random guess and moving on to the next one, you try making small changes to the random guess to see if such changes improve it.

There are several ways you can try to improve a solution. One of the easiest is to randomly pick two stops, swap them, and see if that made the route better. If the route is better, you keep the change and try to make other improvements. If the swap didn’t improve the solution, you move the stops back to their original positions and try again with two other stops.

Figure 2. Improved Random Strategy: Improved random solutions often give better results than purely random solutions.

You can continue trying random improvements for either a certain number of trials or until you’ve tried some reasonable number of random swaps without generating any improvement. For example, you might try random swaps until you make 100 swaps in a row without any improvement. At that point it’s getting hard to find improvements, so you can record the best solution so far and move on.

Figure 2 shows a solution to a 35-stop TSP that uses the technique of improving random solutions. It generated a single random solution and then tried to improve it until it failed to make any improvements 10,000 times in a row.

The result shown in Figure 2 is much better than the one shown in Figure 1, although you can probably spot a few places for improvement.

The problem with this approach is that it sometimes gets stuck with a route that is not perfect but that cannot be improved by simply swapping two stops. The program might need to rearrange three, four, or even more stops to find any improvement.

One way to make this approach more robust is to repeat it many times. Pick a random solution and improve it for a while. Then start over with another random solution and improve it. Repeat the process, picking and improving a few thousand random solutions, until you decide you’ve found a good enough solution.

Another approach is to specifically try other kinds of improvement. Instead of just swapping two stops, you can try other operations for improving the initial random solution.

Making Smarter Improvements

Figure 3. Two-opt Strategy: The Two-opt heuristic looks for improvements by swapping pairs of links.

The random improvement heuristic picks two stops in the route and swaps them to see if it can make an improvement. The Two-opt heuristic randomly picks two links between stops. It removes those links and replaces them with others that keep the route connected and checks whether the change is an improvement.

Figure 3 shows an initial route and an improved version found by Two-opt. The 2-6 and 7-3 links in red on the left have been removed and replaced by the 2-3 and 6-7 links in blue on the right. Notice also that the path 6-5-4-3 on the left was reversed to 3-4-5-6 on the right to keep the route valid.

Comparing Strategies

Figure 4. Comparing Strategies: Different heuristics may produce dramatically different results.

You can make other heuristics that consider rearranging three, four, or more stops or links but the more complicated the heuristic is, the harder it is to implement and debug. Often it’s just about as effective to run more trials starting from different random solutions as it is to build a much more complex heuristic.

Figure 4 shows the TSP example program displaying results for several different heuristics on a 35-stop TSP. The Random heuristic tested 10,000 random solutions in about 0.09 seconds and found one where the total length of the links in the solution was 3,345.

The Random Improvement heuristic generated a single solution and tried to improve it by making random swaps until it found no improvements in 10,000 trials in a row. This example took 0.02 seconds and examined 13,917 possible improvements. This test examined almost 40 percent more possible solutions than the Random heuristic did but in only about a quarter as much time. It was faster because it did not need to pick a completely new solution each time it looked for improvements. Instead it just swapped two stops on the route and checked the result.

The Four-opt heuristic does almost the same thing that Random Improvement does. It picks two stops and considers swapping them. But rather than actually performing the swap and then calculating the new solution’s cost, this program determines how much it would change the route’s cost to rearrange the four links leading into and out of the two stops, then actually makes the swap only if it will be profitable. In this test, Random Improvement found a slightly better solution than Four-opt did in about the same amount of time. In general these algorithms are pretty similar, although Four-opt may save some time in large problems because it doesn’t need to recalculate the whole solution’s cost at each step.

The Two-opt heuristic tries swapping links as described earlier. In this example it found a solution that is significantly better than the ones found by the previous methods.

Finally, the Mix heuristic uses the Four-opt and Two-opt heuristics many times until neither technique can find an improvement in 100 trials. You can see that this technique performed a lot more trials (more than 2 million versus around 10,000) and took longer, although it did find a slightly better solution.

Figure 5. Brute Force: Exhaustive search finds the best possible result but can be very slow.

How good is this solution? I don’t know and I never will. It seems like a pretty good solution but the only way to be certain is to perform an exhaustive search. Until quantum computers appear, or some other science-fiction-like technology comes along, the sun would be a cold dark cinder before my computer could check all of the possible solutions.

Figure 5 shows one final example displaying the results of an exhaustive search for a 10-stop TSP. The exhaustive search took about .3 seconds to examine 3.6 million possible solutions. If you look closely, you’ll see that the more advanced heuristics produced increasingly better results. In this example, the Mix heuristic found the best possible solution, although in general any one of the heuristics might get lucky and find a perfect solution?or might be unlucky and always find bad solutions.

How long you let a heuristic run is for you to decide. You could let the heuristic run indefinitely, constantly displaying the best result it has found so far, until you decide you need to actually drive the route and get some work done. It might be nice to wait for the perfect solution, but if your boss is anything like mine, you won’t be able to wait billions of years for a solution.

Even if you don’t own a huge fleet, these savings can add up. I drive about 15,000 miles per year. If I can reduce this by 10 percent by using shorter routes, then I can save about 1,500 miles. If I get 30 miles per gallon (and most people don’t do that well), that would save about 50 gallons per year. At today’s prices that’s nothing to sneeze at.



Share the Post:
5G Innovations

GPU-Accelerated 5G in Japan

NTT DOCOMO, a global telecommunications giant, is set to break new ground in the industry as it prepares to launch a GPU-accelerated 5G network in

AI Ethics

AI Journalism: Balancing Integrity and Innovation

An op-ed, produced using Microsoft’s Bing Chat AI software, recently appeared in the St. Louis Post-Dispatch, discussing the potential concerns surrounding the employment of artificial

Savings Extravaganza

Big Deal Days Extravaganza

The highly awaited Big Deal Days event for October 2023 is nearly here, scheduled for the 10th and 11th. Similar to the previous year, this

5G Innovations

GPU-Accelerated 5G in Japan

NTT DOCOMO, a global telecommunications giant, is set to break new ground in the industry as it prepares to launch a GPU-accelerated 5G network in Japan. This innovative approach will

AI Ethics

AI Journalism: Balancing Integrity and Innovation

An op-ed, produced using Microsoft’s Bing Chat AI software, recently appeared in the St. Louis Post-Dispatch, discussing the potential concerns surrounding the employment of artificial intelligence (AI) in journalism. These

Savings Extravaganza

Big Deal Days Extravaganza

The highly awaited Big Deal Days event for October 2023 is nearly here, scheduled for the 10th and 11th. Similar to the previous year, this autumn sale has already created

Cisco Splunk Deal

Cisco Splunk Deal Sparks Tech Acquisition Frenzy

Cisco’s recent massive purchase of Splunk, an AI-powered cybersecurity firm, for $28 billion signals a potential boost in tech deals after a year of subdued mergers and acquisitions in the

Iran Drone Expansion

Iran’s Jet-Propelled Drone Reshapes Power Balance

Iran has recently unveiled a jet-propelled variant of its Shahed series drone, marking a significant advancement in the nation’s drone technology. The new drone is poised to reshape the regional

Solar Geoengineering

Did the Overshoot Commission Shoot Down Geoengineering?

The Overshoot Commission has recently released a comprehensive report that discusses the controversial topic of Solar Geoengineering, also known as Solar Radiation Modification (SRM). The Commission’s primary objective is to

Remote Learning

Revolutionizing Remote Learning for Success

School districts are preparing to reveal a substantial technological upgrade designed to significantly improve remote learning experiences for both educators and students amid the ongoing pandemic. This major investment, which

Revolutionary SABERS Transforming

SABERS Batteries Transforming Industries

Scientists John Connell and Yi Lin from NASA’s Solid-state Architecture Batteries for Enhanced Rechargeability and Safety (SABERS) project are working on experimental solid-state battery packs that could dramatically change the

Build a Website

How Much Does It Cost to Build a Website?

Are you wondering how much it costs to build a website? The approximated cost is based on several factors, including which add-ons and platforms you choose. For example, a self-hosted

Battery Investments

Battery Startups Attract Billion-Dollar Investments

In recent times, battery startups have experienced a significant boost in investments, with three businesses obtaining over $1 billion in funding within the last month. French company Verkor amassed $2.1

Copilot Revolution

Microsoft Copilot: A Suit of AI Features

Microsoft’s latest offering, Microsoft Copilot, aims to revolutionize the way we interact with technology. By integrating various AI capabilities, this all-in-one tool provides users with an improved experience that not

AI Girlfriend Craze

AI Girlfriend Craze Threatens Relationships

The surge in virtual AI girlfriends’ popularity is playing a role in the escalating issue of loneliness among young males, and this could have serious repercussions for America’s future. A

AIOps Innovations

Senser is Changing AIOps

Senser, an AIOps platform based in Tel Aviv, has introduced its groundbreaking AI-powered observability solution to support developers and operations teams in promptly pinpointing the root causes of service disruptions

Bebop Charging Stations

Check Out The New Bebob Battery Charging Stations

Bebob has introduced new 4- and 8-channel battery charging stations primarily aimed at rental companies, providing a convenient solution for clients with a large quantity of batteries. These wall-mountable and

Malyasian Networks

Malaysia’s Dual 5G Network Growth

On Wednesday, Malaysia’s Prime Minister Anwar Ibrahim announced the country’s plan to implement a dual 5G network strategy. This move is designed to achieve a more equitable incorporation of both

Advanced Drones Race

Pentagon’s Bold Race for Advanced Drones

The Pentagon has recently unveiled its ambitious strategy to acquire thousands of sophisticated drones within the next two years. This decision comes in response to Russia’s rapid utilization of airborne

Important Updates

You Need to See the New Microsoft Updates

Microsoft has recently announced a series of new features and updates across their applications, including Outlook, Microsoft Teams, and SharePoint. These new developments are centered around improving user experience, streamlining

Price Wars

Inside Hyundai and Kia’s Price Wars

South Korean automakers Hyundai and Kia are cutting the prices on a number of their electric vehicles (EVs) in response to growing price competition within the South Korean market. Many

Solar Frenzy Surprises

Solar Subsidy in Germany Causes Frenzy

In a shocking turn of events, the German national KfW bank was forced to discontinue its home solar power subsidy program for charging electric vehicles (EVs) after just one day,

Electric Spare

Electric Cars Ditch Spare Tires for Efficiency

Ira Newlander from West Los Angeles is thinking about trading in his old Ford Explorer for a contemporary hybrid or electric vehicle. However, he has observed that the majority of

Solar Geoengineering Impacts

Unraveling Solar Geoengineering’s Hidden Impacts

As we continue to face the repercussions of climate change, scientists and experts seek innovative ways to mitigate its impacts. Solar geoengineering (SG), a technique involving the distribution of aerosols

Razer Discount

Unbelievable Razer Blade 17 Discount

On September 24, 2023, it was reported that Razer, a popular brand in the premium gaming laptop industry, is offering an exceptional deal on their Razer Blade 17 model. Typically

Innovation Ignition

New Fintech Innovation Ignites Change

The fintech sector continues to attract substantial interest, as demonstrated by a dedicated fintech stage at a recent event featuring panel discussions and informal conversations with industry professionals. The gathering,

Import Easing

Easing Import Rules for Big Tech

India has chosen to ease its proposed restrictions on imports of laptops, tablets, and other IT hardware, allowing manufacturers like Apple Inc., HP Inc., and Dell Technologies Inc. more time