This article is cited in 3 papers

Control processes

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

A. O. Zakharov^a, Yu. V. Kovalenko<sup>b

a</sup> St. Petersburg State University, 7–9, Universitetskaya nab., St. Petersburg, 199034, Russian Federation
^b Novosibirsk State University, 1, Pirogova ul., Novosibirsk, 630090, Russian Federation

Abstract: 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.

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

UDC: 519.854

MSC: 90C27, 90C29, 90C59

Received: May 18, 2018
Accepted: September 25, 2018

Language: English

DOI: 10.21638/11701/spbu10.2018.410

Bibliographic databases:

•