×

A multi-population cooperative coevolutionary algorithm for multi-objective capacitated arc routing problem. (English) Zbl 1354.90159

Summary: Capacitated Arc Routing Problem (CARP) has drawn much attention during the last few years. In addition to the goal of minimizing the total cost of all the routes, many real-world applications of CARP also need to balance these routes. The Multi-objective CARP (MO-CARP) commonly exists in practical applications. In order to solve MO-CARP efficiently and accurately, this paper presents a Multi-population Cooperative Coevolutionary Algorithm (MPCCA) for MO-CARP. Firstly, MPCCA applies the divide-and-conquer method to decompose the whole population into multiple subpopulations according to their different direction vectors. These subpopulations evolve separately in each generation and the adjacent subpopulations can share their individuals in the form of cooperative subpopulations. Secondly, multiple subpopulations are used to search different objective subregions simultaneously, so individuals in each subpopulation have a different fitness function, which can be modeled as a Single Objective CARP (SO-CARP). The advanced MAENS approach for single-objective CARP can be used to search each objective subregion. Thirdly, the internal elitism archive is used to construct evolutionary pool for each subregion, which greatly speeds up the convergence. Lastly, the fast nondominated ranking and crowding distance of NSGA-II are used for selecting the offspring and keeping the diversity. MPCCA is tested on 91 CARP benchmarks. The experimental results show that MPCCA obtains better generalization performance over the compared algorithms.

MSC:

90C35 Programming involving graphs or networks
90C29 Multi-objective and goal programming
90C59 Approximation methods and heuristics in mathematical programming

Software:

