بهینه‌سازی مسیریابی وسایل نقلیه مبتنی بر ترکیب الگوریتم‌های کلونی مورچه و ازدحام ذرات با تابع ابتکاری کسینوس زوایا

نوع مقاله : مقاله پژوهشی

نویسندگان

1 مهندسی کامپیوتر، دانشگاه اراک، اراک، ایران

2 گروه مهندسی کامپیوتر ، دانشگاه اراک ، اراک ، ایران

3 مهندسی کامپیوترـ دانشگاه اراک ـ اراک ـ ایران

چکیده

برای حل وضعیت شلوغی جاده‌ها پژوهش‌های زیادی انجام شده است که عمده راهکارهای ارائه شده بر مبنای الگوریتم‌های فرا ابتکاری می‌باشند. در بسیاری از این الگوریتم‌ها در ابتدای کار مسیریابی به‌صورت تصادفی و در محدوده‌ای بزرگ انجام می‌شود. این موضوع موجب افزایش زمان جستجو می‌شود. همچنین در تحلیل‌های صورت گرفته بر مبنای این الگوریتم‌ها تنها فاصله‌ی فیزیکی بین خودروها در نظر گرفته‌ شده است. با توجه به اینکه عوامل محیطی نظیر ترافیک، در مسیریابی بسیار مؤثر هستند، باید تأثیر این عوامل را در مسیریابی در نظر گرفت. بدین منظور برای حل مشکلات مطرح‌شده، در این مقاله یک روش برنامه‌ریزی مسیر پویا مبتنی بر ترکیب الگوریتم‌های کلونی مورچگان و ازدحام ذرات با اعمال تابع ابتکاری کسینوس زوایا پیشنهاد شده است. این روش عوامل مختلف وضعیت جاده‌ها از جمله طول جاده‌ی شهری و ترافیک ورودی و خروجی تقاطع‌ها را در مسیریابی وسایل نقلیه در نظر می‌گیرد و در مسیریابی برای نقاطی که هم‌راستای مسیر پیمایش به سمت مقصد نهایی باشد شانس بیشتری قائل می‌شود. نتایج حاصل از اعمال مدل پیشنهادی بر روی‌ داده‌های کتابخانه‌ی معتبر TSPLIB که مبتنی بر فاصله فیزیکی بین خودروها است، نشان می‌دهد که زمان جستجوی روش پیشنهادی نسبت به سایر روش‌ها (ده ارزیابی انجام شده) بطور متوسط 40.74 درصد کاهش داشته است. بیشترین و کمترین میزان کاهش به ترتیب 98.1 و 6.02 درصد می‌باشد. همچنین آزمایش برنامه‌ریزی مسیر پویا تحت ترافیک جاده‌ها بر روی برخی از تقاطع-های شهر پکن نشان می‌دهد که روش پیشنهادی به صورت میانگین 1.57 درصد تراکم و ازدحام ایجاد می‌کند.

کلیدواژه‌ها

موضوعات


عنوان مقاله [English]

Optimization of vehicle routing based on the combination of ant colony and particle swarm algorithms with the heuristic function of the cosine of angles

نویسندگان [English]

  • HamidReza Shafiei 1
  • Vahid Rafe 2
  • Maryam Amiri 3
1 Department of Computer Engineering, Faculty of Engineering. Arak university, Arak, IRAN
2 Department of Computer Engineering, Arak University, Arak, Iran
3 Department of Computer Engineering, Faculty of Engineering. Arak university, Arak, IRAN
چکیده [English]

A lot of research has tried to solve the congestion of roads using meta-heuristic algorithms. In these algorithms, firstly, routing is done randomly over large areas. This will increase the search time. In addition, these algorithms only consider the physical distance between the vehicles. Since environmental factors such as traffic are very effective in routing, these factors should be considered in routing. In this paper, to solve the problems, a dynamic path programming method based on the combination of the ant colony algorithm and particle swarm optimization, along with a function of cosine angle has been proposed. This method takes into account various factors of roads such as the length of the urban road and the incoming and outgoing traffic at intersections. In the method, the points that are aligned with the navigation path towards the final destination are given more chances. Therefore, the overall goal of this paper is to reduce the diversion rate and the search time in finding the best route under road traffic conditions. The results of the proposed model on TSPLIB library, which is based on the physical distance between cars, show that the search time of the proposed method has decreased by 40.74% on average compared to the results of ten other methods used for evaluation. The highest and lowest rates of decrease are 98.01% and 6.02% respectively. The test of dynamic route planning under road traffic on some intersections of Beijing city also shows the proposed method only causes congestion of about 1.57%.

کلیدواژه‌ها [English]

  • Transport Networks
  • Dynamic Path Planning
  • Ant Colony Optimization
  • Particle Swarm Optimization
  • heuristic Cosine Angle Function