Exact algorithms and heuristics for the Capacitated Covering Salesman Problem

Open Access

Issue		RAIRO-Oper. Res. Volume 59, Number 5, September-October 2025


Page(s)		3309 - 3324
DOI		https://doi.org/10.1051/ro/2025131
Published online		04 November 2025

L.R. Abreu, R.F. Tavares-Neto and M.S. Nagano, A new efficient biased random key genetic algorithm for open shop scheduling with routing by capacitated single vehicle and makespan minimization. Eng. App. Artif. Intell. 104 (2021) 104373. [Google Scholar]
S. Allahyari, M. Salari and D. Vigo, A hybrid metaheuristic algorithm for the multi-depot covering tour vehicle routing problem. Eur. J. Oper. Res. 242 (2015) 756–768. [Google Scholar]
D.L. Applegate, R.E. Bixby, V. Chvatal and W.J. Cook, The Traveling Salesman Problem: A Computational Study. Princeton Series in Applied Mathematics. Princeton University Press, Princeton, NJ, USA (2007). [Google Scholar]
N. Christofides and S. Eilon, An algorithm for the vehicle-dispatching problem. J. Oper. Res. Soc. 20 (1969) 309–318. [Google Scholar]
J.-F. Cordeau, G. Laporte, M.W.P. Savelsbergh and D. Vigo, Vehicle routing. Handb. Oper. Res. Manage. Sci. 14 (2007) 367–428. [Google Scholar]
J.R. Current and D.A. Schilling, The covering salesman problem. Transp. Sci. 23 (1989) 208–213. [Google Scholar]
G.B. Dantzig and J.H. Ramser, The truck dispatching problem. Manage. Sci. 6 (1959) 80–91. [Google Scholar]
R. De la Fuente, M.M. Aguayo and C. Contreras-Bolton, An optimization-based approach for an integrated forest fire monitoring system with multiple technologies and surveillance drones. Eur. J. Oper. Res. 313 (2024) 435–451. [Google Scholar]
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. Springer US, Boston, MA (2008) 527–550. [Google Scholar]
E.D. Dolan and J.J. Moré, Benchmarking optimization software with performance profiles. Math. Prog. 91 (2002) 201–213. [CrossRef] [Google Scholar]
S. Domínguez-Casasola, J.L. González-Velarde, Y. Á. Ríos-Solís and K.A. Reyes-Vega, The capacitated family traveling salesperson problem. Int. Trans. Oper. Res. 31 (2024) 2123–2153. [Google Scholar]
M. Gendreau, G. Laporte and F. Semet, The covering tour problem. Oper. Res. 45 (1997) 568–576. [Google Scholar]
B.L. Golden, S. Raghavan and E.A. Wasil, The Vehicle Routing Problem: Latest Advances and New Challenges. Vol. 43 of Operations Research/Computer Science Interfaces Series. Springer, Boston, MA (2008). [Google Scholar]
B. Golden, Z. Naji-Azimi, S. Raghavan, M. Salari and P. Toth, The generalized covering salesman problem. INFORMS J. Comput. 24 (2012) 534–553. [CrossRef] [MathSciNet] [Google Scholar]
J.F. Gonçalves and M.G.C. Resende, Biased random-key genetic algorithms for combinatorial optimization. J. Heuristics 17 (2011) 487–525. [Google Scholar]
Gurobi Optimization, LLC, Gurobi Optimizer Reference Manual (2025). [Google Scholar]
M.H. 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. [Google Scholar]
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. [Google Scholar]
K. Helsgaun, An effective implementation of the Lin–Kernighan traveling salesman heuristic. Eur. J. Oper. Res. 126 (2000) 106–130. [Google Scholar]
M.J. Hodgson, G. Laporte and F. Semet, A covering tour model for planning mobile health care facilities in suhumdistrict, Ghama. J. Reg. Sci. 38 (1998) 621–638. [Google Scholar]
L. Jiao, Z. Peng, L. Xi, M. Guo, S. Ding and Y. Wei, A multi-stage heuristic algorithm based on task grouping for vehicle routing problem with energy constraint in disasters. Expert Syst. App. 212 (2023) 118740. [Google Scholar]
N. Jozefowiez, A branch-and-price algorithm for the multivehicle covering tour problem. Networks 64 (2014) 160–168. [Google Scholar]
M. Kammoun, H. Derbel, M. Ratli and B. Jarboui, An integration of mixed VND and VNS: the case of the multivehicle covering tour problem. Int. Trans. Oper. Res. 24 (2017) 663–679. [Google Scholar]
H. Kellerer, U. Pferschy and D. Pisinger, Knapsack Problems. Vol. 1. Springer-Verlag Berlin Heidelberg (2004). [Google Scholar]
K. Kılıç, M. Meterelliyoz, İ. Güvenç Pelit and M. Soysal, Modeling a humanitarian-aid covering tour problem with location selection and vehicle assignment decisions. Int. Trans. Oper. Res. (2025). DOI: 10.1111/itor.70088. [Google Scholar]
A.F. Kummer N, L.S. Buriol and O.C.B. de Araújo, A biased random key genetic algorithm applied to the VRPTW with skill requirements and synchronization constraints, in Proceedings of the 2020 Genetic and Evolutionary Computation Conference (2020) 717–724. [Google Scholar]
A.F. Kummer, yO.C.B. de Araújo, L.S. Buriol and M.G.C. Resende, A biased random-key genetic algorithm for the home health care problem. Int. Trans. Oper. Res. 31 (2024) 1859–1889. [Google Scholar]
S. Lin and B.W. Kernighan, An effective heuristic algorithm for the traveling-salesman problem. Oper. Res. 21 (1973) 498–516. [Google Scholar]
W. Liu, M. Dridi, H. Fei and A.H. El Hassani, Solving a multi-period home health care routing and scheduling problem using an efficient matheuristic. Comput. Ind. Eng. 162 (2021) 107721. [Google Scholar]
S. Maheshwari, P.K. Jain and K. Kotecha, Route optimization of mobile medical unit with reinforcement learning. Sustainability 15 (2023) 3937. [Google Scholar]
K. Murakami, A column generation approach for the multi-vehicle covering tour problem, in 2014 IEEE International Conference on Automation Science and Engineering (CASE). IEEE (2014) 1063–1068. [Google Scholar]
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. [CrossRef] [Google Scholar]
E. Ruiz, V. Soto-Mendoza, A. Ernesto Ruiz Barbosa and R. Reyes, Solving the open vehicle routing problem with capacity and distance constraints with a biased random key genetic algorithm. Comput. Ind. Eng. 133 (2019) 207–219. [CrossRef] [Google Scholar]
R. Santa González, M. Cherkesly, T. Gabriel Crainic and M.-È. Rancourt, Multi-period location routing: an application to the planning of mobile clinic operations in Iraq. Comput. Oper. Res. 159 (2023) 106288. [Google Scholar]
C.S. Sartori and L.S. Buriol, A matheuristic approach to the pickup and delivery problem with time windows, in International Conference on Computational Logistics. Springer (2018) 253–267. [Google Scholar]
F.A. Tillman, The multiple terminal delivery problem with probabilistic demands. Transp. Sci. 3 (1969) 192–204. [Google Scholar]
R.F. Toso and M.G.C. Resende, A C++ application programming interface for biased random-key genetic algorithms. Optim. Methods Softw. 30 (2015) 81–93. [Google Scholar]
E. Uchoa, D. Pecin, A. Pessoa, M. Poggi, T. Vidal and A. Subramanian, New benchmark instances for the capacitated vehicle routing problem. Eur. J. Oper. Res. 257 (2017) 845–858. [Google Scholar]
J. Zhao, Y. Long, B. Xie, G. Xu and Y. Liu, A matheuristic solution for efficient scheduling in dynamic truck–drone collaboration. Expert Syst. App. 267 (2025) 126218. [Google Scholar]

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.