Astaraki

روش بهينه‌سازي مورچگان براي مسيريابي خودروهاي ظرفيت‌دار

نويسنده : احمد نجومي مرکي

مسئله مسيريابي خودرو، پايه‌اي‌ترين مسئله در مديريت توزيع، شناخته شده است. CVRP به‌عنوان پايه‌اي‌ترين شکل مسئله مسيريابي خودرو، به علت کاربردهاي فراوان و به مبارزه‌طلبي خود مسئله، توجه شمار زيادي از محققان را به خود جلب کرده است. از جمله کاربردهاي اين مسئله در صنعت خودروسازي، مي‌توان به مسئله مسيريابي با هدف جمع‌آوري قطعات خودرو از قطعه‌سازان و انتقال آنها به کارخانه مرکزي، اشاره کرد. در اين مقاله، الگوريتم بهينه‌سازي مورچگان براي حل مسائل CVRP ارائه مي‌شود. نتايج محاسباتي نشان مي‌دهند که اين الگوريتم، مي‌تواند پاسخ‌هايي بسيار نزديک به بهينه را براي اين مسئله بيابد.

معرفي مسئله
مسيريابي خودرو (VRP) نامي کلي است که به تمامي کلاس‌ مسائلي که شامل ملاقات مشتري‌ها با خودروهاست، اطلاق مي‌شود. VRP در نوشته‌ها، به‌صورت زمان‌بندي خودروها و توزيع خودرو يا به‌طور ساده‌تر به صورت مسئله تحويل نيز شناخته شده است.
VPR در حالت‌هاي کاربردي که در برخي موارد حتي مستقيما با توزيع فيزيکي کالاها مرتبط نيستند، بسيار به تناوب ظاهر مي‌شود. سوارکردن کودکان به اتوبوس‌هاي مدرسه، تحويل توليدات بين سوپرمارکت‌ها و فروشگاه‌هاي بزرگ، توزيع روزنامه، تورهاي بازرسي و تعمير بازدارنده، توزيع لباسشويي و غيره، همگي VRPهايي هستند که در آن، کالاها و خودروها مي‌توانند فرم‌هاي متنوعي بگيرند.
اغلب مسائل مسيريابي خودرو، NP-hard هستند و به نظر مي‌رسد که قابل حل در زماني چندجمله‌اي نباشند. الگوريتم‌هاي تحقيقاتي ارائه شده براي VRP عموماً شامل روش‌هاي دقيق و الگوريتم‌هاي بهينه‌سازي هوشمند است. الگوريتم‌هاي دقيق شامل روش‌هاي شاخه و کران، متدهاي برنامه‌ريزي پويا و مانند اينها هستند. مثلا، Nobert روش‌هاي پيشرو شاخه و کران چندگانه پيشرو را ابداع کرد. در مقابل، الگوريتم‌هاي تقريبي عمدتاً شامل روش‌هاي جست‌وجوي ممنوع و شبيه‌سازي حرارتي ، الگوريتم‌هاي ژنتيک بهينه‌سازي مورچگان و غيره است.

مسئله مسيريابي خودرو، تحت محدوديت ظرفيت
نمونه‌اي از مسائل مسيريابي خودرو بر مسيريابي بهينه خودروهايي با ظرفيت داده شده براي سرويس‌دهي به مجموعه‌اي از مشتري‌ها با تقاضاي داده شده، تمرکز دارد که ما به عنوان مسيريابي خودروهاي ظرفيت‌دار (CVRP) به آن اشاره خواهيم کرد. مسيريابي خودرو تحت محدوديت ظرفيت، شامل طراحي مسيرهاي توزيع با کمترين هزينه براي ناوگاني از خودروهاست که در پايانه‌اي مرکزي واقع شده و در آنجا نيز توقف مي‌کنند تا به مجموعه‌اي از مشتري‌ها با تقاضاي مشخص، سرويس‌دهي کنند. اين هزينه مي‌تواند مسافت کل طي شده توسط ناوگان، تعداد خودروهاي لازم براي توزيع يا ترکيبي از هر دو باشد. هر مشتري دقيقا با يک مسير خودرو، سرويس‌دهي مي‌شود. تقاضاي کل هر مسير نبايد از ظرفيت خودرو تجاوز کند. نمودار 1، نمونه‌اي از جواب‌هاي اين مسئله را نشان مي‌دهد.

يکي از کاربردهاي اين مسئله در صنعت خودروسازي، مشکل تعيين مسيرهايي براي جمع‌آوري قطعات از قطعه‌سازان و انتقال آنها به کارخانه خودروسازي توسط ناوگاني از خودروهاست تا با کمترين هزينه ممکن، قطعات را از قطعه‌سازان تحويل گرفته و به کارخانه مرکزي انتقال دهد.
ما از نمادهاي زير براي نمايش CVRP استفاده مي‌کنيم:



هدف ما يافتن پاسخي است که با رعايت شرايط ذکر شده، طول کل مسافرت را به حداقل برساند:




