Using biased randomization for solving the two-dimensional loading vehicle routing problem with heterogeneous fleet.

*(English)*Zbl 1331.90011Summary: This paper discusses the two-dimensional loading capacitated vehicle routing problem (2L-CVRP) with heterogeneous fleet (2L-HFVRP). The 2L-CVRP can be found in many real-life situations related to the transportation of voluminous items where two-dimensional packing restrictions have to be considered, e.g.: transportation of heavy machinery, forklifts, professional cleaning equipment, etc. Here, we also consider a heterogeneous fleet of vehicles, comprising units of different capacities, sizes and fixed/variable costs. Despite the fact that heterogeneous fleets are quite ubiquitous in real-life scenarios, there is a lack of publications in the literature discussing the 2L-HFVRP. In particular, to the best of our knowledge no previous work discusses the non-oriented 2L-HFVRP, in which items are allowed to be rotated during the truck-loading process. After describing and motivating the problem, a literature review on related work is performed. Then, a multi-start algorithm based on biased randomization of routing and packing heuristics is proposed. A set of computational experiments contribute to illustrate the scope of our approach, as well as to show its efficiency.

##### MSC:

90B06 | Transportation, logistics and supply chain management |

90C59 | Approximation methods and heuristics in mathematical programming |

##### Keywords:

heterogeneous vehicle routing problem; two-dimensional bin packing problem; randomized heuristics; multi-start algorithms
PDF
BibTeX
XML
Cite

\textit{O. Dominguez} et al., Ann. Oper. Res. 236, No. 2, 383--404 (2016; Zbl 1331.90011)

Full Text:
DOI

##### References:

[1] | Baldacci, R; Battarra, M; Vigo, D; Golden, BL (ed.); Raghavan, S (ed.); Wasil, EA (ed.), Routing a heterogeneous fleet of vehicles, 3-27, (2008), New York · Zbl 1187.90038 |

[2] | Baldacci, R; Toth, P; Vigo, D, Exact algorithms for routing problems under vehicle capacity constraints, Annals of Operations Research, 175, 213-245, (2010) · Zbl 1185.90033 |

[3] | Bolduc, M-C; Renaud, J; Boctor, FF, A heuristic for the routing and carrier selection problem, European Journal of Operational Research, 183, 926-932, (2007) · Zbl 1179.90029 |

[4] | Burke, EK; Kendall, G; Whitwell, G, A new placement heuristic for the orthogonal stock-cutting problem, Operations Research, 52, 655-671, (2004) · Zbl 1165.90690 |

[5] | Clarke, G; Wright, JW, Scheduling of vehicles from a central depot to a number of delivery points, Operations Research, 12, 568-581, (1964) |

[6] | Cordeau, JF; Gendreau, M; Hertz, A; Laporte, G; Sormany, JS; Langevin, A (ed.); Riopel, D (ed.), New heuristics for the vehicle routing problem, (2005), Boston · Zbl 1130.90416 |

[7] | Couillard, J; Martel, A, Vehicle fleet planning in the road transportation industry, IEEE Transactions on Engineering Management, 37, 31-36, (1990) |

[8] | Drexl, M, Rich vehicle routing in theory and practice, Logistics Research, 5, 47-63, (2012) |

[9] | Duhamel, C., Lacomme, P., Quilliot, A., Toussaint, H. (2009). 2L-CVRP: A GRASP resolution scheme based on RCPSP. International Conference on Computers & Industrial Engineering. CIE 2009. · Zbl 1155.90331 |

[10] | Duhamel, C; Lacomme, P; Quilliot, A; Toussaint, H, A multi-start evolutionary local search for the two-dimensional loading capacitated vehicle routing problem, Computers & Operations Research, 38, 617-640, (2011) · Zbl 1201.90026 |

[11] | Fuellerer, G; Doerner, K; Hartl, R; Iori, M, Ant colony optimization for the two-dimensional loading vehicle routing problem, Computers & Operations Research, 36, 655-673, (2009) · Zbl 1157.90335 |

[12] | Gendreau, M; Iori, M; Laporte, G; Martello, S, A tabu search heuristic for the vehicle routing problem with two-dimensional loading constraints, Networks, 51, 4-18, (2008) · Zbl 1146.90012 |

