فهرس المقالات NP-Complete

• حرية الوصول المقاله
  • صفحة الملخص
  • نص كامل
  
  1 - یک روش رقابت استعماری و یک مدل برنامه‌ریزی صحیح-آمیخته برای مساله مسیریابی وسیله نقلیه ظرفیت‌دار
  مجید یوسفی خوشبخت
  مساله مسیریابی وسیله نقلیه یکی از مشهورترین مسائل تحقیق در عملیات است که از جایگاه بسیار مهمی در مسائل بهینه‌سازی ترکیباتی برخوردار است. در این مسئله ناوگانی از وسایل نقلیه با ظرفیت Q از گره‌ای به نام انبار شروع به حرکت می‌کنند و بعد از سرویس‌دهی به مشتریان به آن باز می أکثر

  مساله مسیریابی وسیله نقلیه یکی از مشهورترین مسائل تحقیق در عملیات است که از جایگاه بسیار مهمی در مسائل بهینه‌سازی ترکیباتی برخوردار است. در این مسئله ناوگانی از وسایل نقلیه با ظرفیت Q از گره‌ای به نام انبار شروع به حرکت می‌کنند و بعد از سرویس‌دهی به مشتریان به آن باز می‌گردند به شرط آنکه هر کدام از مشتریان را فقط یک‌بار مورد ملاقات قرار دهند و در هیچ زمانی بیشتر از ظرفیت محدود Q بارگذاری نکنند. هدف کمینه‌کردن مسیرهای پیموده شده توسط وسایل نقلیه است. این مقاله کاربرد روش رقابت استعماری، را برای حل مساله مسیریابی وسیله نقلیه ارائه می‌کند. برخلاف روش‌های دیگر بهینه‌سازی، این روش از فرآیند اجتماعی-سیاسی جوامع الهام گرفته شده است و از رقابت بین کشورهای استعمارگر و مستعمره برای رسیدن به جواب استفاده می‌کند. برای آزمایش کارایی الگوریتم، دو دسته مثال استاندارد در نظر گرفته شده و الگوریتم بر روی آن مورد اجرا قرار گرفته است. نتایج محاسباتی روی این مثال‌ها که دارای اندازه‌ای از 50 تا 200 می‌باشند نشان می‌دهد که الگوریتم پیشنهادی توانسته رقابت خوبی با الگوریتم‌های مشهور فراابتکاری از نظر کیفیت جواب‌ها داشته باشد. به علاوه جواب‌های نزدیک به بهترین جواب‌های تاکنون بدست آمده  برای بیشتر مثال‌ها بدست آورده شده است. تفاصيل المقالة
• حرية الوصول المقاله
  • صفحة الملخص
  • نص كامل
  
  2 - بهینه‌سازی در مسیریابی باز وسیله نقلیه با استفاده از یک الگوریتم کارای ترکیبی فراابتکاری
  Majid Yousefi khoshbakht Hassan Zarie Zahra Sadati Eskandari Narges Mahmmudi Daranie Ahmad Mahmmud Janlo
  مسئله مسیریابی وسیله نقلیه باز (OVRP) یکی از مسائل مورد علاقه در ریاضیات محاسباتی است که بسیار مورد توجه محققان و دانشمندان قرار می‌گیرد. در این مسئله هدف تعیین کمینه هزینه جابجایی چندین وسیله نقلیه است که به طور هم‌زمان از انبار کالا شروع به حرکت می‌کنند و تعدادی از مش أکثر

  مسئله مسیریابی وسیله نقلیه باز (OVRP) یکی از مسائل مورد علاقه در ریاضیات محاسباتی است که بسیار مورد توجه محققان و دانشمندان قرار می‌گیرد. در این مسئله هدف تعیین کمینه هزینه جابجایی چندین وسیله نقلیه است که به طور هم‌زمان از انبار کالا شروع به حرکت می‌کنند و تعدادی از مشتری‌ها را مورد ملاقات قرار می‌دهند. باید توجه کرد که برخلاف مسئله مسیریابی وسیله نقلیه (VRP)، در این مسئله وسائل نقلیه لازم نیست که به انبار کالا برگردند. این مقاله نوعی روش فراابتکاری که در فاز اول آن از روش اصلاحی نمونه مورچگان (EAS) برای یافتن جوا‌ب‌هایی زیر بهینه استفاده می‌کند و در فاز دوم الگوریتم‌های درج و جابجایی برای یافتن جواب‌های بهتر به کار گرفته می‌شود. این الگوریتم بر روی مجموعه‌ای از 15 مثال با 50-400 مشتری مورد آزمایش واقع گردید که معلوم شد که این الگوریتم قادر است که در 10 مثال به بهترین جواب تاکنون یافت شده دست یابد. به علاوه از نظر کیفیت جواب‌های بدست آمده، ثابت شد که الگوریتم پیشنهادی بسیار رقابت پذیر است و انحراف معیار الگوریتم در همه مثال‌ها در حدود 1 درصد قرار دارد. به طور کل می‌توان گفت که الگوریتم پیشنهادی در مقایسه با سایر روش‌های موجود برای حل مسئله OVRP از نظر کیفیت جواب‌‌ها نتایج بهتری را بدست آورده است. تفاصيل المقالة