prev

next

out of 256

Published on

26-Mar-2015View

398Download

0

Embed Size (px)

Transcript

Heuristic and exact algorithms for vehicle routing problemsStefan Ropke

December 2005

PrefaceThis Ph.D. thesis has been prepared at the Department of Computer Science at the University of Copenhagen (DIKU), during the period November 2002 to December 2005. The work has been supervised by Professor David Pisinger. The thesis consists of four introductory chapters: Chapters 1, 2, 3 and 7, and ve research papers: Chapters 4, 5, 6, 8 and 9. The ve research papers have been written in collaboration with coauthors which are mentioned in the beginning of each paper. The four introductory chapter have been written solely by the undersigned. The ve research papers are relatively self-contained. Note that each research paper contains it own bibliography and sometimes an appendix. The bibliography for the introductory chapters are found at the end of this thesis. The thesis contains three parts. The rst part contains the introduction and is split into two chapters. The next part deals with heuristic and contains one introductory chapter and three research papers about heuristics. These papers are technical report versions that contains more results than the papers that have been submitted to journals. These extra results are placed in the appendix of each paper. The last part is about exact methods and contains one introductory chapter and two research papers. The thesis started out being solely about heuristics, but after having worked with heuristics for four or ve years, rst as a graduate student, then in the industry and as a Ph.D. student I felt it was time to learn something new and started studying exact methods more intensively in 2004. This has certainly been interesting and I hope the knowledge I have obtained will allow me to design even better heuristics in the future. Chapter 9 is the only one of the ve papers that has not been submitted to a journal yet. In its current state it is not ready to be submitted either - it is clearly too long and contains too much material. We do plan to submit a condensed version. The rest of this section is going to describe how the paper could be condensed. To understand this, one needs to have read chapter 9. One way of condensing the paper would be to focus on the SP1 and SP2 relaxations and leave the SP3 and SP4 relaxations out as well as the addition of valid inequalities. The contribution of this paper would be 1. Improvements of domination criteria for ESPPTWCPD. 2. The computational comparison of SP1 and SP2. 3. The new pricing heuristics and experiments. More experiments could be carried out. 4. Introduction of standard test instances for exact solution of the PDPTW. For this paper it would be nice if the issues with algorithms SP1* and SP2* were worked out. The simplest way of doing this would be to use algorithms SP1*/SP2* to get a lower bound. If the linear relaxation solution turns out to be fractional then one should switch to algorithms SP1/SP2 to perform branching. A better approach would be to implement a branching rule that is compatible with the strongest domination criteria. Branching on time windows as proposed in the paper would be a good candidate. An alternative is to nd a way of perturbing the (dij ) matrix such that dij + djk dik i

PREFACE

ii

always holds when j is a delivery node, even when general cuts have been added to the master problem. Valid perturbations of the (dij ) matrix include subtracting a constant i from all edges leaving pickup node i and adding i to all edges leaving node n + i. This is valid as a path in the ESPPTWCPD and SPPTWCPD that visits a pickup must visit the corresponding delivery and vice versa. This would allow us to add cuts in the original variables to the master problem and would thereby make the current branching rule work with with SP1*/SP2*. A second paper could describe the SP3 and SP4 relaxations and incorporate the valid inequalities in the branch-and-price algorithm. This paper could also include the strengthened SP4 relaxation that is described in the conclusion of the paper.

