no. 3
Reactive GRASP for the Prize-collecting Covering Tour Problem
RAIRO. Operations Research, Tome 55 (2021) no. 3, pp. 1441-1457

This paper presents a Greedy Randomized Adaptive Search Procedure (GRASP) for the Prize-Collecting Covering Tour Problem (PCCTP), which is the problem of finding a route for traveling teams that provide services to communities geographically distant from large urban locations. We devised a novel hybrid heuristic by combining a reactive extension of the GRASP with Random Variable Neighborhood Search (VND) meta-heuristic for the purpose of solving the PCCTP. Computational experiments were conducted on a PCCTP benchmark from the literature, and the results demonstrate our approach provides a significant improvement in solving PCCTP and comparable with the state-of-the-art, mainly regarding the computational processing time.

DOI : 10.1051/ro/2021057
Classification : 90C10, 90C11, 90C08, 90C05
Keywords: Prize-collecting covering tour problem, hybrid heuristic, GRASP, VND 
@article{RO_2021__55_3_1441_0,
     author = {Cl{\'\i}maco, Glaubos and Rosseti, Isabel and Silva, Rog\'erioda and Guerine, Marcos},
     title = {Reactive {GRASP} for the {Prize-collecting} {Covering} {Tour} {Problem}},
     journal = {RAIRO. Operations Research},
     pages = {1441--1457},
     year = {2021},
     publisher = {EDP-Sciences},
     volume = {55},
     number = {3},
     doi = {10.1051/ro/2021057},
     mrnumber = {4269474},
     zbl = {1471.90093},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2021057/}
}
TY  - JOUR
AU  - Clímaco, Glaubos
AU  - Rosseti, Isabel
AU  - Silva, Rogérioda
AU  - Guerine, Marcos
TI  - Reactive GRASP for the Prize-collecting Covering Tour Problem
JO  - RAIRO. Operations Research
PY  - 2021
SP  - 1441
EP  - 1457
VL  - 55
IS  - 3
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2021057/
DO  - 10.1051/ro/2021057
LA  - en
ID  - RO_2021__55_3_1441_0
ER  - 
%0 Journal Article
%A Clímaco, Glaubos
%A Rosseti, Isabel
%A Silva, Rogérioda
%A Guerine, Marcos
%T Reactive GRASP for the Prize-collecting Covering Tour Problem
%J RAIRO. Operations Research
%D 2021
%P 1441-1457
%V 55
%N 3
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2021057/
%R 10.1051/ro/2021057
%G en
%F RO_2021__55_3_1441_0
Clímaco, Glaubos; Rosseti, Isabel; Silva, Rogérioda; Guerine, Marcos. Reactive GRASP for the Prize-collecting Covering Tour Problem. RAIRO. Operations Research, Tome 55 (2021) no. 3, pp. 1441-1457. doi: 10.1051/ro/2021057

[1] F. Al-Hawari, M. Al-Ashi, F. Abawi and S. Alouneh, A practical three-phase ilp approach for solving the examination timetabling problem. Int. Trans. Oper. Res. 27 (2020) 924–944. | MR | Zbl | DOI

[2] C. Almeder, A hybrid optimization approach for multi-level capacitated lot-sizing problems. Eur. J. Oper. Res. 200 (2010) 599–606. | Zbl | DOI

[3] J. Bérubé, M. Gendreau and J. Potvin, A branch-and-cut algorithm for the undirected prize collecting traveling salesman problem. Networks: An Int. J. 54 (2009) 56–67. | MR | Zbl | DOI

[4] S. A. Canuto, M. G. C. Resende and C. C. Ribeiro, Local search with perturbations for the prize-collecting Steiner tree problem in graphs. Networks: An Int. J. 38 (2001) 50–58. | MR | Zbl | DOI

[5] G. Climaco, Prize-collecting covering tour problem (Data Set). Mendeley Data, V1, (2020). https://doi.org/10.17632/8yjbfgcfvn.1.

[6] G. Climaco, Prize-collecting covering tour problem (Complete Results). Mendeley Data, V2 (2021). https://doi.org/10.17632/8yjbfgcfvn.2.

[7] G. Clímaco, I. Rosseti, L. Simonetti and M. Guerine, Combining integer linear programming with a state-of-the-art heuristic for the 2-path network design problem. Int. Trans. Oper. Res. 26 (2019) 615–641. | MR | Zbl | DOI

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

[9] A. D. Ebrahimi and R. Sahraeian, The maximal backup covering tour problem. In: 6th International Conference on Industrial Engineering and Industrial Management, Vigo, Spain (2012) 367–374.

[10] D. A. Flores-Garza, M. A. Salazar-Aguilar, S. U. Ngueveu and G. Laporte, The multi-vehicle cumulative covering tour problem. Ann. Oper. Res. 258 (2017) 761–780. | MR | Zbl | DOI

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

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

[13] Gurobi Optimization, Gurobi optimizer reference manual (2019). Last accessed on December 10, 2019.

[14] 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. | Zbl | DOI

[15] M. Hamidi, K. Farahmand, S. Reza and K. E. Nygard, A hybrid grasp-tabu search metaheuristic for a four-layer location-routing problem. Int. J. Logist. Syst. Manag. 12 (2012) 267–287.

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

[17] I. Karaoğlan, G. Erdoğan and Ç. Koç, The multi-vehicle probabilistic covering tour problem. Eur. J. Oper. Res. 271 (2018) 278–287. | MR | Zbl | DOI

[18] H. R. Lourenço, O. C. Martin and T. Stützle, Iterated local search. In: Handbook of metaheuristics, edited by J.-Y. Potvin, M. Gendreau. Springer, Boston, MA (2003) 320–353. | MR | Zbl | DOI

[19] A. R. De Lyra, O problema de recobrimento de rotas com coleta de prêmios: regras de redução, formulação matemática e heursticas (in portuguese), Master’s thesis, Programa de Pós-Graduação em Computao, Instituto de Computação, Universidade Federal Fluminense, Niterói, RJ (2004).

[20] N. Mladenović and P. Hansen, Variable neighborhood search. Comput. Oper. Res. 24 (1997) 1097–1100. | MR | Zbl | DOI

[21] C. Park and J. Seo, A grasp approach to transporter scheduling for ship assembly block operations management. Eur. J. Indus. Eng. 7 (2013) 312–332. | DOI

[22] T. A. Pham, M. Hà and X. H. Nguyen, Solving the multi-vehicle multi-covering tour problem. Comput. Oper. Res. 88 (2017) 258–278. | MR | Zbl | DOI

[23] M. Prais and C. C. Ribeiro, Reactive grasp: An application to a matrix decomposition problem in TDMA traffic assignment. INFORMS J. Comput. 12 (2000) 164–176. | MR | Zbl | DOI

[24] R Core Team, R: A Language and Environment for Statistical Computing. R Foundation for Statistical Computing, Vienna, Austria (2017).

[25] G. Reinelt, TSPLIB – a traveling salesman problem library. ORSA J. Comput. 3 (1991) 376–384. | Zbl | DOI

[26] M. G. C. Resende and C. C. Ribeiro, Greedy randomized adaptive search procedures. In: Handbook of Metaheuristics, edited by F. Glover and G. Kochenberger. Springer, Boston, MA (2003) 219–249. | MR | Zbl | DOI

[27] Í. Santana, A. Plastino and I. Rosseti, Improving a state-of-the-art heuristic for the minimum latency problem with data mining. Int. Trans. Oper. Res. (2020). DOI: 10.1111/itor.12774. | Zbl

[28] S. Siegel, Nonparametric statistics for the behavioral sciences. McGraw-Hill (1956). | Zbl

[29] M. S. A. Silva, Problema de Recobrimento de Rotas com Coleta de Prêmios (in portuguese), Master’s thesis, Programa de Pós-Graduação em Computao, Instituto de Computao, Instituto de Computação, Universidade Federal Fluminense, Niterói, RJ (2009).

[30] B. Sylvain, H. Hideki, M. Vasquez and C. Wilbaut, Un algorithme grasp pour le problème de planification de techniciens et d’interventions pour les télécommunications. RAIRO: OR 43 (2009) 387–407. | Zbl | DOI

[31] D. Trachanatzi, M. Rigakis, M. Marinaki and Y. Marinakis, A firefly algorithm for the environmental prize-collecting vehicle routing problem. Swarm Evol. Comput. 57 (2020). | DOI

[32] F. Tricoire, A. Graf and W. J. Gutjahr, The bi-objective stochastic covering tour problem. Comput. Oper. Res. 39 (2012) 1582–1592. | MR | Zbl | DOI

Cité par Sources :