It might seem strange, but UPS delivery vans don’t always take the shortest route between stops. The company gives each driver a specific route to follow and that includes a policy that drivers should never turn through oncoming traffic (that’s left in countries where they drive on the right and vice versa) unless absolutely necessary. This means that routes are sometimes longer than they have to be. So, why do they do it?
Every day, along with thousands of other companies, UPS solves versions of the vehicle routing problem. In these mathematical problems, you are given a set of points and the distances between them, and you have to find the best route(s) to travel through all of them. Best is usually defined as the route with the shortest overall distance.
Vehicle routing problems are used to organise many things, from coping with more delivery trucks in cities and hailing taxis to catching chickens on a farm. The concept was introduced by George Dantzig in 1959. Over 50 years later, and despite a large body of scientific research, scientists are still looking for new ways to tackle the problem.