No left turn please; we’ll save fuel

And, pertinently, the curious behaviour that a particular species of ant, Temnothorax albipennis, exhibits while exploring “unknown nest sites”. They turn left. 

More correctly, when they are scurrying through those unknown sites and are faced with a choice of which way to turn, they choose left over right most of the time. Here’s one reason for this behaviour, according to ant researchers. If all ants out on a scouting expedition are inclined to choose left in an unknown, possibly hostile space, the ones who enter later “would be more likely to encounter their nest-mates.” Friends, that is, rather than foes.

There was lots to savour in the scientific paper where I first read about these Temnothorax creatures. And I was positively charmed when I found that there are other creatures that do something similar. Well, sort of similar. Well, sort of creatures.

I refer to certain humans. Certain humans are in uniform, driving a certain kind of vehicle. I refer to UPS drivers. I refer to them because UPS has a policy that they should avoid turning left as far as possible. More correctly, they should avoid turning left across oncoming traffic. (Of course, this applies in countries where they drive on the right; in the sensible countries where people drive on the left, the policy advises that UPS drivers should avoid turning right.)

Why would a package delivery service institute such a policy? Won’t it result in longer routes to be driven and more fuel consumed? Well, on the face of it, yes. But the shortest route may not necessarily use less fuel than longer ones. That’s because turning left can mean waiting for a break in the flow of oncoming traffic, which wastes fuel. It also increases the chances of an accident.

What happened here is a real-life example of a generalization of a classic problem that every computer science student learns about: the travelling salesman problem (TSP). It goes something like this: Given a list of cities a salesman must visit, and given the distance between each pair of cities, what is the shortest route the salesman can take so that he visits each city no more than once and returns to where he started?

Solving this is, in CS terms, “NP-hard”. That means what you might guess: that it is essentially impossible. Sure, you would probably be able to do it for three or four cities. But increase that number, and the time a computer takes to find a solution increases accordingly, exponentially. Yet since the TSP has been so intensively studied for so long, there are various known algorithms to tackle it that can produce pretty good approximate solutions, even with millions of cities.

No doubt you’re wondering why solving the TSP matters, besides wondering which salesman would visit millions of cities anyway. But like with so many other themes in mathematics and CS, this one is really an analogy for other optimization problems. Define what a “city” stands for and what “distance” means, and you can apply the same techniques not just to travel but to DNA sequencing, or the layout of electronic chips, or much more.

Generalize the TSP to multiple salesmen, and you have the Vehicle Routing Problem (VRP). Just as you’d expect, solving the VRP is NP-hard as well. But again, there are mathematical techniques that produce acceptable results. And what UPS is faced with every day is a VRP. They have a fleet of vehicles and their drivers and a number of depots from which a whole lot of packages must be delivered to expectant customers. How can UPS route all its vehicles so as to deliver all the packages while minimizing the total cost?

Of course, that “cost” can mean fuel used, or the time spent, or the distance travelled, or the number of drivers needed, or maybe even wear and tear on the delivery trucks. All of those are the costs of using the fleet to make deliveries. Which one should UPS minimize? That depends—which one matters most to UPS?

Their no-left-turn policy suggests that fuel costs matter most. Now that is possibly counter-intuitive. That’s because making a left turn, when it’s required for delivery but not allowed by company policy, may mean making three right turns in a row in a detour to the right. The distance travelled in that manoeuvre adds up and will no doubt exceed what a simple left turn amounts to. Over several turns, over the whole UPS fleet, over even a single day of package deliveries, that can add up to tens of thousands of excess km.

Yet UPS claims that in the US, not making those turns across oncoming traffic—meaning not having to wait for a gap in the traffic—saves about 35 million litres of fuel a year. This is while managing to deliver 350,000 more packages annually.

What’s more, this increased efficiency in delivering packages means UPS was able to pare 1,100 trucks from its fleet. So even though each necessary but unmade left turn makes each delivery route longer, the UPS fleet in the US, as a whole, actually drives nearly 50 million fewer km per year.

Think of what’s actually a triple whammy: less fuel, fewer trucks, fewer kilometres travelled. All by following a simple no-left-turn policy.

There’s a lot more to explore in this story, including the question of whether more vehicles should start avoiding turns across traffic. All Uber drivers? All non-commercial vehicles? All of us? What would happen then?

I’ll leave that for you to ponder. Me, I’ll bask in the rather delightful thought that this might just be the first time in human history that the same column takes in UPS vans, left turns and ants.

Once a computer scientist, Dilip D’Souza now lives in Mumbai and writes for his dinners. His Twitter handle is @DeathEndsFun.