Hybrid algorithms for the vehicle routing problem with clustered backhauls and 3D loading constraints

In this paper, we extend the vehicle routing problem with clustered backhauls (VRPCB) to an integrated routing and three-dimensional loading problem, called VRPCB with 3D loading constraints (3L-VRPCB). In the VRPCB each customer is either a linehaul or a backhaul customer and in each route all linehaul customers must be visited before any backhaul customer. In the 3L-VRPCB, each customer demand is given as a set of 3D rectangular items (boxes) and the vehicle capacity is replaced by a 3D loading space. Moreover, some packing constraints, e.g. concerning stacking of boxes, are also integrated. A set of routes of minimum total length has to be determined such that each customer is visited once. For each route two packing plans have to be provided that stow all boxes of all visited linehaul and backhaul customers, respectively, taking into account the additional packing constraints. We propose two hybrid algorithms for solving the 3L-VRPCB, each of them consisting of a routing and a packing procedure. The routing procedures follow different metaheuristic strategies (large vs. variable neighborhood search) and in both algorithms a tree search heuristic is responsible for packing boxes. Extensive computational experiments were carried out using 95 3L-VRPCB benchmark instances that were derived from well-known VRPCB instances. Good results are also achieved for the capacitated vehicle routing problem with 3D loading constraints as a special case of the 3L-VRPCB.