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

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

0.00 Avg rating0 Votes
Article ID: iaor201524334
Volume: 21
Issue: 3
Start Page Number: 375
End Page Number: 398
Publication Date: May 2014
Journal: International Transactions in Operational Research
Authors: , ,
Keywords: packing
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° 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.

Reviews

Required fields are marked *. Your email address will not be published.