Ιδρυματικό Αποθετήριο [SANDBOX]
Πολυτεχνείο Κρήτης
EN  |  EL

Αναζήτηση

Πλοήγηση

Ο Χώρος μου

Multiple phase neighborhood Search—GRASP based on Lagrangean relaxation, random backtracking Lin–Kernighan and path relinking for the TSP

Marinaki Magdalini, Athanasios Migdalas , Panos Pardalos

Απλή Εγγραφή

URIhttp://purl.tuc.gr/dl/dias/FE84BDB6-E53A-486F-A8C7-A4A3CDB1B6AF-
Αναγνωριστικόhttps://doi.org/10.1007/s10878-007-9104-2-
Γλώσσαen-
Μέγεθος23 pagesen
ΤίτλοςMultiple phase neighborhood Search—GRASP based on Lagrangean relaxation, random backtracking Lin–Kernighan and path relinking for the TSP en
ΔημιουργόςMarinaki Magdalinien
ΔημιουργόςΜαρινακη Μαγδαληνηel
Δημιουργός Athanasios Migdalas en
Δημιουργός Panos Pardalosen
ΕκδότηςSpringer Verlagen
ΠερίληψηIn this paper, a new modified version of Greedy Randomized Adaptive Search Procedure (GRASP), called Multiple Phase Neighborhood Search—GRASP (MPNS-GRASP), is proposed for the solution of the Traveling Salesman Problem. In this method, some procedures have been included to the classical GRASP algorithm in order to improve its performance and to cope with the major disadvantage of GRASP which is that it does not have a stopping criterion that will prevent the algorithm from spending time in iterations that give minor, if any, improvement in the solution. Thus, in MPNS-GRASP a stopping criterion based on Lagrangean Relaxation and Subgradient Optimization is proposed. Also, a different way for expanding the neighborhood search is used based on a new strategy, the Circle Restricted Local Search Moves strategy. A new variant of the Lin-Kernighan algorithm, called Random Backtracking Lin-Kernighan that helps the algorithm to diversify the search in non-promising regions of the search space is used in the Expanding Neighborhood Search phase of the algorithm. Finally, a Path Relinking Strategy is used in order to explore trajectories between elite solutions. The proposed algorithm is tested on numerous benchmark problems from TSPLIB with very satisfactory results.en
ΤύποςPeer-Reviewed Journal Publicationen
ΤύποςΔημοσίευση σε Περιοδικό με Κριτέςel
Άδεια Χρήσηςhttp://creativecommons.org/licenses/by/4.0/en
Ημερομηνία2015-11-05-
Ημερομηνία Δημοσίευσης2009-
Θεματική ΚατηγορίαLagrangean relaxation and subgradient optimizationen
Βιβλιογραφική ΑναφοράY. Marinakis, A. Migdalas , P.M. Pardalos,"Multiple phase neighborhood search GRASP based on lagrangean relaxation, random backtracking lin-kernighan and path relinking for the traveling salesman problem, Journal of Comb. Optimization,vol.17 ,no.2 ,pp. 134-156,Feb. 2009.doi:10.1007/s10878-007-9104-2en

Υπηρεσίες

Στατιστικά

 

Copyright © DIAS 2013