Decomposition-Based Lin–Kernighan Heuristic With Neighborhood Structure Transfer for Multi/Many-Objective Traveling Salesman Problem
Authors: 
Xinye Cai, Kang Wang, Yi Mei, Zhenhua Li, Jun Zhao, Qingfu ZhangAuthors Info & Claims
Pages 1604 - 1617
Abstract
The multi/many-objective traveling salesman problem (MOTSP), which is NP-hard, can be found in many real-world applications. The Lin–Kernighan (LK) algorithm, as one of the most successful local search (LS) methods for the single-objective traveling salesman problem, adopts a variable neighborhood LS. However, LK cannot be directly applied to the decomposition-based multiobjective optimization framework due to its incapability of effective knowledge transfer among different subproblems, especially for problems with more than two objectives. In this article, we propose an algorithm, called decomposition-based multiobjective LK heuristic with neighborhood structure transfer (NST-MOLK) for MOTSP. In NST-MOLK, the knowledge of a neighborhood structure has been transferred to enhance the efficiency and effectiveness of LK. The experimental studies have been conducted on both benchmark and real-world instances constructed based on the flight prices of seven airlines and 266 airports of different cities in China. Experimental results show that NST-MOLK outperforms both classical and state-of-the-art algorithms significantly. It has also been verified that neighborhood structure transfer can effectively improve the performance of NST-MOLK.
References
[1]
R. Matai, S. P. Singh, and M. L. Mittal, Traveling Salesman Problem: An Overview of Applications, Formulations, and Solution Approaches, vol. 1. London, U.K.: IntechOpen, 2010.
[2]
J. K. Lenstra and A. R. Kan, “Complexity of vehicle routing and scheduling problems,” Networks, vol. 11, no. 2, pp. 221–227, 1981.
[3]
J. Wang, T. Weng, and Q. Zhang, “A two-stage multiobjective evolutionary algorithm for multiobjective multidepot vehicle routing problem with time windows,” IEEE Trans. Cybern., vol. 49, no. 7, pp. 2467–2478, Jul. 2019.
[4]
M. Grötschel, M. Jünger, and G. Reinelt, “Optimal control of plotting and drilling machines: A case study,” Zeitschrift für Oper. Res., vol. 35, no. 1, pp. 61–84, 1991.
[5]
O. Goldschmidt, A. Laugier, and E. V. Olinick, “SONET/SDH ring assignment with capacity constraints,” Discr. Appl. Math., vol. 129, no. 1, pp. 99–128, 2003.
[6]
L. Paquete and T. Stützle, “Design and analysis of stochastic local search for the multiobjective traveling salesman problem,” Comput. Oper. Res., vol. 36, no. 9, pp. 2619–2631, 2009.
[7]
A. Alsheddy and E. E. K. Tsang, “Guided Pareto local search based frameworks for biobjective optimization,” in Proc. IEEE Congr. Evol. Comput., 2010, pp. 1–8.
[8]
E. Ulungu, J. Teghem, P. Fortemps, and D. Tuyttens, “MOSA method: A tool for solving multiobjective combinatorial optimization problems,” J. Multicriteria Decis. Anal., vol. 8, no. 4, p. 221, 1999.
[9]
Y.-C. Liang and M.-H. Lo, “Multi-objective redundancy allocation optimization using a variable neighborhood search algorithm,” J. Heuristics, vol. 16, no. 3, pp. 511–535, 2010.
[10]
S. Bandyopadhyay, S. Saha, U. Maulik, and K. Deb, “A simulated annealing-based multiobjective optimization algorithm: AMOSA,” IEEE Trans. Evol. Comput., vol. 12, no. 3, pp. 269–283, Jun. 2008.
[11]
S. Lin and B. W. Kernighan, “An effective heuristic algorithm for the traveling-salesman problem,” Oper. Res., vol. 21, no. 2, pp. 498–516, 1973.
[12]
K. Helsgaun, “An effective implementation of the Lin–Kernighan traveling salesman heuristic,” Eur. J. Oper. Res., vol. 126, no. 1, pp. 106–130, 2000.
[13]
K. Helsgaun, “General k-opt submoves for the Lin–Kernighan TSP heuristic,” Math. Program. Comput., vol. 1, nos. 2–3, pp. 119–163, 2009.
[14]
T. Sahai, A. Ziessler, S. Klus, and M. Dellnitz, “Continuous relaxations for the traveling salesman problem,” Nonlinear Dyn., vol. 97, no. 4, pp. 2003–2022, 2019.
[15]
M. Held and R. M. Karp, “The traveling-salesman problem and minimum spanning trees,” Oper. Res., vol. 18, no. 6, pp. 1138–1162, 1970.
[16]
M. Held and R. M. Karp, “The traveling-salesman problem and minimum spanning trees: Part II,” Math. Program., vol. 1, no. 1, pp. 6–25, 1971.
[17]
S. Fereidouni, “Solving traveling salesman problem by using a fuzzy multi-objective linear programming,” Afr. J. Math. Comput. Sci. Res., vol. 4, no. 11, pp. 339–349, 2011.
[18]
Y. Mei, K. Tang, and X. Yao, “Decomposition-based memetic algorithm for multiobjective capacitated arc routing problem,” IEEE Trans. Evol. Comput., vol. 15, no. 2, pp. 151–165, Apr. 2011.
[19]
Q. Zhang and H. Li, “MOEA/D: A multiobjective evolutionary algorithm based on decomposition,” IEEE Trans. Evol. Comput., vol. 11, no. 6, pp. 712–731, Dec. 2007.
[20]
H. Ishibuchi, N. Akedo, and Y. Nojima, “Behavior of multiobjective evolutionary algorithms on many-objective knapsack problems,” IEEE Trans. Evol. Comput., vol. 19, no. 2, pp. 264–283, Apr. 2015.
[21]
X. Cai, Z. Mei, and Z. Fan, “A decomposition-based many-objective evolutionary algorithm with two types of adjustments for direction vectors,” IEEE Trans. Cybern., vol. 48, no. 8, pp. 2335–2348, Aug. 2018.
[22]
M. Dorigo and L. M. Gambardella, “Ant colony system: A cooperative learning approach to the traveling salesman problem,” IEEE Trans. Evol. Comput., vol. 1, no. 1, pp. 53–66, Apr. 1997.
[23]
M. Padberg and G. Rinaldi, “A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems,” SIAM Rev., vol. 33, no. 1, pp. 60–100, 1991.
[24]
N. Christofides, “Worst-case analysis of a new heuristic for the travelling salesman problem,” Dept. Manag. Sci. Res. Group, Carnegie-Mellon Univ., Pittsburgh, PA, USA, Rep. ADA025602, 1976.
[25]
H. Ishibuchi and T. Murata, “Multi-objective genetic local search algorithm,” in Proc. IEEE Int. Conf. Evol. Comput., 1996, pp. 119–124.
[26]
A. Jaszkiewicz, “On the performance of multiple-objective genetic local search on the 0/1 knapsack problem—A comparative experiment,” IEEE Trans. Evol. Comput., vol. 6, no. 4, pp. 402–412, Aug. 2002.
[27]
V. A. Shim, K. C. Tan, and C. Y. Cheong, “A hybrid estimation of distribution algorithm with decomposition for solving the multiobjective multiple traveling salesman problem,” IEEE Trans. Syst., Man, Cybern. C, Appl. Rev., vol. 42, no. 5, pp. 682–691, Sep. 2012.
[28]
T. Lust and J. Teghem, “Two-phase Pareto local search for the biobjective traveling salesman problem,” J. Heuristics, vol. 16, no. 3, pp. 475–510, 2010.
[29]
L. Ke, Q. Zhang, and R. Battiti, “Hybridization of decomposition and local search for multiobjective optimization,” IEEE Trans. Cybern., vol. 44, no. 10, pp. 1808–1820, Oct. 2014.
[30]
J. Shi, Q. Zhang, and J. Sun, “PPLS/D: Parallel Pareto local search based on decomposition,” IEEE Trans. Cybern., vol. 50, no. 3, pp. 1060–1071, Mar. 2020.
[31]
S. J. Pan and Q. Yang, “A survey on transfer learning,” IEEE Trans. Knowl. Data Eng., vol. 22, no. 10, pp. 1345–1359, Oct. 2010.
[32]
K. C. Tan, L. Feng, and M. Jiang, “Evolutionary transfer optimization—A new frontier in evolutionary computation research,” IEEE Comput. Intell. Mag., vol. 16, no. 1, pp. 22–33, Feb. 2021.
[33]
J. Lin, H.-L. Liu, K. C. Tan, and F. Gu, “An effective knowledge transfer approach for multiobjective multitasking optimization,” IEEE Trans. Cybern., vol. 51, no. 6, pp. 3238–3248, Jun. 2021.
[34]
A. Gupta, Y.-S. Ong, L. Feng, and K. C. Tan, “Multiobjective multifactorial optimization in evolutionary multitasking,” IEEE Trans. Cybern., vol. 47, no. 7, pp. 1652–1665, Jul. 2017.
[35]
L. Feng, Y.-S. Ong, A.-H. Tan, and I. W. Tsang, “Memes as building blocks: A case study on evolutionary optimization + transfer learning for routing problems,” Memetic Comput., vol. 7, no. 3, pp. 159–180, 2015.
[36]
M.-X. Xu, X.-S. Zhang, and T. Yu, “Transfer bees optimizer and its application on reactive power optimization,” Acta Automatica Sinica, vol. 43, no. 1, pp. 83–93, 2017.
[37]
T. T. H. Dinh, T. H. Chu, and Q. U. Nguyen, “Transfer learning in genetic programming,” in Proc. IEEE Congr. Evol. Comput. (CEC), 2015, pp. 1145–1151.
[38]
Z. Zhang, Z. Wu, H. Zhang, and J. Wang, “Meta-learning-based deep reinforcement learning for multiobjective optimization problems,” IEEE Trans. Neural Netw. Learn. Syst., early access, Feb. 16, 2022. 10.1109/TNNLS.2022.3148435.
[39]
V. Satopaa, J. Albrecht, D. Irwin, and B. Raghavan, “Finding a ‘kneedle’ in a haystack: Detecting knee points in system behavior,” in Proc. 31st Int. Conf. Distrib. Comput. Syst. Workshops, 2011, pp. 166–171.
[40]
H. Robbins, “Some aspects of the sequential design of experiments,” Bull. Amer. Math. Soc., vol. 58, no. 5, pp. 527–535, 1952.
[41]
P. Auer, “Using confidence bounds for exploitation-exploration trade-offs,” J. Mach. Learn. Res., vol. 3, pp. 397–422, Nov. 2002.
[42]
J. Vermorel and M. Mohri, “Multi-armed bandit algorithms and empirical evaluation,” in Proc. Eur. Conf. Mach. Learn., 2005, pp. 437–448.
[43]
W. Hoeffding, “Probability inequalities for sums of bounded random variables,” in The Collected Works of Wassily Hoeffding. New York, NY, USA: Springer, 1994, pp. 409–426.
[44]
G. Reinelt, “TSPLIB—A traveling salesman problem library,” ORSA J. Comput., vol. 3, no. 4, pp. 376–384, 1991.
[45]
H. B. Mann and D. R. Whitney, “On a test of whether one of two random variables is stochastically larger than the other,” Ann. Math. Stat., vol. 18, no. 1, pp. 50–60, 1947.
[46]
X. Caiet al., “The collaborative local search based on dynamic-constrained decomposition with grids for combinatorial multiobjective optimization,” IEEE Trans. Cybern., vol. 51, no. 5, pp. 2639–2650, May 2021.
[47]
X. Cai, H. Sun, Q. Zhang, and Y. Huang, “A grid weighted sum Pareto local search for combinatorial multi and many-objective optimization,” IEEE Trans. Cybern., vol. 49, no. 9, pp. 3586–3598, Sep. 2019.
[48]
T. Lust and A. Jaszkiewicz, “Speed-up techniques for solving large-scale biobjective TSP,” Comput. Oper. Res., vol. 37, no. 3, pp. 521–533, 2010.
[49]
I. Das and J. E. Dennis, “Normal-boundary intersection: A new method for generating the Pareto surface in nonlinear multicriteria optimization problems,” SIAM J. Optim., vol. 8, no. 3, pp. 631–657, 1998.
[50]
H. Li and Q. Zhang, “Multiobjective optimization problems with complicated Pareto sets, MOEA/D and NSGA-II,” IEEE Trans. Evol. Comput., vol. 13, no. 2, pp. 284–302, Apr. 2009.
[51]
E. Zitzler and L. Thiele, “Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach,” IEEE Trans. Evol. Comput., vol. 3, no. 4, pp. 257–271, Nov. 1999.
Index Terms
- Decomposition-Based Lin–Kernighan Heuristic With Neighborhood Structure Transfer for Multi/Many-Objective Traveling Salesman Problem
Index terms have been assigned to the content through auto-classification.
Recommendations
Perturbed Decomposition Algorithm applied to the multi-objective Traveling Salesman Problem
Dealing with multi-objective combinatorial optimization, this article proposes a new multi-objective set-based meta-heuristic named Perturbed Decomposition Algorithm (PDA). Combining ideas from decomposition methods, local search and data perturbation, ...
A novel multi-objective evolutionary algorithm based on subpopulations for the bi-objective traveling salesman problem
This paper presents a new approach called MOEA/NSM (multi-objective evolutionary algorithm integrating NSGA-II, SPEA2 and MOEA/D features). This paper combines the main characteristics of the NSGA-II, SPEA2 and MOEA/D algorithms, and also including 2-...
A decomposition based estimation of distribution algorithm for multiobjective traveling salesman problems
The traveling salesman problem (TSP) is a well known NP-hard benchmark problem for discrete optimization. However, there is a lack of TSP test instances for multiobjective optimization and some current TSP instances are combined to form a multiobjective ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
1089-778X © 2022 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See https://www.ieee.org/publications/rights/index.html for more information.
Publisher
IEEE Press
Publication History
Published: 01 December 2023
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 05 Mar 2025