Research output: Contribution to journal › Article › peer-review
Construction and reduction of the Pareto set in asymmetric travelling salesman problem with two criteria. / Zakharov, A. O.; Kovalenko, Yu.V.
In: ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. ПРИКЛАДНАЯ МАТЕМАТИКА. ИНФОРМАТИКА. ПРОЦЕССЫ УПРАВЛЕНИЯ, Vol. 14, No. 4, 2018, p. 378-392.Research output: Contribution to journal › Article › peer-review
}
TY - JOUR
T1 - Construction and reduction of the Pareto set in asymmetric travelling salesman problem with two criteria
AU - Zakharov, A. O.
AU - Kovalenko, Yu.V.
N1 - Zakharov A. O., Kovalenko Yu. V. Construction and reduction of the Pareto set in asymmetric travelling salesman problem with two criteria. Vestnik of Saint Petersburg University. Applied Mathematics. Computer Science. Control Processes, 2018, vol. 14, iss. 4, pp. 378–392. https://doi.org/10.21638/11702/spbu10.2018.410
PY - 2018
Y1 - 2018
N2 - 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.
AB - 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.
KW - reduction of the Pareto set
KW - decision maker preferences
KW - multiobjective genetic algorithm
KW - computational experiment
KW - ALGORITHM
KW - INFORMATION
KW - сужение множества Парето
KW - предпочтения ЛПР
KW - многокритериальный генетический алгоритм
KW - вычислительный эксперимент
UR - http://vestnik.spbu.ru/html18/s10/s10v4/10.pdf
U2 - 10.21638/11702/spbu10.2018.410
DO - 10.21638/11702/spbu10.2018.410
M3 - Article
VL - 14
SP - 378
EP - 392
JO - ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. ПРИКЛАДНАЯ МАТЕМАТИКА. ИНФОРМАТИКА. ПРОЦЕССЫ УПРАВЛЕНИЯ
JF - ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. ПРИКЛАДНАЯ МАТЕМАТИКА. ИНФОРМАТИКА. ПРОЦЕССЫ УПРАВЛЕНИЯ
SN - 1811-9905
IS - 4
ER -
ID: 38400053