A biased-randomised large neighbourhood search for the two-dimensional vehicle routing problem with backhauls.

*(English)*Zbl 1346.90100Summary: The two-dimensional loading vehicle routing problem with clustered backhauls (2L-VRPB) is a realistic extension of the classical vehicle routing problem where both delivery and pickup demands are composed of non-stackable items. Despite the fact that the 2L-VRPB can be frequently found in real-life transportation activities, it has not been analysed so far in the literature. This paper presents a hybrid algorithm that integrates biased-randomised versions of vehicle routing and packing heuristics within a Large Neighbourhood Search metaheuristic framework. The use of biased randomisation techniques allows to better guide the local search process. The proposed approach for solving the 2L-VRPB is tested on an extensive set of instances, which have been adapted from existing benchmarks for the two-dimensional loading vehicle routing problem (2L-VRP). Additionally, when no backhauls are considered our algorithm is able to find new best solutions for several 2L-VRP benchmark instances with sequential oriented loading, both with and without items rotation.

##### MSC:

90B06 | Transportation, logistics and supply chain management |

90C59 | Approximation methods and heuristics in mathematical programming |

##### Software:

VRP
PDF
BibTeX
XML
Cite

\textit{O. Dominguez} et al., Eur. J. Oper. Res. 255, No. 2, 442--462 (2016; Zbl 1346.90100)

Full Text:
DOI

##### References:

[1] | Brandão, J., A new tabu search algorithm for the vehicle routing problem with backhauls, European Journal of Operational Research, 173, 540-555, (2006) · Zbl 1109.90017 |

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

[3] | Cáceres-Cruz, J.; Arias, P.; Guimarans, D.; Riera, D.; Juan, A., Rich vehicle routing problem: survey, ACM Computing Surveys, 47, 2, 1-28, (2014) |

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

[5] | Cordeau, J. F.; Gendreau, M.; Hertz, A.; Laporte, G.; Sormany, J. S., New heuristics for the vehicle routing problem, (Langevin, A.; Riopel, D., Logistics systems: Design and optimization, (2005), Springer Boston, MA), 279-297 · Zbl 1130.90416 |

[6] | Deif, I.; Bodin, L., Extensions of the Clarke and wright algorithm for solving the vehicle routing problem with backhauling, Proceedings of the Babson College conference of software uses in transportation and logistics management, 75-96, (1984) |

[7] | Demir, E.; Bektas, T.; Laporte, G., A review of recent research on Green road freight transportation, European Journal of Operational Research, 237, 3, 775-793, (2014) · Zbl 1338.90004 |

[8] | Dominguez, O.; Juan, A.; Barrios, B.; Faulin, J.; Agustin, A., Using biased randomization for solving the two-dimensional loading vehicle routing problem with heterogeneous fleet, Annals of Operations Research, (2014) |

[9] | Dominguez, O.; Juan, A. A.; Faulin, J., A biased-randomized algorithm for the two-dimensional vehicle routing problem with and without item rotations, International Transactions in Operational Research, 21, 375-398, (2014) · Zbl 1291.90034 |

[10] | Duhamel, C.; Lacomme, P.; Quilliot, A.; Toussaint, H., 2L-CVRP: a GRASP resolution scheme based on RCPSP, Proceedings of international conference on computers & industrial engineering, 1094-1099, (2009) |

[11] | 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, 3, 617-640, (2011) · Zbl 1201.90026 |

[12] | Faulin, J.; Juan, A.; Lera, F.; Grasman, S., Solving the capacitated vehicle routing problem with environmental criteria based on real estimations in road transportation: A case study, Procedia - Social and Behavioral Sciences, 20, 323-334, (2011) |

[13] | 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 |

[14] | Gajpal, Y.; Abad, P., Multi-ant colony system (MACS) for a vehicle routing problem with backhauls, European Journal of Operational Research, 196, 102-107, (2009) · Zbl 1156.90318 |

[15] | García-Nájera, A.; Bullinaria, J.; Gutiérrez-Andrade, M., An evolutionary approach for multi-objective vehicle routing problems with backhauls, Computers & Industrial Engineering, 81, 90-108, (2015) |

[16] | 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 |

[17] | Goetschalckx, M.; Jacobs-Blecha, C., The vehicle routing problem with backhauls, European Journal of Operational Research, 42, 39-51, (1989) · Zbl 0669.90074 |

[18] | Golden, B.; Baker, E.; Alfaro, J.; Schaffer, J., The vehicle routing problem with backhauling: two approaches, Proceedings of the XXI annual meeting of the S.E. TIMS, 90-92, (1985) |

[19] | (Golden, B.; Raghavan, S.; Wasil, E., (2008), Springer New York, NY) |

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

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

