An efficient two-phase metaheuristic algorithm for the time dependent traveling Salesman problem

Ban, Ha Bang

RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 3, pp. 917-935.

Suite au passage du modèle économique de la revue en S20, le texte intégral des articles des années 2019 et 2020 est accessible uniquement sur le site de l'éditeur et est réservé aux abonnés.

The Time Dependent Traveling Salesman Problem (TDTSP) is a class of NP-hard combinatorial optimization problems which has many practical applications. To the best of our knowledge, developing metaheuristic algorithm for the problem has not been studied much before, even though it is a natural and general extension of the Minimum Latency Problem (MLP) or Traveling Salesman Problem (TSP). In this paper, we propose an effective two-phase metaheuristic which combines the Insertion Heuristic (IH), Variable Neighborhood Search (VNS) and the tabu search (TS) to solve the problem. In a construction phase, the IH is used to create an initial solution that is good enough. In an improvement phase, the VNS is employed to generate diverse and various neighborhoods, while the main attribute of tabu search is to prohibit our algorithm from getting trapped into cycles, and to guide the search to escape local optima. Moreover, we introduce a novel neighborhoods’ structure in VNS and present a O(1) operation for calculating the cost of each neighboring solution in a special case of TDTSP where the TDTSP becomes the MLP. Extensive computational experiments on 355 benchmark instances show that our algorithm can find the optimal solutions for small instances with up to 100 vertices in a reasonable amount of time. For larger instances, our algorithm obtains the new best solutions in comparison with the state-of-the-art algorithm solutions.

[1] A. Archer, A. Levin and D. Williamson, A faster, better approximation algorithm for the minimum latency problem. J. SIAM 37 (2007) 1472–1498. | DOI | MR | Zbl

[2] H.G. Abeledo, G. Fukasawa, R. Pessoa and A. Uchoa, The time dependent traveling salesman problem: polyhedra and branch-cut-and price algorithm. J. Math. Prog. Comput. 5 (2013) 27–55. | DOI | MR

[3] S. Arora and G. Karakostas, Approximation schemes for minimum latency problems. Proc. STOC (1999) 688–693. | MR | Zbl

[4] H.B. Ban and D.N. Nguyen, Improved genetic algorithm for minimum latency problem. Proc. SOICT (2010) 9–15.

[5] H.B. Ban, K. Nguyen, M.C. Ngo and D.N. Nguyen, An efficient exact algorithm for Minimum Latency Problem. Progr. Inform. 10 (2013) 167–174. | DOI

[6] N. Balakrishnan, A. Lucena and R.T. Wong, Scheduling examinations to reduce second-order conflicts. Comput. Oper. Res. 19 (1992) 353–361. | DOI | Zbl

[7] A. Blum, P. Chalasani, D. Coppersmith, W. Pulleyblank, P. Raghavan and M. Sudan, The minimum latency problem. Proc. STOC (1994) 163–171. | Zbl

[8] L. Bigras, M. Gamache and G. Savard, The time-dependent traveling salesman problem and single machine scheduling problems with sequence dependent setup time. J. Dis. Optim. 5 (2008) 685–699. | DOI | MR | Zbl

[9] K. Chaudhuri, B. Goldfrey, S. Rao and K. Talwar, Path, tree and minimum latency tour. Proc. FOCS (2003) 36–45.

[10] J.C. Picard and M. Queyranne, The Time-dependent traveling salesman problem and its application to the tardiness problem in one machin scheduling. J. Oper. Res. 26 (1978) 86–110. | DOI | MR | Zbl

[11] T.A. Feo and M.G.C. Resende, Greedy randomized adaptive search procedures. J. Global Opt. 6 (1995) 109–133. | DOI | MR | Zbl

[12] P. Festa and G.M.C. Resende, Hybridizations of GRASP with path-relinking, In Vol. 434 of Hybrid Metaheuristics - Studies in Computational Intelligence, edited by E.-G. Talbi. Springer, Berlin, Heidelberg (2013) 135–155.

[13] K. Fox, Production scheduling on parallel lines with dependencies. Ph.D. thesis, Johns Hopkins University, Baltimore, MD (1973).

[14] K. Fox, B. Gavish and S. Graves, The Time Dependent Traveling Salesman Problem and Extensions. Working paper No. 7904, Graduate School of Management, University of Rochester, NY (1979).