بهينه‌سازي مورچگان
الگوريتم بهينه‌سازي مورچگان (ACO) از رفتار طبيعي مورچگان در حال جست‌وجوي غذا، ايده گرفته شده است. در اين «متاهيوريستيک» مورچه‌ها «پروسيجرهايي» هستند که براي مسئله بهينه‌سازي، جواب مي‌سازند. مهم‌ترين موضوع دراين الگوريتم، موازي‌سازي است، يعني چندين جواب همزمان ساخته و طي پروسيجر اطلاعات، مبادله مي‌شوند و از اطلاعات تکرارهاي پيشين استفاده مي‌کنند.
در هر تکرار، روش پايه بهينه‌سازي مورچگان، هر مورچه گام‌به‌گام يک جواب براي مسئله مي‌سازد. در هر گام، مورچه يک حرکت براي تکميل جواب جاري با انتخاب بين وضعيت‌هاي ممکن، توسط تابع احتمال انجام مي‌دهد. در نسخه اصلي الگوريتم بهينه‌سازي مورچگان، فرمول احتمال حرکت از وضعيت i به وضعيت j به اين صورت مطرح شده است:



الگوريتم‌هاي بهينه‌سازي مورچگان، با موفقيت در مورد چندين مسئله بهينه‌سازي ترکيبي از جمله مسيريابي خودرو، پياده‌سازي شده است.

الگوريتم بهينه‌سازي مورچگان براي CVRP
به منظور رعايت اختصار، ويژگي‌هاي مهم الگوريتم را به صورت زير خلاصه مي‌کنيم.
1. ساختن مسيرها: همان‌گونه که در الگوريتم کلي بيان شد، در هر تکرار از الگوريتم ACO، هر مورچه يک جواب براي CVRP مي‌سازد که اين کار با حرکت به مشتري بعدي، مطابق با روش‌هاي عبور که بر ترکيبي از مقدار فرومون روي هر کمان و طول آن کمان بنا شده است، انجام مي‌گيرد (ويژگي 2 را ببينيد). روش «ليست تابو» که در بخش قبلي ذکر شد، در اينجا با استفاده از حذف همسايگي‌هاي ملاقات شده براي مورچه در تکرار جاري، اعمال مي‌شود.



5. Reduced neighbor list: وقتي مسئله براي جست‌وجوي همه حرکات ممکن، بسيار بزرگ باشد، از ليست بهترين جواب‌هاي کانديد، استفاده مي‌شود.
6. هيوريستيک‌هاي بهبوددهنده : هيوريستيک‌هاي بهبوددهنده براي اصلاح جواب مورچه‌ها، مورداستفاده قرار مي‌گيرند. در حالت عمومي، الگوريتم‌هاي جست‌وجوي محلي جواب‌هاي همسايه، جواب جاري را براي يافتن جوابي بهتر در صورت وجود، جست‌وجو مي‌کنند و در صورت موجود نبودن جواب، بهبود دهنده توقف مي‌کنند [6].
7. Stoping rules: پروسيجر ACO وقتي متوقف مي‌شود که بعد از تعدادي مشخص از تکرارها، در جواب به‌دست آمده بهبود حاصل نشود و يا به تعداد خاص nmax ازتکرارها برسيم.

نتايج محاسباتي
ما اين الگوريتم را در محيط مطلب 7 کدنويسي کرده و آن را در مورد چندين مسئله گرفته شده از آدرس اينترنتي http//www.branchandcut.org /VRP/data/ آزموديم و تعداد کمي از نتايج را در جدول 1 خلاصه کرديم. در اين جدول، در ستون اول، ستون عنوان مسائل، حروف الفباي انگليسي به مرجع اصلي مسئله عدد اول به تعداد گروه‌ها و عدد دوم به تعداد خودرو لازم اشاره دارد. مثلاً، A-n43-k6 مسئله‌اي با 42 مشتري و 6خودرو از سري مسائل Augerat دسته A است. ستون دوم نتايج به‌دست آمده از الگوريتم ما و ستون سوم مقدار جواب بهينه است. اين نتايج نشان مي‌دهند که الگوريتم ارائه شده براي CVRP مناسب است.

منابع
1.M.L.Balinski, R.E.Quandt,”On an Integer Program for a Delivery Problem”, Operations Research, Vol. 12,No. 2 (1964), pp. 300-304.
2. B.Bullnheimer,R.F Hartl, C. Strauss, “An improved ant System algorithm for the vehicle Routing Problem”, Annals of Operations Research, 1999, pp. 319-328.
3. G.Clarke, J.W. Wright, “Scheduling of Vehicles from a Central Depot to a Number of Delivery Points”, Operations Research, 12 (1964) 568-581
4. G.B Dantzig, J.H Ramser, “The Truck Dispatching Problem”, Management Science, Vol. 6, No. 1 (1959), pp. 80-91- JSTOR
5. M. Dorigo, T. Stutzle, “Ant Colony Optimization”, MIT Press, 2004

__________________

تعرفه ارزان تبلیغات در اولین و بزرگترین سایت هوش مصنوعی ایران !
با بیش از صد و چهل هزار کاربر!

saeedkarimi

سلام آقای نجومي مرکي
من در تزم باید با استفاده از الگوریتم مورچگان بهینه ترین مسیر بین دو نقطه رو برای کشیدن خط لوله گاز پیدا کنم. در واقع باید تابع مینیمم رو پیدا کرد. من خودم دانش برنامه نویسیم کم هستش. لطفا بهم کمک کنید.
karimis36@yahoo.com
ممنون.