UPS’s No-Left-Turn Policy: Where Game Theory and Graph Theory Meet
https://theconversation.com/why-ups-drivers-dont-turn-left-and-you-probably-shouldnt-either-71432
The absence of a door on the driver’s side is not a unique feature on UPS’s trucks. Something that is unique, however, is the company’s no-left-turns policy. This policy says that drivers should never turn through oncoming traffic–in the US that would be left. This The Conversation article discusses the logic behind this policy which, as with most things, ties back to mathematics.
Jump to 1959, when mathematicians George Dantzig and John Ramser published a paper that included the traveling salesman problem which is generalized by the vehicle routing problem (VRP). In the VRP, there are a set of nodes with edges that represent distances and you are to find the best route to travel through all of the nodes. One would think that the shortest distance would be the best solution, however, this does not apply to all applications of the VRP. Through the no-left-turn policy, UPS solves the vehicle routing problem. This policy has reduced fuel expenditures and carbon dioxide emissions while delivering more packages than it would if left turns were allowed. If examining only one truck, that truck does travel further, but when you scale it globally UPS travels fewer miles in total.
A figure illustrating the vehicle routing problem. Curtsy of user PierreSelim.
It would seem logical for every driver to adopt this no-left-turn policy, so why haven’t we? The reasoning behind this can be found in the prisoner’s dilemma. The article calls it the Driver’s dilemma. In the prisoner’s dilemma, the best choice for both players is to cooperate since they will both benefit as a unit. However, they do not pick what is seemingly the best choice as self-interests usually presides. If everyone cooperated, we could achieve what UPS has. But if only a few people decide to not cooperate, the system fails.
This concept brings in two topics we covered thus far in lecture: graph theory and game theory. UPS’s routing software must take the VRP, map it, and search for the optimal path. We covered breadth-first search which is used to find the shortest path in an unweighted graph. This graph is weighted as the edges have values so Dijkstra’s shortest path algorithm would not be optimal in this situation. Game theory is seen in the theoretical implementation of a no-left-turn policy for all drivers: there is no incentive to change their driving style as they do not benefit as an individual.