文章基本信息

标题：Covering Salesman Problem with Nodes and Segments
本地全文：下载
作者：Takafumi Matsuura ; Takayuki Kimura
期刊名称：American Journal of Operations Research
印刷版ISSN：2160-8830
电子版ISSN：2160-8849
出版年度：2017
卷号：7
期号：4
页码：249-262
DOI：10.4236/ajor.2017.74017
语种：English
出版社：Scientific Research Pub
摘要：In the Covering Salesman Problem (CSP), a distribution of nodes is provided, and the objective is to identify the shortest-length tour of a subset of all given nodes such that each node is not on the tour which is within a radius r of any node on the tour. In this paper, we define a new covering problem called the CSP with Nodes and Segments (CSPNS). The main difference between the CSP and the CSPNS is that in the CSPNS, not only the nodes on the tour but also the segments on the tour can cover the nodes not on the tour. We formulated the CSPNS via integer programming and found an optimal solution by using a general-purpose mixed-integer program solver. Benchmark instances of the CSPNS were generated by DIMACS, which is one of the benchmark problems of the Traveling Salesman Problem. Optimal solutions could not be obtained in a reasonable time frame for a large size of instances. Thus, in this study, we developed a simple heuristic method to find good near-optimal solutions to the CSPNS. The proposed heuristic method quickly finds good solutions.
关键词：Covering Salesman ProblemCovering Salesman Problem with Nodes and SegmentsCombinatorial Optimization ProblemLocal Search Method