On the one-to-one pickup-and-delivery problem with time windows and trailers

Michael Drexl ()
Additional contact information
Michael Drexl: Deggendorf Institute of Technology

Central European Journal of Operations Research, 2021, vol. 29, issue 3, No 19, 1115-1162

Abstract: 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. Goods are not interchangeable: what is picked up at one particular location must be delivered to one particular other location. The discussed extension 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 lorries. 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 trailers. The contribution of the 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. (iii) It provides a comprehensive set of new benchmark instances on which the runtime of the constant-time test is compared with a naïve one that requires linear time by embedding both tests in an adaptive large neighbourhood search algorithm. Computational experiments show that the constant-time test outperforms its linear-time counterpart by one order of magnitude on average.

Keywords: Vehicle routing; Pickup-and-delivery; Trailers; Insertion heuristic; Constant-time feasibility test (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10100-020-00690-w Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:cejnor:v:29:y:2021:i:3:d:10.1007_s10100-020-00690-w

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10100

DOI: 10.1007/s10100-020-00690-w

Access Statistics for this article

Central European Journal of Operations Research is currently edited by Ulrike Leopold-Wildburger

More articles in Central European Journal of Operations Research from Springer, Slovak Society for Operations Research, Hungarian Operational Research Society, Czech Society for Operations Research, Österr. Gesellschaft für Operations Research (ÖGOR), Slovenian Society Informatika - Section for Operational Research, Croatian Operational Research Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().