AcknowledgmentsI would rst of all like to thank my supervisor, Professor David Pisinger for encouragement, countless discusions and for his help with writing the thesis. Without David I would not had taken on the task of doing a Ph.D. study. Associate Professor Jean-Franois Cordeau and Professor Gilbert Laporte also deserves great thank for making my visits to the University of Montreal possible and for taking time to work with me while I have been visiting. The input I received from my advisory group, Professor Jacques Desrosiers and Professor Oli Madsen, is also greatly appreciated. I would also like to thank the guys at the Algorithmics and Optimization Group at DIKU for encouragement and for making the average work day more fun and interesting. Similarly I would like to thank the people I met at the Centre for Research and Transportation in Montreal, especially the gang, for making me feel welcome in a foreign country. I also wish to thank Irina Dumitrescu for her patience with me when I have postponed working on our joint projects because of the work involved in nishing this thesis. Finally I would like to thank friends and family for their support. I especially wish to thank my parents for their love and support throughout my life. And to my girlfriend Alice: Thank you for lifting my mood on the days when I have been feeling down in the last couple of months, for helping me improving the language in the thesis and for being you! Copenhagen, December 2005, Stefan Rpke

Updated version, June 2006A number of typos and errors have been corrected in this version of the thesis. Since December 2005 I have spent time working on the research paper presented in chapter 9. This work has lead to resolution of the most of the issues discussed above and mentioned in the chapter 9: A transformation of the distance matrix has been found that makes it possible to use SP1*/SP2* after adding cuts in the master problem and it has been shown that many of the cuts that seemed worthless in the computational experiements in fact are implied by the strongest set partition relaxations. These developments have not been included in the updated version of the thesis, but are described in Ropke and Cordeau [2006]. Let me use the opportunity to thank my opponents: Stefan Irnich, Daniele Vigo and Martin Zachariasen at the Ph.D. defense, for evaluating the thesis within a short time and for valuable comments that has lead to several improvements in this updated version of the thesis. Montreal, June 2006, Stefan Rpke

ContentsPreface i

I

Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Ph.D. thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12 2 3 5 5 6 7 8 11 11 12 13 16 18 20 22

1 Introduction 1.1 Motivation . . . . . . . . . . . . . . . . . . . 1.2 Modeling and solution methods . . . . . . . . 1.2.1 Modeling . . . . . . . . . . . . . . . . 1.2.2 Solution methods . . . . . . . . . . . . 1.3 Goals . . . . . . . . . . . . . . . . . . . . . . 1.3.1 Achievements and contributions of the 1.4 Overview of Ph.D. thesis . . . . . . . . . . . .

2 Classes of vehicle routing problems 2.1 The traveling salesman problem . . . . . . . . . . 2.2 m-Traveling salesman problem . . . . . . . . . . 2.3 Capacitated vehicle routing problem . . . . . . . 2.4 The vehicle routing problem with time windows . 2.5 Pickup and delivery problem with time windows 2.5.1 Heuristics for PDPTW and DARP . . . . 2.5.2 Exact methods for PDPTW and DARP .

II

Heuristics. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2425 25 25 25 26 28 28 29 30 30 35

3 Introduction to heuristics 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Heuristic categories . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Construction heuristics . . . . . . . . . . . . . . . . . 3.2.2 Local search heuristics . . . . . . . . . . . . . . . . . . 3.2.3 Neighborhoods . . . . . . . . . . . . . . . . . . . . . . 3.2.3.1 Small neighborhoods . . . . . . . . . . . . . . 3.2.3.2 Large and exponential sized neighborhoods . 3.2.4 Metaheuristics . . . . . . . . . . . . . . . . . . . . . . 3.3 Trends in heuristic research for the VRP . . . . . . . . . . . . 3.3.1 Trends in heuristic research for the VRP - conclusion

4 An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows 36 5 A unied heuristic for a large class of vehicle routing problems with backhauls 67

iii

CONTENTS 6 A general heuristic for vehicle routing problems

ccxxxix 100

III

Exact methods. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

145146 146 146 149 150 151 151 153 155 156 156

7 Introduction to exact methods 7.1 Introduction . . . . . . . . . . . . . . . . 7.2 Linear programming based lower bounds 7.2.1 Cutting plane algorithm . . . . . 7.2.2 Branch-and-cut . . . . . . . . . . 7.3 Introduction to branch-and-price . . . . 7.3.1 Decomposition . . . . . . . . . . 7.3.2 Column generation . . . . . . . 7.3.3 Branch-and-price . . . . . . . . . 7.3.4 Branch-and-cut-and-price . . . . 7.3.5 Further topics . . . . . . . . . . .

