This paper studies the equality generalized symmetric traveling salesman problem (EGSTSP). A salesman has to visit a predefined set of countries. S/he must determine exactly one city (of a subset of cities) to visit in each country and the sequence of the countries such that s/he minimizes the overall travel cost. From an academic perspective, EGSTSP is very important. It is NP-hard. Its relaxed version TSP is itself NP-hard, and no exact technique solves large difficult instances. From a logistic perspective, EGSTSP has a broad range of applications that vary from sea, air, and train shipping to emergency relief to elections and polling to airlines’ scheduling to urban transportation. During the COVID-19 pandemic, the roll-out of vaccines further emphasizes the importance of this problem. Pharmaceutical firms are challenged not only by a viable production schedule but also by a flawless distribution plan especially that some of these vaccines must be stored at extremely low temperatures. This paper proposes an approximate tree-based search technique for EGSTSP . It uses a beam search with low and high level hybridization. The low-level hybridization applies a swap based local search to each partial solution of a node of a tree whereas the high-level hybridization applies 2-Opt, 3-Opt or Lin-Kernighan to the incumbent. Empirical results provide computational evidence that the proposed approach solves large instances with 89 countries and 442 cities in few seconds while matching the best known cost of 8 out of 36 instances and being less than 1.78% away from the best known solution for 27 instances.
Keywords: Generalized traveling salesman, beam search, symmetric traveling salesman, $$-opt, Lin-Kernighan heuristic
@article{RO_2021__55_5_3021_0,
author = {Ben Nejma, Ibtissem and M{\textquoteright}Hallah, Rym},
title = {A beam search for the equality generalized symmetric traveling salesman problem},
journal = {RAIRO. Operations Research},
pages = {3021--3039},
year = {2021},
publisher = {EDP-Sciences},
volume = {55},
number = {5},
doi = {10.1051/ro/2021148},
mrnumber = {4324004},
zbl = {1485.90117},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2021148/}
}
TY - JOUR AU - Ben Nejma, Ibtissem AU - M’Hallah, Rym TI - A beam search for the equality generalized symmetric traveling salesman problem JO - RAIRO. Operations Research PY - 2021 SP - 3021 EP - 3039 VL - 55 IS - 5 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2021148/ DO - 10.1051/ro/2021148 LA - en ID - RO_2021__55_5_3021_0 ER -
%0 Journal Article %A Ben Nejma, Ibtissem %A M’Hallah, Rym %T A beam search for the equality generalized symmetric traveling salesman problem %J RAIRO. Operations Research %D 2021 %P 3021-3039 %V 55 %N 5 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2021148/ %R 10.1051/ro/2021148 %G en %F RO_2021__55_5_3021_0
Ben Nejma, Ibtissem; M’Hallah, Rym. A beam search for the equality generalized symmetric traveling salesman problem. RAIRO. Operations Research, Tome 55 (2021) no. 5, pp. 3021-3039. doi: 10.1051/ro/2021148
[1] , , and , A novel imperialist competitive algorithm for generalized traveling salesman problems. Appl. Soft Comput. 26 (2015) 546–555. | DOI
[2] , , , and , Transformations of generalized ATSP into ATSP. Oper. Res. Lett. 31 (2003) 357–365. | MR | Zbl | DOI
[3] , and , A memetic algorithm with a large neighborhood crossover operator for the generalized traveling salesman problem. Comput. Oper. Res. 37 (2010) 1844–1852. | MR | Zbl | DOI
[4] , and , Sensitive ant systems in combinatorial optimization. Proceedings of the International Conference on Knowledge Engineering, Principles and Techniques, KEPT, Cluj-Napoca, Romania (2007) 185–192.
[5] and , An efficient transformation of the generalized traveling salesman problem into the traveling salesman problem. Geogr. Inf. Sci. 102 (1997) 105–110. | MR | Zbl | DOI
[6] , and , A branch-and-cut algorithm for the symmetric generalized traveling salesman problem. Oper. Res. 45 (1997) 378–394. | MR | Zbl | DOI
[7] , and , The generalized traveling salesman and orienteering problems. In edited by and . Vol 12 of The traveling salesman problem and its variations Combinatorial Optimization. Springer, Boston, MA (2007). | DOI
[8] , and , Memetic algorithm for the generalized asymmetric traveling salesman problem. Stud. Comput. Intell. 129 (2008) 199–210. | DOI
[9] , Solving the equality generalized traveling salesman problem using the Lin-Kernighan-Helsgaun-algorithm. Math. Program. Comput. 17 (2015) 1–19. | MR | Zbl
[10] , and , A new efficient hybrid algorithm for large scale multiple traveling salesman problems. Expert Syst. Appl. 139 (2020) 112867. | DOI
[11] and , Lin-Kernighan heuristic adaptations for the generalized traveling salesman problem. Eur. J. Oper. Res. 208 (2011) 221–232. | MR | Zbl | DOI
[12] and , Efficient local search algorithms for known and new neighborhoods for the generalized traveling salesman problem. Eur. J. Oper. Res. 219 (2012) 234–251. | MR | Zbl | DOI
[13] and , Approximation schemes for the generalized traveling salesman problem. Proc. Steklov Inst. Math. 299 (2017) 97–105. | Zbl | MR | DOI
[14] , and , Generalized traveling salesman problem through sets of nodes: The asymmetric case. Discrete Appl. Math. 18 (1987) 185–197. | MR | Zbl | DOI
[15] and , A random-key genetic algorithm for the generalized traveling salesman problem. Eur. J. Oper. Res. 174 (2006) 38–53. | MR | Zbl | DOI
[16] , and , Transformation of the generalized traveling salesman problem into the standard traveling salesman problem. Inf. Sci. 74 (1993) 177–189. | MR | Zbl | DOI
[17] and , An effective heuristic Algorithm for the traveling-salesman problem. Oper. Res. 21 (1973) 498–516. | MR | Zbl | DOI
[18] , and , Software development for cutting tool routing problems. Procedia Manuf. 29 (2019) 567–574. | DOI
[19] , New hybrid heuristic algorithm for the clustered traveling salesman problem. Comput. Ind. Eng. 116 (2018) 1–12. | DOI
[20] and , A Lagrangian based approach for the asymmetric generalized traveling salesman problem. Oper. Res. 39 (1991) 623–632. | MR | Zbl | DOI
[21] , and , On the new algorithm for solving continuous cutting problems. IFAC 52 (2019) 2320–2325.
[22] and , An efficient composite heuristic for the symmetric generalized travelling salesman problem. Eur. J. Oper. Res. 108 (1998) 571–584. | Zbl | DOI
[23] , and , A fast composite heuristic for the symmetric traveling salesman problem. INFORMS J. Comput. 8 (1996) 134–143. | Zbl | DOI
[24] , and , Branch-and-bound for the precedence constrained generalized traveling salesman problem. Oper. Res. Lett. 48 (2020) 163–166. | MR | Zbl | DOI
[25] and , GLNS: An effective large neighborhood search heuristic for the generalized traveling salesman problem. Comput. Oper. Res. 87 (2017) 1–19. | MR | Zbl | DOI
[26] , , and , Generalized traveling salesman problem through sets of nodes. CORS J. 7 (1969) 97–101. | MR | Zbl
[27] and , Generalized multiple depot traveling salesmen problem-Polyhedral study and exact algorithm. Comput. Oper. Res. 70 (2016) 39–55. | MR | Zbl | DOI
[28] , , and , An ant colony optimization method for generalized TSP problem. Prog. Nat. Sci. 18 (2008) 1417–1422. | MR | DOI
[29] , , and , A branch-and-cut algorithm for the generalized traveling salesman problem with time windows. Oper. Res. Lett. 286 (2020) 849–866. | MR | Zbl | DOI
[30] and , An extension of the Christofides heuristic for the generalized multiple depot multiple traveling salesmen problem. Oper. Res. Lett. 257 (2017) 735–745. | MR | Zbl | DOI
Cité par Sources :
