期刊名称：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 isa well-known NP-hard problem. This problem assumes that there are multiple cities that each grant prizemoney and attempts to determine the path that maximizes prize money while satisfying a predeterminedpath cost constraint. However, it is difficult for a user to make diverse queries because comparisoncomputations are performed using only a single attribute (i.e., prize money). To solve these problems, thispaper proposes a technique that applies multidimensional attributes to each city to allow users to makevarious 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 comparingcomputation speeds under numerous conditions, we experimentally demonstrate the effectiveness of theproposed technique.
