車輛路徑問題

作者：（意大利）托夫（Paolo Toth） （意大利）Daniele Vigo

Paolo Toth is a Professor of Combinatorial Optimization at the Faculty of Engineering of the University of Bologna. His current research interests concern the design of algorithms for combinatorial optimization and graph theory problems and their application in real-world transportation, crew management and routing and loading problems. In July 1998, he was awarded the Euro Gold Medal. He has published more than 90 papers internationally,has co-authored and edited several books, and serves as editor for several journals. He is president of the International Federation of the Operational Research Societies （IFORS）for the period 2001-2003.

Daniele Vigo is an Associate Professor of Operations Research at the Faculty of Engineering of the University of Bologna. His main research activities are in the field of combinatorial optimization, with particular interest in the design of algorithms for routing, cutting, packing, and crew management problems. He has published more than 30 papers internationally and serves as Associate Editor for the journal Operations Research.

《車輛路徑問題(影印版)》內容簡介：in the field of combinatorial optimization problems, the vehicle routing problem (vrp) is one of the most challenging. defined more than 40 years ago, the problem involves designing the optimal set of routes for fleets of vehicles for the purpose of serving a given set of customers . interest in vrp is motivated by its practical relevance as well as its considerable difficulty.

the vehicle routing problem covers both exact and heuristic methods developed for the vrp and some of its main variants, emphasizing the practical issues common to vrp. the book is composed of three parts containing contributions from well-known experts. the first part covers basic vrp, known more commonly as capacitated vrp. the second part covers three main variants of vrp: with time windows, backhauls, and pickup and delivery. the third part covers issues arising in real-world vrp applications and includes both case studies and references to software packages.

this book will be of interest to both researchers and graduate-level students in the communities of operations research and mathematical sciences. it focuses on a specific family of problems while offering a complete overview of the effective use of the most important techniques proposed for the solution of hard combinatorial problems. practitioners will find this book particularly useful.

reader need a basic knowledge of the main methods for the solution of combinatorial optimization problems.

list of contributors

preface

1 an overview of vehicle routing problems

p. toth, d. vigo

1.1 introduction

1.2 problem definition and basic notation

1.2.1 capacitated and distance-constrained vrp

1.2.2 vrp with time windows

1.2.3 vrp with backhauls

1.2.4 vrp with pickup and delivery

1.3 basic models for the vrp

1.3.1 vehicle flow models

1.3.2 extensions of vehicle flow models

1.3.3 commodity flow models

1.3.4 set-partitioning models

1.4 test instances for the cvrp and other vrps

bibliography

Ⅰ capacitated vehicle routing problem

2 branch-and-bound algorithms for the capacitated vrp

p. toth, d. vigo

2.1 introduction

2.2 basic relaxations

2.2.1 bounds based on assignment and matching

2.2.2 bounds based on arborescences and trees

2.2.3 comparison of the basic relaxations

2.3 better relaxations

2.3.1 additive bounds for acvrp

2.3.2 further lower bounds for acvrp

2.3.3 lagrangian lower bounds for scvrp

2.3.4 lower bounds from a set-partitioning formulation

2.3.5 comparison of the improved lower bounds

2.4 structure of the branch-and-bound algorithms for cvrp

2.4.1 branching schemes and search strategies

2.4.2 reduction, dominance rules, and other features

2.4.3 performance of the branch-and-bound algorithms

2.5 distance-constrained vrp

bibliography

3 branch-and-cut algorithms for the capacitated vrp

d. naddef, g. rinami

3.1 introduction and two-index flow model

3.2 branch-and-cut

3.3 polyhedral studies

3.3.1 capacity constraints

3.3.2 generalized capacity constraints

3.3.3 framed capacity constraints

3.3.4 valid inequalities from stsp

3.3.5 valid inequalities combining bin packing and stsp

3.3.6 valid inequalities from the stable set problem

3.4 separation procedures

3.4.1 exact separation of capacity constraints

3.4.2 heuristics for capacity and related constraints

3.4.3 stsp constraints

3.5 branching strategies

3.6 computational results

3.7 conclusions

