Covering Salesman Problem with Nodes and Segments
- 1 Department of Computer & Information Engineering, Nippon Institute of Technology, Saitama, Japan
- 2 Department of Electrical and Electronic Engineering, Nippon Institute of Technology, Saitama, Japan
Abstract
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.
- Danzig, G., Fulkerson, R. and Johnson, S. (1954) Solution of a Large Scale Traveling Salesman Problem. Operations Research, 2, 393-410.
- Kirkpatrick, S., Gelatt, C.D. and Vecchi, M.P. (1983) Optimization by Simulated Annealing. Science, 220, 671-680. https://doi.org/10.1126/science.220.4598.671
- Grefenstette, J.J., Gopal, R., Rosmaita, B.J. and Gucht, D.V. (1985) Genetic Algorithms for the Traveling Salesman Problem. Proceedings of the 1st International Conference on Genetic Algorithms, Erlbaum Associates Inc., Hillsdale, 160-168.
- Dorigo, M. and Gambardellab, L.M. (1997) Ant Colonies for the Traveling Salesman Problem. Biosystems, 43, 73-81. https://doi.org/10.1016/S0303-2647(97)01708-5
- Glover, F. (1989) Tabu Search I. ORSA Journal on Computing, 1, 190-206. https://doi.org/10.1287/ijoc.1.3.190
- Glover, F. (1990) Tabu Search II. ORSA Journal on Computing, 2, 4-32. https://doi.org/10.1287/ijoc.2.1.4
- Hasegawa, M., Ikeguchi, T. and Aihara, K. (1997) Combination of Chaotic Neurodynamics with the 2-Opt Algorithm to Solve Traveling Salesman Problems. Physical Review Letters, 79, 2344-2347. https://doi.org/10.1103/PhysRevLett.79.2344
- Current, J.R. and Schilling, D.A. (1989) The Covering Salesman Problem. Transportation Science, 23, 208-213. https://doi.org/10.1287/trsc.23.3.208
- Gurobi Optimizer. http://www.gurobi.com/index
- Johnson, D.S., McGeoch, L.A., Glover, F. and Rego, C. (2000) 8th DIMACS Implementation Challenge: The Traveling Salesman Problem. http://dimacs.rutgers.edu/Challenges/TSP/index.html
- Or., I. (1967) Traveling Salesman-Type Combinatorial Problems and Their Relation to the Logistics of Regional Blood Banking. Ph.D. Thesis, Northwestern University, Illinois.
- Lin, S. and Kernighan, B.W. (1973) An Effective Heuristic Algorithm for the Traveling-Salesman Problem. Operations Research, 21, 498-516. https://doi.org/10.1287/opre.21.2.498
- Held, M. and Karp, R.M. (1970) The Traveling-Salesman Problem and Minimum Spanning Trees. Operations Research, 18, 1138-1162. https://doi.org/10.1287/opre.18.6.1138
- Held, M. and Karp, R.M. (1971) The Traveling-Salesman Problem and Minimum Spanning Trees: Part II. Mathematical Programming, 1, 6-25. https://doi.org/10.1007/BF01584070