[13] | Gendreau, M; Laporte, G; Musaraganyi, C; Taillard, ED, A tabu search heuristic for the heterogeneous fleet vehicle routing problem, Computers & Operations Research, 26, 1153-1173, (1999) · Zbl 0967.90019 |

[14] | Golden, B; Assad, AA; Levy, L; Gheysens, FG, The fleet size and mix vehicle routing problem, Computers & Operations Research, 11, 49-66, (1984) · Zbl 0607.90043 |

[15] | Golden, B; Assad, AA; Wasil, E; Toth, P (ed.); Vigo, D (ed.), Routing vehicles in the real world: applications in the solid waste, beverage, food, dairy, and newspaper industries, 245-286, (2002), Philadelphia · Zbl 1076.90546 |

[16] | Golden, B., Raghavan, S., & Wasil, E. (Eds.). (2008). The Vehicle Routing Problem: Latest Advances and New Challenges. New York: Springer. · Zbl 1142.90004 |

[17] | Hoff, A; Andersson, H; Christiansen, M; Hasle, G; Løkketangen, A, Industrial aspects and literature survey: fleet composition and routing, Computers & Operations Research, 37, 2041-2061, (2010) · Zbl 1231.90091 |

[18] | Iori M (2005). Metaheuristic Algorithms for Combinatorial Optimization Problems. 4OR, 3:163-166. · Zbl 1134.90300 |

[19] | Iori, M; Martello, S, Routing problems with loading constraints, TOP, 18, 4-27, (2010) · Zbl 1279.90146 |

[20] | Iori, M; Salazar, JJ; Vigo, D, An exact approach for the vehicle routing problem with two-dimensional loading constraints, Transportation Science, 41, 253-264, (2007) |

[21] | Juan, A; Faulin, J; Ferrer, A; Lourenço, H; Barrios, B, MIRHA: multi-start biased randomization of heuristics with adaptive local search for solving non-smooth routing problems, TOP, 21, 109-132, (2013) · Zbl 1263.90132 |

[22] | Juan, A; Faulin, J; Jorba, J; Riera, D; Masip, D; Barrios, B, 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, 1085-1097, (2011) |

[23] | Laporte, G, The vehicle routing problem: an overview of exact and approximate algorithms, European Journal of Operational Research, 59, 345-358, (1992) · Zbl 0761.90034 |

[24] | Lee Y H, Kim J I, Kang K H, and Kim K H (2006). A heuristic for vehicle fleet mix problem using tabu search and set partitioning. Technical Report Seoul, South Korea: Yonsei University. · Zbl 1153.90359 |

[25] | Leung, SCH; Zhang, Z; Zhang, D; Hua, X; Lim, MK, A meta-heuristic algorithm for heterogeneous fleet vehicle routing problems with two-dimensional loading constraints, European Journal of Operational Research, 225, 199-210, (2013) |

[26] | Leung, SCH; Zheng, J; Zhang, D; Zhou, X, Simulated annealing for the vehicle routing problem with two-dimensional loading constraints, Flexible Services and Manufacturing Journal, 22, 61-82, (2010) |

[27] | Leung, SCH; Zhou, X; Zhang, D; Zheng, J, Extended guided tabu search and a new packing algorithm for the two-dimensional loading vehicle routing problem, Computers & Operations Research, 38, 205-215, (2010) · Zbl 1231.90096 |

[28] | Lima, CMRdR; Goldbarg, MC; Goldbarg, EFG, A memetic algorithm for the heterogeneous fleet vehicle routing problem, Electronic Notes in Discrete Mathematics, 18, 171-176, (2004) · Zbl 1075.90571 |

[29] | Liu, S; Huang, W; Ma, H, An effective genetic algorithm for the fleet size and mix vehicle routing problem, Transportation Research Part E, 45, 434-445, (2009) |

[30] | Liu, F-H; Shen, S-Y, The fleet size and mix vehicle routing problem with time windows, Journal of the Operational Research Society, 50, 721-732, (1999) · Zbl 1054.90522 |

[31] | Lodi, A; Martello, S; Vigo, D, Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems, INFORMS Journal on Computing, 11, 345-357, (1999) · Zbl 1034.90500 |