bibliography

4 set-covering-based algorithms for the capacitated vrp

j. bramel, d. simchi-levi

4.1 introduction

4.2 solving the linear programming relaxation of p

4.3 set-covering-based solution methods

4.3.1 branch-and-bound algorithm for problem cg

4.3.2 polyhedral branch-and-bound algorithm

4.3.3 pseudo-polynomial lower bound on cmin

4.3.4 solving pa via dual-ascent and branch-and-bound

4.4 solving the set-covering integer program

4.4.1 a cutting plane method

4.4.2 branch-and-price

4.4.3 additional comments on computational approaches

4.5 computational results

4.6 effectiveness of the set-covering formulation

4.6.1 worst-case analysis

4.6.2 average-case analysis

bibliography

5 classical heuristics for the capacitated vrp

g. laporte, f. semet

5.1 introduction

5.2 constructive methods

5.2.1 clarke and wright savings algorithm

5.2.2 enhancements of the clarke and wright algorithm

5.2.3 matching-based savings algorithms

5.2.4 sequential insertion heuristics

5.3 two-phase methods

5.3.1 elementary clustering methods

5.3.2 truncated branch-and-bound

5.3.3 petal algorithms

5.3.4 route-first, cluster-second methods

5.4 improvement heuristics

5.4.1 single-route improvements

5.4.2 multiroute improvements

5.5 conclusions

bibliography

6 metaheuristics for the capacitated vrp

m. gendreau, g. laporte, j y. potvin

6.1 introduction

6.2 simulated annealing

6.2.1 two early simulated annealing algorithms

6.2.2 osman's simulated annealing algorithms

6.2.3 van breedam's experiments

6.3 deterministic annealing

6.4 tabu search

6.4.1 two early tabu search algorithms

6.4.2 osman's tabu search algorithm

6.4.3 taburoute

6.4.4 taillard's algorithm

6.4.5 xu and kelly's algorithm

6.4.6 rego and roucairol's algorithms

6.4.7 barbarosoglu and ozgur's algorithm

6.4.8 adaptive memory procedure of rochat and taillard

6.4.9 granular tabu search of toth and vigo

6.4.10 computational comparison

6.5 genetic algorithms

6.5.1 simple genetic algorithm

6.5.2 application to sequencing problems

6.5.3 application to the vrp

6.6 ant algorithms

6.7 neural networks

6.8 conclusions

bibliography

Ⅱ important variants of the vehicle routing problem

7 vrp with time windows

j.-f. cordeau, g. desaulniers, j. desrosiers, m. m. solomon, e soumis

7. i introduction

7.2 problem formulation

7.2.1 formulation

7.2.2 network lower bound

7.2.3 linear programming lower bound

7.2.4 algorithms

7.3 upper bounds: heuristic approaches

7.3.1 route construction

7.3.2 route improvement

7.3.3 composite heuristics

7.3.4 metaheuristics

7.3.5 parallel implementations

7.3.6 optimization-based heuristics

7.3.7 asymptotically optimal heuristics

7.4 lower bounds from decomposition approaches

7.4.1 lagrangian relaxation

7.4.2 capacity and time-constrained shortest-path problem.

7.4.3 variable splitting

7.4.4 column generation

7.4.5 set-partitioning formulation

7.4.6 lower bound

7.4.7 commodity aggregation

7.4.8 hybrid approach

7.5 integer solutions

7.5.1 binary decisions on arc flow variables

7.5.2 integer decisions on arc flow variables

7.5.3 binary decisions on path flow variables

7.5.4 subtour elimination and 2-path cuts

7.5.5 k-path cuts and parallelism

7.5.6 integer decisions on (fractional and integer) time variables

7.6 special cases

7.6.1 multiple tsp with time windows

7.6.2 vrp with backhauls and time windows

7.7 extensions

7.7.1 heterogeneous fleet, multiple-depot, and initial conditions

7.7.2 fleet size

7.7.3 multiple time windows

7.7.4 soft time windows

7.7.5 time- and load-dependent costs

7.7.6 driver considerations

7.8 computational results for vrptw.

7.9 conclusions

