The Covering Salesman Problem

Problem definition:

The Covering Salesman Problem (CSP) is an NP-hard combinatorial optimization problem proposed by Current and Schilling [1] and it can be defined as follows. Consider an undirected graph G(V, E), where V is the set of vertices and E is the set of edges. Each edge e ∈ E is associated with a non-negative cost ce. For each vertex v ∈ V, C(v) is the set of vertices that cover v and D(v) is the set of vertices that are covered by v. It is considered that v ∈ C(v) and v ∈ D(v), ∀ v ∈ V. An optimal solution to the CSP is a minimum length Hamiltonian cycle (tour) over a subset of vertices that covers all vertices in G.

Known solution methodologies:

LS2: Local search [2]

SN: Heuristic embedded within an integer linear programming (ILP) framework [3]

SRS: Integer linear programming formulation [4]

Hybrid ACO: Hybrid heuristic combining ant colony optimization and dynamic programming [4]

MS-ILS: Multi-start Iterated Local Search [5]

PVNS: Parallel variable neighborhood search [6]

ABC and GEA: Artificial bee colony algorithm and genetic algorithm (GA) [7]

HEA: Hybrid evolutionary algorithm [8]

CSP-I, CSP-&Fvp, CSP-I&Fh, CSP-I&Fvp-X and CSP-I&Fh-X: Branch-and-Cut algorithms [9]


Bibliography:

[1] J. R. Current, D. A. Schilling, The covering salesman problem , Transportation science 23 (3) (1989) 208–213.

[2] B. Golden, Z. Naji-Azimi, S. Raghavan, M. Salari, P. Toth, The generalized covering salesman problem , INFORMS Journal on Computing, v. 24, n. 4, p. 534-553, 2012.

[3] M. Salari, Z. Naji-Azimi, An integer programming-based local search for the covering salesman problem , Computers & Operations Research 39 (11)(2012) 2594–2602.

[4] M. Salari, M. Reihaneh, M. S. Sabbagh, Combining ant colony optimization algorithm and dynamic programming technique for solving the covering salesman problem , Computers & Industrial Engineering 83 (2015) 244–251.

[5] P. Venkatesh, G. Srivastava, A. Singh, A multi-start iterated local search algorithm with variable degree of perturbation for the covering salesman problem , Harmony Search and Nature Inspired Optimization Algorithms. Springer, Singapore, 2019. p. 279-292.

[6] X. Zang, L. Jiang, M. Ratli, B. Ding, A parallel variable neighborhood search for solving covering salesman problem , Optimization Letters (2020) 1–16.

[7] V. Pandiri, A. Singh, A. Rossi, Two hybrid metaheuristic approaches for the covering salesman problem , Neural Computing and Applications (2020) 1–21.

[8] Y. Lu, U. Benlic, Q. Wu, A highly effective hybrid evolutionary algorithm for the covering salesman problem , Information Sciences 564 (2021) 144–162.

[9] L. M. Maziero, F. L. Usberti, C. Cavellucci, Branch-and-Cut algorithms for the covering salesman problem , RAIRO-Oper. Res. 57(3) (2023), 1149-1166.


Download:

The CSP instances [4] and the B&C [9] source-code can be downloaded here.


Tables of results:

The results of the computational experiments for the small, medium and large instances are reported by the following table.

BestUB: Best upper bound known in the literature (References [2], [3], [4], [5], [6], [7], and [8]);

LB: Best lower bound obtained in one hour of execution;

Gap: Deviation of best upper bound from best lower bound (%);

Time: Execution time in seconds.

The SRS has not been tested with medium and large instances. For the column group SRS the symbol '-' means that no lower bounds are known.

