A biased-randomized algorithm for the two-dimensional vehicle routing problem with and without item rotations

Abstract

This paper proposes an efficient algorithm, with a reduced number of parameters, for solving the two-dimensional loading-capacitated vehicle routing problem (2L-CVRP). This problem combines two of the most important issues in logistics, that is, vehicle routing and packing problems. Our approach contemplates unrestricted loading including the possibility of applying 90 degrees rotations to each rectangular-shaped item while loading it into the vehicle, which is a realistic assumption seldom considered in the existing literature. The algorithm uses a multistart approach that is designed to avoid local minima and also to make the algorithm an easily parallelizable one. At each restart, a biased randomization of a savings-based routing algorithm is combined with an enhanced version of a classical packing heuristic to produce feasible good solutions for the 2L-CVRP. The proposed algorithm has been compared with the classical benchmarks for two different 2L-CVRP variants, that is, with and without item rotations. Experimental results show that our approach outperforms several best-known solutions from previous work, both in terms of quality and the computational time needed to obtain them.