ارائه روشی برای انتخاب کوتاه ترین مسیر مقید با استفاده از برش های منطقی
عنوان مقاله: ارائه روشی برای انتخاب کوتاه ترین مسیر مقید با استفاده از برش های منطقی
شناسه ملی مقاله: JR_DMOR-4-3_002
منتشر شده در در سال 1398
شناسه ملی مقاله: JR_DMOR-4-3_002
منتشر شده در در سال 1398
مشخصات نویسندگان مقاله:
سجاد مرادی - دانشکده علوم پایه، گروه ریاضی کاربردی، دانشگاه علوم و فنون هوایی شهید ستاری، مهرآباد جنوبی، تهران، ایران.
غلامرضا کرمعلی - دانشکده علوم پایه، گروه ریاضی کاربردی، دانشگاه علوم و فنون هوایی شهید ستاری، مهرآباد جنوبی، تهران، ایران.
خلاصه مقاله:
سجاد مرادی - دانشکده علوم پایه، گروه ریاضی کاربردی، دانشگاه علوم و فنون هوایی شهید ستاری، مهرآباد جنوبی، تهران، ایران.
غلامرضا کرمعلی - دانشکده علوم پایه، گروه ریاضی کاربردی، دانشگاه علوم و فنون هوایی شهید ستاری، مهرآباد جنوبی، تهران، ایران.
مسئلهی کوتاهترین مسیر یکی از مسائل کلاسیک و پرکاربرد بهینهسازی است که الگوریتمهای کارآمدی برای آن ارائه شده است. در این مسئله شبکهای شامل مجموعهای از نقاط و کمانهای بین آنها درنظر گرفته شده و به هر کمان پارامتری مانند طول، هزینه یا زمان طی مسیر نسبت داده میشود. هدف اصلی مسئله، یافتن کوتاهترین یا کمهزینهترین مسیر بین دو نقطهی مشخص است. با درنظر گرفتن پارامتر دیگری برای هریک از کمانها و اضافهکردن یک محدودیت دیگر، بهصورت قید ظرفیت، مسئله به شرایط واقعی نزدیکتر خواهد شد. این مسئله توسعه دادهشده به مسئلهی کوتاهترین مسیر مقید معروف است که پیچیدگی بالاتری دارد و برای حل آن به الگوریتمهای کارآمدی نیاز است. در این مطالعه، یک روش حل برای این مسئله ارائه شده است که قادر است در مدت زمان کوتاهی به جواب بهین برسد. در این روش از یک الگوی تکراری حل مدل آزادشده و اضافهکردن برشهای منطقی در هر تکرار استفاده میشود. نتایج پیادهسازی الگوریتم ارائهشده بر روی شبکههای مختلف، کارایی آن را بهخوبی نشان میدهد.
کلمات کلیدی: شبکه, مسیریابی مقید, مدل آزادشده, الگوریتم حل
صفحه اختصاصی مقاله و دریافت فایل کامل: https://civilica.com/doc/1167611/