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

Αναζήτηση

Πλοήγηση

Ο Χώρος μου

Multiple phase neighborhood search GRASP for the capacitated vehicle routing problem

Marinakis Ioannis

Πλήρης Εγγραφή


URI: http://purl.tuc.gr/dl/dias/3B5B7066-D476-4E25-ADE6-8F21C59F4F56
Έτος 2012
Τύπος Δημοσίευση σε Περιοδικό με Κριτές
Άδεια Χρήσης
Λεπτομέρειες
Βιβλιογραφική Αναφορά Y. 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.015 https://doi.org/10.1016/j.eswa.2012.01.015
Εμφανίζεται στις Συλλογές

Περίληψη

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

Υπηρεσίες

Στατιστικά