×

Swarm intelligence-based hyper-heuristic for the vehicle routing problem with prioritized customers. (English) Zbl 1486.90168

Summary: The vehicle routing problem (VRP) is a combinatorial optimization management problem that seeks the optimal set of routes traversed by a vehicle to deliver products to customers. A recognized problem in this domain is to serve ‘prioritized’ customers in the shortest possible time where customers with known demands are supplied by one or several depots. This problem is known as the Vehicle Routing with Prioritized Customers (VRPC). The purpose of this work is to present and compare two artificial intelligence-based novel methods that minimize the traveling distance of vehicles when moving cargo to prioritized customers. Various studies have been conducted regarding this topic; nevertheless, up to now, few studies used the Cuckoo Search-based hyper-heuristic. This paper modifies a classical mathematical model that represents the VRPC, implements and tests an evolutionary Cuckoo Search-based hyper-heuristic, and then compares the results with those of our proposed modified version of the Clarke Wright (CW) algorithm. In this modified version, the CW algorithm serves all customers per their preassigned priorities while covering the needed working hours. The results indicate that the solution selected by the Cuckoo Search-based hyper-heuristic outperformed the modified Clarke Wright algorithm while taking into consideration the customers’ priority and demands and the vehicle capacity.

MSC:

90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
90B06 Transportation, logistics and supply chain management
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abu-Khzam, F. N., Jahed, K. A., & Mouawad, A. E. (2014). A hybrid graph representation for exact graph algorithms. arXiv preprint arXiv:1404.6399.
[2] Ai, TJ; Kachitvichyanukul, VA, Particle swarm optimization and two solution representations for solving the capacitated vehicle routing problem, Computers & Industrial Engineering, 56, 1, 380-387 (2009) · doi:10.1016/j.cie.2008.06.012
[3] Akpinar, S., Hybrid large neighbourhood search algorithm for capacitated vehicle routing problem, Expert Systems Applications, 61, 28-38 (2016) · doi:10.1016/j.eswa.2016.05.023
[4] Asta, S. & Ozcan, E. (2014). An apprenticeship learning ¨ hyper-heuristic for vehicle routing in hyflex. In IEEE symposium on evolving and autonomous learning systems (EALS) (pp. 65-72).
[5] Baradaran, V.; Shafaei, A.; Hosseinian, AH, Stochastic vehicle routing problem with heterogeneous vehicles and multiple prioritized time windows: Mathematical modeling and solution approach, Computers & Industrial Engineering, 131, 187-199 (2019) · doi:10.1016/j.cie.2019.03.047
[6] Bhargava, V.; Fateen, SEK; Bonilla-Petriciolet, A., Cuckoo search: A new natureinspired optimization method for phase equilibrium calculations, Fluid Phase Equilibria, 337, 191-200 (2013) · doi:10.1016/j.fluid.2012.09.018
[7] Bodin, L.; Golden, B.; Assad, A.; Ball, M., Routing and scheduling of vehicles and crews. The state of the art, Computers & Operations Research, 10, 2, 63-211 (1983) · doi:10.1016/0305-0548(83)90030-8
[8] Bulatović, RR; Dordević, SR; Dordević, VS, Cuckoo search algorithm: A metaheuristic approach to solving the problem of optimum synthesis of a six-bar double dwell linkage, Mechanism and Machine Theory, 61, 1-13 (2013) · doi:10.1016/j.mechmachtheory.2012.10.010
[9] Burke, EK; Hyde, M.; Kendall, G.; Ochoa, G.; Ozcan, E.; Woodward, JR; Grendreau, M.; Potvin, JY, A Classification of hyper-heuristic approaches, Handbook of metaheuristics, international series in operations research and management science, 449-468 (2010), Cham: Springer, Cham
[10] Burke, EK, Hyper-heuristics: A survey of the state of the art, Journal of the Operational Research Society, 64, 1695-1724 (2013) · doi:10.1057/jors.2013.71
[11] Burnwal, S.; Deb, S., Scheduling optimization of flexible manufacturing system using cuckoo search-based approach, The International Journal of Advanced Manufacturing Technology, 64, 5-8, 951-959 (2013) · doi:10.1007/s00170-012-4061-z
[12] Captivo, M.; Clímaco, J.; Figueira, J.; Martins, E.; Santos, JL, Solving multiple criteria 0-1 knapsack problems using a labeling algorithm, Computers & Operations Research, 30, 1865-1886 (2003) · Zbl 1047.90054 · doi:10.1016/S0305-0548(02)00112-0
[13] Chen, A.; Yang, G.; Wu, Z., Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem, Journal of Zhejiang University Science A, 7, 4, 607-614 (2006) · Zbl 1166.90319 · doi:10.1631/jzus.2006.A0607
[14] Chifu, V.; Pop, CB; Salomie, I.; Suia, DS; Niculici, AN; Brazier, FMT, Optimizing the semantic web service composition process using cuckoo search, Intelligent distributed computing, 93-102 (2012), Berlin: Springer, Berlin
[15] Clarke, G.; Wright, J., Scheduling of vehicles from a central depot to a number of delivery points, Operations Research, 12, 4, 568-581 (1964) · doi:10.1287/opre.12.4.568
[16] Comtois, C.; Slack, B.; Rodrigue, JP, The geography of transport systems (2013), London: Routledge, London
[17] Cordeau, JF; Gendreau, M.; Hertz, A.; Laporte, G.; Sormany, JS; Langevin, A.; Riopel, D., New heuristics for the vehicle routing problem, Logistics systems: Design and optimization (2005), Boston: Springer, Boston · Zbl 1130.90416
[18] Côté, J.; Potvin, J.; Gendreau, M., The vehicle routing problem with stochastic two-dimensional items, Transportation Science, 54, 299-564 (2020)
[19] Du, L.; He, R., Combining nearest neighbor search with Tabu search for large-scale vehicle routing problem, Physics Procedia, 25, 1536-1546 (2012) · doi:10.1016/j.phpro.2012.03.273
[20] El Khoury, J.; Akle, B.; Katicha, S.; Ghaddar, A.; Daou, M., A microscale evaluation of pavement roughness effects for asset management, International Journal of Pavement Engineering, 15, 4, 323-333 (2014) · doi:10.1080/10298436.2013.792930
[21] Fink, M.; Desaulniers, G.; Frey, M.; Kiermaier, F.; Kolisch, R.; Soumis, F., Column generation for vehicle routing problems with multiple synchronization constraints, European Journal Operation Research, 272, 699-711 (2019) · Zbl 1403.90107 · doi:10.1016/j.ejor.2018.06.046
[22] Gandomi, A.; Yang, XS; Alavi, A., Cuckoo search algorithm: A metaheuristic approach to solve structural optimization problems, Engineering with Computers, 29, 1, 17-35 (2013) · doi:10.1007/s00366-011-0241-y
[23] Garrido, P. & Castro, C. (2009). Stable solving of cvrps using hyper-heuristics. In Proceedings of the 11th annual conference on genetic and evolutionary computation, GECCO’09 (pp. 255-262), New York, NY, USA, ACM.
[24] Gomez, A. & Salhi, S. (2014). Solving capacitated vehicle routing problem by artificial bee colony algorithm. In 2014 IEEE symposium on computational intelligence in production and logistics systems (CIPLS).
[25] Gounaris, C.; Repoussis, P.; Tarantilis, C.; Wiesemann, W.; Floudas, C., An adaptive memory programming framework for the robust capacitated vehicle routing problem, Transportation Science, 50, 4, 141223041352002 (2014) · doi:10.1287/trsc.2014.0559
[26] Haraty, RA; Mansour, N.; Zeitunlian, H., Metaheuristic algorithm for state-based software testing, Applied Artificial Intelligence, 32, 2, 197-213 (2018) · doi:10.1080/08839514.2018.1451222
[27] IBC. (2019). International Business Corporation. Retrieved May 2019 from http://ibcleb.com/.
[28] Jin, J.; Crainic, TG; Løkketangen, A., A parallel multi-neighborhood cooperative tabu search for capacitated vehicle routing problems, European Journal of Operational Research, 222, 3, 441-451 (2012) · doi:10.1016/j.ejor.2012.05.025
[29] Jin, J.; Crainic, TG; Løkketangen, A., A cooperative parallel metaheuristic for the capacitated vehicle routing problem, Computers & Operations Research, 44, 33-41 (2014) · Zbl 1307.90024 · doi:10.1016/j.cor.2013.10.004
[30] Khoury, J., Amine, K., & Abi Saad, R. (2019). An initial investigation of the effects of a fully automated vehicle fleet on geometric design. Journal of Advanced Transportation. doi:10.1155/2019/6126408.
[31] Kim, B-I; Son, S-J, A probability matrix based particle swarm optimization for the capacitated vehicle routing problem, Journal of Intelligent Manufacturing, 23, 4, 1119-1126 (2012) · doi:10.1007/s10845-010-0455-7
[32] Layeb, A., A novel quantum inspired cuckoo search for knapsack problems, International Journal of Bio-Inspired Computations, 3, 5, 297-305 (2011) · doi:10.1504/IJBIC.2011.042260
[33] Lenstra, JK; Rinnooy Kan, AHG, Complexity of vehicle routing and scheduling problems, Networks, 11, 221-227 (1981) · doi:10.1002/net.3230110211
[34] Marinaki, M.; Marinakis, Y.; Zopounidis, C., Honey bees mating optimization algorithm for financial classification problems, Applied Soft Computing, 10, 3, 806-812 (2010) · doi:10.1016/j.asoc.2009.09.010
[35] Marshall, R., Johnston, M., & Zhang, M. (2014). Hyper-heuristics, grammatical evolution and the capacitated vehicle routing problem. In Proceedings of the companion publication of the 2014 annual conference on genetic and evolutionary computation, GECCO Comp’14 (pp. 71-72), New York, NY, USA: ACM.
[36] Nazif, H.; Lee, LS, Optimised crossover genetic algorithm for capacitated vehicle routing problem, Applied Mathematical Modelling, 36, 5, 2110-2117 (2012) · Zbl 1243.90026 · doi:10.1016/j.apm.2011.08.010
[37] Niu, Y.; Wang, S.; He, J.; Xiao, J., A novel membrane algorithm for capacitated vehicle routing problem, Soft Computing, 19, 2, 471-482 (2015) · doi:10.1007/s00500-014-1266-0
[38] Ouaarab, A.; Ahiod, B.; Yang, XS, Discrete cuckoo search algorithm for the travelling salesman problem, Neural Computational Applications, 24, 1659-1669 (2014) · doi:10.1007/s00521-013-1402-2
[39] Payne, RB; Sorensen, MD, The cuckoos (2005), Oxford: Oxford University Press, Oxford
[40] Shour, A., Danash, K., & Tarhini, A. (2015). Modified clarke wright algorithms for solving the realistic vehicle routing problem. In 2015 3rd international conference on technological advances in electrical, electronics and computer engineering, TAEECE 2015 7113606 (pp. 89-93).
[41] Szeto, WY; Wu, Y.; Ho, SC, An artificial bee colony algorithm for the capacitated vehicle routing problem, European Journal of Operational Research, 215, 1, 126-135 (2011) · doi:10.1016/j.ejor.2011.06.006
[42] Tarhini, A., Makki, J., & Chamsiddine, M. (2014). Scatter search algorithm for the cross-dock door assignment problem. In Proceedings of the mediterranean electrotechnical conference—MELECON 6820575 (pp. 444-450).
[43] Tarhini, A.; Yunis, M.; Chamseddine, M., Natural optimization algorithms for the cross-dock door assignment problem, IEEE Transactions on Intelligent Transportation Systems, 17, 8, 2324-2333 (2016) · doi:10.1109/TITS.2016.2519104
[44] Vazquez, R. A. (2011). Training spiking neural models using cuckoo search algorithm. In Evolutionary computation (CEC), IEEE congress.
[45] Yang, X.-S., Deb, S. (2009). Cuckoo search via Lévy flights. In Proceedings of the world congress on nature and biologically inspired computing (NaBIC), Coimbatore, India, 9-11 December 2009 (pp. 210-214).
[46] Yang, XS; Deb, S., Engineering optimisation by cuckoo search, International Journal of Mathematical Modeling and Numerical Optimization, 1, 330-343 (2010) · Zbl 1279.90204 · doi:10.1504/IJMMNO.2010.035430
[47] Yang, XS; Deb, S., Multiobjective cuckoo search fordesign optimization, Computers & Operations Research, 40, 6, 1616-1624 (2013) · Zbl 1348.90650 · doi:10.1016/j.cor.2011.09.026
[48] Yang, X., Deb, S., Karamanoglu, M., & He, X., (2012). Cuckoo search for business optimization applications. In National conference on computing and communication systems, Durgapur (pp. 1-5).
[49] Yildiz, AR, Cuckoo search algorithm for the selection of optimal machining parameters in milling operations, International Journal of Advanced Manufacturing and Technology, 64, 55-61 (2013) · doi:10.1007/s00170-012-4013-7
[50] Zainudin, S.; Kerwad, M.; Othman, ZA, A water flow-like algorithm for capacitated vehicle routing problem, Journal of Theoretical and Applied Information Technology, 77, 1, 125-135 (2015)
[51] Zhen, L., Modeling of yardcongestion and optimization of yardtemplate in container ports, Transportation Research Part B, 90, 80-104 (2016) · doi:10.1016/j.trb.2016.04.011
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.