Results for small and medium instances created by Salari et al. [4]
SRS CSP-I CSP-I&Fvp CSP-I&Fh CSP-I&Fvp-X CSP-I&Fh-X
Instance NC BestUB LB Gap Time LB Gap Time LB Gap Time LB Gap Time LB Gap Time LB Gap Time
eil51 7 164 164 0 149 164 0 2 164 0 4 164 0 3 164 0 3 164 0 3
9 159 159 0 220 159 0 1 159 0 2 159 0 2 159 0 4 159 0 3
11 147 147 0 681 147 0 1 147 0 2 147 0 2 147 0 5 147 0 4
berlin52 7 3887 3887 0 140 3887 0 2 3887 0 2 3887 0 2 3887 0 4 3887 0 3
9 3430 3430 0 212 3430 0 1 3430 0 3 3430 0 2 3430 0 6 3430 0 3
11 3262 3262 0 255 3262 0 1 3262 0 2 3262 0 2 3262 0 4 3262 0 4
st70 7 288 288 0 490 288 0 3 288 0 7 288 0 5 288 0 7 288 0 7
9 259 259 0 1391 259 0 3 259 0 7 259 0 6 259 0 13 259 0 9
11 247 218 13.14 3600 247 0 3 247 0 7 247 0 5 247 0 14 247 0 9
eil76 7 207 193 7.45 3600 207 0 6 207 0 29 207 0 9 207 0 15 207 0 12
9 185 161 14.65 3600 185 0 10 185 0 10 185 0 9 185 0 13 185 0 12
11 170 145 17.08 3600 170 0 6 170 0 8 170 0 7 170 0 15 170 0 13
pr76 7 50275 50275 0 2488 50275 0 7 50275 0 8 50275 0 6 50275 0 12 50275 0 8
9 45348 42935 5.62 3600 45348 0 6 45348 0 32 45348 0 10 45348 0 16 45348 0 14
11 43028 39022 10.27 3600 43028 0 28 43028 0 17 43028 0 46 43028 0 27 43028 0 28
rat99 7 486 433 12.21 3600 486 0 238 486 0 19 486 0 17 486 0 33 486 0 17
9 455 377 20.73 3600 438 3.88 3600 455 0 30 455 0 27 455 0 28 455 0 29
11 444 350 26.81 3600 444 0 203 444 0 32 444 0 138 444 0 37 444 0 197
kroA100 7 9674 9177 5.42 3600 9674 0 15 9674 0 18 9674 0 27 9674 0 27 9674 0 30
9 9159 7938 15.38 3600 9159 0 154 9159 0 28 9159 0 2040 9159 0 36 9159 0 2230
11 8901 8593 3.59 3600 8608 3.40 3600 8901 0 45 8640 3.02 3600 8901 0 79 8801 1.14 3600
kroB100 7 9537 - - 3600 9537 0 45 9537 0 22 9537 0 20 9537 0 26 9537 0 23
9 9240 7678 20.34 3600 9240 0 363 9240 0 21 9240 0 21 9240 0 31 9240 0 28
11 8842 - - 3600 8842 0 141 8842 0 25 8842 0 29 8842 0 40 8842 0 36
kroC100 7 9723 8564 13.54 3600 9723 0 561 9723 0 107 9723 0 102 9723 0 67 9723 0 92
9 9171 7663 19.68 3600 8920 2.81 3600 9171 0 45 9171 0 783 9171 0 123 9171 0 972
11 8632 7590 13.73 3600 8632 0 254 8632 0 38 8632 0 820 8632 0 222 8632 0 870
kroD100 7 9626 8724 10.34 3600 9626 0 59 9626 0 17 9626 0 20 9626 0 34 9626 0 23
9 8885 - - 3600 8885 0 16 8885 0 22 8885 0 27 8885 0 62 8885 0 35
11 8725 - - 3600 8725 0 51 8725 0 35 8725 0 48 8725 0 63 8725 0 80
kroE100 7 10150 9274 9.44 3600 10150 0 520 10150 0 81 10150 0 42 10150 0 76 10150 0 32
9 8991 8500 5.77 3600 8991 0 336 8991 0 31 8991 0 55 8991 0 28 8991 0 88
11 8450 7739 9.19 3600 8450 0 237 8450 0 23 8450 0 261 8450 0 33 8450 0 193
rd100 7 3461 3094 11.88 3600 3461 0 119 3461 0 20 3461 0 20 3461 0 24 3461 0 22
9 3194 2664 19.90 3600 3194 0 63 3194 0 18 3194 0 18 3194 0 24 3194 0 25
11 2922 2648 10.33 3600 2922 0 28 2922 0 21 2922 0 20 2922 0 34 2922 0 27
kroA150 7 11423 10658 7.18 3600 11423 0 174 11423 0 137 11423 0 147 11423 0 90
9 10056 10056 0.00 147 10056 0 84 10056 0 85 10056 0 92 10056 0 122
11 9439 9240 2.15 3600 9439 0 95 9439 0 67 9439 0 243 9439 0 91
kroB150 7 11457 10663 7.45 3600 11457 0 334 11457 0 116 11457 0 113 11457 0 81
9 10121 9951 1.71 3600 10121 0 280 10121 0 130 10121 0 145 10121 0 112
11 9611 9611 0.00 902 9611 0 849 9611 0 429 9611 0 947 9611 0 282
kroA200 7 13285 11660 13.94 3600 12611 5.34 3600 12955 2.55 3600 12697 4.63 3600 13108 1.35 3600
9 11708 10327 13.37 3600 11094 5.53 3600 11708 0 2252 11537 1.48 3600 11708 0 1008
11 10748 9508 13.04 3600 10342 3.93 3600 10748 0 1044 10748 0 3582 10748 0 648
kroB200 7 13051 12260 6.45 3600 12462 4.73 3600 12904 1.14 3600 12697 2.79 3600 13051 0 1487
9 11864 11209 5.84 3600 11379 4.26 3600 11864 0 2281 11695 1.45 3600 11864 0 1242
11 10644 10405 2.30 3600 10644 0 800 10644 0 907 10644 0 514 10644 0 938
att532 3 51616 41269 25.07 3600 46529 10.93 3600 46530 10.93 3600 47581 8.48 3600 47574 8.50 3600
5 42212 30150 40.01 3600 37436 12.76 3600 37463 12.68 3600 38712 9.04 3600 38724 9.01 3600
7 37741 24591 53.47 3600 33414 12.95 3600 33409 12.97 3600 34643 8.94 3600 34649 8.92 3600
ali535 3 1367 1178 16.04 3600 1260 8.49 3600 1259 8.58 3600 1269 7.72 3600 1269 7.72 3600
5 1184 927 27.72 3600 1075 10.14 3600 1075 10.14 3600 1082 9.43 3600 1082 9.43 3600
7 1083 805 34.53 3600 980 10.51 3600 980 10.51 3600 995 8.84 3600 994 8.95 3600
u574 3 22990 18321 25.48 3600 20646 11.35 3600 20614 11.53 3600 21261 8.13 3600 21256 8.16 3600
5 19014 14157 34.31 3600 17098 11.21 3600 17012 11.77 3600 17667 7.62 3600 17587 8.11 3600
7 16597 11485 44.51 3600 14987 10.74 3600 14940 11.09 3600 15420 7.63 3600 15323 8.31 3600
rat575 3 3707 2786 33.06 3600 3265 13.54 3600 3261 13.68 3600 3397 9.13 3600 3396 9.16 3600
5 3034 1939 56.47 3600 2571 18.01 3600 2567 18.19 3600 2726 11.30 3600 2724 11.38 3600
7 2635 1573 67.51 3600 2284 15.37 3600 2287 15.22 3600 2413 9.20 3600 2412 9.25 3600
p654 3 25155 17367 44.84 3600 13141 91.42 3600 13141 91.42 3600 13141 91.42 3600 13141 91.42 3600
5 23211 15367 51.04 3600 17664 31.40 3600 17655 31.47 3600 17949 29.32 3600 17943 29.36 3600
7 22121 16530 33.82 3600 10515 110.38 3600 10515 110.38 3600 10515 110.38 3600 10515 110.38 3600
d657 3 30278 25170 20.29 3600 28127 7.65 3600 28118 7.68 3600 28704 5.48 3600 28724 5.41 3600
5 25890 18513 39.85 3600 23026 12.44 3600 23018 12.48 3600 23807 8.75 3600 23791 8.82 3600
7 23198 16018 44.82 3600 20500 13.16 3600 20447 13.45 3600 21151 9.68 3600 21114 9.87 3600
gr666 3 1981 1678 18.06 3600 1849 7.14 3600 1849 7.14 3600 1879 5.43 3600 1880 5.37 3600
5 1655 1282 29.10 3600 1510 9.60 3600 1512 9.46 3600 1557 6.29 3600 1558 6.23 3600
7 1470 1064 38.16 3600 1351 8.81 3600 1352 8.73 3600 690 113.04 3600 690 113.04 3600
u724 24545 18977 29.34 3600 15530 58.05 3600 15530 58.05 3600 15530 58.05 3600 15530 58.05 3600
5 20305 13448 50.99 3600 7898 157.09 3600 7898 157.09 3600 7898 157.09 3600 7898 157.09 3600
7 17737 9777 81.42 3600 5681 212.22 3600 5681 212.22 3600 5681 212.22 3600 5681 212.22 3600
rat783 3 5021 3834 30.96 3600 2844 76.55 3600 2844 76.55 3600 2844 76.55 3600 2844 76.55 3600
5 4117 2407 71.04 3600 1433 187.30 3600 1433 187.30 3600 1433 187.30 3600 1433 187.30 3600
7 3615 2691 34.34 3600 1804 100.39 3600 1804 100.39 3600 1804 100.39 3600 1804 100.39 3600



