Article Preview
Top1. Introduction
The shortest Hamiltonian path is a well-known and important combinatorial optimization problem. The goal of Traveling Salesman Problem (TSP) is to find the shortest path that visits each city in a given list exactly once and then returns to the starting city. The distances between n cities are stored in a distance matrix D with elements dij where i, j = 1, 2, ..., n and the diagonal elements dij are zero (Hahsler & Hornik, 2007). In the 1920’s, the mathematician and economist Menger publicized this problem among his colleagues in Vienna. In the 1930’s the problem reappeared in the mathematical circles of Princeton (Applegate et al., 1998). In the 1940’s, mathematician Flood publicized the name, TSP, within the mathematical community at mass (Lawler et al., 1985). Despite this simple problem statement, solving the TSP is difficult, since it belongs to the class of NP-complete problems (Johnson & Papadimitriou, 1985). The importance of the TSP arises besides from its theoretical appeal from the variety of its applications. Typical applications in operations research include vehicle routing, computer wiring, cutting wallpaper, job sequencing, and job scheduling. Recognizing methods to solve TSP and find the appropriate method is one of the important research areas (Hahsler & Hornik, 2009). In this paper, a comparative study is conducted between Simulated Annealing (SA) and Tabu Search (TS) algorithm as single-solution-based algorithms, Ant Colony Optimization (ACO), and Genetic Algorithm (GA) as population-based-algorithms to find the shortest Hamiltonian path for 1071 Iranian cities.
The proposed algorithms are implemented based on Design and Implementation Methodology for Metaheuristic Algorithms (DIMMA). DIMMA has three sequential phases that each of them has several steps (Figure 1). These phases are as follows: initiation, in which the problem in hand must be understood precisely, the goal of designing metaheuristic must be clearly defined, and the instances must be selected. The next phase is blueprint, the important goals of this phase are selecting solution strategy, defining performance measures, and designing algorithm for the solution strategy. The last phase is construction in which implementing the designed algorithm, parameters tuning (parameter setting), analyzing its performance, and finally documentation of results must be done (Yaghini & Kazemzadeh, 2010).
Figure 1. Steps in each phases of DIMMA. (Adapted from [Yaghini & Kazemzadeh], 2010)
The contribution of our paper could be summarized as follows. In this paper, we proposed four effectiveness and efficient hybrid algorithms for solving TSP problem. High quality of the solution and short computation time show the efficiency and effectiveness of the algorithms. Tuning parameter has been done using DOE based on sequential methodology. Using metaheuristic algorithms with local search to finding the shortest Hamiltonian path between the Iranian cities is the practical contribution of this paper.
The paper is organized as follows. In section two, literature review is conducted. In the third section, the initiation phase of the proposed algorithms is presented. In the fourth section, blueprint, and in the fifth section construction phase of algorithms are discussed. In section six, the shortest Hamiltonian path between Iranian cities is derived by using the proposed algorithms. Conclusion is presented in section seven.
Top2. Literature Review
The TSP problem has different types, such as Probabilistic Traveling Salesman Problem (PTSP), Traveling Salesman Problem with Time Windows (TSPTW), Multicommodity Traveling Salesman Problem (MTSP), and Railway Traveling Salesman Problem (RTSP).