Alinaghian, M., Goli, A. (2015). Two new heuristic algorithms for Covering Tour Problem. Journal of Industrial and Systems Engineering, 8(3), 24-41.

Mehdi Alinaghian; Alireza Goli. "Two new heuristic algorithms for Covering Tour Problem". Journal of Industrial and Systems Engineering, 8, 3, 2015, 24-41.

Alinaghian, M., Goli, A. (2015). 'Two new heuristic algorithms for Covering Tour Problem', Journal of Industrial and Systems Engineering, 8(3), pp. 24-41.

Alinaghian, M., Goli, A. Two new heuristic algorithms for Covering Tour Problem. Journal of Industrial and Systems Engineering, 2015; 8(3): 24-41.

Two new heuristic algorithms for Covering Tour Problem

^{}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.

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