Results for medium instances created by Maziero et al. [9]
CSP-I CSP-I&Fvp CSP-I&Fh CSP-I&Fvp-X CSP-I&Fh-X
Instance NC LB Gap Time LB Gap Time LB Gap Time LB Gap Time LB Gap Time
ts225 7 68805 3.74 3600 70254 1.79 3600.00 70988 0.50 3600 70802 0.83 3600 70976 0.25 3600
9 59718 10.36 3600 61834 16.17 3600.00 64048 1.72 3600 62899 4.77 3600 64404 1.22 3600
11 50022 15.54 3600 51057 15.51 3600.00 53691 8.45 3600 52755 37.07 3600 53786 7.40 3600
tsp225 7 1565 8.05 3600 1622 3.70 3600.00 1649 1.88 3600 1644 2.19 3600 1669 0.66 3600
9 1310 15.34 3600 1476 2.30 3600.00 1492 1.21 3600 1500 0.67 3600 1510 0.00 1218
11 1223 12.26 3600 1310 6.49 3600.00 1346 1.56 3600 1340 2.01 3600 1367 0.00 1271
pr226 7 50479 13.89 3600 47279 - 3600.00 50216 85.87 3600 48646 - 3600 50420 89.03 3600
9 50916 8.90 3600 47230 - 3600.00 49911 - 3600 51110 43.43 3600 50191 85.38 3600
11 50236 6.51 3600 44162 - 3600.00 48925 - 3600 45569 - 3600 49444 127.37 3600
gil262 7 938 12.15 3600 931 - 3600.00 991 6.76 3600 943 - 3600 965 - 3600
9 804 20.27 3600 865 - 3600.00 888 - 3600 877 - 3600 901 5.33 3600
11 798 10.03 3600 850 3.06 3600.00 850 2.71 3600 856 1.99 3600 854 2.69 3600
pr264 7 19057 191.89 3600 20360 - 3600.00 20970 - 3600 20425 - 3600 20983 - 3600
9 17962 - 3600 18986 - 3600.00 20257 - 3600 19115 - 3600 20497 375.64 3600
11 17052 - 3600 18790 - 3600.00 19748 409.25 3600 19183 - 3600 19556 - 3600
a280 7 772 53.63 3600 1046 - 3600.00 1083 21.79 3600 1088 122.15 3600 1086 - 3600
9 876 25.23 3600 946 15.22 3600.00 1003 2.89 3600 988 5.87 3600 983 - 3600
11 817 20.93 3600 871 12.40 3600.00 911 5.16 3600 917 - 3600 939 2.56 3600
pr299 7 17263 42.72 3600 20545 - 3600.00 21488 16.31 3600 21291 16.21 3600 21517 - 3600
9 18121 20.46 3600 19609 - 3600.00 20092 5.14 3600 19972 143.62 3600 20305 3.97 3600
11 13806 45.84 3600 18256 - 3600.00 18485 5.17 3600 18275 23.76 3600 18452 5.84 3600
lin318 7 17634 23.90 3600 18715 12.95 3600.00 19331 - 3600 18991 209.48 3600 18886 - 3600
9 14073 42.85 3600 16012 - 3600.00 16718 - 3600 16229 223.08 3600 16920 15.76 3600
11 12389 48.97 3600 15511 - 3600.00 15425 247.70 3600 15809 - 3600 15526 236.91 3600
rd400 7 4272 73.36 3600 5935 - 3600.00 6093 - 3600 6054 - 3600 6041 - 3600
9 3705 82.73 3600 5354 - 3600.00 5342 237.06 3600 5389 - 3600 5388 - 3600
11 2948 93.69 3600 4755 - 3600.00 4749 22.53 3600 4819 - 3600 4825 21.24 3600
fl417 7 4670 141.31 3600 5465 - 3600.00 5452 1125.84 3600 5553 - 3600 5540 - 3600
9 3900 246.90 3600 5011 - 3600.00 5447 - 3600 5097 - 3600 5281 - 3600
11 4119 - 3600 4894 - 3600.00 4882 - 3600 4891 - 3600 4881 - 3600
pr439 7 38920 81.77 3600 49869 - 3600.00 49794 - 3600 50865 - 3600 50704 - 3600
9 35796 121.95 3600 42732 - 3600.00 42734 - 3600 46196 - 3600 46046 - 3600
11 30738 85.65 3600 43008 - 3600.00 42962 369.00 3600 43389 - 3600 43321 - 3600
pcb442 7 13992 89.07 3600 19760 - 3600.00 19768 20.62 3600 20618 - 3600 20560 - 3600
9 12390 142.28 3600 17009 - 3600.00 17105 - 3600 18434 - 3600 18403 35.18 3600
11 10760 103.79 3600 16436 - 3600.00 16144 - 3600 17478 13.13 3600 17448 16.94 3600
d493 7 12961 91.00 3600 16160 - 3600.00 16044 - 3600 16628 - 3600 16373 - 3600
9 11939 78.78 3600 15010 - 3600.00 14796 - 3600 15078 - 3600 15230 - 3600
11 10935 92.91 3600 13937 - 3600.00 13894 - 3600 14189 18.40 3600 14146 - 3600