[32] | Ochi, LS; Vianna, DS; Drummond, MA; Victor, AO, An evolutionary hybrid metaheuristic for solving the vehicle routing problem with heterogeneous fleet, Lecture Notes in Computer Science, 1391, 187-195, (1998) |

[33] | Ochi, LS; Vianna, DS; Drummond, MA; Victor, AO, A parallel evolutionary algorithm for the vehicle routing problem with heterogeneous fleet, Future Generation Computer Systems, 14, 285-292, (1998) |

[34] | Oppen, J; Løkketangen, A; Desrosiers, J, Solving a rich vehicle routing and inventory problem using column generation, Computers & Operations Research, 37, 1308-1317, (2010) · Zbl 1178.90021 |

[35] | Osman, IH; Salhi, S; Rayward-Smith, VJ (ed.); Osman, IH (ed.); Reeves, CR (ed.); Smith, GD (ed.), Local search strategies for the vehicle fleet mix problem, 131-153, (1996), Wiley |

[36] | Prins, C, Efficient heuristics for the heterogeneous fleet multi trip VRP with application to a large-scale real case, Journal of Mathematical Modelling and Algorithms, 1, 135-150, (2002) · Zbl 1036.90019 |

[37] | Privé, J; Renaud, J; Boctor, F; Laporte, G, Solving a vehicle routing problem arising in soft-drink distribution, Journal of Operational Research Society, 57, 1045-1052, (2006) · Zbl 1171.90341 |

[38] | Rieck, J; Zimmermann, J, A new mixed integer linear model for a rich vehicle routing problem with docking constraints, Annals of Operations Research, 181, 337-358, (2010) · Zbl 1209.90098 |

[39] | Ruiz, R; Maroto, C; Alcaraz, J, A decision support system for a real vehicle routing problem, European Journal of Operational Research, 153, 593-606, (2004) · Zbl 1099.90509 |

[40] | Salhi, S; Sari, M, A multi-level composite heuristic for the multi-depot vehicle fleet mix problem, European Journal of Operational Research, 103, 95-112, (1997) · Zbl 0922.90061 |

[41] | Sbihi, A; Eglese, RW, Combinatorial optimization and Green logistics, Annals of Operations Research, 175, 159-175, (2010) · Zbl 1185.90178 |

[42] | Semet, F; Taillard, E, Solving real-life vehicle routing problems efficiently using tabu search, Annals of Operations Research, 175, 159-175, (1993) |

[43] | Taillard, ED, A heuristic column generation method for the heterogeneous fleet VRP, RAIRO, 33, 1-14, (1999) · Zbl 0992.90008 |

[44] | Tarantilis, CD; Kiranoudis, CT, Boneroute: an adaptive memory-based method for effective fleet management, Annals of Operations Research, 115, 227-241, (2002) · Zbl 1013.90020 |

[45] | Tarantilis, CD; Kiranoudis, CT, A flexible adaptive memory-based algorithm for real-life transportation operations: two case studies from dairy and construction sector, European Journal of Operational Research, 179, 806-822, (2007) · Zbl 1163.90638 |

[46] | Tavakkoli-Moghaddam, R; Safeai, N; Kah, MMO; Rabbani, M, A new capacitated vehicle routing problem with split service for minimizing fleet cost by simulated annealing, Journal of the Franklin Institute, 344, 406-425, (2007) · Zbl 1269.90033 |

[47] | Toth, P., & Vigo, D. (2002). The vehicle routing problem, monographs on discrete mathematics and applications. Philadelphia: SIAM Publishers. |

[48] | Vallejo, M., Vargas, P., and Corne, D. (2012). A fast approximative approach for the vehicle routing problem. 12th Workshop UK on Computational Intelligence (UKCI) pp 1-8. · Zbl 1179.90029 |

[49] | Wang, F; Tao, Y; Shi, N, A survey on vehicle routing problem with loading constraints, International Joint Conference on Computational Sciences and Optimization, 2, 602-606, (2009) |

[50] | Zachariadis, EE; Tarantilis, CD; Kiranoudis, CT, A guided tabu search for the vehicle routing problem with two-dimensional loading constraints, European Journal of Operational Research, 195, 729-743, (2009) · Zbl 1155.90331 |

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.