An effective genetic algorithm for solving the capacitated vehicle routing problem with two-dimensional loading constraint

In this article, we focus on the symmetric capacitated vehicle routing problem where customer demand is composed of two-dimensional weighted items. The objective consists in designing a set of trips, starting and terminating at a central depot, that minimise the total transportation cost with a homogenous fleet of vehicles based on a depot node. Items in each vehicle trip must satisfy the two-dimensional orthogonal packing constraint. The capacitated vehicle routing problem with two-dimensional loading constraint is an NP-hard problem of high complexity. Given the importance of this problem, many solution approaches have been developed. However, it still a challenging problem. Then, we propose to use a new heuristic based on an adaptive genetic algorithm in order to find better solution. Our algorithm is tested with 150 benchmark instances and compared with state-of-the-art approaches. Results shown that our proposed approach is competitive in terms of the quality of the solutions found.