Document Type : Research Paper

**Authors**

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

**Abstract**

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.

**Keywords**

**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.

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.

Fischetti M. and Toth P.,(1988). "AN ADDITIVE APPROACH FOR THE OPTIMAL SOLUTION

OF THE PRIZE-COLLECTING TRAVELLING SALESMAN PROBLEM. VEHICLE ROUTING:

METHODS AND STUDIES. STUDIES IN MANAGEMENT SCIENCE AND SYSTEMSVOLUME

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.

Fischetti M. and Toth P.,(1988). "AN ADDITIVE APPROACH FOR THE OPTIMAL SOLUTION

OF THE PRIZE-COLLECTING TRAVELLING SALESMAN PROBLEM. VEHICLE ROUTING:

METHODS AND STUDIES. STUDIES IN MANAGEMENT SCIENCE AND SYSTEMSVOLUME

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.

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.

Summer 2015

Pages 24-41

**Receive Date:**10 April 2015**Revise Date:**06 June 2015**Accept Date:**12 June 2015