A generalized model and a heuristic algorithm for the large-scale covering tour problem
RAIRO - Operations Research - Recherche Opérationnelle, Tome 52 (2018) no. 2, pp. 577-594.

The covering tour problem (CTP) is defined on a graph, where there exist two types of vertices. One is called visited vertex, which can be visited. The other is called covered vertex, which must be covered but cannot be visited. Each visited vertex covers a subset of covered vertices, and the costs of edges between visited vertices are given. The objective of the CTP is to obtain a minimum cost tour on a subset of visited vertices while covering all covered vertices. In this paper, we deal with the large-scale CTPs, which are composed of tens of thousands of vertices; in the previous studies, the scales of the instances in the experiments are at most a few hundred vertices. We propose a heuristic algorithm using local search techniques for the large-scale CTP. With computational experiments, we show that our algorithm outperforms the existing methods.

DOI : 10.1051/ro/2017090
Classification : 90C06, 90C27, 90C59
Mots-clés : Covering tour problem, traveling salesman problem, set-covering problem, local search techniques, large-scale problem
Murakami, Keisuke 1

1 
@article{RO_2018__52_2_577_0,
     author = {Murakami, Keisuke},
     title = {A generalized model and a heuristic algorithm for the large-scale covering tour problem},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {577--594},
     publisher = {EDP-Sciences},
     volume = {52},
     number = {2},
     year = {2018},
     doi = {10.1051/ro/2017090},
     zbl = {1401.90122},
     mrnumber = {3880546},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2017090/}
}
TY  - JOUR
AU  - Murakami, Keisuke
TI  - A generalized model and a heuristic algorithm for the large-scale covering tour problem
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2018
SP  - 577
EP  - 594
VL  - 52
IS  - 2
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2017090/
DO  - 10.1051/ro/2017090
LA  - en
ID  - RO_2018__52_2_577_0
ER  - 
%0 Journal Article
%A Murakami, Keisuke
%T A generalized model and a heuristic algorithm for the large-scale covering tour problem
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2018
%P 577-594
%V 52
%N 2
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2017090/
%R 10.1051/ro/2017090
%G en
%F RO_2018__52_2_577_0
Murakami, Keisuke. A generalized model and a heuristic algorithm for the large-scale covering tour problem. RAIRO - Operations Research - Recherche Opérationnelle, Tome 52 (2018) no. 2, pp. 577-594. doi : 10.1051/ro/2017090. http://www.numdam.org/articles/10.1051/ro/2017090/

[1] C.E. Andrade, F.K. Miyazawa and M.G. Resende, Evolutionary algorithm for the k-interconnected multi-depot multi-traveling salesmen problem, in Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation. ACM (2013) 463–470. | DOI | MR

[2] E. Balas and A. Ho, Set covering algorithms using cutting planes, heuristics, and subgradient optimization: a computational study. Math. Prog. 12 (1980) 37–60. | MR | Zbl

[3] R. Baldacci, M.A. Boschetti, V. Maniezzo and M. Zamboni, Scatter Search Methods for the Covering Tour Problem. Vol. 30 of Metaheuristic Optimization via Memory and Evolution (2005) 59–91. | DOI | MR | Zbl

[4] V. Chvata, A greedy heuristic for the set-covering problem. Math. Oper. Res. 4 (1979) 233–235. | DOI | MR | Zbl

[5] Concorde TSP solver. Available at: http://www.math.uwaterloo.ca/tsp/concorde.html (2016).

[6] J.R. Current and D.A. Schilling, The covering salesman problem. Transp. Sci. 23 (1989) 208–213. | DOI | MR | Zbl

[7] K.F. Doerner and R.F. Hartl, Health care logistics, emergency preparedness, and disaster relief: new challenges for routing problems with a focus on the Austrian situation, in The Vehicle Routing Problem: Latest Advances and New Challenges (2008) 527–550. | Zbl

[8] R.Z. Farahani, N. Asgari, N. Heidari, M. Hosseininia and M. Goh, Covering problems in facility location: a review. Comput. Ind. Eng. 62 (2012) 368–407. | DOI

[9] M. Gendreau, A. Hertz and G. Laperte, New insertion and postoptimization procedures for the traveling salesman problem. Oper. Res. 40 (1992) 1086–1094. | DOI | MR | Zbl

