×

Testing local search move operators on the vehicle routing problem with split deliveries and time windows. (English) Zbl 1348.90627

Summary: The vehicle routing problem (VRP) is an important transportation problem. The literature addresses several extensions of this problem, including variants having delivery time windows associated with customers and variants allowing split deliveries to customers. The problem extension including both of these variations has received less attention in the literature. This research effort sheds further light on this problem. Specifically, this paper analyzes the effects of combinations of local search (LS) move operators commonly used on the VRP and its variants. We find when paired with a MAX-MIN Ant System constructive heuristic, Or-opt or 2-opt\(\ast\) appear to be the ideal LS operators to employ on the VRP with split deliveries and time windows with Or-opt finding higher quality solutions and 2-opt\(\ast\) requiring less run time.

MSC:

90C49 Extreme-point and pivoting methods
90C59 Approximation methods and heuristics in mathematical programming
90B06 Transportation, logistics and supply chain management

Software:

MACS-VRPTW
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Laporte, G., What you should know about the vehicle routing problem, Nav Res Logist, 54, 8, 811-819 (2007) · Zbl 1135.90308
[2] Archetti, C.; Savelsbergh, M. W.; Speranza, M. G., To split or not to split: that is the question, Transp Res Part E, 44, 114-123 (2008)
[3] Nowak, M.; Ergun, O.; White, C. C.I., Pickup and delivery with split loads, Transp Sci, 42, 1, 32-43 (2008)
[4] Nowak, M.; Ergun, O.; White, C. C.I., An empirical study on the benefit of split loads with the pickup and delivery problem, Eur J Oper Res, 198, 734-740 (2008) · Zbl 1176.90058
[5] Nagy, G.; Wassan, N. A.; Speranza, M. G.; Archetti, C., The vehicle routing problem with divisible deliveries and pickups, Transp Sci, 1-24 (2014), (vol. articles in advance)
[7] Archetti, C.; Speranza, M., Vehicle routing problems with split deliveries, Int Trans Oper Res, 19, 3-22 (2012) · Zbl 1267.90030
[8] Feillet, D.; Dejax, P.; Gendreau, M.; Gueguen, C., Vehicle routing with time windows and split deliveries (2002), Laboratoire d׳Informatique d׳Avignon, Universite d’Avignon: Laboratoire d׳Informatique d׳Avignon, Universite d’Avignon Avignon, France
[9] Belfiore, P.; Tsugunobu, H.; Yoshizaki, Y., Scatter search for vehicle routing problem with time windows and split deliveries, (Caric, T.; Gold, H., Vehicle routing problem (2008), I-Tech: I-Tech Vienna), 142
[10] Frizzell, P.; Giffin, J., The split delivery vehicle scheduling problem with time windows and grid network distances, Comput Oper Res, 22, 6, 655-667 (1995) · Zbl 0827.90072
[11] Ho, S.; Haugland, D., A tabu search heuristic for the vehicle routing problem with time windows and split deliveries, Comput Oper Res, 31, 1947-1964 (2004) · Zbl 1074.68614
[12] Campos, G. G.; Yoshizaki, H. T.Y.; Belfiore, P. P., Genetic algorithms and parallel computing for the vehicle routing problem with time windows and split deliveries, Manag Prod, 13, 2, 271-281 (2006)
[13] Dror, M.; Trudeau, P., Savings by split delivery routing, Transp Sci, 23, 141-145 (1989) · Zbl 0668.90044
[14] Aleman, R. E.; Zhang, X.; Hill, R. R., An adaptive memory algorithm for the split delivery routing problem, J Heuristics, 16, 3, 441-473 (2010) · Zbl 1187.90036
[15] Derigs, U.; Li, B.; Vogel, U., Local search-based metaheuristics for the split delivery vehicle routing problem, J Oper Res Soc, 61, 1356-1364 (2010)
[16] Braysy, O.; Gendreau, M., Vehicle routing problem, Part I: route construction and local search algorithms, Transp Sci, 39, 1, 104-118 (2005)
[18] Zhang, X.; Wang, J.-Q., Hybrid ant algorithm and applications for vehicle routing problem, Phys Proc, 25, 1892-1899 (2012)
[19] Yu, B.; Yang, Z.-Z.; Yao, B., An improved ant colony optimization for vehicle routing problem, Eur J Oper Res, 196, 171-176 (2009) · Zbl 1156.90434
[20] Gambardella, L. M.; Taillard, E.; Agazzi, G., MACS-VRPTW: a multiple ant colony system for vehicle routing problems with time windows, New Ideas in Optimization (1999)
[21] Ding, Q.; Hu, X.; Sun, L.; Wang, Y., An improved ant colony optimization and its application to vehicle routing problem with time windows, Neurocomputing, 98, 101-107 (2012)
[22] Sodsoon, S.; Changyom, P., Max-Min Ant System (MMAS) for vehicle routing problem with time windows, KKU Eng J, 38, 3, 313-323 (2011)
[23] Kytojoki, J.; Nuortio, T.; Braysy, O.; Gendreau, M., An efficient variable neighborhood search heuristic for very large scale vehicle routing problems, Comput Oper Res, 34, 2743-2757 (2007) · Zbl 1141.90429
[24] Stutzle, T., Local search algorithms for combinatorial problems: analysis, improvements, and new applications, Darmstadt, Germany (1998), Technical University of Darmstadt
[25] Van Breedam, A., An analysis of the behavior of heuristics for the vehicle routing Problem for a selection of problems with vehicle-related, customer-related, and time-related constraints (1994), University of Antwerp: University of Antwerp Antwerp, Belgium
[26] Bell, J. E.; McMullen, P. R., Ant colony optimization techniques for the vehicle routing problem, Adv Eng Inf, 18, 41-48 (2004)
[27] El-Sherbeny, N. A., Vehicle routing with time windows: an overview of exact, heuristic and metaheuristic methods, J King Saud Univ, 22, 123-131 (2010)
[28] Dorigo, M., Optimization, learning, and natural algorithms (1992), Politecnico di Milano: Politecnico di Milano Milan, Italy
[29] Dorigo, M.; Stutzle, T., Ant colony optimization: overview and recent advances, Handbook of metaheuristics, 227-263 (2010), Springer: Springer US
[31] Stutzle, T.; Hoos, H. H., MAX-MIN ant system, Future Gener Comput Syst, 16, 889-914 (2000)
[32] Stutzle, T.; Dorigo, M., a short convergence proof for a class of ant colony optimization algorithms, IEEE Trans Evol Comput, 6, 4, 358-365 (2002)
[33] Mazzeo, S.; Loiseau, I., An ant colony algorithm for the capacitated vehicle routing, Electron Notes Discret Math, 18, 181-186 (2004) · Zbl 1075.90568
[35] Pelligrini, P.; Favaretto, D.; Moretti, E., On MAX-MIN ant system׳s parameters, (Dorigo, M.; Gambardella, L. M.; Birattari, M.; Martinoli, A.; Poli, R.; Stutzle, T., Ant colony and swarm intelligence (2006), Springer: Springer Heidelberg), 203-214
[36] Solomon, M. M., Algorithms for the vehicle routing and scheduling problems with time window constraints, Oper Res, 35, 2, 254-265 (1987) · Zbl 0625.90047
[37] Boudia, M.; Prins, C.; Reghioui, M., An effective memetic algorithm with population management for the split delivery vehicle routing problem, (Bartz-Beielstein, T.; Aguilera, M. J.B.; Blum, C.; Naujoks, B.; Roli, A.; Rudolph, G.; Sampels, M., Hybrid metaheuristics, lecture notes in computer science, 4771 (2007), Springer: Springer Berlin), 16-30
[38] Mota, E.; Campos, V.; Corberan, A., A new metaheuristic for the vehicle routing problem with split demands, Lecture notes in computer science, 4446, 121-129 (2007), Springer: Springer Berlin
[39] Wilck, J. H.I.; Cavalier, T. M., A construction heuristic for the split delivery vehicle routing problem, Am J Oper Res, 2, 153-162 (2012)
[40] Duda, R. O.; Hart, P. E.; Stork, D. G., Pattern classification, 550-556 (2001), Wiley-Interscience: Wiley-Interscience New York
[42] Dunnett, C. W., A multiple comparison procedure for comparing several treatments with a control, J Am Stat Assoc, 50, 272, 1096-1121 (1955) · Zbl 0066.12603
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.