Ιδρυματικό Αποθετήριο
Πολυτεχνείο Κρήτης
Πολυτεχνείο Κρήτης
EN
|
EL
| URI: | http://purl.tuc.gr/dl/dias/46EB592A-3CD1-477D-82F3-B2D90311E0E1 | ||
| Έτος | 2007 | ||
| Τύπος | Πλήρης Δημοσίευση σε Συνέδριο | ||
| Άδεια Χρήσης |
|
||
| Βιβλιογραφική Αναφορά | Y. Marinakis, M. Marinaki, G. Dounias, "Honey bees mating optimization algorithm for combinatorial optimization problems,"in 3rd Annual Symposium,2007. | ||
| Εμφανίζεται στις Συλλογές |
This paper introduces a new hybrid algorithmic nature inspired approach based on Honey Bees Mating Optimization, for successfully solving two Combinatorial Optimization Problems, the Travelling Salesman Problem and the Vehicle Routing Problem. The Honey Bees Mating Optimization algorithm simulates the mating process of the queen of the hive. The mating process of the queen begins when the queen flights away from the nest performing the mating flight during which the drones follow the queen and mate with her in the air. The proposed algorithm for the solution, the Honey Bees Mating Optimization (HBMOCOP), combines a Honey Bees Mating Optimization (HBMO) algorithm, the Multiple Phase Neighborhood Search - Greedy Randomized Adaptive Search Procedure (MPNS-GRASP) algorithm and the Expanding Neighborhood Search Strategy. The proposed algorithm is tested on two sets of benchmark instances, one for the Travelling Salesman Problem and one for the Vehicle Routing Problem and produces very satisfactory results for both of them. In the Travelling Salesman Problem, the proposed algorithm is tested on a set of 74 benchmark instances from the TSPLIB and in all but eleven instances the best known solution is found. For the rest instances the quality of the produced solution is less than 0.1% from the optimum. In the Vehicle Routing Problem, the algorithm is tested in the 14 classic instances proposed by Christofides and in all instances the quality is less than 0.20% from the optimum and the average quality is 0.029% from the optimum. The algorithm is ranked in the 2th place among the most known and effective algorithms in the literature for both problems and in the first place among all Nature Inspired methods that have ever been used for the Vehicle Routing Problem.
Copyright © DIAS 2013
