Two new heuristic algorithms for Covering Tour Problem

Document Type : Research Paper


Department of Industrial and Systems Engineering, Isfahan University of Technology, 84156-83111 Isfahan, Iran.


Covering Tour Problem (CTP) is the generalized form of Traveling Salesman Problem (TSP), which has found different applications in the designing of distribution networks, disaster relief, and transportation routing. The purpose of this problem is to determine the Hamiltoniancyclewiththe lowest costusinga subset of all the nodes, such that the other nodes would be in a distance shorter than the pre-specified one, from at least one visited node. In this paper, two new heuristic algorithms called MDMC and AGENI are offered to solve CTP. In order to assess the performance of the proposed algorithms in small scale, several test problems are accurately solved and the results compared with those from the proposed heuristic algorithms. Also, in large scales, the results of each of proposed algorithms are compared with the three heuristic algorithms existing in the literature. Finally, the effect of neighborhood searcheson the performance of the proposed algorithms will be investigated. The results, show that the performance of the proposed algorithms in small and large scales is appropriate.


Main Subjects

Arkin E. M. and Hassin R.,(1994)."Approximation algorithms for the geometric covering salesman
problem," Discrete Applied Mathematics, vol. 55, pp. 197-218.
Croes G.,(1958). "A method for solving traveling-salesman problems," Operations Research, vol. 6,
pp. 791-812.
Current J. R. and Schilling D. A.,(1989). "The covering salesman problem," Transportation science,
vol. 23, pp. 208-213.
Current J. R. and Schilling D. A.,(1994). "The median tour and maximal covering tour problems:
Formulations and heuristics," European Journal of Operational Research, vol. 73, pp. 114-126.
Daskin M.,(1995). "Network and discrete location analysis," ed: John Wiley and Sons, New York.
16," Publication of: Dalctraf.
Gendreau M., Hertz A., and Laporte G.,(1992). "New insertion and postoptimization procedures for
the traveling salesman problem," Operations Research, vol. 40, pp. 1086-1094.
Golden B., Naji-Azimi Z., Raghavan S., Salari M., and Toth P.,(2012). "The generalized covering
salesman problem," INFORMS Journal on Computing, vol. 24, pp. 534-553.
Hachicha M., John Hodgson M., Laporte G., and Semet F.,(2000). "Heuristics for the multi-vehicle
covering tour problem," Computers & Operations Research, vol. 27, pp. 29-42.
Hodgson M. J., Laporte G., and Semet F., (1998). "A Covering Tour Model for Planning Mobile
Health Care Facilities in SuhumDistrict, Ghama," Journal of Regional Science, vol. 38, pp. 621-638.
Labbé M., Laporte G., Martín I. R., and González J. J. S.,(2004). "The ring star problem: Polyhedral
analysis and exact algorithm," Networks, vol. 43, pp. 177-189.
Jozefowiez N., Semet F., and Talbi E.-G.,(2007). "The bi-objective covering tour problem,"
Computers & operations research, vol. 34, pp. 1929-1942.
Jozefowiez, N. (2014). A branch‐and‐price algorithm for the multivehicle covering tour problem.
Networks, 64(3), 160-168.
Laporte G. and Martello S.,(1990). "The selective travelling salesman problem," Discrete applied
mathematics, vol. 26, pp. 193-207.
Lin S. and Kernighan B. W.,(1973). "An effective heuristic algorithm for the traveling-salesman
problem," Operations research, vol. 21, pp. 498-516.
Moreno Pérez J. A., Marcos Moreno-Vega J., and Rodrı́guez Martı́n I.,(2003). "Variable
neighborhood tabu search and its application to the median cycle problem," European Journal of
Operational Research, vol. 151, pp. 365-378.
Naji-Azimi Z. and Salari M.,(2014). "The time constrained maximal covering salesman problem,"
Applied Mathematical Modelling, vol. 38, pp. 3945-3957.
Salari M., Reihaneh M., and Sabbagh M. S.,(2015). "Combining ant colony optimization algorithm
and dynamic programming technique for solving the covering salesman problem," Computers &
Industrial Engineering.
Nolz P. C., Doerner K. F., Gutjahr W. J., and Hartl R. F.,(2010). "A bi-objective metaheuristic for
disaster relief operation planning," in Advances in multi-objective nature inspired computing, ed:
Springer, pp. 167-187.
Salari M. and Naji-Azimi Z.,(2012). "An integer programming-based local search for the covering
salesman problem," Computers & Operations Research, vol. 39, pp. 2594-2602.
Schilling D. A., Jayaraman V., and Barkhi R., ( 1993). "A REVIEW OF COVERING PROBLEMS
IN FACILITY LOCATION," Computers & Operations Research.
Snyder L. V. and Daskin M. S.,(2006). "A random-key genetic algorithm for the generalized traveling
salesman problem," European Journal of Operational Research, vol. 174, pp. 38-53.
Tricoire F., Graf A., and Gutjahr W. J.,(2012). "The bi-objective stochastic covering tour problem,"
Computers & operations research, vol. 39, pp. 1582-15922.