Carp

Transportation Logistics
Lecture held by Gilbert Laporte
Winter Term 2004 (University of Vienna)

Summarized by Guenther Fuellerer

Contents

1 Travelling Sales Person Problem (TSP) 1.1 1.2 Applications of the TSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Different Solving Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.1 1.2.2 1.2.3 Enumeration . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Exact Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5 5 6 6 6 9 20 20 21 22 27 28 29 33 34 34 35 35 35 37 39 39 39 39

2 Vehicle Routing Problem (VRP) 2.1 2.2 Applications of the VRP . . . . . . . . . . . . . . . . . . . . . . . . . . . .Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1 2.2.2 2.3 2.3.1 2.3.2 Construction Heuristics . . . . . . . . . . . . . . . . . . . . . . . . Classical Improvement Heuristices . . . . . . . . . . . . . . . . . . Local Search Metaheuristics . . . . . . . . . . . . . . . . . . . . . . Genetic Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . .Metaheuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 Location Problems 3.1 3.2 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 3.2.2 3.2.3 Median Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . p-Median Problems . . . . . . . . .. . . . . . . . . . . . . . . . . Covering Problems . . . . . . . . . . . . . . . . . . . . . . . . . . .

4 Arc Routing Problems 4.1 4.2 Applications and Graphical Representation . . . . . . . . . . . . . . . . . Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.1 Undirected Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

4.2.2 4.2.34.2.4 4.2.5

The Chinese Postman Problem (CPP) . . . . . . . . . . . . . . . . Directed Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . The Undirected Rural Postman Problem (RPP), Ortoff (1976) . . .

42 43 44

The Capacitated Arc Routing Problem (CARP) Golden, Wong (1981) 47

2

List of Figures

1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9

Two-opt . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . Three-opt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Or-opt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Patching Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Branching I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Branching II . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Connectivity Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . Case 2 TSP Relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Case 3 TSP Relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8 8 9 13 13 14 16 18 18 18 19 20 22 22 23 24 25 25 27 28 29 35 36 36 38

1.10 Case 4 TSPRelaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.11 Feasible but necessarily not optimal solution . . . . . . . . . . . . . . . . 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 Classical Vehicle Routing Problem . . . . . . . . . . . . . . . . . . . . . . Multiple Depot VRP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Savingsheuristic . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . Sweep Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Cluster first - Route second . . . . . . . . . . . . . . . . . . . . . . . . . . Routing Phase - Create a Giant TSP Tour . . . . . . . . . . . . . . . . . . . Clustering Phase - Shortest Path Problem . . . . . . . . . . . . . . . . . . Ejection Chains . . . . . . . . . . . . . . . . . . . . . ....