Metaheuristics 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, calle d 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 th e vehicle capacity is replaced by a 3D loading space. Moreover, some packing constraints, e.g. concerning stacking of boxes, ar e 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 packin g constraints. We propose two hybrid algorithms for solving the 3L-VRPCB, each of them consisting of a routing and a packing procedure. The routing proce- dures follow different metaheuristic strategies (Lar ge 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 ac hieved for the capacitated vehicle routing problem with 3D loading constraints as a special case of the 3L-VRPCB.
Nutzung und Vervielfältigung:
Alle Rechte vorbehalten