Covering Salesman Problem with Nodes and Segments

Takafumi Matsuura¹, Takayuki Kimura²

¹Department of Computer & Information Engineering, Nippon Institute of Technology, Saitama, Japan.
²Department of Electrical and Electronic Engineering, Nippon Institute of Technology, Saitama, Japan.

DOI: 10.4236/ajor.2017.74017                

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.

Keywords

Covering Salesman Problem, Covering Salesman Problem with Nodes and Segments, Combinatorial Optimization Problem, Local Search Method

1. Introduction

The Traveling Salesman Problem (TSP) is one of the most famous combinatorial optimization problems [1] . In the TSP, a set of nodes $V=\left\{1,2,\cdots ,n\right\}$ is provided. Let d_ij be the distance from node i to node j. A salesman starts from a node, visits each node exactly once, and returns to the starting node. The objective of the TSP is to find the shortest-length tour. The TSP has several practical applications, such as drilling, computer wiring, routing, very-large-scale integration design, and job sequencing. To reduce the cost of solving such problems, the development of an algorithm for finding an optimal solution or a near- optimal solution to the TSP has been actively pursued [2] - [7] . Figure 1(a) shows a graphical example of the TSP.

In recent years, several mobile-service cars, for example, mobile libraries, mobile shops, and waste-recovery vehicles, have traveled in our town. In the service systems, the vehicle does not visit all the users to provide the service. A service provider selects stopping places, and the vehicle visits these places to provide the service; the users visit the nearest stopping place to receive the service. If the service provider selects many stopping places, the distances between a user and a stopping place are short. However, the tour of the vehicle is long. Therefore, in the service system, it is important to determine optimal stopping places and an optimal tour. To solve this problem, the Covering Salesman Problem (CSP) has been formulated [8] . In the CSP, a set of nodes $V=\left\{1,2,\cdots ,n\right\}$ is provided, along with the distance d_ij between nodes i and j for all nodes. In addition, the covering distance r is given. The salesman visits a node. The node visited by the salesman can cover other nodes within a radius r. The objective of the CSP is to identify the shortest tour of a subset of all given nodes, such that each node that is not on the tour is within a radius r of a node on the tour [8] . Figure 1(b) shows a graphical example of the CSP.

In this study, we define a new covering problem called the CSP with Nodes and Segments (CSPNS). To illustrate the CSPNS, we consider advertising, which is one of inevitable activities in modern business. It requires a medium for sending promotional messages to targeted people, for example, an advertising truck (AD-truck) that drives on town streets while displaying and broadcasting information about a new product or a local event. The aim of the AD-truck is to promote new products or local events to people on the street. Even though the truck is moving, announcements from the truck can be heard by people on the street. Therefore, the AD-truck does not have to stop for people to see and hear the advertising. This is the most important difference between the CSP and the CSPNS. In the CSP, the nodes on the tour can only cover the nodes not on the tour. However, in the CSPNS, not only the nodes but also the segments on the

Figure 1. Graphical interpretation of (a) Traveling Salesman Problem; (b) Covering Salesman Problem; and (c) Covering Salesman Problem with Nodes and Segments. In these figures, red lines indicate the optimal tours. Red circles represent the visited nodes. The covering area is shown in gray.

tour can cover the nodes not on the tour. Figure 1(c) shows a graphical example of the CSPNS.

The rest of this paper is organized as follows. In Section 2, we formally define the Covering Salesman Problem with Nodes and Segments. We also present the simulation results by using a general purpose mixed integer program solver. Section 3 describes a local search method for solving the CSPNS. Section 4 discusses computational results of the proposed method. Section 5 provides concluding remarks and discusses possible extensions of the proposed method.

2. CSPNS

2.1. Problem Definition

In the CSPNS, a set of nodes $V=\left\{1,2,\cdots ,n\right\}$ , the distance d_ij between nodes i and j, and the perpendicular distance p_ijk between node i and edge (j, k) are given, along with the covering distance of the node, r_n ≥ 0, and that of the edge, r_e ≥ 0. From the data provided, we have two constant values:

