JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE) ›› 2012, Vol. 42 ›› Issue (2): 30-35.

• Articles • Previous Articles     Next Articles

Heuristic construction method for the initial tour of the Lin-Kernighan algorithm

ZENG Hua1, CUI Wen2, FU Lian-ning1, WU Yao-hua1*   

  1. 1. School of Control Science and Engineering, Shandong University, Jinan 250061, China;
    2.  The Logistics Institute, Shandong University, Jinan 250061, China
  • Received:2011-05-28 Online:2012-04-20 Published:2011-05-28

PDF (PC)

4731

Abstract:

 Initialization construction strategy is an important phase of the LinKernighan algorithm, which is known as one of the most efficient heuristic methods to solve the traveling salesman problem. In most past research, only one construction strategy was adopted, but there was little  research on what strategies could be used in the LinKernighan algorithm and how differently  they perform. 8 construction strategies were analyzed, and 4 of them were found applicable  for LinKernighan initialization. Numerical experiments and computational results with 6 TSPLIP instances showed that  the 4 construction strategies proposed were effective and efficient initialization methods. Additionally, it was proved that the Clark Wright algorithm had the best convergence speed, while the nearest insertion algorithm had the best optimization rate.

Key words: LinKernighan, initial path, heuristic algorithm, the traveling salesman problem, performance evaluation

[1] CAO Fubo, XIAO Shengxian, WANG Chenxia, GAO Delong, LI Dun, SU Tian, QIN Shijie, WANG Yufei. Comprehensive performance evaluation of recycled brick mixed water stabilized material with multiple indicators based on entropy weight TOPSIS [J]. Journal of Shandong University(Engineering Science), 2025, 55(6): 151-162.
[2] WANG Shi, XU Xiaohui, ZHU Xiaoying, JIANG Han, CAO Dayan. A dynamic pricing spectrum strategy responded customized requirements in heterogeneous cognitive radio-based Internet of Things [J]. Journal of Shandong University(Engineering Science), 2025, 55(3): 100-110.
[3] Jun QIN,Weidong LI,Jinli YI,Jing LIU,Maode MA. Ant colony optimization for solving maximization problem based ondouble heuristic information [J]. Journal of Shandong University(Engineering Science), 2020, 50(3): 45-50.
[4] WU Ke-shou, CHEN Yu-ming, ZENG Zhi-qiang. Decision table reduction based on neighborhood relation [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2012, 42(2): 7-10.
[5] FU Lian-ning1, CUI Wen2, ZENG Hua1 . The adaptive neighborhood selection strategy of the parallel Clarke-Wright algorithm [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2012, 42(1): 72-80.
[6] LI Yu-jian, MENG Dong-xia*, GUI Zhi-ming. Fast computation of characteristic boundary points for improving geometric ensembles [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2011, 41(4): 56-60.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] . [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(1): 27 -32 .
[2] YUE Yuan-Zheng. Relaxation in glasses far from equilibrium[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(5): 1 -20 .
[3] XU Li-li,JI Zhong,XIA Ji-mei . The optimum algorithm for the container loading problem with homogeneous cargoes[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2008, 38(3): 14 -17 .
[4] YU Hai-bo,LI Yu,YU Tian,LEI Hong . Influence of the dimensions of W-band folded waveguide slow-wave system on its cold characteristics[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2008, 38(3): 90 -94 .
[5] KONG Xian-Meng, JU Pei-Jun. New stability criterion for a class of uncertain neutral systems with time-varying delay[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(5): 48 -51 .
[6] XU Xiaodan, DUAN Zhengjie, CHEN Zhongyu. The sentiment mining method based on extended sentiment dictionary and integrated features[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2014, 44(6): 15 -18 .
[7] MENG Jian, LI Yibin, LI Bin. Bound gait controlling method of quadruped robot[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2015, 45(3): 28 -34 .
[8] ZHU Xiang-cai,LUAN Yun-cai,XU Jian . An urban traffic evaluation system based on VB and FTA[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2007, 37(4): 89 -92 .
[9] MA Shi-Wei, MEI Zhi-Rong, ZHANG Jun-Wei, DU Jun. The mechanism and prevention technology of the inrush  water disaster warning of karst tunnels[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(4): 12 -16 .
[10] HE Dongzhi, ZHANG Jifeng, ZHAO Pengfei. Parallel implementing probabilistic spreading algorithm using MapReduce programming mode[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 0, (): 22 -28 .
Copyright 2018 © Editorial office of Journal of Shandong University (Engineering Science)
Supported by Beijing Magtech Co.Ltd