Please use this identifier to cite or link to this item: https://hdl.handle.net/10419/288461 
Authors: 
Year of Publication: 
2020
Citation: 
[Journal:] Central European Journal of Operations Research [ISSN:] 1613-9178 [Volume:] 29 [Issue:] 3 [Publisher:] Springer [Place:] Berlin, Heidelberg [Year:] 2020 [Pages:] 1115-1162
Publisher: 
Springer, Berlin, Heidelberg
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.
Subjects: 
Vehicle routing
Pickup-and-delivery
Trailers
Insertion heuristic
Constant-time feasibility test
Persistent Identifier of the first edition: 
Creative Commons License: 
cc-by Logo
Document Type: 
Article
Document Version: 
Published Version

Files in This Item:
File
Size





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.