Muutke küpsiste eelistusi

Vehicle Routing Problem [Kõva köide]

4.00/5 (6 hinnangut Goodreads-ist)
Edited by , Edited by
Teised raamatud teemal:
Vehicle Routing ProblemSuurem pilt
Teised raamatud teemal:
Püsilink: https://www.kriso.ee/db/9780898714982.html
Märksõnad:
Contributors from business, science, and engineering present both exact and heuristic methods that have been developed over the past decades to determine the optimal set of routes to be performed by a fleet of vehicles to serve a given set of customers. Assuming readers to have a basic knowledge of the main methods for solving combinatorial optimization problems, they offer a broad overview of the effective use of the most important techniques proposed for solving hard combinatorial problems, of which vehicle routing is one example. After an overview, they cover the capacitated vehicle routing problem, variants on it, and applications and case studies. Annotation c. Book News, Inc., Portland, OR (booknews.com)
List of Contributors
v
Preface xvii
An Overview of Vehicle Routing Problems
1(26)
P. Toth
D. Vigo
Introduction
1(4)
Problem Definition and Basic Notation
5(6)
Capacitated and Distance-Constrained VRP
5(3)
VRP with Time Windows
8(1)
VRP with Backhauls
9(1)
VRP with Pickup and Delivery
10(1)
Basic Models for the VRP
11(11)
Vehicle Flow Models
11(6)
Extensions of Vehicle Flow Models
17(2)
Commodity Flow Models
19(2)
Set-Partitioning Models
21(1)
Test Instances for the CVRP and Other VRPs
22(5)
Bibliography
23(4)
I Capacitated Vehicle Routing Problem 27(128)
Branch-and-Bound Algorithms for the Capacitated VRP
29(24)
P. Toth
D. Vigo
Introduction
29(1)
Basic Relaxations
30(5)
Bounds Based on Assignment and Matching
30(2)
Bounds Based on Arborescences and Trees
32(1)
Comparison of the Basic Relaxations
33(2)
Better Relaxations
35(9)
Additive Bounds for ACVRP
35(4)
Further Lower Bounds for ACVRP
39(1)
Lagrangian Lower Bounds for SCVRP
40(1)
Lower Bounds from a Set-Partitioning Formulation
41(1)
Comparison of the Improved Lower Bounds
42(2)
Structure of the Branch-and-Bound Algorithms for CVRP
44(4)
Branching Schemes and Search Strategies
44(2)
Reduction, Dominance Rules, and Other Features
46(1)
Performance of the Branch-and-Bound Algorithms
47(1)
Distance-Constrained VRP
48(5)
Bibliography
49(4)
Branch-and-Cut Algorithms for the Capacitated VRP
53(32)
D. Naddef
G. Rinaldi
Introduction and Two-Index Flow Model
53(2)
Branch-and-Cut
55(3)
Polyhedral Studies
58(13)
Capacity Constraints
59(2)
Generalized Capacity Constraints
61(1)
Framed Capacity Constraints
62(1)
Valid Inequalities from STSP
62(5)
Valid Inequalities Combining Bin Packing and STSP
67(2)
Valid Inequalities from the Stable Set Problem
69(2)
Separation Procedures
71(4)
Exact Separation of Capacity Constraints
71(1)
Heuristics for Capacity and Related Constraints
72(3)
STSP Constraints
75(1)
Branching Strategies
75(3)
Computational Results
78(3)
Conclusions
81(4)
Bibliography
81(4)
Set-Covering-Based Algorithms for the Capacitated VRP
85(24)
J. Bramel
D. Simchi-Levi
Introduction
85(2)
Solving the Linear Programming Relaxation of P
87(2)
Set-Covering-Based Solution Methods
89(7)
Branch-and-Bound Algorithm for Problem CG
89(2)
Polyhedral Branch-and-Bound Algorithm
91(1)
Pseudo-Polynomial Lower Bound on cmin
92(2)
Solving PD via Dual-Ascent and Branch-and-Bound
94(2)
Solving the Set-Covering Integer Program
96(4)
A Cutting Plane Method
97(2)
Branch-and-Price
99(1)
Additional Comments on Computational Approaches
100(1)
Computational Results
100(2)
Effectiveness of the Set-Covering Formulation
102(7)
Worst-Case Analysis
103(1)
Average-Case Analysis
103(3)
Bibliography
106(3)
Classical Heuristics for the Capacitated VRP
109(20)
G. Laporte
F. Semet
Introduction
109(1)
Constructive Methods
110(6)
Clarke and Wright Savings Algorithm
110(1)
Enhancements of the Clarke and Wright Algorithm
111(2)
Matching-Based Savings Algorithms
113(1)
Sequential Insertion Heuristics
114(2)
Two-Phase Methods
116(5)
Elementary Clustering Methods
116(2)
Truncated Branch-and-Bound
118(2)
Petal Algorithms
120(1)
Route-First, Cluster-Second Methods
120(1)
Improvement Heuristics
121(4)
Single-Route Improvements
121(1)
Multiroute Improvements
122(3)
Conclusions
125(4)
Bibliography
126(3)
Metaheuristics for the Capacitated VRP
129(26)
M. Gendreau
G. Laporte
J.-Y. Potvin
Introduction
129(1)
Simulated Annealing
130(3)
Two Early Simulated Annealing Algorithms
130(1)
Osman's Simulated Annealing Algorithms
131(2)
Van Breedam's Experiments
133(1)
Deterministic Annealing
133(1)
Tabu Search
134(6)
Two Early Tabu Search Algorithms
134(1)
Osman's Tabu Search Algorithm
134(1)
Taburoute
135(2)
Taillard's Algorithm
137(1)
Xu and Kelly's Algorithm
137(1)
Rego and Roucairol's Algorithms
137(1)
Barbarosoglu and Ozgur's Algorithm
138(1)
Adaptive Memory Procedure of Rochat and Taillard
138(1)
Granular Tabu Search of Toth and Vigo
138(2)
Computational Comparison
140(1)
Genetic Algorithms
140(4)
Simple Genetic Algorithm
140(1)
Application to Sequencing Problems
141(1)
Application to the VRP
142(2)
Ant Algorithms
144(2)
Neural Networks
146(2)
Conclusions
148(7)
Bibliography
149(6)
II Important Variants of the Vehicle Routing Problem 155(88)
VRP with Time Windows
157(38)
J.-F. Cordeau
G. Desaulniers
J. Desrosiers
M. M. Solomon
F. Soumis
Introduction
157(1)
Problem Formulation
158(2)
Formulation
158(1)
Network Lower Bound
159(1)
Linear Programming Lower Bound
159(1)
Algorithms
160(1)
Upper Bounds: Heuristic Approaches
160(6)
Route Construction
160(1)
Route Improvement
161(1)
Composite Heuristics
161(1)
Metaheuristics
162(3)
Parallel Implementations
165(1)
Optimization-Based Heuristics
165(1)
Asymptotically Optimal Heuristics
165(1)
Lower Bounds from Decomposition Approaches
166(7)
Lagrangian Relaxation
166(1)
Capacity and Time-Constrained Shortest-Path Problem
167(1)
Variable Splitting
168(1)
Column Generation
169(1)
Set-Partitioning Formulation
169(1)
Lower Bound
170(1)
Commodity Aggregation
171(1)
Hybrid Approach
172(1)
Integer Solutions
173(4)
Binary Decisions on Arc Flow Variables
173(1)
Integer Decisions on Arc Flow Variables
173(1)
Binary Decisions on Path Flow Variables
174(1)
Subtour Elimination and 2-Path Cuts
175(1)
κ-Path Cuts and Parallelism
176(1)
Integer Decisions on (Fractional and Integer) Time Variables
176(1)
Special Cases
177(1)
Multiple TSP with Time Windows
177(1)
VRP with Backhauls and Time Windows
177(1)
Extensions
178(3)
Heterogeneous Fleet, Multiple-Depot, and Initial Conditions
178(1)
Fleet Size
179(1)
Multiple Time Windows
179(1)
Soft Time Windows
179(1)
Time- and Load-Dependent Costs
180(1)
Driver Considerations
180(1)
Computational Results for VRPTW
181(3)
Conclusions
184(11)
Bibliography
186(9)
VRP with Backhauls
195(30)
P. Toth
D. Vigo
Introduction
195(3)
Benchmark Instances
197(1)
Integer Linear Programming Models
198(3)
Formulation of Toth and Vigo
198(2)
Formulation of Mingozzi, Giorgi, and Baldacci
200(1)
Relaxations
201(7)
Relaxation Obtained by Dropping the CCCs
202(1)
Relaxation Based on Projection
202(1)
Lagrangian Relaxation
203(1)
Overall Additive Lower Bound
204(1)
Relaxation Based on the Set-Partitioning Model
204(4)
Exact Algorithms
208(6)
Algorithm of Toth and Vigo
208(1)
Algorithm of Mingozzi, Giorgi, and Baldacci
209(1)
Computational Results for the Exact Algorithms
210(4)
Heuristic Algorithms
214(11)
Algorithm of Deif and Bodin
214(1)
Algorithms of Goetschalckx and Jacobs-Blecha
215(1)
Algorithm of Toth and Vigo
216(1)
Computational Results for the Heuristics
217(4)
Bibliography
221(4)
VRP with Pickup and Delivery
225(18)
G. Desaulniers
J. Desrosiers
A. Erdmann
M. M. Solomon
F. Soumis
Introduction
225(1)
Mathematical Formulation
226(3)
Construction of the Networks
226(1)
Formulation
227(1)
Service Quality
228(1)
Reduction of the Network Size
228(1)
Heuristics
229(3)
Construction and Improvement
229(1)
Clustering Algorithms
230(1)
Metaheuristics
230(1)
Neural Network Heuristics
231(1)
Theoretical Analysis of Algorithms
231(1)
Optimization-Based Approaches
232(4)
Single Vehicle Cases
232(2)
Multiple Vehicle Cases
234(2)
Applications
236(1)
Computational Results
236(1)
Conclusions
237(6)
Bibliography
238(5)
III Applications and Case Studies 243(120)
Routing Vehicles in the Real World: Applications in the Solid Waste, Beverage, Food, Dairy, and Newspaper Industries
245(42)
B. L. Golden
A. A. Assad
E. A. Wasil
Introduction
245(2)
Computerized Vehicle Routing in the Solid Waste Industry
247(7)
History
247(1)
Background
247(2)
Commercial Collection
249(1)
Residential Collection
250(1)
Case Studies
250(2)
Roll-on-Roll-off
252(2)
Further Remarks
254(1)
Vehicle Routing in the Beverage, Food, and Dairy Industries
254(12)
Introduction
254(1)
Beverage Industry
255(4)
Food Industry
259(1)
Dairy Industry
260(6)
Distribution and Routing in the Newspaper Industry
266(14)
Industry Background
266(2)
Newspaper Distribution Problem
268(3)
Vehicle Routing Algorithms for NDP
271(5)
Three Case Studies
276(4)
Further Remarks
280(1)
Conclusions
280(7)
Bibliography
281(6)
Capacitated Arc Routing Problem with Vehicle-Site Dependencies: The Philadelphia Experience
287(22)
J. Sniezek
L. Bodin
L. Levy
M. Ball
Introduction
287(1)
Networks, Assumptions, and Goals of the CARP-VSD
288(5)
Travel Network
288(1)
Service Network
289(1)
Vehicle Classes
290(1)
Travel Network and Service Network for a Vehicle Class
291(1)
Vehicle Preference List
291(1)
Other Assumptions
292(1)
Goals and Constraints of the CARP-VSD
292(1)
Vehicle Decomposition Algorithm (VDA)
293(12)
Step A. Create and Verify Vehicle Class Networks
293(1)
Step B. Estimate Total Work and Determine Initial Fleet Mix
294(7)
Step C. Partition the Service Network
301(3)
Step D. Determine Travel Path and Balance the Partitions
304(1)
Step E. Revise Estimate of Total Work and Adjust Fleet Mix
305(1)
Implementation of the VDA in Philadelphia
305(2)
Enhancements and Extensions
307(2)
Bibliography
308(1)
Inventory Routing in Practice
309(22)
Ann M. Campbell
Lloyd W. Clarke
Martin W. P. Savelsbergh
Introduction
309(1)
Problem Definition
310(1)
Literature Review
311(2)
Solution Approach
313(6)
Phase I: Integer Programming Model
313(2)
Phase I: Solving the Integer Programming Model
315(1)
Phase II: Scheduling
316(3)
Computational Experience
319(8)
Instances
319(3)
Solution Quality
322(2)
Alternate Heuristic
324(1)
Computational Experiments
324(3)
Conclusion
327(4)
Bibliography
329(2)
Routing Under Uncertainty: An Application in the Scheduling of Field Service Engineers
331(22)
E. Hadjiconstantinou
D. Roberts
Introduction
331(1)
VRPSST with Variable Costs of Recourse
332(1)
Literature Review
332(2)
VRPST
333(1)
VRPSD
333(1)
Stochastic Integer VRPSST Formulation
334(2)
First-Stage Problem
334(1)
Second-Stage Problem
335(1)
Paired Tree Search Algorithm (PTSA)
336(3)
Linked Trees
337(1)
Lower Bounds
337(2)
Computational Implementation
339(1)
Applied Maintenance Scheduling Problem
339(2)
Maintenance Scheduling System in Practice
340(1)
Stochastic Problem Setting
340(1)
Modeling the Applied Problem as a VRPSST
341(1)
Model Input
342(1)
Job Locations and the Road Network
342(1)
Service Times
342(1)
Model Output: Computational Considerations
343(2)
Framework for the Analysis of Results
343(1)
Reoptimization
344(1)
Example Scenario
345(3)
Overall Computational Results
348(2)
Conclusion
350(3)
Bibliography
350(3)
Evolution of Microcomputer-Based Vehicle Routing Software: Case Studies in the United States
353(10)
E. K. Baker
Introduction
353(3)
Definition of the VRP
356(2)
Customer Specification
356(1)
Product Specification
357(1)
Vehicle Specification
357(1)
Algorithms
358(1)
Future Trends in Vehicle Routing Software
358(2)
Summary and Conclusions
360(3)
Bibliography
360(3)
Index 363