SnailMail 2.0

Any eighth grader who has finished Introductory Geometry can tell you that the shortest distance between two points is a line, but any postal worker who has hauled a mailbag along a 10-kilometer route can tell you that figuring out the shortest distance between 400 or more addresses is nearly impossible. Software aimed at doing just that recently made its commercial debut, in Denmark, with the hope of shortening mail delivery times and slashing postal-service costs. The software, developed by Paris-based company Eurobios, takes a novel approach to what is known as the “traveling-salesman problem,” which has stymied mathematicians for decades. The central challenge: adding a single new address multiplies the number of possible paths by the total number of addresses, so calculating an ideal route quickly becomes untenably time-consuming. (At present, using a standard PC to compare every possible route spanning just 100 addresses would take years.) Computer scientists have developed various programs that solve the traveling-salesman problem for limited research purposes. But according to Dave Cliff, a complexity expert at Hewlett-Packard’s Bristol laboratories in England, the vast scale of postal systems meant that “until recently it wasn’t worth looking at computer methods, because the processing power wasn’t there.” Indeed, a single regional mail-sorting area can be responsible for some 30,000 postal addresses—a number that would have hitherto defeated calculation, explains Cliff. Eurobios’s software copes with the challenge in part by reducing the number of possible routes using heuristics, or rules of thumb, to rule out the impractical options. For example, unless a street is very long, the system makes the assumption that mail going to all addresses on one side of the street will be delivered in one trip rather than multiple trips. Then, says Eurobios’s Vince Darley, who created the program, the software employs an iterative technique to optimize the routes. It starts off with a random set of routes and then makes a series of changes to them. By evaluating the outcome after each change and keeping those changes that shorten the route, while rejecting most of those that do not, the system quickly converges on a near-optimum solution. In February, Post Danmark, the Danish postal service, began using the Eurobios software to determine the shortest routes for postal workers on the Danish island of Fyn. In trials, Eurobios’s system has shown it can reduce the time it takes postal workers to deliver the mail each day by up to 10 percent. At the same time, the software cuts the distance that the delivery people travel by as much as 20 percent. That might not sound like much, but a typical European postal organization has between 10,000 and 50,000 delivery people, says Darley, which is one of the reasons that so-called last-mile distribution accounts for as much as 70 percent of postal systems’ total expenses. Emptying each worker’s mailbag just a few minutes faster could translate into millions of euros in annual savings for even one country, Darley says.