نوع مقاله : مقاله پژوهشی
نویسندگان
دانشکده علوم پایه، گروه ریاضی کاربردی، دانشگاه علوم و فنون هوایی شهید ستاری، مهرآباد جنوبی، تهران، ایران.
چکیده
مسئلهی کوتاهترین مسیر یکی از مسائل کلاسیک و پرکاربرد بهینهسازی است که الگوریتمهای کارآمدی برای آن ارائه شده است. در این مسئله شبکهای شامل مجموعهای از نقاط و کمانهای بین آنها درنظر گرفته شده و به هر کمان پارامتری مانند طول، هزینه یا زمان طی مسیر نسبت داده میشود. هدف اصلی مسئله، یافتن کوتاهترین یا کمهزینهترین مسیر بین دو نقطهی مشخص است. با درنظر گرفتن پارامتر دیگری برای هریک از کمانها و اضافهکردن یک محدودیت دیگر، بهصورت قید ظرفیت، مسئله به شرایط واقعی نزدیکتر خواهد شد. این مسئله توسعه دادهشده به مسئلهی کوتاهترین مسیر مقید معروف است که پیچیدگی بالاتری دارد و برای حل آن به الگوریتمهای کارآمدی نیاز است. در این مطالعه، یک روش حل برای این مسئله ارائه شده است که قادر است در مدت زمان کوتاهی به جواب بهین برسد. در این روش از یک الگوی تکراری حل مدل آزادشده و اضافهکردن برشهای منطقی در هر تکرار استفاده میشود. نتایج پیادهسازی الگوریتم ارائهشده بر روی شبکههای مختلف، کارایی آن را بهخوبی نشان میدهد.
کلیدواژهها
موضوعات
عنوان مقاله [English]
Providing a method for selecting the constrained shortest path problem using logical cuts
نویسندگان [English]
- Sajad Moradi
- Gholamreza Karamali
Faculty of Basic Sciences, Department of Applied Mathematics, Shahid Sattari Aeronautical University of Sciences and Technology, South Mehrabad, Tehran, Iran.
چکیده [English]
Shortest path problem is one of the practical issues in optimization, and there are many efficient algorithms in this area. In this issue, a network of some nodes and arcs is considered in which, each arc has a specific parameter such as distance or cost. The main objective is to find the shortest or least costly route between two distinct points. By considering an additional parameter and adding a new limitation, as a capacity constraint, the problem will be closer to the real world condition. This extended issue is known as the constrained shortest path problem and has a higher complexity order and practical algorithms are needed to solve it. In this study, an effective algorithm is presented that obtains the optimal solution within a short time. In this method, a repetitive pattern is used so that, in each iteration, the relaxed model, after adding a logical cut, is solved. The results of the implementation of the proposed algorithm on different networks show its efficiency.
کلیدواژهها [English]
- Network
- Constrained routing
- Relaxed model
- Solution algorithm