Our Research on Pickup and Delivery Problems

Manar Hosny and Christine Mumford

pd_new2.png

1  Overview of Research

We tackle three variants of the pickup and delivery problem:
These problems are difficult to solve because of the hard constraints, and feasible solutions can be challenging to find. We devise simple representations and operators that deal with constraints as naturally as possible. In particular, we present a duplicate code which encodes paired pickup and delivery locations with identical IDs [1] [2]. This approach easily handles the precedence constraint (for which the pickup of goods must always precede the delivery of those goods). We beat previously best published results for the single vehicle pickup and delivery problem [2] using simple three-stage metaheuristic algorithms. Our algorithms also proved to be very fast and robust, needing little re-tuning when run on new unseen instances.
We also beat previously best published results for the single commodity pickup and delivery problem [5], although our approach needs some more work to improve the run time.
Our main contribution to the multiple vehicle pickup and delivery problem with time windows has been our work on construction heuristics [3]. We also developed a new genetic algorithm [4] to solve the problem.

2  Introduction

The Vehicle Routing Problem (VRP) involves the distribution and transportation of people and goods. The problem can be generally described as finding a set of minimum cost routes for a fleet of vehicles, located at a central depot, to serve a number of customers. Each vehicle should depart from and return to the same depot, while each customer should be visited exactly once. Since the introduction of this problem by Dantzig and Fulkerson in 1954 [7], several extensions and variations have been added to the basic VRP model, in order to meet the demand of realistic applications. For example, restricting the capacity of the vehicle and specifying certain service times for visiting clients are among the popular constraints that have been considered.
One important variant of the VRP is the Pickup and Delivery Problem (PDP). Unlike the classical VRP, where all customers require the same service type, a central assumption in the PDP is that there are two different types of services that can be performed at a customer location, a pickup or a delivery. Based on this assumption, other variants of the PDP have also been introduced depending on, for example, whether the origin/destination of the commodity is the depot or some customer location, whether one or multiple commodities are transferred, whether origins and destinations are paired, and whether people or goods are transported. In addition, some important real-life constraints that have been applied to the basic VRP have also been applied to the PDP, such as the vehicle capacity and service time constraints. Applications of the PDP are frequently seen in transportation and logistics. In addition, the problem is likely to become even more important in the future, due to the rapid growth in parcel transportation as a result of e-commerce. Some applications of this problem include bus routing, food and beverage distribution, currency collection and delivery between banks and ATM machines, Internet-based pickup and delivery, collection and distribution of charitable donations between homes and different organizations, and the transport of medical samples from medical offices to laboratories, just to name a few. Also, an important PDP variant, known as dial-a-ride, can provide an effective means of transport for delivering people from door to door. This model is frequently adopted for the disabled, but could provide a greener alternative than the car and taxi to the wider community. Besides road-based transportation, applications of the PDP can also be seen in maritime and airlift planning.
As previously mentioned, considerable attention has been paid to the classical VRP and its related variants by the scientific community. Literally thousands of papers have been published in this domain (see for example survey papers [12], [9], [8], [13] and the survey paper in the 50th anniversary of the VRP [10]). Despite this, research on Pickup and Delivery (PD) problems is relatively scarce [11]. A possible reason is the complexity of these problems and the difficulty in handling the underlying problem constraints. Innovations in solution methods that handle different types of PD problems are certainly in great demand.

3  Main themes of our research

We have selected two important variants of PD problems as the focus of this research. These are: the Pickup and Delivery Problem with Time Windows (PDPTW), and the one-commodity pickup and delivery problem (1-PDP), with more emphasis on the first of these two variants and a thorough investigation of both its single and multiple vehicle cases. The main difference between the two problems is that the PDPTW assumes that origins and destinations are paired, while the 1-PDP assumes that a single commodity may be picked up from any pickup location and delivered to any delivery location
In both problems, the total transportation cost should be minimized, without violating a number of pre-specified problem constraints. In our research, we investigate heuristic and meta-heuristic approaches for solving the selected PDP variants. Unlike previous research in this area, though, we try to focus on handling the difficult problem constraints in a simple and effective way, without complicating the overall solution methodology. Two main aspects of the solution algorithm are directed to achieve this goal: Based on this perception, we tailored a number of heuristic and meta-heuristic algorithms for solving our problems. Among these algorithms are: Genetic Algorithms, Simulated Annealing, Hill Climbing and Variable Neighbourhood Search. In general, the findings of the research indicate the success of our approach in handling the difficult problem constraints and devising simple and robust solution mechanisms that can be integrated with vehicle routing optimization tools and used in a variety of real world applications.
Our work culminated in several research papers and, in 2010, a PhD was awarded to Manar Hosny [6].

4  Downloadable Documents

