Masoud Yaghini (Iran University of Science and Technology, Iran), Mohsen Momeni (Iran University of Science and Technology, Iran) and Mohammadreza Sarmadi (Iran University of Science and Technology, Iran)

Copyright: © 2013
|Pages: 17

DOI: 10.4018/978-1-4666-2145-9.ch017

Chapter Preview

TopThe 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 *d _{ij}* where

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).

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.

TopThe 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).

The PTSP is a topic of theoretical and practical importance in the study of stochastic network problems. It provides researchers with a modeling framework for exploring the stochastic effects in routing problems. Designing effective algorithms for stochastic routing problems is a difficult task. This is due to the element of uncertainty in the data, which increases the difficulty of finding an optimal solution in a large search space (Jaillet, 1988; Bertsimas, 1988).

Search this Book:

Reset

Copyright © 1988-2020, IGI Global - All Rights Reserved