کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
475205 699245 2012 18 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A GRASP with adaptive large neighborhood search for pickup and delivery problems with transshipment
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
A GRASP with adaptive large neighborhood search for pickup and delivery problems with transshipment
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 39, Issue 10, October 2012, Pages 2439–2456
نویسندگان
, ,