Computational Intelligence - November 2014 - 30

best solutions at about 1024s for instances with 20 customers.
It converges after 2048s for instances of 50 and 75 customers.
VII. Conclusions

We introduce a new variant of the integrated routing and
loading problem, 3L-HFVRP, and generate benchmark
instances for future studies. The vehicle fleet is heterogeneous in capacity, loading space, and fixed and variable costs.
The number of each type of vehicle is unlimited. The customer demand consists of 3D, rectangular, weighted items. It
is a challenging NP-hard problem and has many practical
applications.
We develop a hybrid VNS algorithm to intensively explore
the solution space and an adaptive diversification mechanism is
incorporated to adjust the search trajectory. An extreme pointbased first fit heuristic is frequently invoked to produce the
loading pattern for the candidate solutions. And the loading is
the most time-consuming operator, the data structures Trie
and Fibonacci heap are creatively used to speed up the process,
which dramatically reduces the loading check for the routes.
The proposed algorithm was extensively tested on
instances of the pure HFVRP, 3L-CVRP and 3L-HFVRP.
For the pure HFVRP, the obtained results are quite close to
the optimum. The AVNS outperforms the existing algorithms
and improves several best known results for the 3L-CVRP.
References

[1] A. Hoff, H. Andersson, M. Christiansen, G. Hasle, and A. Løkketangen, "Industrial
aspects and literature survey: Fleet composition and routing," Comput. Oper. Res., vol. 37,
no. 12, pp. 2041-2061, 2010.
[2] G. Fuellerer, K. F. Doerner, R. F. Hartl, and M. Iori, "Metaheuristics for vehicle routing problems with three-dimensional loading constraints," Eur. J. Oper. Res., vol. 201,
no. 3, pp. 751-759, 2010.
[3] P. Toth and D. Vigo, The Vehicle Routing Problem. Philadelphia, PA: Soc. Ind. Appl.
Math., 2002.
[4] B. Golden, A. Assad, L. Levy, and F. Gheysens, "The f leet size and mix vehicle routing
problem," Comput. Oper. Res., vol. 11, no. 1, pp. 49-66, 1984.
[5] É. D. Taillard, "A heuristic column generation method for the heterogeneous f leet
VRP," RAIRO-Oper. Res., vol. 33, no. 1, pp. 1-14, 1999.
[6] E. Choi and D.-W. Tcha, "A column generation approach to the heterogeneous f leet
vehicle routing problem," Comput. Oper. Res., vol. 34, no. 7, pp. 2080-2095, 2007.
[7] J. Brandão, "A deterministic tabu search algorithm for the f leet size and mix vehicle
routing problem," Eur. J. Oper. Res., vol. 195, no. 3, pp. 716-728, June 2009.
[8] C. Duhamel, P. Lacomme, and C. Prodhon, "A hybrid evolutionary local search with
depth first search split procedure for the heterogeneous vehicle routing problems," Eng.
Appl. Artif. Intell., vol. 25, no. 2, pp. 345-358, Mar. 2012.
[9] A. Imran, S. Salhi, and N. A. Wassan, "A variable neighborhood-based heuristic for
the heterogeneous f leet vehicle routing problem," Eur. J. Oper. Res., vol. 197, no. 2, pp.
509-518, 2009.
[10] D. C. Paraskevopoulos, P. P. Repoussis, C. D. Tarantilis, G. Ioannou, and G. P.
Prastacos, "A reactive variable neighborhood tabu search for the heterogeneous f leet vehicle routing problem with time windows," J. Heuristics, vol. 14, no. 5, pp. 425-455,
Oct. 2007.
[11] S. Liu, W. Huang, and H. Ma, "An effective genetic algorithm for the f leet size and
mix vehicle routing problems," Transp. Res. Part E Logist. Transp. Rev., vol. 45, no. 3, pp.
434-445, May 2009.
[12] C. Prins, "Two memetic algorithms for heterogeneous f leet vehicle routing problems," Eng. Appl. Artif. Intell., vol. 22, no. 6, pp. 916-928, 2009.
[13] A. Subramanian, P. H. V. Penna, E. Uchoa, and L. S. Ochi, "A hybrid algorithm for
the heterogeneous f leet vehicle routing problem," Eur. J. Oper. Res., vol. 221, no. 2, pp.
285-295, 2012.
[14] F. Li, B. Golden, and E. Wasil, "A record-to-record travel algorithm for solving the
heterogeneous f leet vehicle routing problem," Comput. Oper. Res., vol. 34, no. 9, pp.
2734-2742, 2007.
[15] X. Li, P. Tian, and Y. Aneja, "An adaptive memory programming metaheuristic for
the heterogeneous fixed f leet vehicle routing problem," Transp. Res. Part E Logist. Transp.
Rev., vol. 46, no. 6, pp. 1111-1127, Nov. 2010.
[16] J. Brandão, "A tabu search algorithm for the heterogeneous fixed f leet vehicle routing
problem," Comput. Oper. Res., vol. 38, no. 1, pp. 140-151, 2011.

