The hybrid genetic algorithm with two local optimization strategies for traveling salesman problem |
| |
| Affiliation: | 1. College of Management & Economics, Tianjin University, 92 Weijin Road, Nankai District, Tianjin, 300072, China;2. Department of Civil and Environmental Engineering, Rutgers, The State University of New Jersey, CoRE 736, 96 Frelinghuysen Road, Piscataway, NJ, 08854-8018, United States;1. School of Management, Chongqing Jiaotong University, Chongqing 400074, China;2. Department of Civil and Environmental Engineering, University of Washington, Seattle, WA 98195-2700, USA;3. School of Transportation Science and Engineering, Beijing Key Laboratory for Cooperative Vehicle Infrastructure, Systems, and Safety Control, Beihang University, Beijing 100191, China;4. Jiangsu Province Collaborative Innovation Center of Modern Urban Traffic Technologies, SiPaiLou #2, Nanjing 210096, China;1. University of Vigo, Spain;2. University of Girona, Spain |
| |
| Abstract: | Traveling salesman problem (TSP) is proven to be NP-complete in most cases. The genetic algorithm (GA) is improved with two local optimization strategies for it. The first local optimization strategy is the four vertices and three lines inequality, which is applied to the local Hamiltonian paths to generate the shorter Hamiltonian circuits (HC). After the HCs are adjusted with the inequality, the second local optimization strategy is executed to reverse the local Hamiltonian paths with more than 2 vertices, which also generates the shorter HCs. It is necessary that the two optimization strategies coordinate with each other in the optimization process. The two optimization strategies are operated in two structural programs. The time complexity of the first and second local optimization strategies are O(n) and O(n3), respectively. The two optimization strategies are merged into the traditional GA. The computation results show that the hybrid genetic algorithm (HGA) can find the better approximate solutions than the GA does within an acceptable computation time. |
| |
| Keywords: | Traveling salesman problem Genetic algorithm Local optimization strategies |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
