An Improved Simulated Annealing Algorithm for Traveling Salesman Problem
Traveling salesman problem (TSP) is one of the well-known NP-Complete problems. The simulated annealing algorithm is improved with the four vertices and three lines inequality to search the optimal Hamiltonian circuit or near optimal Hamiltonian circuit.
- PDF / 1,788,286 Bytes
- 8 Pages / 439.37 x 666.142 pts Page_size
- 53 Downloads / 292 Views
An Improved Simulated Annealing Algorithm for Traveling Salesman Problem Yong Wang, De Tian and Yuhua Li
Abstract Traveling salesman problem (TSP) is one of the well-known NP-Complete problems. The simulated annealing algorithm is improved with the four vertices and three lines inequality to search the optimal Hamiltonian circuit or near optimal Hamiltonian circuit. The four vertices and three lines inequality is considered as the heuristic information to change the local Hamiltonian paths into the local optimal Hamiltonian paths. The local optimal Hamiltonian circuits are generated with the basic simulated algorithm firstly, and the local Hamiltonian paths in them are changed into the local optimal Hamiltonian paths with the four vertices and three lines inequality, and then the shorter local optimal Hamiltonian circuits are obtained. The algorithm of the improved simulated annealing is designed and tested with several TSP instances. The experimental results show that the shorter local optimal Hamiltonian circuits are found than those searched with the basic simulated annealing algorithm under the same preconditions.
Keywords Traveling salesman problem Simulated annealing Four vertices and three lines inequality Algorithm
56.1 Introduction Traveling salesman problem (TSP) aims to find the optimal Hamiltonian circuit (OHC) in a tourist map. It has been proven to be one of the NP-Complete problems. The number of the Hamiltonian circuits (HC) increases exponentially
Y. Wang (&) D. Tian Y. Li School of Renewable Energy, North China Electric Power University, No.2 Beinong Road, Hui Longguan, Changping district, 102206 Beijing, China e-mail: [email protected]
W. Lu et al. (eds.), Proceedings of the 2012 International Conference on Information Technology and Software Engineering, Lecture Notes in Electrical Engineering 211, DOI: 10.1007/978-3-642-34522-7_56, Springer-Verlag Berlin Heidelberg 2013
525
526
Y. Wang et al.
proportion to the number of the cities in the map [1] (given the cities are connected by the routes). The TSP has been widely studied in the fields of combinatorial mathematics, graph theory and computer science due to its theoretical and practical values as it is resolved within a reasonable computation time. The algorithms for TSP can be categorized into three types which are the exact algorithms, the approximate algorithms and the intelligent algorithms. With the exact algorithms, the OHC is ensured to be found whereas they are not appropriate to cope with the large scale TSP. These algorithms include the traditional graph search algorithms [2], linear programming methods [3] and dynamic programming methods [4]. The experiments illustrated that the better exact algorithms are feasible to resolve the TSP with less than 1,000 cities [5] with powerful computers. If the TSP scale becomes larger, the computation time is too long. The approximate algorithms can not guarantee to find the OHC. However, they play an important role for TSP because the time complexity is polynomial but
Data Loading...
