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.
Don’t settle for half the story.
Get paywall-free access to technology news for the here and now.