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

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.