Finding the formula for the travelling salesman problem

Back in the real world

One difficulty with the travelling salesman problem is that it plays out on paper in a spatial system unsullied by worldly constraints.

Back in the unforgiving world of logistics, things are far more complex, according to Bookbinder.

“There are so many other issues that the optimisation on the routing part isn't the be all and end all,” he says.

Capacity is one such constraint. A van may be able to take only so much product, based on its size. A manufacturing or distribution plant may have only so much stock.

Road quality is another. Which are the good, fast roads to use and how well do they connect the stops on the route?

“I may start out with a full truck making deliveries to customers but I may end up back in the factory,” says Bookbinder.

“If there are suppliers of raw materials nearby, where I can deviate a little from the delivered route, then I can mix pickup and deliveries. Then I can really have an efficient route. That has become a standard variation on the vehicle routing problem.”

Your goals may also be different. Delivery in as short a time as possible may be the primary objective in some cases. In others, the lowest cost may top the list.

Some organisations may have a need to factor carbon emissions into their supply-chain management operation to meet a corporate sustainability requirement.

“These things are expressed as thousands or millions of additional equations. All of them describe a network which is a series of locations and the transportation links between them, such as ports, suppliers, cross docks and customers,” says Bookbinder.

Thinking inside the box

Those calculations address the big picture, ranging from 30-mile delivery routes to global logistics systems, but sometimes the mathematical problems simply explore the inside of a 40ft van.

Even the mathematics of loading and unloading a truck creates software challenges, says Jim Lodwick, transport and logistics consultant at Rocket Consulting, which makes warehouse management and supply-chain visibility software for clients.

“Mathematics will be used to sequence things such as the right way to load the vehicles so that the product comes off in the right order,” he says.

Other things to consider include product sizes, the weight and dimensions of the vehicle and how much weight you can put over its various axles.

Road sense

This kind of complexity is why UPS devoted so much attention to its On-Road Integrated Optimization and Navigation (Orion) system, designed to optimise deliveries across its vast global network of drop points.

The system began its first rollouts last year and will be deployed to all 55,000 north American routes by 2017, the firm says. Currently it is in operation only in the US.

Remember that a 25-stop route has the same number of combinations as there are stars in the visible universe, give or take a few trillion?

The average UPS truck makes between 125 and 175 stops a day, creating more possible combinations than there are nanoseconds in the earth’s history, the firm says.

The system not only uses advanced heuristics to carve up delivery routes while taking into account many of the constraints mentioned, but it also optimises the placement of packages inside the vehicle.

This enables drivers to avoid moving more than 30 inches to select the next package in the truck. Every second shaved off a driver’s time could represent hundreds of thousands of dollars when replicated across the entire UPS network.

So, where do the doughnuts come in?

Mathematics doesn’t solve everything. Bausch recalls one delivery problem in which a contact at a particular location insisted on taking deliveries outside lunch hours.

Unfortunately, this threw a mathematical spanner in the works for the planning software, which needed to schedule a delivery at noon to make everything workable. The alternative would be to send a dedicated truck to that address just for a single delivery.

Instead, Bausch says, the delivery dispatcher called the person in question, who it turned out just really wanted to take lunch during those hours.

“What about if we bring you a sandwich?” the dispatcher asked.

“Make it doughnuts and you have a deal.”

Problem solved, and not an equation in sight. Sometimes, even mathematics needs a little sugar coating. ®