FINDING A MINIMAL HAMILTONIAN TOUR THROUGH A SELECTED SET OF IRANIAN POINTS USING HYBRID ANT COLONY SYSTEM AND LOCAL SEARCH ALGORITHM

Q: How can I download an article?

To download an article from SID, first log in to the site, search for the article title, and click on the 'Download Article' option.

Q: How can I download an ISI article?

To download an ISI article on SID, enter the keyword or article title in the search bar, view the relevant results, click on the desired article, and select the 'Download Article' option.

Q: How can I access the SID database?

To access the SID database, visit SID.ir, create an account, and log in to access scientific resources.

Q: Is downloading articles from SID free?

Some articles on SID are available for free, while others require payment. Details are specified on the article's page.

GHOSEYRI K.; SARHADI H.

مرکز اطلاعات علمی Scientific Information Database (SID) - Trusted Source for Research and Academic Resources

Journal Paper

Paper Information

Journal: JOURNAL OF TRANSPORTATION RESEARCH Year:2009 | Volume:6 | Issue:2 (19) Page(s): 149-161

Download Full-Text

Persian Verion

View:

960

Download:

Cites:

Information Journal Paper

Title

FINDING A MINIMAL HAMILTONIAN TOUR THROUGH A SELECTED SET OF IRANIAN POINTS USING HYBRID ANT COLONY SYSTEM AND LOCAL SEARCH ALGORITHM

Author(s)

GHOSEYRI K. | SARHADI H. | Issue Writer Certificate

Keywords

TRAVELING SALESMAN PROBLEMQ3

MINIMAL HAMILTONIAN IRANIAN TOURQ3

COMBINATORIAL OPTIMIZATIONQ3

ANT OPTIMIZATIONQ3

LOCAL SEARCH ALGORITHMQ3

Abstract

TRAVELING 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 NPCompleteness 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 bioinformatics. 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 16 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.

Cites

FINDING THE SHORTEST HAMILTONIAN PATH FOR IRANIAN CITIES, USING TABU SEARCH AND MEMETIC ALGORITHMS

References

No record.

Cite

APA: Copy

GHOSEYRI, K., & SARHADI, H.. (2009). FINDING A MINIMAL HAMILTONIAN TOUR THROUGH A SELECTED SET OF IRANIAN POINTS USING HYBRID ANT COLONY SYSTEM AND LOCAL SEARCH ALGORITHM. JOURNAL OF TRANSPORTATION RESEARCH, 6(2 (19)), 149-161. SID. https://sid.ir/paper/83773/en

Vancouver: Copy

GHOSEYRI K., SARHADI H.. FINDING A MINIMAL HAMILTONIAN TOUR THROUGH A SELECTED SET OF IRANIAN POINTS USING HYBRID ANT COLONY SYSTEM AND LOCAL SEARCH ALGORITHM. JOURNAL OF TRANSPORTATION RESEARCH[Internet]. 2009;6(2 (19)):149-161. Available from: https://sid.ir/paper/83773/en

IEEE: Copy

K. GHOSEYRI, and H. SARHADI, “FINDING A MINIMAL HAMILTONIAN TOUR THROUGH A SELECTED SET OF IRANIAN POINTS USING HYBRID ANT COLONY SYSTEM AND LOCAL SEARCH ALGORITHM,” JOURNAL OF TRANSPORTATION RESEARCH, vol. 6, no. 2 (19), pp. 149–161, 2009, [Online]. Available: https://sid.ir/paper/83773/en

Related Journal Papers