Construction and reduction of the Pareto set in asymmetric travelling salesman problem with two criteria

A. O. Zakharov ; Yu. V. Kovalenko

Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ, Tome 14 (2018) no. 4, pp. 378-392

Résumé

We consider the bicriteria asymmetric traveling salesman problem (bi-ATSP). The optimal solution to a multicriteria problem is usually supposed to be the Pareto set, which is rather wide in real-world problems. For the first time, we apply to the bi-ATSP the axiomatic approach of the Pareto set reduction proposed by V. Noghin. We identify series of “quanta of information” that guarantee the reduction of the Pareto set for particular cases of the bi-ATSP. An approximation of the Pareto set to the bi-ATSP is constructed by a new multi-objective genetic algorithm. The experimental evaluation carried out in this paper shows the degree of reduction of the Pareto set approximation for various “quanta of information” and various structures of the bi-ATSP instances generated randomly or from TSPLIB problems.

Détail

Keywords: reduction of the Pareto set, decision maker preferences, multiobjective genetic algorithm, computational experiment.

Bibliographie

[1] Ausiello G., Crescenzi P., Gambosi G., Kann V., Marchetti-Spaccamela A., Protasi M., Complexity and approximation, Springer-Verlag Publ., Berlin–Heidelberg, 1999, 524 pp. | MR | Zbl

[2] Ehrgott M., Multicriteria optimization, Springer-Verlag Publ., Berlin–Heidelberg, 2005, 323 pp. | MR | Zbl

[3] Podinovskiy V. V., Noghin V. D., Pareto-optimal solutions of multicriteria problems, Fizmatlit Publ., M., 2007, 256 pp. (In Russian) | MR

[4] Figueira J. L., Greco S., Ehrgott M., Multiple criteria decision analysis: state of the art surveys, Springer-Verlag Publ., New York, 2005, 1048 pp. | MR | Zbl

[5] Noghin V. D., Reduction of the Pareto Set: An axiomatic approach, Springer Intern. Publ., Cham, 2018, 232 pp.

[6] Klimova O. N., “The problem of the choice of optimal chemical composition of shipbuilding steel”, Journal of Computer and Systems Sciences International, 46:6 (2007), 903–907 | DOI | Zbl

[7] Noghin V. D., Prasolov A. V., “The quantitative analysis of trade policy: a strategy in global competitive conflict”, Intern. Journal of Business Continuity and Risk Management, 2:2 (2011), 167–182 | DOI

[8] Angel E., Bampis E., Gourvés L., Monnot J., “(Non)-approximability for the multicriteria TSP(1,2)”, Fundamentals of Computation Theory 2005: 15th Intern. Symposium (Lubeck, Germany, 2005), Lecture Notes in Computer Science, 3623, 329–340 | DOI | MR | Zbl

[9] Buzdalov M., Yakupov I., Stankevich A., “Fast implementation of the steady-state NSGA-II algorithm for two dimensions based on incremental non-dominated sorting”, Proceedings of the 2015 Annual conference on Genetic and Evolutionary Computation (GECCO–15) (Madrid, Spain, 2015), 647–654

[10] Deb K., Pratap A., Agarwal S., Meyarivan T., “A fast and elitist multiobjective genetic algorithm: NSGA-II”, IEEE Transactions on Evolutionary Computation, 6:2 (2002), 182–197 | DOI

[11] Li H., Zhang Q., “Multiobjective optimization problems with complicated Pareto sets, MOEA/D and NSGA-II”, IEEE Transactions on Evolutionary Computation, 13:2 (2009), 284–302 | DOI

[12] Yuan Y., Xu H., Wang B., “An improved NSGA-III procedure for evolutionary many-objective optimization”, Proceedings of the 2014 Annual conference on Genetic and Evolutionary Computation (GECCO–14) (Vancouver, BC, Canada, 2014), 661–668

[13] Zitzler E., Brockhoff D., Thiele L., “The hypervolume indicator revisited: On the design of Pareto-compliant indicators via weighted integration”, Proceedings of conference on Evolutionary Multi-Criterion Optimization, Lecture Notes in Computer Science, 4403, Springer Publ., Berlin, 2007, 862–876 | DOI | MR

