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.
Accepté le :
DOI : 10.1051/ro/2019006
Mots-clés : The Time Dependent Traveling Salesman Problem, tabu search, Variable Neighborhood Search
@article{RO_2019__53_3_917_0,
author = {Ban, Ha Bang},
title = {An efficient two-phase metaheuristic algorithm for the time dependent traveling {Salesman} problem},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {917--935},
publisher = {EDP-Sciences},
volume = {53},
number = {3},
year = {2019},
doi = {10.1051/ro/2019006},
zbl = {1423.90204},
mrnumber = {3979010},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ro/2019006/}
}
TY - JOUR AU - Ban, Ha Bang TI - An efficient two-phase metaheuristic algorithm for the time dependent traveling Salesman problem JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2019 SP - 917 EP - 935 VL - 53 IS - 3 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro/2019006/ DO - 10.1051/ro/2019006 LA - en ID - RO_2019__53_3_917_0 ER -
%0 Journal Article %A Ban, Ha Bang %T An efficient two-phase metaheuristic algorithm for the time dependent traveling Salesman problem %J RAIRO - Operations Research - Recherche Opérationnelle %D 2019 %P 917-935 %V 53 %N 3 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro/2019006/ %R 10.1051/ro/2019006 %G en %F RO_2019__53_3_917_0
Ban, Ha Bang. An efficient two-phase metaheuristic algorithm for the time dependent traveling Salesman problem. RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 3, pp. 917-935. doi : 10.1051/ro/2019006. http://www.numdam.org/articles/10.1051/ro/2019006/
[1] , and , A faster, better approximation algorithm for the minimum latency problem. J. SIAM 37 (2007) 1472–1498. | DOI | MR | Zbl
[2] , , and , The time dependent traveling salesman problem: polyhedra and branch-cut-and price algorithm. J. Math. Prog. Comput. 5 (2013) 27–55. | DOI | MR
[3] and , Approximation schemes for minimum latency problems. Proc. STOC (1999) 688–693. | MR | Zbl
[4] and , Improved genetic algorithm for minimum latency problem. Proc. SOICT (2010) 9–15.
[5] , , and , An efficient exact algorithm for Minimum Latency Problem. Progr. Inform. 10 (2013) 167–174. | DOI
[6] , and , Scheduling examinations to reduce second-order conflicts. Comput. Oper. Res. 19 (1992) 353–361. | DOI | Zbl
[7] , , , , and , The minimum latency problem. Proc. STOC (1994) 163–171. | Zbl
[8] , and , 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] , , and , Path, tree and minimum latency tour. Proc. FOCS (2003) 36–45.
[10] and , 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] and , Greedy randomized adaptive search procedures. J. Global Opt. 6 (1995) 109–133. | DOI | MR | Zbl
[12] and , Hybridizations of GRASP with path-relinking, In Vol. 434 of Hybrid Metaheuristics - Studies in Computational Intelligence, edited by . Springer, Berlin, Heidelberg (2013) 135–155.
[13] , Production scheduling on parallel lines with dependencies. Ph.D. thesis, Johns Hopkins University, Baltimore, MD (1973).
[14] , and , The Time Dependent Traveling Salesman Problem and Extensions. Working paper No. 7904, Graduate School of Management, University of Rochester, NY (1979).
[15] and , An improved approximation ratio for the minimum latency problem. Proc. SIAM SODA (1996) 152–158. | MR | Zbl
[16] , Tabu search. J. INFORMS 2 (1990) 4–32. | DOI | Zbl
[17] , 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] , and , 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] , Performance of various computers using standard linear equations software. Linpack Benchmark Report, University of Tennessee Computer Science Technical Report, CS-89-85 (2013).
[20] , and , Solving the time dependent traveling salesman problem. The Next Wave in Computing, Optimization, and Decision Technologies. Springer (2005) 163–182.
[21] , Time-dependent traveling salesman problem – the deliveryman case. J. Networks 20 (1990) 753–763. | DOI | MR | Zbl
[22] and , Time dependent vehicle routing problems: formulations, properties and heuristic algorithms. J. Transp. Sci. 26 (1992) 185–200. | DOI | Zbl
[23] and , Variable neighborhood search. J. Oper. Res. 24 (1997) 1097–1100. | MR | Zbl
[24] and , Shortest-path and minimumdelay algorithms in networks with time-dependent edgelength. J. ACM 37 (1990) 607–625. | DOI | MR | Zbl
[25] , , and , Efficient GRASP+VND and GRASP+VNS meta-heuristics for the traveling repairman problem. J. Oper. Res. 9 (2011) 189–209. | DOI | MR | Zbl
[26] , , and , A simple and effective metaheuristic for the Minimum Latency Problem. J. Oper. Res. 221 (2012) 513–520. | DOI | Zbl
[27] and , Minimizing the total flow time of n jobs on a network. IEEE. Trans. 23 (1991) 236–244. | DOI
[28] , and , Evolving efficient theme park tours. J. Comput. Inform. Technol. 7 (1999) 77–92.
[29] , , Hybrid metaheuristics for dynamic and stochastic vehicle routing, In Vol. 434 of Hybrid Metaheuristics – Studies in Computational Intelligence. Edited by . Springer, Berlin, Heidelberg (2003) 77–95.
[30] , Polyhedral solution to the pickup and delivery problem, Ph.D. thesis, Washington University, Saint Louis, MO (1995).
[31] and , An exact solution approach for the time-dependent traveling salesman problem. Naval Res. Logistics (NRL) 43 (1996) 797–820. | DOI | MR | Zbl
[32] and , Heuristics bounds and test problem generation for the time-dependent traveling salesman problem. J Transp. Sci. 29 (1995) 167–183. | DOI | Zbl
[33] , , , and , Optimization of the time-dependent traveling salesman problem with Monte Carlo methods. Phys. Rev. E 64 (2001) 36701–1–36701-8. | DOI
[34] and , The traveling salesman problem: a case study in local optimization. Local Search Comb. Optim. 1 (1997) 215–310. | MR | Zbl
[35] , and , 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.
Cité par Sources :
