يافتن كوتاه ترين تور هميلتوني ايران با استفاده از تركيب الگوريتم سيستم اجتماع مورچه ها و جستجوي محلي

Finding a Minimal Hamiltonian Tour through a selected set of Iranian Points using Hybrid Ant Colony System and Local Search Algorithm

raveling Salesman Problem (TSP) is one of the most well known and applicable problems in combinatorial optimization that transportation makes up the most notable applications of the problem. Its definition is simple and clear while its solving is very hard. In the classic TSP, a salesman wants to find the cheapest way of visiting a number of cities in which each city must be visited exactly once. The TSP can be symmetric or asymmetric. In symmetric one, the distance between each two cities does not depend on the direction. The classic TSP is also known as finding the shortest Hamiltonian tour. In addition to the classic TSP, which is defined so far, the problem has numerous variants from which we can mention traveling salesman problem with time windows, period traveling salesman problem, selective traveling salesman problem, moving object traveling salesman problem and so on. The importance of the TSP lies in two aspects: theoretical and practical aspects. In theoretical aspect, because the TSP is one of the first problems that its NP-Completeness has been proved, i.e. there is no algorithm to solve it in polynomial time; it has become a test bed for new algorithmic ideas. In the practical aspect, its simple definition has resulted to many direct or indirect applications in different problems of various domains like transportation, production planning, and bio informatics. In transportation domain, as our attention. General routing problems generally deal with transporting of customers/commodities on a given network using an optimal method, from which, we can mention the distribution of services/commodities from depots to customers, vehicle routing problems, production and distribution planning and so on. These problems occur in operational management while the classic TSP is the core of most of them. In fact, although the TSP has direct applications, we can also mention indirect applications of the TSP in many other problems like the vehicle routing problems, crew scheduling, and train scheduling. Because the physical costs of distribution make up a considerable amount of the total distribution costs in each economy, any reduction in these costs through improved solution methods and algorithms of routing problems results in great savings and benefits to the final customers. So, in this paper we develop a successful solution method in solving the TSP and then apply it for the first time to 360 selected cities of Iran to find the shortest Hamiltonian tour. The cities had been chosen based on their economical and political importance. As a solution method, among numerous exact and approximate ones, a new combination of the ant colony system (ACS) and the local search is used. Ant algorithms with inspirations of real antsʹ foraging behavior are competent in solving hard optimization problems while using a local search can lead to better results. In other words, the ACS section of the proposed algorithm is rather responsible for searching the solution space while the local search part refines the search and directs it to the most promising regions by locally optimizing the solutions of the ACS section. To check for quality of the solutions, results are compared to the results of the well-known ACS. This comparison shows the complete superiority of the suggested method over the ACS. These results also can be used in future for other comparisons of different solution methods for this problem.