[1] and [2] describe our work on the single vehicle pickup and delivery problem. Research on this problem was very successful, beating previously best published results using a fairly simple and robust approach with a fast run time. [1] describes our initial research covering some very important groundwork on our duplicate code representation and various operators. We use a genetic algorithm to solve the problem in this paper. We generated our large data set test data for this paper (see below).
[2] presents our most successful work on the single vehicle problem. Here we develop fast and robust three-stage hill-climbing and simulated annealing algorithms, using the same duplicate code representation as our GA in [1], and also use efficient neighbourhood move operators that are guided by the time windows.
[3] investigates several solution construction heuristics for the multiple vehicle pickup and delivery problem, aiming to find methods capable of producing good starting solutions for metaheuristic algorithms, including genetic algorithms which require a population of diverse starting solutions. We developed a simple sequential algorithm that produced impressive results, yet is simple to code and fast to run.
[4] describes our GA for the multiple vehicle pickup and delivery problem. Our approach manipulates the grouping and routing aspects of the problem simultaneously, and avoids the need for repair of infeasible solutions.Overall our algorithm is simple and straightforward. Our GA performed well but was behind the best published results obtained by the Grouping Genetic Algorithm [16].
Finally, in [5] we introduce a new adaptive hybrid VNS/SA (Variable Neighborhood Search/Simulated Annealing) approach for solving the single commodity pickup and delivery problem. We perform sequences of VNS runs, where neighborhood sizes are adaptable, within which the search is performed at each run. Experimental results on a large number of benchmark instances indicate that the algorithm outperforms previous heuristics in 90 % of the large size test cases. However the current form of the algorithm is inefficient and the run time needs to be reduced.

Data

The data we used in [1] and [2] for the single vehicle pickup and delivery problem with time windows can be downloaded from the links provided here. The first data set, ntu04, (we call Set 1 in our papers) was provided by Wan-rong Jih, and used in their publications: [14] and [15]. Please cite these publications if you use this data. The file format for these data sets is as follows:
- First the number of tasks (where each task consists of a pickup and delivery pair) and the vehicle capacity
- Then the number of locations (which is twice the number of tasks +1 (for the depot) )
- Then a list of location numbers (location IDs), and the x and y coordinates of each location (in parenthesis)
- Then the number (ID) of the depot
- Then a list describing each task, where each task consists of: a task ID, followed by the ID of the pickup and the ID of the delivery (in parenthesis) , then the earliest time window and the latest time window of the pickup (in square brackets), then the earliest time window and the latest time window of the delivery (in square brackets), then the demand of the task.
The second data set, PDP.zip, (Set 2 in our papers) was generated by ourselves to cover larger instances. A readme file is included with the second data set to describe the format of our test data files. Please cite our papers if you use our data.

References

       This Research

[1]
M. I. Hosny and C. L. Mumford. Single vehicle pickup and delivery with time windows: Made to measure genetic encoding and operators. In Proceedings of the 2007 GECCO Conference Companion on Genetic and Evolutionary Computation, SESSION: Late-breaking papers, pages 2489-2496, 2007. DOI Link
[2]
M. I. Hosny and C. L. Mumford. The single vehicle pickup and delivery problem with time windows: Intelligent operators for heuristic and metaheuristic algorithms. Journal of Heuristics, Special Issue on Advances in Metaheuristics, 16(3):417-439, June 2010. DOI Link.
[3]
M. I. Hosny and C. L. Mumford. New solution construction heuristics for the multiple vehicle pickup and delivery problem with time windows. In MIC2009, Metaheuristic International Conference, July 2009.
[4]
M. I. Hosny and C. L. Mumford. Investigating genetic algorithms for solving the multiple vehicle pickup and delivery problem with time windows. In MIC2009, Metaheuristic International Conference, July 2009.
[5]
M. I. Hosny and C. L. Mumford. Solving the one-commodity pickup and delivery problem using an adaptive hybrid VNS/SA approach. In Proceedings of the 11th International Conference on Parallel Problem Solving From Nature (PPSN2010), LNCS, Springer, Verlag pp 189-198, September 2010. DOI Link.
[6]
M. I. Hosny Investigating Heuristic and Meta-Heuristic Algorithms for Solving Pickup and Delivery Problems. Doctorial Thesis, School of Computer Science & Informatics, Cardiff University, United Kingdom, March 2010.

References

[7]
G. B. Dantzig and D. R. Fulkerson. Minimizing the number of tankers to meet a fixed schedule. Naval Research Logistics Quarterly, 1:217-222, 1954.
[8]
B. Eksioglu, A. V. Vural, and A. Reisman. The vehicle routing problem: A taxonomic review. Computers & Industrial Engineering, 57(4):1472-1483, 2009.
[9]
G. Laporte. The vehicle routing problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59(3):345-358, 1992.
[10]
G. Laporte. Fifty years of vehicle routing. Transportation Science, 43(4):408-416, 2009.
[11]
M. Savelsbergh and M. Sol. The general pickup and delivery problem. Transportation Science, 29(1):17-29, 1995.
[12]
M. M. Solomon and J. Desrosiers. Survey paper-time window constrained routing and scheduling problems. Transportation Science, 22(1):1-13, 1988.
[13]
P. Toth and D. Vigo, editors. The vehicle routing problem. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2001.
[14]
Jih, Wan-rong and Kao, Cheng-Yen and Hsu, Jane Yung-jen, Using Family Competition Genetic Algorithm in Pickup and Delivery Problem with Time Window Constraints, In Proceedings of the 2002 IEEE International Symposium on Intelligent Control, pp 496-501, 2002.
[15]
Jih, Wan-rong and Hsu, Jane Yung-jen, A Family Competition Genetic Algorithm for the Pickup and Delivery Problems with Time Window, Bulletin of the College of Engineering, Vol. 90, pp 121-130, 2004.
[16]
Pankratz. G., A grouping genetic algorithm for the pickup and delivery problem with time windows. OR Spectrum, 27:21–24, 2005.


File translated from TEX by TTH, version 3.87.
On 31 Dec 2010, 13:47.