bibliography

8 vrp with backhauls

p. toth, d. vigo

8.1 introduction

8.1.1 benchmark instances

8.2 integer linear programming models

8.2.1 formulation of toth and vigo

8.2.2 formulation of mingozzi, giorgi, and baldacci

8.3 relaxations

8.3.1 relaxation obtained by dropping the cccs

8.3.2 relaxation based on projection

8.3.3 lagrangian relaxation

8.3.4 overall additive lower bound

8.3.5 relaxation based on the set-partitioning model

8.4 exact algorithms

8.4. i algorithm of toth and vigo

8.4.2 algorithm of mingozzi, giorgi, and baldacci

8.4.3 computational results for the exact algorithms

8.5 heuristic algorithms

8.5.1 algorithm of deif and bodin

8.5.2 algorithms of goetschalckx and jacobs-blecha

8.5.3 algorithm of toth and vigo

8.5.4 computational results for the heuristics

bibliography

9 vrp with pickup and delivery

g. desaulniers, j. desrosiers, a. erdmann, m. m. solomon, f. soumis

9.1 introduction

9.2 mathematical formulation

9.2.1 construction of the networks

9.2.2 formulation

9.2.3 service quality

9.2.4 reduction of the network size

9.3 heuristics

9.3.1 construction and improvement

9.3.2 clustering algorithms

9.3.3 metaheuristics

9.3.4 neural network heuristics

9.3.5 theoretical analysis of algorithms

9.4 optimization-based approaches

9.4.1 single vehicle cases

9.4.2 multiple vehicle cases

9.5 applications

9.6 computational results

9.7 conclusions

bibliography

Ⅲ applications and case studies

10 routing vehicles in the real world: applications in the solid waste,

beverage, food, dairy, and newspaper industries

b. l. golden, a. a. assad, e. a. wasil

10.1 introduction

10.2 computerized vehicle routing in the solid waste industry

10.2.1 history

10.2.2 background

10.2.3 commercial collection

10.2.4 residential collection

10.2.5 case studies

10.2.6 roll-on-roll-off

10.2.7 further remarks

10.3 vehicle routing in the beverage, food, and dairy industries

10.3.1 introduction

10.3.2 beverage industry

10.3.3 food industry

10.3.4 dairy industry

10.4 distribution and routing in the newspaper industry

10.4.1 industry background

10.4.2 newspaper distribution problem

10.4.3 vehicle routing algorithms for ndp

10.4.4 three case studies

10.4.5 further remarks

10.5 conclusions

bibliography

11 capacitated arc routing problem with vehicle-site dependencies:

the philadelphia experience

j. sniezek, l. bodin, l. levy, m. ball

11.1 introduction

11.2 networks, assumptions, and goals of the carp-vsd

11.2.1 travel network

11.2.2 service network

11.2.3 vehicle classes

11.2.4 travel network and service network for a vehicle class

11.2.5 vehicle preference list

11.2.6 other assumptions

11.2.7 goals and constraints of the carp-vsd

11.3 vehicle decomposition algorithm (vda)

11.3.1 step a. create and verify vehicle class networks

11.3.2 step b. estimate total work and determine initial fleet mix

11.3.3 step c. partition the service network

11.3.4 step d. determine travel path and balance the partitions

11.3.5 step e. revise estimate of total work and adjust fleet mix

11.4 implementation of the vda in philadelphia

11.5 enhancements and extensions

bibliography

12 inventory routing in practice

ann m. campbell, lloyd w. clarke, martin w.p. savelsbergh

12.1 introduction

12.2 problem definition

12.3 literature review

12.4 solution approach

12.4.1 phase i: integer programming model

12.4.2 phase i: solving the integer programming model

12.4.3 phase ii: scheduling

12.5 computational experience

12.5.1 instances

12.5.2 solution quality

12.5.3 alternate heuristic

12.5.4 computational experiments

12.6 conclusion

bibliography

13 routing under uncertainty: an application in the scheduling of field

service engineers

e. hadjiconstantinou, d. roberts

13.1 introduction

13.2 vrpsst with variable costs of recourse