[15] M. Goemans and J. Kleinberg, An improved approximation ratio for the minimum latency problem. Proc. SIAM SODA (1996) 152–158. | MR | Zbl

[16] F. Glover, Tabu search. J. INFORMS 2 (1990) 4–32. | DOI | Zbl

[17] M.A. Figliozzi, The time dependent vehicle routing problem with time windows: benchmark problems, an efficient solution algorithm, and solution characteristics. J. Transp. Res. Part E Logist. Transp. Rev. 48 (2012) 616–636. | DOI

[18] H. Hashimoto, M. Yagiura and T. Ibaraki, An iterated local search algorithm for the time-dependent vehicle routing problem with time windows. J. Dis. Optim. 5 (2008) 434–456. | DOI | MR | Zbl

[19] J.J. Dongarra, Performance of various computers using standard linear equations software. Linpack Benchmark Report, University of Tennessee Computer Science Technical Report, CS-89-85 (2013).

[20] F. Li, B. Golden and E. Wasil, Solving the time dependent traveling salesman problem. The Next Wave in Computing, Optimization, and Decision Technologies. Springer (2005) 163–182.

[21] A. Lucena, Time-dependent traveling salesman problem – the deliveryman case. J. Networks 20 (1990) 753–763. | DOI | MR | Zbl

[22] C. Malandraki and M. Daskin, Time dependent vehicle routing problems: formulations, properties and heuristic algorithms. J. Transp. Sci. 26 (1992) 185–200. | DOI | Zbl

[23] N. Mladenovic and P. Hansen, Variable neighborhood search. J. Oper. Res. 24 (1997) 1097–1100. | MR | Zbl

[24] A. Orda and R. Rom, Shortest-path and minimumdelay algorithms in networks with time-dependent edgelength. J. ACM 37 (1990) 607–625. | DOI | MR | Zbl

[25] A. Salehipour, K. Sorensen, P. Goos and O. Braysy, Efficient GRASP+VND and GRASP+VNS meta-heuristics for the traveling repairman problem. J. Oper. Res. 9 (2011) 189–209. | DOI | MR | Zbl

[26] M. Silva, A. Subramanian, T. Vidal and L. Ochi, A simple and effective metaheuristic for the Minimum Latency Problem. J. Oper. Res. 221 (2012) 513–520. | DOI | Zbl

[27] D. Simchi-Levi and O. Berman, Minimizing the total flow time of n jobs on a network. IEEE. Trans. 23 (1991) 236–244. | DOI

[28] L. Testa, A. Esterline and G. Dozier, Evolving efficient theme park tours. J. Comput. Inform. Technol. 7 (1999) 77–92.

[29] U. Ritzinger, J. Puchinger, Hybrid metaheuristics for dynamic and stochastic vehicle routing, In Vol. 434 of Hybrid Metaheuristics – Studies in Computational Intelligence. Edited by E.G. Talbi. Springer, Berlin, Heidelberg (2003) 77–95.

[30] K. Ruland, Polyhedral solution to the pickup and delivery problem, Ph.D. thesis, Washington University, Saint Louis, MO (1995).

[31] R. Vander Wiel and N. Sahinidis, An exact solution approach for the time-dependent traveling salesman problem. Naval Res. Logistics (NRL) 43 (1996) 797–820. | DOI | MR | Zbl

[32] R.J. Vander Wiel and N.V. Sahinidis, Heuristics bounds and test problem generation for the time-dependent traveling salesman problem. J Transp. Sci. 29 (1995) 167–183. | DOI | Zbl

[33] J. Bentner, G. Bauer, G.M. Obermai, I. Morgensten and J. Schneider, Optimization of the time-dependent traveling salesman problem with Monte Carlo methods. Phys. Rev. E 64 (2001) 36701–1–36701-8. | DOI

[34] D.S. Johnson and L.A. Mcgeoch, The traveling salesman problem: a case study in local optimization. Local Search Comb. Optim. 1 (1997) 215–310. | MR | Zbl

[35] B.Y. Wu, Z.-N. Huang and F.-J. Zhan, Exact algorithms for the minimum latency problem. Inf. Proc. Lett. 92 (2004) 303–309. | DOI | MR | Zbl

[36] https://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/.

[37] http://liris.cnrs.fr/christine.solnon/TDTSP.html.