Theoretical research and practical applications in the ?eld of vehicle
routing started in 1959 with the truck dispatching problem posed by
Dantzig and Ramser [1]: ?nd the ". . . optimum routing of a ?eet of
gasoline delivery trucks between a bulk terminal and a large number of
service stations supplied by the terminal. " Using a method based on a
linear programming formulation, their hand calculations produced a
near-optimal solution with four routes to aproblemwithtwelve service
stations. The authorsproclaimed: "Nopractical applications of the method
have been made as yet. " In the nearly 50 years since the Dantzig and
Ramser paper appeared, work in the ?eld has exploded dramatically.
Today, a Google Scholar search of the words vehicle routing problem
(VRP) yields more than 21,700 entries. The June 2006 issue of OR/MS
Today provided a survey of 17 vendors of commercial routing software
whose packages are currently capable of solving average-size problems
with 1,000 stops, 50 routes, and two-hour hard-time windows in two to
ten minutes [2]. In practice, vehicle routing may be the single
biggest success story in operations research. For example, each day
103,500 drivers at UPS follow computer-generated routes. The drivers
visit 7. 9 million customers and handle an average of 15. 6 million
packages [3].