8 Models and a Branch-and-Cut Algorithm for Pickup and Delivery Problems with Time Windows 158 9 Branch-and-Cut-and-Price for the Pickup and Delivery Problem with Time Windows 186

IV

Conclusion

239240 242

10 Conclusion 11 Summary (in Danish)

Part I

Introduction

1

Chapter 1

Introduction1.1 Motivation

Transportation of goods and passengers is an important task in the society of today. Astronomical amounts of money are spent daily on fuel, equipment, maintenance of equipment and wages. It is therefore obvious to attempt to reduce the amount of money spent on transportation as even small improvements can lead to huge improvements in absolute terms. Several approaches could be taken, one could improve equipment or make the infrastructure better. One could also look at operations research (OR) techniques - given the resources available, what is the best that can be done? Toth and Vigo [2002b] estimate that the use of computerized procedures for planning of the distribution process often leads to savings in the area of 5% to 20% of the transportation costs, so studying such procedures denitely seems worthwhile. Furthermore, transportation accounts for a great part of the CO2 pollution in the world today. According to Pedersen [2005] the transportation sector was in 1998 responsible for 28% of the CO2 emission in the Europe Union and road transportation alone accounted for 84% of the total CO2 emissions from the transportation sector. Moreover, it is exected that the CO2 emissions from the transportation sector is going to increase by 50% by 2010 (according to Pedersen [2005]). Thus, improvements in planning techniques could help easing the strain on the environment caused by transportation. Operations research has been quite successful in the transportation area. One could see optimization within transportation as one of the successes of OR. Today OR techniques are applied within for example the airline, railway, trucking and shipping industries; and OR techniques are used to optimize the interplay between the dierent modes of transportation, for example in handling port operations. Several companies exist that solely or primarily develop software for optimization within the transportation industry. Some examples are the Swedish based Carmen Systems 1 that develop software for airlines and railways; the Canadian Giro 2 that develops software for routing and scheduling of ground based vehicles; the Danish Transvision 3 that develops software for ground based distribution; the Danish e2e factory 4 that develops software controlling ground personnel at airports. Consequently it is fair to say that optimization within transportation is a subject that is used and sought-after in the real world and not just a topic studied in academia. Also, the eld seems to have reached a certain level of maturity as it has been studied for many decades. Having said that, there remain ample room for improvement in the solution methods employed and OR methods could be applied to a wider array of problems faced within the transportation industry. The real world need solution methods that are:1 http://www.carmen.se 2 http://www.giro.ca/ 3 http://www.transvision.dk 4 http://www.e2efactory.dk/

2

CHAPTER 1. INTRODUCTION Fast the quicker the operator gets an answer back from the computer the better,

3

Easy to apply to a variety of problem characteristics when developing software for real life problems one wants to avoid reinventing the wheel every time a new client wants a software application for a new type of transportation problem, Precise the better results a solution method returns the larger is the potential for savings, More robust when solving real world problems it is often better to have a solution method that produces fairly good results for all problem instances, than one that produces very good results for 70% of the problem instances and very poor results for the remaining 30%. The four characteristics listed above are to a certain extent in conict with each other, so some sort of trade-o has to be achieved. Solution methods described in the literature are often evaluated in terms of speed, solution quality, and to a certain extent, robustness while the second characteristic listed above often receives less attention. In this thesis a solution method that takes all four characteristics into account is presented. One problem in the eld of transportation related OR that has been given a lot of attention in the scientic literature is the so called vehicle routing problem (VRP). In the vehicle routing problem we are given a eet of vehicles and a set of customers to be visited. The vehicles are often assumed to have a common...