[14] Zitzler E., Laumanns M., Thiele L., “SPEA2: Improving the strength Pareto evolutionary algorithm”, Evolutionary Methods for Design, Optimization and Control with Application to Industrial Problems, Proceedings of EUROGEN 2001 conference (Athens, Greece, 2001), 95–100

[15] Garcia-Martinez C., Cordon O., Herrera F., “A taxonomy and an empirical analysis of multiple objective ant colony optimization algorithms for the bi-criteria TSP”, European Journal of Operational Research, 180 (2007), 116–148 | DOI | Zbl

[16] Psychas I. D., Delimpasi E., Marinakis Y., “Hybrid evolutionary algorithms for the multiobjective traveling salesman problem”, Expert Systems with Applications, 42:22 (2015), 8956–8970 | DOI

[17] Reinelt G., “TSPLIB — a traveling salesman problem library”, ORSA Journal on Computing, 3:4 (1991), 376–384 | DOI | MR | Zbl

[18] Zakharov A. O., Kovalenko Yu. V., “Reduction of the Pareto set in bicriteria assymmetric traveling salesman problem”, OPTA-2018, Communications in Computer and Information Science, 871, eds. A. Eremeev, M. Khachay, Y. Kochetov, P. Pardalos, Springer Intern. Publ., Cham, 2018, 93–105 | DOI

[19] Noghin V. D., “Reducing the Pareto set algorithm based on an arbitrary finite set of information “quanta””, Scientific and Technical Information Processing, 41:5 (2014), 309–313 | DOI

[20] Klimova O. N., Noghin V. D., “Using interdependent information on the relative importance of criteria in decision making”, Computational Mathematics and Mathematical Physics, 46:12 (2006), 2080–2091 | DOI | MR

[21] Noghin V. D., “Reducing the Pareto set based on set-point information”, Scientific and Technical Information Processing, 38:6 (2011), 435–439 | DOI

[22] Zakharov A. O., “Pareto-set reduction using compound information of a closed type”, Scientific and Technical Information Processing, 39:5 (2012), 293–302 | DOI

[23] Emelichev V. A., Perepeliza V. A., “Complexity of vector optimization problems on graphs”, Optimization: A Journal of Mathematical Programming and Operations Research, 22:6 (1991), 906–918 | MR

[24] Vinogradskaya T. M., Gaft M. G., “The least upper estimate for the number of nondominated solutions in multicriteria problems”, Automation and Remote Control, 9 (1974), 111–118 (In Russian) | MR | Zbl

[25] Reeves C. R., “Genetic algorithms for the operations researcher”, INFORMS Journal on Computing, 9:3 (1997), 231–250 | DOI | MR | Zbl

[26] Eremeev A. V., Kovalenko Y. V., “Genetic algorithm with optimal recombination for the asymmetric travelling salesman problem”, Large-Scale Scientific Computing 2017, Lecture Notes of Computer Science, 10665, 2018, 341–349 | DOI | MR

[27] Whitley D., Starkweather T., McDaniel S., Mathias K., “A comparison of genetic sequencing operators”, Proceedings of the Fourth Intern. conference on Genetic Algorithms (San Diego, California, USA, 1991), 69–76

[28] Radcliffe N. J., “The algebra of genetic algorithms”, Annals of Mathematics and Artificial Intelligence, 10:4 (1994), 339–384 | DOI | MR | Zbl

[29] Jaszkiewicz A., Zielniewicz P., “Pareto memetic algorithm with path relinking for bi-objective traveling salesperson problem”, European Journal of Operational Research, 193 (2009), 885–890 | DOI | MR | Zbl

[30] Kumar R., Singh P. K., “Pareto evolutionary algorithm hybridized with local search for bi-objective TSP”, Hybrid Evolutionary Algorithms, Studies in Computational Intelligence, 75, eds. A. Abraham, C. Grosan, H. Ishibuchi, Springer Publ., Berlin–Heidelberg, 2007, 361–398

[31] Lust T., Teghem J., “The multiobjective traveling salesman problem: A survey and a new approach”, Advances in Multiobjective Nature Inspired Computing, Studies in Computational Intelligence, 272, eds. C. A. Coello Coello, C. Dhaenens, L. Jourdan, Springer Publ., Berlin–Heidelberg, 2010, 119–141 | Zbl

[32] Multiobjective optimization library, (accessed: 09.02.2018) http://home.ku.edu.tr/m̃oolibrary/