期刊名称：Indian Journal of Computer Science and Engineering
印刷版ISSN：2231-3850
电子版ISSN：0976-5166
出版年度：2020
卷号：11
期号：2
页码：168-179
DOI：10.21817/indjcse/2020/v11i2/201102107
出版社：Engg Journals Publications
摘要：The prize-collecting traveling salesman problem is a derivation of the traditional TSP, which is a well-known NP-hard problem. This problem assumes that there are multiple cities that each grant prize money and attempts to determine the path that maximizes prize money while satisfying a predetermined path cost constraint. However, it is difficult for a user to make diverse queries because comparison computations are performed using only a single attribute (i.e., prize money). To solve these problems, this paper proposes a technique that applies multidimensional attributes to each city to allow users to make various queries. Additionally, we adopt Euclidean distance, which is primarily used for similarity problems, to reduce computation time by pruning data that are not relevant to a user’s preferences. By comparing computation speeds under numerous conditions, we experimentally demonstrate the effectiveness of the proposed technique.
