×

zbMATH — the first resource for mathematics

A biased-randomized algorithm for the two-dimensional vehicle routing problem with and without item rotations. (English) Zbl 1291.90034
Summary: 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^\circ \) 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.

MSC:
90B06 Transportation, logistics and supply chain management
90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
Software:
SSJ; VRP
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Burke, A new placement heuristic for the orthogonal stock-cutting problem, Operations Research 52 pp 655– (2004) · Zbl 1165.90690 · doi:10.1287/opre.1040.0109
[2] Clarke, Scheduling of vehicles from a central depot to a number of delivery points, Operations Research 12 pp 568– (1964) · doi:10.1287/opre.12.4.568
[3] Cordeau, Logistics Systems: Design and Optimization (2005) · Zbl 1115.90002
[4] Duhamel, International Conference on Computers & Industrial Engineering pp 1094– (2009)
[5] Duhamel, A multi-start evolutionary local search for the two-dimensional loading capacitated vehicle routing problem, Computers & Operations Research 38 (3) pp 617– (2011) · Zbl 1201.90026 · doi:10.1016/j.cor.2010.08.017
[6] Fuellerer, Ant colony optimization for the two-dimensional loading vehicle routing problem, Computers and Operations Research 36 pp 655– (2009) · Zbl 1157.90335 · doi:10.1016/j.cor.2007.10.021
[7] Gendreau, A tabu search heuristic for the vehicle routing problem with two-dimensional loading constraints, Networks 51 pp 4– (2008) · Zbl 1146.90012 · doi:10.1002/net.20192
[8] Golden, The Vehicle Routing Problem: Latest Advances and New Challenges (2008) · Zbl 1142.90004 · doi:10.1007/978-0-387-77778-8
[9] Iori, Metaheuristic algorithms for combinatorial optimization problems, 4OR 3 pp 163– (2005) · Zbl 1134.90300 · doi:10.1007/s10288-005-0052-3
[10] Iori, Routing problems with loading constraints, TOP 18 pp 4– (2010) · Zbl 1279.90146 · doi:10.1007/s11750-010-0144-x
[11] Iori, An exact approach for the vehicle routing problem with two-dimensional loading constraints, Transportation Science 41 (2) pp 253– (2007) · doi:10.1287/trsc.1060.0165
[12] Juan, MIRHA: multi-start biased randomization of heuristics with adaptive local search for solving non-smooth routing problems, TOP 21 (1) pp 109– (2011a) · Zbl 1263.90132 · doi:10.1007/s11750-011-0245-1
[13] Juan, On the use of Monte Carlo simulation, cache and splitting techniques to improve the Clarke and Wright saving heuristics, Journal of the Operational Research Society 62 (6) pp 1085– (2011b) · doi:10.1057/jors.2010.29
[14] Juan, The SR-GCWS hybrid algorithm for solving the capacitated vehicle routing, Applied Soft Computing 10 pp 215– (2010) · Zbl 05739683 · doi:10.1016/j.asoc.2009.07.003
[15] Laporte, The vehicle routing problem: an overview of exact and approximate algorithms, European Journal of Operational Research 59 pp 345– (1992) · Zbl 0761.90034 · doi:10.1016/0377-2217(92)90192-C
[16] L’Ecuyer , P. Meliani , L. Vaucher , J. 2002 SSJ: a framework for stochastic simulation in Java 234 242
[17] Leung, Simulated annealing for the vehicle routing problem with two-dimensional loading constraints, Flexible Services and Manufacturing Journal 22 pp 61– (2010) · Zbl 05898938 · doi:10.1007/s10696-010-9061-4
[18] Leung, Extended guided tabu search and a new packing algorithm for the two-dimensional loading vehicle routing problem, Computers & Operations Research 38 pp 205– (2011) · Zbl 1231.90096 · doi:10.1016/j.cor.2010.04.013
[19] Luke , S. 2011 Essential of Metaheuristics http://cs.gmu.edu/ sean/book/metaheuristics/
[20] Prins, Bio-Inspired Algorithms for the Vehicle Routing Problem, Studies in Computational Intelligence 161 pp 35– (2009) · doi:10.1007/978-3-540-85152-3_2
[21] Riff, A revision of recent approaches for two-dimensional strip-packing problems, Engineering Applications of Artificial Intelligence 198 pp 823– (2009) · doi:10.1016/j.engappai.2008.10.025
[22] Toth, The Vehicle Routing Problem (2002) · Zbl 0979.00026 · doi:10.1137/1.9780898718515
[23] Wang, A survey on vehicle routing problem with loading constraints, International Joint Conference on Computational Sciences and Optimization 2 pp 602– (2009) · doi:10.1109/CSO.2009.127
[24] Zachariadis, A guided tabu search for the vehicle routing problem with two-dimensional loading constraints, European Journal of Operational Research 195 pp 729– (2009) · Zbl 1155.90331 · doi:10.1016/j.ejor.2007.05.058
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.