$a_{ij}=\{\begin{array}{l}1:\text{ifnode}i\text{iscoveredbynode}j\left(d_{ij}\le r_n\right)\text{,}\hfill \\ 0:\text{otherwise}\hfill \end{array}$ (1)

and

$b_{ijk}=\{\begin{array}{l}1:\text{ifnode}i\text{iscoveredbyedge}\left(j,k\right)\left(p_{ijk}\le r_e\right)\text{,}\hfill \\ 0:\text{otherwise}\text{.}\hfill \end{array}$ (2)

In the CSPNS, node 1 must be visited by the salesman, because node 1 is a depot. The salesman visits some nodes such that all nodes that are not on the tour are within the covering distance r_n of the visited nodes or the covering distance r_e of the edges on the tour. When r_n and r_e are set to zero, this is the TSP, because the salesman must visit all nodes. In the case of r_n ≥ 1 and r_e = 0, the CSPNS becomes the CSP, because the edges on the tour cannot cover the unvisited nodes. We introduce two decision variables:

$y_i=\{\begin{array}{l}1:\text{if}\text{thesalesmanvisitsnode}i\text{,}\hfill \\ 0:\text{otherwise}\hfill \end{array}$ (3)

and

$x_{ij}=\{\begin{array}{l}1:\text{if}\text{the}\text{salesman}\text{moves}\text{directly}\text{from}\text{node}i\text{to}\text{node}j\left(\ne i\right)\text{,}\hfill \\ 0:\text{otherwise}\text{.}\hfill \end{array}$ (4)

If the salesman moves directly from node i to node j (x_ij = 1), node i is the visited node (y_i = 1). In addition, we introduce a counting value f_ij to eliminate a sub-tour. If the salesman does not move from node i to node j, f_ij is set as 0. The value of f_ij is increased by 1 whenever the salesman visits a node. Using this notation, the CSPNS is formulated as follows:

$\text{Minimize}{\displaystyle \underset{i\in V}{\sum }{\displaystyle \underset{j\in V\backslash \left\{i\right\}}{\sum }{d}_{ij}{x}_{ij}}}$ (5)

$\text{Subject}\text{to}{y}_{\text{1}}=1$ (6)

${\displaystyle \underset{h\in V\backslash \left\{i\right\}}{\sum }{x}_{hi}}=y_i\forall i\in V$ (7)

${\displaystyle \underset{j\in V\backslash \left\{i\right\}}{\sum }{x}_{ij}}=y_i\forall i\in V$ (8)

${\displaystyle \underset{j\in V}{\sum }{a}_{ij}{y}_i}+{\displaystyle \underset{j\in V}{\sum }{\displaystyle \underset{k\in V\backslash \left\{j\right\}}{\sum }{b}_{ijk}{x}_{jk}}}\ge 1\forall i\in V$ (9)

${\displaystyle \underset{j\in V\backslash \left\{i\right\}}{\sum }{f}_{ij}{y}_i}-{\displaystyle \underset{h\in V\backslash \left\{i\right\}}{\sum }{f}_{hi}{y}_i}=y_i\forall i\in V$ (10)

$f_{ij}\le \left(n-\text{1}\right)x_{ij}\forall i\in V,\forall j\in V\backslash \left\{i\right\}$ (11)

${\displaystyle \underset{j\in V\backslash \left\{1\right\}}{\sum }{f}_{1j}}=0$ (12)

${\displaystyle \underset{h\in V\backslash \left\{1\right\}}{\sum }{f}_{h1}}={\displaystyle \underset{k\in V}{\sum }{y}_k}-\text{1}$ (13)

$f_{ij}\ge \text{0}\forall i\in V,\forall j\in V\backslash \left\{i\right\}$ (14)

$y_i\in \left\{0,1\right\}\forall i\in V$ (15)

$x_{ij}\in \left\{0,\text{1}\right\}\forall i\in V,\forall j\in V\backslash \left\{i\right\}$ (16)

In this formulation, Equation (5) is the objective function that minimizes the length of the tour. Equations (6)-(16) are constraints of the CSPNS. Equation (6) specifies that the salesman must visit node 1, because node 1 is the depot. Equations (7) and (8) ensure that if the salesman directly moves from node i to node j, nodes i and j become visited nodes. In addition, each visited node should be visited exactly once. Equation (9) enforces the condition that every node is covered by the visited nodes or the edges on the tour. Equations (10)-(14) eliminate sub-tours by using flow formulation. Finally, constraints (15) and (16) define the variables as binary value.

2.2. Computational Simulations Using Mixed-Integer Programming Solver

In this section, we present optimal solutions of the CSPNS obtained using the formulation of the CSPNS and a mixed-integer programming solver. In this simulation, we used a Gurobi Optimizer 6.5.0 on a Mac Pro (3.0-GHz 8-core Intel Xeon E5) with 64 GB of memory running Mac OS X 10.11.5.Gurobi Optimizer is one of the powerful solvers and showed good performances for MIP benchmarks [9] . All simulations were performed using 16 threads, and the solver time limit was set to 12 h. The optimality tolerance of the solver was left as the Gurobi default of 0.0001.

For the benchmark instances, DIMACS [10] , which is a benchmark problem of the TSP, was used. The number of nodes n was set to 50, 60, 70, 80, 90, and 100. In the simulation, 10 instances were created for each number of nodes (the values of the seed of DIMACS were 1 - 10). The covering distances r_n and r_e were set to the same value: 0, 10,000, 20,000, 30,000, 40,000, 50,000, 60,000, 70,000, and 80,000. In the case of r_n = r_e = 0, the problem was the TSP.

Table 1 presents the number of instances that could be solved within the 12 h time limit. As indicated by the table, we obtained feasible solutions for a small size of instances. However, for a large size of instances (n = 90, 100), when the covering area was large, optimal solutions could not be found. In such cases, even though time limit was set to five days, the optimal solution could not be found by the Gurobi optimizer.

Figure 2 shows the average computational times required for an optimal solution to be found by the Gurobi optimizer. From Figure 2, the calculation times for the CSPNS were longer than those for the TSP (r_n = r_e = 0). Although the number of nodes increased slightly, the computational time increased exponentially. The results indicate that there is a need to develop a heuristic method for finding solutions in a reasonable time frame for cases of a large size of instances.

Table 1. The number of instances that could be solved within the 12 h time limit.

Figure 2. Average calculation times for finding an optimal solution by a Gurobi optimizer.

3. Local Search Method

In this section, we develop a heuristic method for determining the optimal or near-optimal tour in the CSPNS. Figure 3 shows an optimal tour of the TSP and the CSPNS. From these optimal tours, the shape of the optimal tour of the TSP (Figure 3(a)) and that of the CSPNS (Figure 3(b) and Figure 3(c)) are very similar. In the proposed method, this similarity is used to devise a short tour for the CSNPS.

Figure 3. Optimal tours for the TSP and CSPNS. The red lines indicate the optimal tours. The red and blue circles represent the visited and unvisited nodes, respectively. The covering area is shown in gray.

In the proposed method, first, an initial tour passing through all the given nodes is constructed; that is, the TSP is solved. Second, the length of the initial tour is improved via local search methods for the TSP, such as the 2-opt, Or-opt [11] , and Lin-Kernighan algorithms [12] [13] [14] . Finally, the tour is improved via local search methods, i.e., eliminating a node, exchanging two nodes, exchanging two edges, and inserting a node. Figure 4 shows graphical explanation of the local search methods used.

Figure 4. Graphical explanation of the local search methods used in the proposed method.

In the CSPNS, the distance from node i to node j is the same as that from node j to node i, and the distances are Euclidean distances in a two-dimensional space, rounded to the nearest integer. Therefore, if a visited node is eliminated from the current tour, the length of a new tour is inevitably shorter than that of the current tour. Eliminating a node involves removing one node from the current tour if a new tour is the feasible: all given nodes can be covered by the visited nodes or the segments on the new tour. Now, nodes i, j, and k are the (i − 1)th, ith, and (i + 1)th visited nodes in the current tour, respectively. Node j is eliminated from the current tour, and nodes i and k are connected, if the new tour is feasible (Figure 4(a)). Exchanging two nodes involves switching a visited node $i\in V^{\prime }$ and an unvisited node $i\in V\backslash V^{\prime }$ (Figure 4(b)). Here, $V^{\prime }$ is the set of visited nodes. Exchanging two edges involves switching an edge (i, j) ( $i,j\in V^{\prime }$ ) and another edge (k, l) ( $k,l\in V\backslash V^{\prime }$ ) (Figure 4(c)). Finally, inserting a node involves adding a visited node $i\in V^{\prime }$ to an edge (j, k) ( $j,k\in V^{\prime }$ ) (Figure 4(d)). Figure 5 shows a flowchart of the proposed method.

4. Results

The proposed method was coded in C and run on a Mac Pro with a 3.0-GHz 8-Core Intel Xeon E5 processor and 64 GB of RAM using the Mac OS X 10.11.5 operating system. To investigate the performance of the method, we solved the benchmark instances used in Section 2.2. The number of nodes n was set as 50, 60, 70, 80, 90, and 100. The cities were uniformly distributed in the 10⁶ × 10⁶ square, and the seed for generating the instances was set as 1 - 3. The covering distances (r_n and r_e) were set as 20,000, 40,000, 60,000, and 80,000.

Figure 5. Flowchart of the proposed method.

In the proposed method, each instance was tested 50 times, and each run stopped when the local optimal solution was found. Initial random tours were constructed 50 times for each instance, and the initial tours were improved via the local search method for the TSP. In these experiments, we used three algorithms: the Lin-Kernighan, 2-opt, and Or-opt algorithms. Among these, the Lin-Kernighan algorithm exhibited the best performance for the TSP. The performance of the proposed method was indicated by the percentage of the gaps between the obtained solutions and the optimal solution obtained using the Gurobi optimizer.

Figure 6 shows calculation costs of the proposed method. According to the results, the proposed method can quickly obtain solutions to the CSPNS. We observe that as the covering area increased, the calculation time increased. This is because eliminating the visited nodes from the tour required considerable time.

Tables 2-7 report on the results of the proposed method for the different number of nodes. The first column is seed of the instance; the second column shows the covering distances r_n and r_e. The third to the 11th columns show the results of the proposed method. Avg, Best, and Worst denote the average, best, and worst gaps, respectively.

From Tables 2-7, for the TSP (r_n = r_e = 0), the Lin-Kernighan algorithm obtained better solutions than the other methods because it is the most powerful local search method. For the CSPNS, when the initial random tours were improved by the Lin-Kernighan algorithm, we obtained the best tour. The method employing the Lin-Kernighan algorithm found an optimal solution for some in

Figure 6. Average calculation times of the proposed method.

Table 2. Performances of the proposed methods for n = 50.

Table 3. Performances of the proposed methods for n = 60.

Table 4. Performances of the proposed methods for n = 70.

Table 5. Performances of the proposed methods for n = 80.

Table 6. Performances of the proposed methods for n = 90.

Table 7. Performances of the proposed methods for n = 100.

stances. In the proposed method, first, the tour of the TSP was constructed; then, the nodes on the tour were deleted. These results indicate that if a good tour of the TSP can be constructed, a good tour of the CSPNS can also be constructed. However, as the covering area increases, the quality of the solution for the CSPNS becomes worse. The proposed method is quickly trapped by local minima because it employs the local search algorithm. Several methods for avoiding local minima have been proposed, such as Tabu Search [5] [6] , simulated annealing [2] , and genetic algorithms [3] . We expect that applying such algorithms to the proposed method can yield better solutions and an improved performance.

5. Conclusions

This paper defines and formulates a new CSP called the CSPNS. We presented mixed-integer linear programming formulations of the CSPNS, and by using the formulations and a mixed-integer programming solver, optimal solutions of the CSPNS were obtained. However, if the number of nodes was large, a long time was needed to find the optimal solution.

To find near-optimal solutions quickly, we proposed a heuristic method employing simple local search methods. Experimental results for a set of benchmark instances show that the proposed method quickly obtained good solutions. For some instances, the optimal solution was found in a few seconds. However, the tour obtained by the proposed method is not a global optimum but a local optimum. In future work, powerful meta-strategies, such as genetic algorithms, Tabu Search, and simulated annealing can be employed to improve the search capability of the proposed method.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Danzig, G., Fulkerson, R. and Johnson, S. (1954) Solution of a Large Scale Traveling Salesman Problem. Operations Research, 2, 393-410.
[2]	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
[3]	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.
[4]	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
[5]	Glover, F. (1989) Tabu Search I. ORSA Journal on Computing, 1, 190-206. https://doi.org/10.1287/ijoc.1.3.190
[6]	Glover, F. (1990) Tabu Search II. ORSA Journal on Computing, 2, 4-32. https://doi.org/10.1287/ijoc.2.1.4
[7]	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
[8]	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
[9]	Gurobi Optimizer. http://www.gurobi.com/index
[10]	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
[11]	Or., I. (1967) Traveling Salesman-Type Combinatorial Problems and Their Relation to the Logistics of Regional Blood Banking. Ph.D. Thesis, Northwestern University, Illinois.
[12]	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
[13]	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
[14]	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