The Vehicle Routing Problem: Latest Advances and New ChallengesBruce L. Golden, S. Raghavan, Edward A. Wasil 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]. |
Contents
| 3 | |
A Decade of Capacitated Arc Routing | 29 |
Inventory Routing | 49 |
The Period Vehicle Routing Problemand its Extensions | 73 |
A Survey | 103 |
Challenges and Advances in A Priori Routing | 123 |
A Categorized Bibliography | 143 |
Parallel Solution Methods for Vehicle Routing Problems | 170 |
Robust BranchCutandPrice Algorithms for Vehicle Routing Problems | 296 |
Recent Models and Algorithms for OnetoOne Pickup and Delivery Problems | 327 |
OnetoManytoOne Single Vehicle Pickup and Delivery Problems | 358 |
Challenges and Opportunities in Attended Home Delivery | 379 |
ChvátalGomory Rank1 Cuts Used in a DantzigWolfe Decomposition of the Vehicle Routing Problem with Time Windows | 397 |
Vehicle Routing Problems with InterTour Resource Constraints | 420 |
Motivations Case Studies and Methods | 445 |
Part III Practical Applications | 472 |
Recent Developments in Dynamic Vehicle Routing Systems | 199 |
Part II New Directions in Modeling and Algorithms | 219 |
A Survey | 221 |
Modeling and Solving the Capacitated Vehicle Routing Problem on Trees | 238 |
Using a Genetic Algorithm to Solve the Generalized Orienteering Problem | 263 |
An Integer Linear Programming Local Search for Capacitated Vehicle Routing Problems | 275 |
Vehicle Routing for Small Package Delivery and Pickup Services | 473 |
Heuristic Solution of the Close Enough Traveling Salesman Problem over a Street Network | 487 |
Multiperiod Planning and Routing on a Rolling Horizon for Field Force Optimization Logistics | 502 |
New Challenges for Routing Problems with a Focus on the Austrian Situation | 527 |
Vehicle Routing Problems and Container Terminal Operations An Update of Research | 551 |
Other editions - View all
The Vehicle Routing Problem: Latest Advances and New Challenges Bruce L. Golden,S. Raghavan,Edward A. Wasil No preview available - 2008 |
The Vehicle Routing Problem: Latest Advances and New Challenges Bruce L. Golden,S. Raghavan,Edward A. Wasil No preview available - 2010 |
Common terms and phrases
applications approach arc routing problem branch-and-cut capacitated CARP Christofides column Combinatorial Optimization competitive ratio Computers & Operations considered constraints container terminals Cordeau cost CVRP defined delivery problem demand denoted depot distance dynamic European Journal feasible fleet formulation Gendreau genetic algorithm graph horizon improve instances integer inventory holding inventory routing problems iterations Journal of Operational Laporte local search logistics lower bound LP relaxation Mathematics metaheuristic minimize multi-objective neighborhood node number of vehicles objective function online algorithm optimal solution parallel path performed pickup and delivery planning procedure programming proposed PTSP PVRP quay cranes requests resource Savelsbergh scheduling SDVRP Section segment sequence shortest path problem simulated annealing slot solve Speranza Springer Science+Business Media stochastic strategy SVPDP tabu search heuristic tion tour Transportation Science traveling salesman problem valid inequalities variables variants vehicle capacity vehicle routing problem vertex visited VRPTW
Popular passages
Page v - The paper is concerned with the optimum routing of a fleet of gasoline delivery trucks between a bulk terminal and a large number of service stations supplied by the terminal. The shortest routes between any two points in the system are given and a demand for one or several products is specified for a number of stations within the distribution system. It is desired to find a way to assign stations to trucks in such a manner that station demands are satisfied and total mileage...
Page 6 - VRP use binary variables as vehicle flow variables to indicate if a vehicle travels between two customers in the optimal solution.
Page iv - University of Maryland University of Maryland College Park, MD, USA College Park, MD, USA...
Page 3 - Problem (VRP) is one of the most studied combinatorial optimization problems and is concerned with the optimal design of routes to be used by a fleet of vehicles to serve a set of customers.
Page 3 - Heterogeneous vehicle routing problem. 1 Introduction The Vehicle Routing Problem (VRP) is one of the most...