مهندسی عمران شریف (Aug 2017)
AN EVALUATION OF PERFORMANCE OF ARTIFICIAL BEE COLONY ALGORITHM FOR SOLVING THE COMBINATORIAL OPTIMIZATION PROBLEMS
Abstract
Optimization methods are one of the strongest tools for managing time and decreasing unnecessary costs in operational issues. The purpose of optimization, regarding constraints and requirements, is to find an appropriate and acceptable solution to a problem. Since; most of the combinatorial optimization problems, such as Travelling Salesman Problem (TSP) and different types of Vehicle Routing Problem (VRP), are subcategories of NP-Hard class, expert recommendations are toward solving these kinds of problems by metaheuristic algorithms such as Artificial Bee Colony (ABC) algorithm instead of exact solving methodologies. In this paper, a comprehensive study was conducted on the background of Artificial Bee Colony algorithms and the results of its application on various transportation problems. The formulation of Vehicle Routing Problem and its constraints was also discussed. The results show that the ABC algorithm has a significant power to improve solving various problems. As an intuitive summary, one can refer to Szeto et al. (2010) who proposed an ABC algorithm for solving the Capacitated Vehicle Routing Problem in which the mean percentage improvement of the average results of all test instances was 4.16\% and the best percentage improvement was 3.53\%. Further, a Hybrid ABC algorithm was designed by Zhang et al. (2014) for one of the latest Vehicle Routing Problems. They implemented the algorithm for Environmental Vehicle Routing Problem which outperforms the original ABC algorithm by 5\% on average. Therefore, it can be concluded that the Artificial Bee Colony algorithm is very successful in improving the results of this kind of experiment.In completion of the above-mentioned, the results of the proposed ABC algorithm by this study for solving Travelling Salesman Problem and Vehicle Routing Problem with Simultaneous Pickup and Delivery confirmed the expressed idea. As a result, the assumed algorithm improved instances of TSP about 1.03\% and 8.88\% which were named gr120 and gr202, respectively. It also enhanced the CMT1X and CMT3X instances in VRP-SPD about 0.41\% and 1.31\%, respectively. This certificates the quality, high capacity and preference of the ABC algorithm.
Keywords
