A Hybrid Algorithm for the Vehicle Routing Problem with Pickup and Delivery and 3D Loading Constraints

Abstract

In this paper, we extend the classical Pickup and Delivery Problem (PDP) to an integrated routing and three-dimensional loading problem, called PDP with 3D loading constraints (3L-PDP). A set of routes of minimum total length has to be determined such that each request is transported from a loading site to the corresponding unloading site. In the 3L-PDP, each request is given as a set of 3D rectangular items (boxes) and the vehicle capacity is replaced by a 3D loading space. We investigate which constraints will ensure that no reloading effort will occur, i.e. that no box is moved after loading and before unloading. A spectrum of 3L-PDP variants is introduced with different characteristics in terms of reloading effort. We propose a hybrid algorithm for solving the 3L-PDP consisting of a routing and a packing procedure. The routing procedure modifies a well-known large neighborhood search for the 1D-PDP. A tree search heuristic is responsible for packing boxes. Computational experiments were carried out using 54 newly proposed 3L-PDP benchmark instances.