Covering Salesman Problem with Nodes and Segments
Covering Salesman Problem with Nodes and Segments作者机构：Department of Computer & Information Engineering Nippon Institute of Technology Saitama Japan Department of Electrical and Electronic Engineering Nippon Institute of Technology Saitama Japan
出 版 物：《American Journal of Operations Research》 (美国运筹学期刊（英文）)
年 卷 期：2017年第7卷第4期
页 面：249-262页
学科分类：1002[医学-临床医学] 100214[医学-肿瘤学] 10[医学]
主 题：Covering Salesman Problem Covering Salesman Problem with Nodes and Segments Combinatorial Optimization Problem Local Search Method
摘 要：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.
维普期刊数据库