基本説明
Vehicle routing problems (VRP), including the traveling salesman problem, have marked the success of operations research.
Full Description
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
Overviews and Surveys.- Routing a Heterogeneous Fleet of Vehicles.- A Decade of Capacitated Arc Routing.- Inventory Routing.- The Period Vehicle Routing Problem and its Extensions.- The Split Delivery Vehicle Routing Problem: A Survey.- Challenges and Advances in A Priori Routing.- Metaheuristics for the Vehicle Routing Problem and Its Extensions: A Categorized Bibliography.- Parallel Solution Methods for Vehicle Routing Problems.- Recent Developments in Dynamic Vehicle Routing Systems.- New Directions in Modeling and Algorithms.- Online Vehicle Routing Problems: A Survey.- Modeling and Solving the Capacitated Vehicle Routing Problem on Trees.- Using a Genetic Algorithm to Solve the Generalized Orienteering Problem.- An Integer Linear Programming Local Search for Capacitated Vehicle Routing Problems.- Robust Branch-Cut-and-Price Algorithms for Vehicle Routing Problems.- Recent Models and Algorithms for One-to-One Pickup and Delivery Problems.- One-to-Many-to-One Single Vehicle Pickup and Delivery Problems.- Challenges and Opportunities in Attended Home Delivery.- Chvátal-Gomory Rank-1 Cuts Used in a Dantzig-Wolfe Decomposition of the Vehicle Routing Problem with Time Windows.- Vehicle Routing Problems with Inter-Tour Resource Constraints.- From Single-Objective to Multi-Objective Vehicle Routing Problems: Motivations, Case Studies, and Methods.- Practical Applications.- Vehicle Routing for Small Package Delivery and Pickup Services.- Advances in Meter Reading: Heuristic Solution of the Close Enough Traveling Salesman Problem over a Street Network.- Multiperiod Planning and Routing on a Rolling Horizon for Field Force Optimization Logistics.- Health Care Logistics, Emergency Preparedness, and Disaster Relief: New Challenges for Routing Problems with a Focus on theAustrian Situation.- Vehicle Routing Problems and Container Terminal Operations - An Update of Research.
