Institutional Repository [SANDBOX]
Technical University of Crete
EN  |  EL

Search

Browse

My Space

Multiple phase neighborhood search GRASP for the capacitated vehicle routing problem

Marinakis Ioannis

Simple record


URIhttp://purl.tuc.gr/dl/dias/3B5B7066-D476-4E25-ADE6-8F21C59F4F56-
Identifierhttps://doi.org/10.1016/j.eswa.2012.01.015-
Languageen-
Extent9 pagesen
TitleMultiple phase neighborhood search GRASP for the capacitated vehicle routing problemen
CreatorMarinakis Ioannisen
CreatorΜαρινακης Ιωαννηςel
PublisherElsevieren
Content SummaryGreedy Randomized Adaptive Search Procedure (GRASP) has been proved to be a very efficient algorithm for the solution of the Traveling Salesman Problem. Also, it has been proved that expanding the local search with the use of two or more different local search strategies helps the algorithm to avoid trapping in a local optimum. In this paper, a new modified version of GRASP, called Multiple Phase Neighborhood Search-GRASP (MPNS-GRASP), for the solution of the Vehicle Routing Problem is proposed. In this method, a stopping criterion based on Lagrangean Relaxation and Subgradient Optimization is utilized. In addition, a different way for expanding the neighborhood search is used based on a new strategy, the Circle Restricted Local Search Moves strategy. The algorithm was tested on two sets of benchmark instances and gave very satisfactory results. In both sets of instances the results have solution qualities with average values near to the optimum values and in a number of them the algorithm finds the optimum. The computational time of the algorithm is decreased significantly compared to other heuristic and metaheuristic algorithms due to the fact that the new strategy, the Expanding Neighborhood Search Strategy, is used.en
Type of ItemPeer-Reviewed Journal Publicationen
Type of ItemΔημοσίευση σε Περιοδικό με Κριτέςel
Licensehttp://creativecommons.org/licenses/by/4.0/en
Date of Item2015-11-05-
Date of Publication2012-
SubjectVRP (Vehicle routing problem)en
Subjectvehicle routing problemen
Subjectvrp vehicle routing problemen
Bibliographic CitationY. Marinakis, "Multiple phase neighborhood search GRASP for the capacitated vehicle routing problem," Exp. Systems with Appl. ,vol. 39,no. 8, pp. 6807-6815 ,Ju. 2012.doi:10.1016/j.eswa.2012.01.015en

Services

Statistics