A Hybrid Metaheuristic Algorithm for the Integrated Vehicle Routing and Three-Dimensional Container-Loading Problem

This paper examines a recently addressed practical variant of the capacitated vehicle routing problem (VRP) called the capacitated vehicle routing problem with 3-D loading constraints (3L-CVRP). This problem considers customer demand to be formed by 3-D rectangular items. Additional loading constraints often encountered in real-life applications of transportation logistics are imposed on the examined problem model. In addition to 3L-CVRP, we also introduce and solve a new practical problem version that was dictated by a transportation logistics company and covers cases in which transported items are manually unloaded from the loading spaces of the vehicles. Both problem versions are solved by a hybrid metaheuristic methodology that combines the strategies of tabu search (TS) and guided local search (GLS). The loading characteristics are tackled by employing a collection of packing heuristics. The proposed algorithm´s robustness was tested for both problem versions, solving benchmark instances derived from the literature and new benchmark problems with diverse features in terms of customer set size and transported-item dimensions. It produced fine results, improving most of the best solutions that were previously reported.