Paper Info
Title
A GRASP with adaptive large neighborhood search for pickup and delivery problems with transshipment
Abstract
The pickup and delivery problem (PDP) has been studied extensively for applications ranging from courier, cargo and postal services, to public transportation. The work presented here was inspired by a daily route planning problem at a regional air carrier who was trying to determine the benefits of transshipment. Accordingly, a primary goal of this paper is identify the circumstances under which measurable cost saving can be achieved when one aircraft transports a request from its origin to an intermediate point and a second aircraft picks it up and delivers it to its final destination. In structuring the analysis, we describe a unique way to model this transshipment option on a directed graph and introduce a specialized two-route insertion heuristic that considers when to exploit this option. Based on the new representation, most existing heuristics for the PDP can be readily extended to handle transshipments. To find solutions, we developed a greedy randomized adaptive search procedure (GRASP) with several novel features. In the construction phase, shipment requests are inserted into routes until all demand is satisfied or no feasible insertion exists. In the improvement phase, an adaptive large neighborhood search algorithm is used to modify portions of the feasible routes. Specialized removal and insertion heuristics were designed for this purpose. In the absence of test cases in the literature, we also developed a procedure for randomly generating problem instances. Testing was done on 56 existing PDP instances which have 50 requests each, and on 50 new data sets with 25 requests each and one transshipment location. For the former, the performance and solution quality of the GRASP were comparable to the best known heuristics. For the latter, GRASP found the solutions within 1% of optimality on 88% of the instances.
Year
DOI
Venue
2012
10.1016/j.cor.2011.11.016
Computers & OR
Keywords
DocType
Volume
specialized two-route insertion heuristic,transshipment location,daily route planning problem,known heuristics,problem instance,feasible insertion,existing heuristics,PDP instance,adaptive large neighborhood search,insertion heuristics,delivery problem
Journal
39
Issue
ISSN
Citations 
10
0305-0548
6
PageRank 
References 
Authors
0.45
12
2
Name
Order
Citations
PageRank
Yuan Qu171.20
Jonathan F. Bard21428144.29