MSOPS-II; HypE; SPEA2; MOEA/D; PAES
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bader, J.; Zitzler, E., HypE: an algorithm for fast hypervolume-based many-objective optimization, Evol. Comput., 19, 1, 45-76 (2011)
[2] Bandyopadhyay, S.; Pal, S.; Aruna, B., Multiobjective GAs, quantitative indices, and pattern classification, IEEE Trans. Syst., Man, Cybernet. Part B, 4, 5, 2088-2099 (2004)
[3] Batista, L.; Campelo, F.; Guimaraes, F.; Ramírez, J., Pareto cone \(ε\)-dominance: improving convergence and diversity in multiobjective evolutionary algorithms, (Evolutionary Multi-Criterion Optimization (2011), Springer: Springer Berlin Heidelberg), 76-90
[4] Bektas, T.; Elmastas, S., Solving school bus routing problems through integer programming, J. Oper. Res. Soc., 58, 12, 1599-1604 (2007) · Zbl 1210.90117
[5] Benavent, E.; Campos, V.; Corberan, A.; Mota, E., The capacitated arc routing problem: lower bounds, Networks, 22, 669 (1992) · Zbl 0762.90077
[6] Beullens, P.; Muyldermans, L.; Cattrysse, D.; Van Oudheusden, D., A guided local search heuristic for the capacitated arc routing problem, Eur. J. Oper. Res., 147, 3, 629-643 (2003) · Zbl 1026.90015
[7] Brandão, J.; Eglese, R., A deterministic tabu search algorithm for the capacitated arc routing problem, Comput. Oper. Res., 35, 4, 1112-1126 (2008) · Zbl 1179.90031
[8] Chakraborty, P.; Das, S.; Roy, G. G.; Abraham, A., On convergence of the multi-objective particle swarm optimizers, Inform. Sci., 181, 1411-1425 (2011) · Zbl 1222.90051
[9] Czyzak, P.; Jaszkiewicz, A., Pareto simulated annealing - a metaheuristic technique for multiple-objective combinatorial optimization, J. Multicriteria Decis. Anal., 7, 34-47 (1998) · Zbl 0904.90146
[11] Deb, K., Multi-Objective Optimization Using Evolutionary Algorithms (2001), Wiley: Wiley Chichester, UK · Zbl 0970.90091
[12] Deb, K.; Agrawal, S.; Pratap, A.; Meyarivan, T., A fast and elitist multi-objective genetic algorithm: NSGA-II, IEEE Trans. Evol. Comput., 6, 2, 182-197 (2002)
[13] Dror, M.; Stern, H.; Trudeau, P., Postman tour on a graph with precedence relation on arcs, Networks, 17, 3, 283-294 (1987) · Zbl 0644.90090
[14] Eglese, R. W., Routeing winter gritting vehicles, Discr. Appl. Math., 48, 3, 231-244 (1994) · Zbl 0790.90031
[15] Ehrgott, M.; Gandibleux, X., A survey and annotated bibliography of multiobjective combinatorial optimization, OR Spectrum, 22, 4, 425-460 (2000) · Zbl 1017.90096
[16] Fonseca, C. M.; Fleming, P. J., On the performance assessment and comparison of stochastic multiobjective optimizers, (Parallel Problem Solving from Nature—PPSN IV, Lecture Notes in Computer Science (1996), Springer: Springer Berlin Heidelberg), 584-593
[17] Gilberto, R. M.; Javier, S.; Xavier, B.; Miguel, M., Design of continuous controllers using a multiobjective differential evolution algorithm with spherical pruning, (Applications of Evolutionary Computation (2010), Springer: Springer Berlin Heidelberg), 532-541
[18] Gibbons, J. D., Nonparametric Statistical Inference (1985), M. Dekker
[19] Goh, C. K.; Tan, K. C., A competitive-cooperative coevolutionary paradigm for dynamic multiobjective optimization, IEEE Trans. Evol. Comput., 13, 1, 103-127 (2009)
[20] Golden, B. L.; Wong, R. T., Capacitated arc routing problems, Networks, 11, 3, 305-316 (1981) · Zbl 0459.90083
[21] Golden, B. L.; DeArmon, J. S.; Baker, E. K., Computational experiments with algorithms for a class of routing problems, Comput. Oper. Res., 10, 1, 47-59 (1983)
[22] Greistorfer, P., A tabu scatter search metaheuristic for the arc routing problem, Comput. Ind. Eng., 44, 2, 249-266 (2003)
[23] Guo, Y. N.; Liu, D. D.; Cheng, J., Multi-population cooperative cultural algorithms, (Bio-Inspired Computing and Applications (2012), Springer: Springer Berlin Heidelberg), 199-206
[24] Hertz, A.; Laporte, G.; Mittaz, M., A tabu search heuristic for the capacitated arc routing Problem, Oper. Res., 48, 1, 129-135 (2000) · Zbl 1106.90384
[25] Hertz, A.; Mittaz, M., A variable neighborhood descent algorithm for the undirected capacitated arc routing problem, Transport. Sci., 35, 4, 425-434 (2001) · Zbl 1069.90517
[26] Hillis, W. D., Co-evolving parasites improve simulated evolution as an optimization procedure, Phys. D: Nonlinear Phenom., 42, 228-234 (1990)
[27] Hughes, E. J., MSOPS-II: a general-purpose many-objective optimiser, IEEE Cong. Evol. Comput., 3944-3951 (2007)
[28] Jiao, L. C.; Wang, H. D.; Shang, R. H.; Liu, F., A co-evolutionary multi-objective optimization algorithm based on direction vectors, Inform. Sci., 228, 90-112 (2013) · Zbl 1293.90066
[29] Knowles, J.; Corne, D., The Pareto archived evolution strategy: a new baseline algorithm for Pareto multiobjective optimisation, IEEE Cong. Evol. Comput., 98-105 (1999)
[31] Lacomme, P.; Prins, C.; Ramdane-Cherif, W., Evolutionary algorithms for periodic arc routing problems, Eur. J. Oper. Res., 165, 2, 535-553 (2005) · Zbl 1066.90006
[32] Lacomme, P.; Prins, C.; Sevaux, M., A genetic algorithm for a bi-objective capacitated arc routing problem, Comput. Oper. Res., 33, 12, 3473-3493 (2006) · Zbl 1094.90054
[33] Lacomme, P.; Prins, C.; Ramdane-Cherif, W., Competitive memetic algorithms for arc routing problems, Ann. Oper. Res., 131, 1, 159-185 (2004) · Zbl 1066.90010
[34] Li, B.; Lin, T. S.; Liao, L.; Fan, C., Genetic algorithm based on multipopulation competitive coevolution, IEEE Cong. Evol. Comput., 225-228 (2008)
[35] Mei, Y.; Tang, K.; Yao, X., Decomposition-based memetic algorithm for multiobjective capacitated arc routing problems, IEEE Trans. Evol. Comput., 15, 2, 151-165 (2011)
[36] Mei, Y.; Tang, K.; Yao, X., A global repair operator for capacitated arc routing problem, IEEE Trans. Syst., Man, Cybernet. Part B, 39, 3, 723-734 (2009)
[37] Messac, A.; Yahaya, A. I.; Mattson, C. A., The normalized normal constraint method for generating the Pareto frontier, Struct. Multidiscip. Optimiz., 25, 2, 86-98 (2003) · Zbl 1243.90200
[38] Mezura-Montes, E.; Miranda-Varela, M. E.; del Carmen Gómez-Ramón, R., Differential evolution in constrained numerical optimization: an empirical study, Inform. Sci., 180, 22, 4223-4262 (2010) · Zbl 1206.90226
[39] Oliver, K.; Koch, P., Rake selection: a novel evolutionary multi-objective optimization algorithm, (KI 2009: Advances in Artificial Intelligence (2009), Springer: Springer Berlin Heidelberg), 177-184
[40] Oliver, S.; Esquivel, X.; Lara, A.; Coello Coello, C. A., Using the averaged hausdorff distance as a performance measure in evolutionary multiobjective optimization, IEEE Trans. Evol. Comput., 16, 4, 504-522 (2012)
[41] Paredis, J., Coevolutionary computation, Artif. Life, 2, 4, 355-375 (1995)
[42] Polacek, M.; Doerner, K. F.; Hartl, R. F.; Maniezzo, V., A variable neighborhood search for the capacitated arc routing problem with intermediate facilities, J. Heuristics, 14, 5, 405-423 (2008) · Zbl 1211.90314
[43] Potter, M.; Jong, K. D., A cooperative coevolutionary approach to function optimization, Parallel Prob. Solv. Nat., Lect. Notes Comput. Sci., 866, 249-257 (1994)
[44] Potter, M.; Jong, K. D., Cooperative coevolution: an architecture for evolving coadapted subcomponents, Evol. Comput., 8, 1, 1-29 (2000)
[45] Potvin, J. Y.; Bengio, S., The vehicle routing problem with time windows. Part II: Genetic search, Informs J. Comput., 8, 165-172 (1996) · Zbl 0866.90058
[46] Qu, B.; Suganthan, P., Multi-objective evolutionary algorithms based on the summation of normalized objectives and diversified selection, Inform. Sci., 180, 3170-3181 (2010)
[47] Rosin, C.; Belew, R., New methods for competitive coevolution, Evol. Comput., 5, 1, 1-29 (1997)
[48] Shang, R. H.; Jiao, L. C.; Liu, F., A novel immune clonal algorithm for MO problems, IEEE Trans. Evol. Comput., 16, 1, 35-49 (2012)
[49] Shi, C.; Yan, Z.; Lü, K.; Shi, Z.; Wang, B., A dominance tree and its application in evolutionary multi-objective optimization, Inform. Sci., 1, 79, 3540-3560 (2009)
[50] Singh, H. K.; Ray, T.; Smith, W., C-PSA: constrained Pareto simulated annealing for constrained multi-objective optimization, Inform. Sci., 180, 2499-2513 (2010)
[51] Srinivas, N.; Deb, K., Muiltiobjective optimization using nondominated sorting in genetic algorithms, Evol. Comput., 2, 3, 221-248 (1994)
[52] Tahk, M. J.; Sun, B. C., Coevolutionary augmented Lagrangian methods for constrained optimization, IEEE Trans. Evol. Comput., 4, 2, 114-124 (2000)
[53] Tan, K. C.; Yang, Y. J.; Goh, C. K., A distributed cooperative coevolutionary algorithm for multiobjective optimization, IEEE Trans. Evol. Computat., 10, 5, 527-549 (2006)
[54] Tang, K.; Mei, Y.; Yao, X., Memetic algorithm with extended neighborhood search for capacitated arc routing problems, IEEE Trans. Evol. Comput., 13, 5, 1151-1166 (2009)
[55] Tavakkoli-Moghaddam, R.; Rahimi-Vahed, A.; Mirzaei, A. H., A hybrid multi-objective immune algorithm for a flow shop scheduling problem with bi-objectives: weighted mean completion time and weighted mean tardiness, Inform. Sci., 177, 22, 5072-5090 (2007) · Zbl 1121.90340
[56] Ulusoy, G., The fleet size and mix problem for capacitated arc routing, Eur. J. Oper. Res., 22, 3, 329-337 (1985) · Zbl 0576.90094
[57] van den Bergh, F.; Engelbrecht, A. P., A cooperative approach to particle swarm optimization, IEEE Trans. Evol. Comput., 8, 3, 225-239 (2004)
[58] Wang, D. L.; Gao, Y., Competitive evolution and coevolution, Ecology, 24, 10, 1182-1186 (2005)
[59] Wang, J.; Peng, H.; Shi, P., An optimal image watermarking approach based on a multi-objective genetic algorithm, Inform. Sci., 181, 5501-5514 (2011)
[61] Yang, Z.; Tang, K.; Yao, X., Large scale evolutionary optimization using cooperative coevolution, Inform. Sci., 178, 2985-2999 (2008) · Zbl 1283.65064
[62] Zhang, Q.; Li, H., MOEA/D: a multi-objective evolutionary algorithm based on decomposition, IEEE Trans. Evol. Comput., 11, 6, 712-731 (2007)
[63] Zitzler, E.; Thiele, L., Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach, IEEE Trans. Evol. Comput., 3, 4, 257-271 (2009)
[65] Zitzler, E.; Thiele, L.; Laumanns, M.; Fonseca, C. M.; da Fonseca, V. G., Performance assessment of multiobjective optimizers: an analysis and review, IEEE Trans. Evol. Comput., 7, 2, 117-132 (2003)
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.