Finding the formula for the travelling salesman problem

Inside the mathematics of supply chain logistics


A wrong way road sign in Boston, Massachusetts

What do heuristics, graph theory and doughnuts have in common? Each of them, in its own way, underpins one of the most challenging parts of the logistics process: planning delivery routes.

Every day, millions of products find their way from manufacturers to distributors, retailers and finally to homes and businesses everywhere.

Making sure those products get there on time is a gargantuan task which has its roots in a mathematical conundrum from the 1800s: the travelling salesman problem.

In its simplest form, the problem takes a hypothetical salesperson tasked with visiting a certain number of places in one day. How can the salesperson visit all of the places via the shortest route?

This problem is a product of graph theory – the study of nodes and lines – and it is the perfect kind of mathematics for logistics networks. After all, these are effectively collections of the same thing.

“If you think of what the supply chain looks like, you draw circles on paper and label them,” says Jeff Karrenbauer, president and founding director of Insight, which specialises in planning solutions for logistics and supply-chain operations.

“You draw lines between them that represent transportation links.”

The travelling salesman problem may be a fun puzzle to solve at home with about six nodes. But for logistics firms dealing with thousands of circles and lines, it is far more challenging.

The problem lies in the fact that as you add places to visit, the number of possible combinations increases exponentially. And the reason for that lies with the logistics route planner’s nemesis: the factorial.

Dizzying numbers

The factorial of a number, n, is the product of all the positive integers equal to or less than itself, and is denoted as n! . The factorial of 4 (4!), for example, is 4 x 3 x 2 x 1 (24).

That is how many combinations you would have for a travelling salesman with four places to visit. 5! Is 120. 6! Is 720.

Now, think about a single driver making 25 stops in a day. That provides 1.551121 x 1025 different combinations (25!).

Given that there are about 1025 stars in the visible universe, the average delivery driver would earn a lot of overtime doing that on paper – and would probably have to skip breakfast.

“It's a very special situation, because once you have decided that every node will be visited once, every node has exactly one predecessor and every node has one successor. It's what is called a combinatorial optimisation problem,” says Jim Bookbinder, director of the Management of Integrated Manufacturing Systems research group at Canada’s University of Waterloo.

In real life, the whole thing becomes intractable long before you reach 25 stops, explains Danny Bausch, director of analytics and product management at Insight.

“That problem doesn't yield well to optimisation. Once you get above about nine stopping locations, the number of combinations explodes exponentially and optimisation routines melt down,” he says.

To ease the load, logistics experts must try to bring in another kind of mathematics: heuristics. This is a way of finding approximate solutions to mathematical problems when there are simply too many potential inputs to handle.

“At some point the brain says there are too many things going on"

We have found them in popular computing applications before, such as anti-virus software, for example, where many files must be checked quickly, often in real time, to look for malicious bugs.

“At some point the brain says there are too many things going on so I will follow some rules of thumb,” says Bausch.

For example, 25 different stops may be too difficult to analyse using the computing technology available. But you may be able simply to look at the map where the drops are to be made and divide them into more easily manageable chunks, for example north, south, east and west quadrants. Each of those could then be subject to its own travelling salesman analysis.

After all, it is unlikely that a driver would ever want to go directly from the southernmost point in a daily route to the northernmost point, so that is one of many combinations it wouldn’t make sense to compute.

“That's a manual heuristic. Those rules can be put together like that,” says Bausch. “They are a series of steps that the computer understands well.”

There are a handful of commonly used heuristics when it comes to mathematical problems of this sort. One of them is the sweep algorithm, which uses a line that sweeps across the map to find potential intersections between the different points and come up with an optimal order for deliveries.

Another is the exchange heuristic. “If an order turns out not to be a good sequence, then you operate on it with exchanges, saying ‘trade stop one for stop two, and switch nine for six’,” says Bausch. “You can do that for a long time, too.”

Yet another, far more complex algorithm deals with quadratic assignments. It considers the sweep and exchanges together and the expected value.


Other stories you might like

  • Will Lenovo ever think beyond hardware?
    Then again, why develop your own software à la HPE GreenLake when you can use someone else's?

    Analysis Lenovo fancies its TruScale anything-as-a-service (XaaS) platform as a more flexible competitor to HPE GreenLake or Dell Apex. Unlike its rivals, Lenovo doesn't believe it needs to mimic all aspects of the cloud to be successful.

    While subscription services are nothing new for Lenovo, the company only recently consolidated its offerings into a unified XaaS service called TruScale.

    On the surface TruScale ticks most of the XaaS boxes — cloud-like consumption model, subscription pricing — and it works just like you'd expect. Sign up for a certain amount of compute capacity and a short time later a rack full of pre-plumbed compute, storage, and network boxes are delivered to your place of choosing, whether that's a private datacenter, colo, or edge location.

    Continue reading
  • Intel is running rings around AMD and Arm at the edge
    What will it take to loosen the x86 giant's edge stranglehold?

    Analysis Supermicro launched a wave of edge appliances using Intel's newly refreshed Xeon-D processors last week. The launch itself was nothing to write home about, but a thought occurred: with all the hype surrounding the outer reaches of computing that we call the edge, you'd think there would be more competition from chipmakers in this arena.

    So where are all the AMD and Arm-based edge appliances?

    A glance through the catalogs of the major OEMs – Dell, HPE, Lenovo, Inspur, Supermicro – returned plenty of results for AMD servers, but few, if any, validated for edge deployments. In fact, Supermicro was the only one of the five vendors that even offered an AMD-based edge appliance – which used an ageing Epyc processor. Hardly a great showing from AMD. Meanwhile, just one appliance from Inspur used an Arm-based chip from Nvidia.

    Continue reading
  • NASA's Psyche mission: 2022 launch is off after software arrives late
    Launch window slides into 2023 or 2024 for asteroid-probing project

    Sadly for NASA's mission to take samples from the asteroid Psyche, software problems mean the spacecraft is going to miss its 2022 launch window.

    The US space agency made the announcement on Friday: "Due to the late delivery of the spacecraft's flight software and testing equipment, NASA does not have sufficient time to complete the testing needed ahead of its remaining launch period this year, which ends on October 11."

    While it appears the software and testbeds are now working, there just isn't enough time to get everything done before a SpaceX Falcon Heavy sends the spacecraft to study a metallic-rich asteroid of the same name.

    Continue reading

Biting the hand that feeds IT © 1998–2022