[10] M. Gendreau, G. Laporte and F. Semet, The covering tour problem. Oper. Res. 45 (1997) 568–576. | DOI | MR | Zbl

[11] B. Golden, Z. Naji-Azimi, S. Raghavan, M. Salari and P. Toth, The generalized covering salesman problem. INFORMS J. Comput. 24 (2012) 534–553. | DOI | MR | Zbl

[12] M.H.N. Ha, N. Bostel, A. Langevin and L.M. Rousseau, An exact algorithm and a metaheuristic for the multi-vehicle covering tour problem with a constraint on the number of vertices. Eur. J. Oper. Res. 226 (2013) 211–220. | DOI | MR | Zbl

[13] M. Hachicha, M.J. Hodgson, G. Laporte and F. Semet, Heuristics for the multi-vehicle covering tour problem. Comput. Oper. Res. 27 (2000) 29–42. | DOI | Zbl

[14] M.J. Hodgson, G. Laporte and F. Semet, A covering tour model for planning mobile health care facilities in Suhum district, Ghana. J. Reg. Sci. 38 (1998) 621–628. | DOI

[15] ILOG: CPLEX. Available at: http://www.ilog.com/ (2018).

[16] N. Jozefowiez, F. Semet and E. Talbi, The bi-objective covering tour problem. Comput. Oper. Res. 34 (2007) 1929–1942. | DOI | Zbl

[17] M. Labbe and G. Laporte, Maximizing user convenience and postal service efficiency in post box location. Belgian J. Oper. Res. Statt. Comput. Sci. 26 (1986) 21–35.

[18] S. Lin and B.W. Kernighan, An effective heuristic algorithm for the traveling-salesman problem. Oper. Res. 21 (1973) 498–516. | DOI | MR | Zbl

[19] E. Luis, I.S. Dolinskaya and K.R. Smilowitz, Disaster relief routing: integrating research and practice. Socio-econ. Plan. Sci. 46 (2012) 88–97. | DOI

[20] M. Matsumoto, T. Nishimura, Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Trans. Model. Comput. Simul. 8 (1998) 3–30. | DOI | Zbl

[21] L. Motta, L.S. Ochi and C. Martinhon, Grasp metaheuristics for the generalized covering tour problem, Vol. 1 of Proceedings of IV Metaheuristic International Conference, Porto, Portugal (2001) 387–93.

[22] G. Nagy and S. Salhi, Location-routing: issues, models and methods. Eur. J. Oper. Res. 177 (2007) 649–72. | DOI | MR | Zbl

[23] Z. Naji-Azimi, J. Renaud, A. Ruiz and M. Salari, A covering tour approach to the location of satellite distribution centers to supply humanitarian aid. Eur. J. Oper. Res. 222 (2012) 596–605. | DOI

[24] C. Prodhon and C. Prins, A survey of recent research on location-routing problems. Eur. J. Oper. Res. 238 (2014) 1–17. | DOI | MR | Zbl

[25] S. Rath and W.J. Gutjahr, A math-heuristic for the warehouse location-routing problem in disaster relief. Comput. Oper. Res. 42 (2014) 25–39. | DOI | MR | Zbl

[26] I. Rodriguez-Martin, J.J. Salazar-Gonzalez and H. Yaman, A branch-and-cut algorithm for the hub location and routing problem. Comput. Oper. Res. 50 (2014) 161–174. | DOI | MR | Zbl

[27] M. Salari and Z. Naji-Azimi, An integer programming-based local search for the covering salesman problem. Comput. Oper. Res. 39 (2012) 2594–2602. | DOI | MR | Zbl

[28] M. Salari, M. Reihaneh and M.S. Sabbagh, Combining ant colony optimization algorithm and dynamic programming technique for solving the covering salesman problem. Comput. Ind. Eng. 83 (2015) 244–251. | DOI

[29] G. Schrimpf, J. Schneider, H. Stamm-Wilbrandt and G. Dueck, Record breaking optimization results using the ruin and recreate principle. J. Comput. Phys. 159 (2000) 139–171. | DOI | MR | Zbl

Cité par Sources :