On the One-to-One Pickup-and-Delivery Problem with Time Windows and Trailers

Michael Drexl (michael.drexl@th-deg.de)
Additional contact information
Michael Drexl: Deggendorf Institute of Technology, Johannes Gutenberg-University

No 1816, Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz

Abstract: This paper studies an extension of the well-known one-to-one pickup-and-delivery problem with time windows. In the latter problem, requests to transport goods from pickup to delivery locations must be fulfilled by a set of vehicles with limited capacity subject to time window constraints at locations. The goods are not interchangeable; what is picked up at one particular location must be delivered to one particular other location. The extension discussed here consists in the consideration of a heterogeneous vehicle fleet comprising lorries with detachable trailers. Trailers are advantageous as they increase the overall vehicle capacity. However, some locations may be accessible only by a lorry without a trailer. Therefore, special locations are available where trailers can be parked while lorries visit accessibility-constrained locations. This induces a nontrivial tradeoff between an enlarged vehicle capacity and the necessity of scheduling detours for parking and reattaching a trailer. The contribution of the present paper is threefold: (i) It studies a practically relevant generalization of the one-to-one pickup-and-delivery problem with time windows. (ii) It develops an exact amortized constant-time procedure for testing the feasibility of an insertion of a transport task into a given route with regard to time windows and lorry and trailer capacities and embeds this test in an adaptive large neighbourhood search algorithm for the heuristic solution of the problem. (iii) It provides a comprehensive set of benchmark instances on which the running time of the constant-time test is compared with a naïve one that requires linear time. The results of computational experiments show significant speedups of one order of magnitude on average.

Keywords: Vehicle routing; Pickup-and-delivery; Trailers; Adaptive large neighbourhood search; Insertion heuristic; Constant-time feasibility test. (search for similar items in EconPapers)
Pages: 26 pages
Date: 2018-10-04
New Economics Papers: this item is included in nep-cmp and nep-tre
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://download.uni-mainz.de/RePEc/pdf/Discussion_Paper_1816.pdf First version, 2018 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:jgu:wpaper:1816

Access Statistics for this paper

More papers in Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz Contact information at EDIRC.
Bibliographic data for series maintained by Research Unit IPP (ipp-mainz@uni-mainz.de).