13.3 literature review

13.3.1 vrpst

13.3.2 vrpsd

13.4 stochastic integer vrpsst formulation

13.4.1 first-stage problem

13.4.2 second-stage problem

13.5 paired tree search algorithm (ptsa)

13.5.1 linked trees

13.5.2 lower bounds

13.5.3 computational implementation

13.6 applied maintenance scheduling problem

13.6.1 maintenance scheduling system in practice

13.6.2 stochastic problem setting

13.7 modeling the applied problem as a vrpsst

13.8 model input

13.8.1 job locations and the road network

13.8.2 service times

13.9 model output: computational considerations

13.9.1 framework for the analysis of results

13.9.2 reoptimization

13.10 example scenario

13.11 overall computational results

13.12 conclusion

bibliography

14 evolution of microcomputer-based vehicle routing software:

case studies in the united states

e. k. baker

14.1 introduction

14.2 definition of the vrp

14.2.1 customer specification

14.2.2 product specification

14.2.3 vehicle specification

14.3 algorithms

14.4 future trends in vehicle routing software

14.5 summary and conclusions

bibliography

index

車輛路徑問題的發展

1959年Dantzig和Ramse首次對閉合式VRP進行了研究，描述的是將汽油送往各個加油站的實際問題，並首次提出了相應的數學規劃模型以及求解算法。

1964年，Clark和Wright[4]一種對Dantzig-Ramse方法改進的有效的啓發式算法Clark-Wright節約算法。

正是由於以上兩篇開創性論文的發表，使得VRP成為運籌學以及組合優化領域的前沿和研究熱點課題。

1969年，Christofides和Eilon應用2-opt[5]和3-opt[6]處理車輛路徑問題。

1970年，提出了兩階段方法求解車輛路徑問題，包括先分組後定路線（clusterfirst-route second）和先定路線後分組（routefirst-cluster second）兩種啓發式策略。

1981年，Fisher和Jaikumar提出以數學規劃為主的最優化方法來處理包含大約50個顧客點的問題,同樣其運算效率是一個亟待解決的問題。同年，Gullen，Jarvis和Ratliff建立了人機互動的啓發式方法。

1981年，Bodin and Golden將眾多的VRP求解方法進行了歸納。分為以下七種：數學解析法（Exact Procedure）；人機互動法（Interactive Optimization）；先分羣再排路線（Cluster First–Route Second）；先排路線再分羣（Route First–Cluster Second）；節省法或插入法（Saving or Insertion）；改善或交換法（Improvement or Exchanges）；數學規劃近似法（Mathematical programming）。

1990年以來，人工智能方法在解決組合優化問題上顯示出強大功能，在各個領域得到充分應用，很多學者也將人工智能引入車輛路線問題的求解中，並構造了大量的基於人工智能的啓發式算法。 禁忌搜索法（TS）基本上是屬於一種人工智能型（AI）的局部搜尋方法，Willard首先將此算法用來求解VRP 。袁慶達[7]等設計了考慮時間窗和不同車輛類型的禁忌算法，這種算法主要採用GA方法產生初始解，然後禁忌算法對初始解優化。模擬退火方法具有收斂速度快，全局搜索的特點，Osman[8]對VRP的模擬退火算法進行了研究。遺傳算法具有求解組合優化問題的良好特性，Holland首先採用遺傳算法（GA）編碼解決VRPTW 問題。現在多數學者採用混合策略，分別採用兩種人工智能方法進行路線分組和路線優化。Ombuki[9]提出了用GA進行路線分組，然後用TS方法進行路線優化的混合算法。Bent和Van Hentenryck[10]則首先用模擬退火算法將車輛路線的數量最小化，然後用大鄰域搜索法（largneighborhood search）將運輸費用降到最低。

綜合過去有關VRP的求解方法，可以將其分為精確算法（exact algorithm）與啓發式算法（heuristics），其中精確算法有分支界限法、分支切割法、集合涵蓋法等；啓發式算法有節約法、模擬退火法、確定性退火法、禁忌搜尋法、基因算法、神經網絡、螞蟻殖民算法等。