A variable neighborhood search for the capacitated vehicle routing problem with two-dimensional loading constraints

• We propose a variable neighborhood search to address the routing aspect.
• We adapt a skyline heuristic to examine the loading constraints.
• We propose an efficient data structure to record the loading information.
• We outperform all existing approaches on numerical experiments.
• We improve or match the best known solutions for majority of benchmark instances.

This paper addresses the capacitated vehicle routing problem with two-dimensional loading constraints (2L-CVRP), which is a generalized capacitated vehicle routing problem in which customer demand is a set of two-dimensional, rectangular, weighted items. The objective is to design the route set of minimum cost for a homogenous fleet of vehicles, starting and terminating at a central depot, to serve all the customers. All the items packed in one vehicle must satisfy the two-dimensional orthogonal packing constraints. A variable neighborhood search is proposed to address the routing aspect, and a skyline heuristic is adapted to examine the loading constraints. To speed up the search process, an efficient data structure (Trie) is utilized to record the loading feasibility information of routes, but also to control the computational effort of the skyline spending on the same route. The effectiveness of our approach is verified through experiments on widely used benchmark instances involving two distinct versions of loading constraints (unrestricted and sequential versions). Numerical experiments show that the proposed method outperforms all existing methods and improves or matches the majority of best known solutions for both problem versions.