×

An effective tabu search approach with improved loading algorithms for the 3L-CVRP. (English) Zbl 1348.90135

Summary: In this paper, we consider the Three-Dimensional Loading Capacitated Vehicle Routing Problem(3L-CVRP) which combines the routing of a fleet of vehicles and the loading of three-dimensional shaped goods into the vehicles while minimizing the total travel distance incurred. Apparently, 3L-CVRP is a combination of capacitated vehicle routing and three-dimensional bin packing problem and thus of high complexity. Different from most of previous works, we propose an innovative approach, called improved least waste heuristic for solving the loading subproblem, which is iteratively invoked by a simple tabu search algorithm for the routing. The good performance in terms of the solution quality and computational efficiency of our approach is shown through the numerical experiments on the benchmark instances from literature.

MSC:

90B06 Transportation, logistics and supply chain management
90C59 Approximation methods and heuristics in mathematical programming

Software:

VRP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Archetti, C.; Speranza, M. G.; Savelsbergh, M. W.P., An optimization-based heuristic for the split delivery vehicle routing problem, Transp Sci, 2, 22-31 (2008)
[3] Baker, B. S.; Coffman, E. G.; Rivest, R. L., Orthogonal packing in two dimensions, SIAM J Comput, 9, 846-855 (1980) · Zbl 0447.68080
[4] Boef, E. D.; Korst, J.; Martello, S.; Pisinger, D.; Vigo, D., Erratum to “the three-dimensional bin packing problem”robot-packable and orthogonal variants of packing problems, Oper Res, 53, 4, 735-736 (2005) · Zbl 1165.90603
[5] Bortfeldt, A., A hybrid algorithm for the capacitated vehicle routing problem with three-dimensional loading constraints, Comput Oper Res, 39, 2248-2257 (2012) · Zbl 1251.90013
[6] Boschetti, M., New lower bounds for the three-dimensional finite bin packing problem, Discret Appl Math, 140, 1-3, 241-258 (2004) · Zbl 1069.90085
[7] Christofides, N.; Whitlock, C., An algorithm for two-dimensional cutting problems, Oper Res, 25, 30-44 (1977) · Zbl 0369.90059
[8] Clarke, G.; Wright, J. W., Scheduling of vehicles from a central depot to a number of delivery points, Oper Res, 12, 4, 568-581 (1964)
[9] Cordeau, J.; Gendreau, M.; Hertz, A.; Laporte, G.; Sormany, J., New heuristics for the vehicle routing problem, (Langevin, A.; Riopel, D., Logistics systems (2005), Kluwer: Kluwer Boston) · Zbl 1130.90416
[10] Cordeau, J.; Laporte, G.; Savelsbergh, M.; Vigo, D., Vehicle routing, (Barnhart, C.; Laporte, G., Transportation, handbooks in operations research and management science, Vol. 14 (2007), Elsevier: Elsevier Amsterdam), 367-428
[11] Crainic, T. G.; Perboli, G.; Tadei, R., Ts2packa two-level tabu search for the three-dimensional bin packing problem, Eur J Oper Res, 195, 3, 744-760 (2009) · Zbl 1161.90012
[12] Crainic, T.; Perboli, G.; Tadei, R., Extreme point-based heuristics for three-dimensional bin packing, INFORMS J Comput, 20, 3, 368-384 (2008) · Zbl 1243.90088
[13] Derigs, U.; Reuter, K., A simple and efficient tabu search heuristic for solving the open vehicle routing problem, J Oper Res Soc, 60, 1658-1669 (2009), (12 pp) · Zbl 1196.90022
[14] Faroe, O.; Pisinger, D.; Zachariasen, M., Guided local search for three-dimensional bin-packing problem, INFORMS J Comput, 15, 3, 267-283 (2003) · Zbl 1238.90112
[15] Fekete, S. P.; Schepers, J., New classes of fast lower bounds for bin packing problems, Math Program, 91, 1, 11-31 (2001) · Zbl 1051.90020
[16] Fleszar, K.; Osman, I. H.; Hindi, K. S., A variable neighbourhood search algorithm for the open vehicle routing problem, Eur J Oper Res, 195, 3, 803-809 (2009) · Zbl 1155.90323
[17] Fuellerer, G., Vehicle routing with multi-dimensional loading constraints (2009), University of Vienna: University of Vienna Vienna, Austria
[18] Fuellerer, G.; Doerner, K. F.; Hartl, R. F.; Iori, M., Ant colony optimization for the two-dimensional loading vehicle routing problem, Comput Oper Res, 36, 3, 655-673 (2009) · Zbl 1157.90335
[19] Fuellerer, G.; Doerner, K. F.; Hartl, R. F.; Iori, M., Metaheuristics for vehicle routing problems with three-dimensional loading constraints, Eur J Oper Res, 201, 751-759 (2009) · Zbl 1173.90511
[20] Fuellerer, G.; Doerner, K.; Hartl, R.; Iori, M., Metaheuristics for vehicle routing problems with loading constraints, Networks, 49, 4, 294-307 (2007) · Zbl 1141.90336
[21] Gendreau, M.; Hertz, A.; Laporte, G., New insertion and post-optimization procedures for the traveling salesman problem, Oper Res, 40, 1086-1094 (1992) · Zbl 0767.90087
[22] Gendreau, M.; Iori, M.; Laporte, G.; Martello, S., A tabu search algorithm for a routing and container loading problem, Transp Sci, 40, 3, 342-350 (2006)
[23] Gendreau, M.; Iori, M.; Laporte, G.; Martello, S., A tabu search heuristic for the vehicle routing problem with two-dimensional loading constraints, Networks, 51, 1, 4-18 (2008) · Zbl 1146.90012
[24] Golden, B. L.; Raghavan, S.; Wasil, E. A., The vehicle routing problemlatest advances and new challenges (2008), Springer
[25] Goncalves, J. F.; Resende, MGC., A biased random key genetic algorithm for 2D and 3D bin packing problems, Int J Prod Econ, 145, 2, 500-510 (2013)
[27] Iori, M., Metaheuristic algorithms for combinatorial optimization problems, 4OR, 3, 163-166 (2005) · Zbl 1134.90300
[28] Iori, M.; Gonzalez, J. J.S.; Vigo, D., An exact approach for the vehicle routing problem with two-dimensional loading constraints, Transp Sci, 41, 2, 253-264 (2007)
[30] Lodi, A.; Martello, S.; Vigo, D., Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems, INFORMS J Comput, 11, 345-357 (1999) · Zbl 1034.90500
[31] Lodi, A.; Martello, S.; Vigo, D., Heuristic algorithms for the three-dimensional bin packing problem, Eur J Oper Res, 141, 410-420 (2002) · Zbl 1081.90612
[32] Martello, S.; Pisinger, D.; Vigo, D., The three-dimensional bin packing problem, Oper Res, 48, 2, 256-267 (2000) · Zbl 1106.90371
[33] Martello, S.; Pisinger, D.; Vigo, D.; Boef, E. D.; Korst, J., Algorithm 864general and robot-packable variants of the three-dimensional bin packing problem, ACM Trans Math Softw, 33, 1 (2007)
[34] Moura, A., A multi-objective genetic algorithm for the vehicle routing with time windows and loading problem, Intell Decis Support, 2, 187-201 (2008)
[35] Moura, A.; Oliveira, J. F., An integrated approach to the vehicle routing and container loading problems, OR Spectr, 31, 4, 775-800 (2009) · Zbl 1175.90045
[36] Parreno, F.; Alvarez-Valdes, R.; Oliveira, J. F.; Tamarit, J. M., A hybrid grasp/vnd algorithm for two- and three-dimensional bin packing, Ann Oper Res, 179, 203-220 (2010) · Zbl 1201.90176
[37] Pisinger, D., Heuristics for the container loading problem, Eur J Oper Res, 141, 382-392 (2002) · Zbl 1081.90613
[38] Ruan, Q.; Zhang, Z.; Miao, L.; Shen, H., A hybrid approach for the vehicle routing problem with three-dimensional loading constraints, Comput Oper Res, 40, 6, 1579-1589 (2013) · Zbl 1348.90120
[39] Seiden; Stee, V., New bounds for multidimensional packing, Algorithmica, 36, 3, 261-293 (2007) · Zbl 1045.68160
[41] Tarantilis, C. D.; Zachariadis, E. E.; Kiranoudis, C. T., A hybrid metaheuristic algorithm for the integrated vehicle routing and three-dimensional container-loading problem, IEEE Trans Intell Transp Syst, 10, 2, 255-271 (2009)
[43] Tricoire, F.; Doerner, K. F.; Hartl, R. F.; Iori, M., Heuristic and exact algorithms for the multi-pile vehicle routing problem, OR Spectr, 33, 4, 931-959 (2011) · Zbl 1229.90039
[45] Wei, L.; Zhang, D.; Chen, Q., A least wasted first heuristic algorithm for the rectangular packing problem, Comput Oper Res, 36, 5, 1608-1614 (2009) · Zbl 1179.90174
[46] Zachariadis, E. E.; Tarantilis, C. D.; Kiranoudis, C. T., A guided tabu search for the vehicle routing problem with two-dimensional loading constraints, Eur J Oper Res, 195, 3, 729-743 (2009) · Zbl 1155.90331
[47] Zhu, W.; Qin, H.; Lim, A.; Wang, L., A two-stage tabu search algorithm with enhanced packing heuristics for the 3l-cvrp and m3l-cvrp, Comput Oper Res, 39, 2178-2195 (2012) · Zbl 1251.90346
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.