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: Vestnik Sankt-Peterburgskogo Universiteta, Prikladnaya Matematika, Informatika, Protsessy Upravleniya, Vol. 14, No. 4, 01.01.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.
PY - 2018/1/1
Y1 - 2018/1/1
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 multiobjective 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 multiobjective 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 - Computational experiment
KW - Decision maker preferences
KW - Multiobjective genetic algorithm
KW - Reduction of the Pareto set
UR - http://www.scopus.com/inward/record.url?scp=85063093698&partnerID=8YFLogxK
U2 - 10.21638/11702/spbu10.2018.410
DO - 10.21638/11702/spbu10.2018.410
M3 - Article
AN - SCOPUS:85063093698
VL - 14
SP - 378
EP - 392
JO - Vestnik Sankt-Peterburgskogo Universiteta, Prikladnaya Matematika, Informatika, Protsessy Upravleniya
JF - Vestnik Sankt-Peterburgskogo Universiteta, Prikladnaya Matematika, Informatika, Protsessy Upravleniya
SN - 1811-9905
IS - 4
ER -
ID: 21450695