[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 savings heuristic, Journal of the Operational Research Society, 62, 6, 1085-1097, (2011) |

[23] | Juan, A.; Faulin, J.; Ruiz, R.; Barrios, B.; Gilibert, M.; Vilajosana, X., Using oriented random search to provide a set of alternative solutions to the capacitated vehicle routing problem, (Chinneck, J.; Kristjansson, B.; Saltzman, M., Operations research and cyber-infrastructure, (2009), Springer New York, USA), 331-345 |

[24] | Juan, A.; Goentzel, J.; Bektas, T., Routing fleets with multiple driving ranges: Is it possible to use greener fleet configurations?, Applied Soft Computing, 21, 84-94, (2014) |

[25] | Lahyani, R.; Khemakhem, M.; Semet, F., Rich vehicle routing problems: from a taxonomy to a definition, European Journal of Operational Research, 241, 1, 1-14, (2015) · Zbl 1338.90007 |

[26] | 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 |

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

[28] | Leung, S.; 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, 1, 205-215, (2011) · Zbl 1231.90096 |

[29] | 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 |

[30] | Malapert, A.; Guéret, C.; Jussien, N.; Langevin, A.; Rousseau, L., Two-dimensional pickup and delivery routing problem with loading constraints, Technical report, CIRRELT-2008-37, (2008), CIRRELT, Montréal, Canada |

[31] | Mingozzi, A.; Giorgi, S.; Baldacci, R., An exact method for the vehicle routing problem with backhauls, Transportation Science, 33, 315-329, (1999) · Zbl 1004.90016 |

[32] | Osman, I.; Wassan, N., A reactive tabu search meta-heuristic for the vehicle routing problem with backhauls, Journal of Scheduling, 5, 263-285, (2002) · Zbl 1009.90018 |

[33] | Palhazi Cuervo, D.; Goos, P.; Sörensen, K.; Arráiz, E., An iterated local search algorithm for the vehicle routing problem with backhauls, European Journal of Operational Research, 237, 2, 454-464, (2014) · Zbl 1304.90041 |

[34] | Parragh, S.; Doerner, K.; Hartl, R., A survey on pickup and delivery problems. part I: transportation between customers and depot, Journal für Betriebswirtschaft, 58, 1, 21-51, (2008) |

[35] | Pisinger, D.; Røpke, S., Large neighborhood search, (Gendreau, M.; Potvin, J., Handbook of metaheuristics, (2010), Springer New York, NY), 399-419 |

[36] | Potvin, J.; Duhamel, C.; Guertin, F., A genetic algorithm for vehicle routing with backhauling, Applied Intelligence, 6, 4, 345-355, (1996) |

[37] | Røpke, S.; Pisinger, D., A unified heuristic for a large class of vehicle routing problems with backhauls, European Journal of Operational Research, 171, 750-775, (2006) · Zbl 1116.90019 |

[38] | Toth, P.; Vigo, D., A heuristic algorithm for the vehicle routing problem with backhauls, (Bianco, L.; Thot, P., Advanced methods in transportation analysis, (1996), Springer Berlin, Germany), 585-608 · Zbl 0876.90049 |

[39] | Toth, P.; Vigo, D., An exact algorithm for the vehicle routing problem with backhauls, Transportation Science, 31, 372-385, (1997) · Zbl 0919.90057 |

[40] | Toth, P.; Vigo, D., A heuristic algorithm for the symmetric and asymmetric vehicle routing problem with backhauls, European Journal of Operational Research, 113, 528-543, (1999) · Zbl 0947.90011 |

[41] | Toth, P.; Vigo, D., Vehicle routing: Problems, methods, and applications, (2014), SIAM Publishers Philadelphia, PA · Zbl 1305.90012 |

[42] | Wang, F.; Tao, Y.; Shi, N., A survey on vehicle routing problem with loading constraints, Proceedings of international joint conference on computational sciences and optimization, 2, 602-606, (2009) |

[43] | Wassan, N., Reactive tabu adaptive memory programming search for the vehicle routing problem with backhauls, Journal of the Operational Research Society, 58, 12, 1630-1641, (2007) |

[44] | Wei, L.; Zhang, Z.; Zhang, D.; Lim, A., A variable neighborhood search for the capacitated vehicle routing problem with two-dimensional loading constraints, European Journal of Operational Research, 243, 3, 798-814, (2015) · Zbl 1346.90193 |

[45] | Yano, C.; Chan, T.; Richter, L.; Cutler, T.; Murty, K.; McGettigan, D., Vehicle routing at quality stores, Interfaces, 17, 52-63, (1987) |

[46] | Zachariadis, E.; Kiranoudis, C., An effective local search approach for the vehicle routing problem with backhauls, Expert Systems with Applications, 39, 3, 3174-3184, (2012) |

[47] | Zachariadis, E.; Tarantilis, C.; Kiranoudis, C., 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 |

[48] | Zachariadis, E.; Tarantilis, C.; Kiranoudis, C., Integrated distribution and loading planning via a compact metaheuristic algorithm, European Journal of Operational Research, 228, 1, 56-71, (2013) · Zbl 1332.90361 |

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.