ارائه روشی برای انتخاب کوتاه ترین مسیر مقید با استفاده از برش های منطقی

Publish Year: 1398
نوع سند: مقاله ژورنالی
زبان: Persian
View: 221

This Paper With 12 Page And PDF Format Ready To Download

  • Certificate
  • من نویسنده این مقاله هستم

استخراج به نرم افزارهای پژوهشی:

لینک ثابت به این Paper:

شناسه ملی سند علمی:

JR_DMOR-4-3_002

تاریخ نمایه سازی: 24 اسفند 1399

Abstract:

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

Authors

سجاد مرادی

دانشکده علوم پایه، گروه ریاضی کاربردی، دانشگاه علوم و فنون هوایی شهید ستاری، مهرآباد جنوبی، تهران، ایران.

غلامرضا کرمعلی

دانشکده علوم پایه، گروه ریاضی کاربردی، دانشگاه علوم و فنون هوایی شهید ستاری، مهرآباد جنوبی، تهران، ایران.

مراجع و منابع این Paper:

لیست زیر مراجع و منابع استفاده شده در این Paper را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود Paper لینک شده اند :
  • Ahuja, R. K., Magnanti, T. L., Orlin, J. B., & ...
  • Cherkassky, B. V., Goldberg, A. V., & Radzik, T. (1996). ...
  • Zhan, F. B., & Noon, C. E. (1998). Shortest path ...
  • Sedeño-Noda, A., & González-Martín, C. (2010). Shortest path simplex algorithm ...
  • Lozano, L., & Medaglia, A. L. (2013). On an exact ...
  • Garey, M. R. (1979). Computers and intractability: A guide to ...
  • Tarapata, Z. (2003). Military route planning in battlefield simulation: effectiveness ...
  • Mora, A. M., Merelo, J. J., Laredo, J. L. J., ...
  • MirHassani, S. A., Moradi, S., & Taghinezhad, N. (2011). Algorithm ...
  • Avella, P., Boccia, M., & Sforza, A. (2004). Resource constrained ...
  • Eppstein, D. (1998). Finding the k shortest paths. SIAM journal on ...
  • Pugliese, L. D. P., & Guerriero, F. (2013). A survey ...
  • Handler, G. Y., & Zang, I. (1980). A dual algorithm ...
  • Santos, L., Coutinho-Rodrigues, J., & Current, J. R. (2007). An ...
  • Carlyle, W. M., Royset, J. O., & Kevin Wood, R. ...
  • Verstichel, J., Kinable, J., De Causmaecker, P., & Berghe, G. ...
  • Gendron, B., Garroppo, R. G., Nencioni, G., Scutellà, M. G., ...
  • نمایش کامل مراجع