A N E V A L U A T I O N O F P E R F O R M A N C E O F A R T I F I C I A L B E E C O L O N Y A L G O R I T H M F O R S O L V I N G T H E C O M B I N A T O R I A L O P T I M I Z A T I O N P R O B L E M S
Author(s):
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.
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:
Language:
Persian
Published:
Sharif Journal Civil Engineering, Volume:33 Issue: 2, 2017
Pages:
15 to 23
magiran.com/p1753818
دانلود و مطالعه متن این مقاله با یکی از روشهای زیر امکان پذیر است:
اشتراک شخصی
با عضویت و پرداخت آنلاین حق اشتراک یکساله به مبلغ 1,390,000ريال میتوانید 70 عنوان مطلب دانلود کنید!
اشتراک سازمانی
به کتابخانه دانشگاه یا محل کار خود پیشنهاد کنید تا اشتراک سازمانی این پایگاه را برای دسترسی نامحدود همه کاربران به متن مطالب تهیه نمایند!
توجه!
- حق عضویت دریافتی صرف حمایت از نشریات عضو و نگهداری، تکمیل و توسعه مگیران میشود.
- پرداخت حق اشتراک و دانلود مقالات اجازه بازنشر آن در سایر رسانههای چاپی و دیجیتال را به کاربر نمیدهد.
In order to view content subscription is required
Personal subscription
Subscribe magiran.com for 70 € euros via PayPal and download 70 articles during a year.
Organization subscription
Please contact us to subscribe your university or library for unlimited access!