30

IEEE ComputatIonal IntEllIgEnCE magazInE | novEmbEr 2014

[17] S. Liu, "A hybrid population heuristic for the heterogeneous vehicle routing problems," Transp. Res. Part E Logist. Transp. Rev., vol. 54, pp. 67-78, Aug. 2013.
[18] A. Bortfeldt and H. Gehring, "A hybrid genetic algorithm for the container loading
problem," Eur. J. Oper. Res., vol. 131, no. 1, pp. 143-161, May 2001.
[19] D. Pisinger, "Heuristics for the container loading problem," Eur. J. Oper. Res., vol.
141, no. 2, pp. 382-392, Sept. 2002.
[20] L. Wei, W.-C. Oon, W. Zhu, and A. Lim, "A reference length approach for the 3D
strip packing problem," Eur. J. Oper. Res., vol. 220, no. 1, pp. 37-47, 2012.
[21] W. Zhu and A. Lim, "A new iterative-doubling greedy-lookahead algorithm for the single
container loading problem," Eur. J. Oper. Res., vol. 222, no. 3, pp. 408-417, Nov. 2012.
[22] M. Gendreau, M. Iori, G. Laporte, and S. Martello, "A tabu search algorithm for a
routing and container loading problem," Transp. Sci., vol. 40, no. 3, pp. 342-350, 2006.
[23] C. D. Tarantilis, E. E. Zachariadis, and C. T. Kiranoudis, "A hybrid metaheuristic
algorithm for the integrated vehicle routing and three-dimensional container-loading
problem," IEEE Trans. Intell. Transport. Syst., vol. 10, no. 2, pp. 255-271, 2009.
[24] W. Zhu, H. Qin, A. Lim, and L. Wang, "A two-stage tabu search algorithm with
enhanced packing heuristics for the 3L-CVRP and M3L-CVRP," Comput. Oper. Res.,
vol. 39, no. 9, pp. 2178-2195, 2012.
[25] A. Bortfeldt, "A hybrid algorithm for the capacitated vehicle routing problem with
three-dimensional loading constraints," Comput. Oper. Res., vol. 39, no. 9, pp. 2248-2257,
Sept. 2012.
[26] Q. Ruan, Z. Zhang, L. Miao, and H. Shen, "A hybrid approach for the vehicle routing problem with three-dimensional loading constraints," Comput. Oper. Res., vol. 40, no.
6, pp. 1579-1589, June 2013.
[27] P. Lacomme, H. Toussaint, and C. Duhamel, "A GRASP#ELS for the vehicle routing problem with basic three-dimensional loading constraints," Eng. Appl. Artif. Intell.,
vol. 26, no. 8, pp. 1795-1810, Sept. 2013.
[28] M. Iori, J.-J. Salazar-González, and D. Vigo, "An exact approach for the vehicle
routing problem with two-dimensional loading constraints," Transp. Sci., vol. 41, no. 2,
pp. 253-264, 2007.
[29] M. Gendreau, M. Iori, G. Laporte, and S. Martello, "A tabu search heuristic for the
vehicle routing problem with two-dimensional loading constraints," Networks, vol. 51,
no. 1, pp. 4-18, 2008.
[30] E. E. Zachariadis, C. D. Tarantilis, and C. T. Kiranoudis, "A guided tabu search for
the vehicle routing problem with two-dimensional loading constraints," Eur. J. Oper.
Res., vol. 195, no. 3, pp. 729-743, 2009.
[31] G. Fuellerer, K. F. Doerner, R. F. Hartl, and M. Iori, "Ant colony optimization for
the two-dimensional loading vehicle routing problem," Comput. Oper. Res., vol. 36, no.
3, pp. 655-673, 2009.
[32] C. Duhamel, P. Lacomme, A. Quilliot, and H. Toussaint, "A multi-start evolutionary local search for the two-dimensional loading capacitated vehicle routing problem,"
Comput. Oper. Res., vol. 38, no. 3, pp. 617-640, 2011.
[33] S. C. H. Leung, X. Zhou, D. Zhang, and J. Zheng, "Extended guided tabu search
and a new packing algorithm for the two-dimensional loading vehicle routing problem,"
Comput. Oper. Res., vol. 38, no. 1, pp. 205-215, 2011.
[34] S. C. H. Leung, J. Zheng, D. Zhang, and X. Zhou, "Simulated annealing for the
vehicle routing problem with two-dimensional loading constraints," Flex. Serv. Manuf. J.,
vol. 22, no. 1, pp. 61-82, 2010.
[35] E. E. Zachariadis, C. D. Tarantilis, and C. T. Kiranoudis, "Integrated distribution
and loading planning via a compact metaheuristic algorithm," Eur. J. Oper. Res., vol. 228,
no. 1, pp. 56-71, Jan. 2013.
[36] S. C. H. Leung, Z. Zhang, D. Zhang, X. Hua, and M. K. Lim, "A meta-heuristic
algorithm for heterogeneous f leet vehicle routing problems with two-dimensional loading constraints," Eur. J. Oper. Res., vol. 225, no. 2, pp. 199-210, 2013.
[37] M. Iori and S. Martello, "Routing problems with loading constraints," TOP, vol. 18,
no. 1, pp. 4-27, 2010.
[38] K. Fleszar, I. H. Osman, and K. S. Hindi, "A variable neighbourhood search algorithm for the open vehicle routing problem," Eur. J. Oper. Res., vol. 195, no. 3, pp.
803-809, 2009.
[39] V. C. Hemmelmayr, K. F. Doerner, and R. F. Hartl, "A variable neighborhood search
heuristic for periodic routing problems," Eur. J. Oper. Res., vol. 195, no. 3, pp. 791-802,
2009.
[40] G. Clarke and J. W. Wright, "Scheduling of vehicles from a central depot to a number
of delivery points," Oper. Res., vol. 12, no. 4, pp. 568-581, Aug. 1964.
[41] M. L. Fredman and R. E. Tarjan, "Fibonacci heaps and their uses in improved network optimization algorithms," J. ACM, vol. 34, no. 3, pp. 596-615, July 1987.
[42] D. Pisinger and S. Ropke, "Large neighborhood search," in Handbook Metaheuristics,
vol. 146, M. Gendreau and J.-Y. Potvin, Eds. Berlin Heidelberg, Germany: SpringerVerlag, 2010, pp. 399-419.
[43] C. Prins, "A simple and effective evolutionary algorithm for the vehicle routing
problem," Comput. Oper. Res., vol. 31, no. 12, pp. 1985-2002, 2004.
[44] T. G. Crainic, G. Perboli, and R. Tadei, "Extreme point-based heuristics for threedimensional bin packing," INFORMS J. Comput., vol. 20, no. 3, pp. 368-384, 2008.
[45] L. Wei, Z. Zhang, and A. Lim. (2014, July). Supplement for 'an adaptive variable
neighborhood search for a heterogeneous f leet vehicle routing problem with three-dimensional loading constraints'. [Online]. Available: http://www.computational-logistics.
org/orlib/3l-hfvrp
[46] P. Penna, A. Subramanian, and L. Ochi, "An iterated local search heuristic for the heterogeneous f leet vehicle routing problem," J. Heuristics, vol. 19, no. 2, pp. 201-232, 2013.
http://www.computational-logistics
Table of Contents for the Digital Edition of Computational Intelligence - November 2014
