A quick Heuristic and a general search algorithm for traveling salesman problem
This paper puts forward a constructive heuristic algorithm called the method of inserting the minimum neighbor edge from outside to the center (IMNEFOTC) that can be applied to solve large-scale and ultra-large-scale travelling salesman problems. Through it and the randomized greedy heuristic algori...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
EDP Sciences
2022-01-01
|
| Series: | E3S Web of Conferences |
| Subjects: | |
| Online Access: | https://www.e3s-conferences.org/articles/e3sconf/pdf/2022/27/e3sconf_vesep2022_01097.pdf |
| _version_ | 1811186272125845504 |
|---|---|
| author | Wang Chao Wang Deguang Jin Chun |
| author_facet | Wang Chao Wang Deguang Jin Chun |
| author_sort | Wang Chao |
| collection | DOAJ |
| description | This paper puts forward a constructive heuristic algorithm called the method of inserting the minimum neighbor edge from outside to the center (IMNEFOTC) that can be applied to solve large-scale and ultra-large-scale travelling salesman problems. Through it and the randomized greedy heuristic algorithm (RGH) which greedy heuristic algorithm is modified, a general meta-heuristic search algorithm framework is built. The general search algorithm (GSA) is based on a set of initial solutions, and continuous 2-opt operations are performed, so as to search for solutions in better quality. The data from the experiment reveals that the performance of IMNEFOTC is better than the traditional greedy algorithm, and the GSA can obtain a pretty satisfactory solution in a reasonable range of time. |
| first_indexed | 2024-04-11T13:43:50Z |
| format | Article |
| id | doaj.art-264f499eb9804481be400771d2e1fd53 |
| institution | Directory Open Access Journal |
| issn | 2267-1242 |
| language | English |
| last_indexed | 2024-04-11T13:43:50Z |
| publishDate | 2022-01-01 |
| publisher | EDP Sciences |
| record_format | Article |
| series | E3S Web of Conferences |
| spelling | doaj.art-264f499eb9804481be400771d2e1fd532022-12-22T04:21:10ZengEDP SciencesE3S Web of Conferences2267-12422022-01-013600109710.1051/e3sconf/202236001097e3sconf_vesep2022_01097A quick Heuristic and a general search algorithm for traveling salesman problemWang Chao0Wang Deguang1Jin Chun2School of Software, Dalian University of Foreign LanguagesSchool of Software, Dalian Jiaotong UniversityInstitute of Systems Engineering, Dalian University of TechnologyThis paper puts forward a constructive heuristic algorithm called the method of inserting the minimum neighbor edge from outside to the center (IMNEFOTC) that can be applied to solve large-scale and ultra-large-scale travelling salesman problems. Through it and the randomized greedy heuristic algorithm (RGH) which greedy heuristic algorithm is modified, a general meta-heuristic search algorithm framework is built. The general search algorithm (GSA) is based on a set of initial solutions, and continuous 2-opt operations are performed, so as to search for solutions in better quality. The data from the experiment reveals that the performance of IMNEFOTC is better than the traditional greedy algorithm, and the GSA can obtain a pretty satisfactory solution in a reasonable range of time.https://www.e3s-conferences.org/articles/e3sconf/pdf/2022/27/e3sconf_vesep2022_01097.pdftraveling salesman problemgreedy heuristic2-opt operationsimulate annealing |
| spellingShingle | Wang Chao Wang Deguang Jin Chun A quick Heuristic and a general search algorithm for traveling salesman problem E3S Web of Conferences traveling salesman problem greedy heuristic 2-opt operation simulate annealing |
| title | A quick Heuristic and a general search algorithm for traveling salesman problem |
| title_full | A quick Heuristic and a general search algorithm for traveling salesman problem |
| title_fullStr | A quick Heuristic and a general search algorithm for traveling salesman problem |
| title_full_unstemmed | A quick Heuristic and a general search algorithm for traveling salesman problem |
| title_short | A quick Heuristic and a general search algorithm for traveling salesman problem |
| title_sort | quick heuristic and a general search algorithm for traveling salesman problem |
| topic | traveling salesman problem greedy heuristic 2-opt operation simulate annealing |
| url | https://www.e3s-conferences.org/articles/e3sconf/pdf/2022/27/e3sconf_vesep2022_01097.pdf |
| work_keys_str_mv | AT wangchao aquickheuristicandageneralsearchalgorithmfortravelingsalesmanproblem AT wangdeguang aquickheuristicandageneralsearchalgorithmfortravelingsalesmanproblem AT jinchun aquickheuristicandageneralsearchalgorithmfortravelingsalesmanproblem AT wangchao quickheuristicandageneralsearchalgorithmfortravelingsalesmanproblem AT wangdeguang quickheuristicandageneralsearchalgorithmfortravelingsalesmanproblem AT jinchun quickheuristicandageneralsearchalgorithmfortravelingsalesmanproblem |