×

zbMATH — the first resource for mathematics

Heuristic solution approaches for the cumulative capacitated vehicle routing problem. (English) Zbl 1360.90036
Summary: Cumulative capacitated vehicle routing problem (CCVRP) is an extension of the well-known capacitated vehicle routing problem, where the objective is minimization of sum of the arrival times at nodes instead of minimizing the total tour cost. This type of routing problem arises when a priority is given to customer needs or dispatching vital goods supply after a natural disaster. This paper focuses on comparing the performances of neighbourhood and population-based approaches for the new problem CCVRP. Genetic algorithm (GA), an evolutionary algorithm using particle swarm optimization mechanism with GA operators, and tabu search (TS) are compared in terms of required CPU time and obtained objective values. In addition, a nearest neighbourhood-based initial solution technique is also proposed within the paper. To the best of authors’ knowledge, this paper constitutes a base for comparisons along with GA, and TS for further possible publications on the new problem CCVRP.

MSC:
90B06 Transportation, logistics and supply chain management
90C59 Approximation methods and heuristics in mathematical programming
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] DOI: 10.1287/opre.12.4.568
[2] DOI: 10.1287/trsc.1070.0209
[3] DOI: 10.1016/j.cor.2009.06.014 · Zbl 1188.90037
[4] NgueveuSU, PrinsC, CalvoRW. An effective evolutionary algorithm for the Cumulative capacitated vehicle routing problem. In: GiacobiniM, BrabazonA, CagnoniS, CaroGAD, EkartA, Esparcia-AlcazarAI, FarooqM, FinkA, editors. Applications of evolutionary computing. Berlin: Springer-Verlag; 2009. p. 778–787.
[5] DOI: 10.1016/j.cor.2011.05.005 · Zbl 1251.90057
[6] DOI: 10.1002/net.3230200605 · Zbl 0744.90063
[7] DOI: 10.1287/opre.41.6.1055 · Zbl 0791.90062
[8] DOI: 10.1016/S0305-0548(03)00158-8 · Zbl 1100.90504
[9] DOI: 10.1007/978-3-540-73556-4_9 · Zbl 1175.90333
[10] DOI: 10.1016/j.jalgor.2005.01.007 · Zbl 1112.68135
[11] DOI: 10.1016/j.ejor.2006.03.071 · Zbl 1146.90497
[12] ChenP, DongX, NiuY. An iterated local search algorithm for the cumulative capacitated vehicle routing problem. In: TanH, editor. Technology for education and learning. Berlin: Springer-Verlag; 2012. p. 575–581.
[13] DOI: 10.1016/j.eswa.2009.06.047 · Zbl 05884177
[14] DOI: 10.1016/S0305-0548(97)00031-2 · Zbl 0889.90119
[15] DOI: 10.1016/j.cor.2012.08.020 · Zbl 1349.90859
[16] LourencoHR, MartinOC, StutzleT. Iterated local search: framework and applications. In: GendreauM, PotvinJY, editors. Handbook of metaheuristics. Berlin: Springer-Verlag; 2010. p. 363–397.
[17] Gen M, Genetic alogirthms and engineering design (1997)
[18] DOI: 10.1287/inte.20.4.74
[19] DOI: 10.1287/ijoc.1.3.190 · Zbl 0753.90054
[20] Glover F, Tabu search, modern heuristic techniques for combinatorial problems (1992)
[21] DOI: 10.1287/mnsc.40.10.1276 · Zbl 0822.90053
[22] DOI: 10.1002/(SICI)1097-0037(199709)30:2<105::AID-NET5>3.0.CO;2-G · Zbl 0885.90037
[23] DOI: 10.1057/palgrave.jors.2601163 · Zbl 1181.90034
[24] DOI: 10.1016/j.ejor.2013.02.053 · Zbl 1317.90006
[25] DOI: 10.1007/BF02023004 · Zbl 0775.90153
[26] DOI: 10.1287/trsc.31.2.170 · Zbl 0886.90070
[27] Badeau P, Trans. Res 5 pp 109– (1997)
[28] DOI: 10.1016/j.ejor.2012.05.025 · Zbl 06119523
[29] DOI: 10.1016/j.cor.2011.09.021 · Zbl 06106564
[30] DOI: 10.1016/S0191-2615(02)00045-0
[31] DOI: 10.1287/ijoc.15.4.333.24890 · Zbl 1238.90141
[32] DOI: 10.1016/j.ejor.2005.01.042 · Zbl 1109.90017
[33] DOI: 10.1016/j.cor.2010.04.008 · Zbl 1231.90078
[34] DOI: 10.1287/trsc.1050.0145
[35] DOI: 10.1002/net.20192 · Zbl 1146.90012
[36] DOI: 10.1057/palgrave.jors.2602405 · Zbl 1144.90312
[37] DOI: 10.1504/IJMHEUR.2010.033123 · Zbl 1219.90018
[38] DOI: 10.1057/palgrave.jors.2602504 · Zbl 1155.90488
[39] DOI: 10.1016/j.eswa.2011.09.111
[40] DOI: 10.1016/j.cor.2011.11.001 · Zbl 1251.90346
[41] Goldberg DE, genetic algorithms in search, optimization, and machine learning (1989) · Zbl 0721.68056
[42] Holland JH, Adaptation in natural and artificial systems (1975)
[43] DOI: 10.1016/j.ipl.2006.02.006 · Zbl 1187.68676
[44] DOI: 10.1016/j.cor.2005.07.025 · Zbl 1163.90357
[45] Dorronsoro B, A grid-based hybrid cellular genetic algorithm for very large scale instances of the CVRP (2007)
[46] DOI: 10.1109/TASE.2009.2019265
[47] DOI: 10.1007/978-3-540-85152-3_4
[48] DOI: 10.1007/s10898-006-9094-0 · Zbl 1145.90010
[49] DOI: 10.1287/opre.1120.1048 · Zbl 1260.90058
[50] DOI: 10.1016/j.cor.2012.07.018 · Zbl 1349.90137
[51] DOI: 10.1109/ICNN.1995.488968
[52] Eberhart RC, A new optimizer using particle swarm theory (1995)
[53] Eberhart RC, Computational ıntelligence PC tools (1996)
[54] Kennedy J, The particle swarm: social adaptation of knowledge (1997)
[55] Kennedy J, Swarm Intelligence (2001)
[56] DOI: 10.1080/02331930902928310 · Zbl 1175.90316
[57] DOI: 10.1016/j.ejor.2007.10.044 · Zbl 1152.90423
[58] DOI: 10.1016/j.cor.2006.12.030 · Zbl 1144.90393
[59] DOI: 10.1016/j.amc.2005.07.042 · Zbl 1137.90503
[60] DOI: 10.1016/j.ejor.2007.08.030 · Zbl 1149.90064
[61] DOI: 10.1016/j.amc.2008.05.086 · Zbl 1175.90187
[62] DOI: 10.1016/j.ipl.2007.03.010 · Zbl 1187.90238
[63] Fang L, Particle swarm optimization with simulated annealing for TSP (2007)
[64] DOI: 10.1016/j.engappai.2010.02.002
[65] DOI: 10.1016/j.eswa.2009.06.085 · Zbl 05884157
[66] DOI: 10.1016/j.amc.2012.08.092 · Zbl 1308.90021
[67] DOI: 10.1016/j.cie.2005.01.018
[68] Kaur A, Int. J. Comput. Appl 27 pp 27– (2011)
[69] Pant M, A new PSO algorithm with crossover operator for global optimization problems, ınnovations in hybrid ıntelligent systems (2007)
[70] Pant M, IAENG IJCS 36 (2009)
[71] Premalatha K, Int. J. Rec. Trends Eng 1 pp 20– (2009)
[72] Park JB, A hybrid particle swarm optimization employing crossover operation for economic dispatch problems with valve-point effects (2007)
[73] Su D, Quantum-behaved particle swarm optimization with crossover operator (2009)
[74] Zhang G, Hybrid genetic algorithm with particle swarm optimization technique (2009)
[75] DOI: 10.1016/j.asoc.2011.11.012
[76] Augerat P, Computational results with a branch and cut code for the capacitated vehicle routing problem, Research report 949-M (1995)
[77] DOI: 10.1057/jors.1969.75
[78] Christofides N, The vehicle routing problem, combinatorial optimization (1979) · Zbl 0413.90075
[79] DOI: 10.1287/opre.42.4.626 · Zbl 0815.90066
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.