fa روش دوگان لاگرانژی برای مسأله کوتاهترین مسیر با درنظرگرفتن طرح‌های عمرانی همراه با محدودیت بودجه تخصصي Special پژوهشي Research <span style="color:black;"><span style="font-family:b zar;"><span style="font-size:12.0pt;">در این مقاله یک مساله کوتاه‌ترین مسیر مقید&nbsp; مورد بررسی قرار می&lrm;‌گیرد</span></span></span> <span style="color:black;"><span style="font-family:b zar;"><span style="font-size:12.0pt;">‌که در آن برای هر یک از یال‌های شبکه طرح‌های عمرانی مختلف با هزینه اجرای مشخص و نیز میزان کاهش مشخص برای زمان (طول) یال درنظر گرفته شده‌است. هدف مساله تعیین مسیر بین یک زوج مبدأ و مقصد و انتخاب طرح‌های بهینه بر روی یال‌های این مسیر است، به گونه‌ای که زمان تغییر یافته مسیر، کم‌ترین مقدار ممکن بوده و هزینه اجرایی طرح‌های انتخابی از میزان بودجه در دسترس تجاوز نکند. با استفاده از روش دوگان لاگرانژی دسته‌ای از محدودیت‌های مساله آزاد شده و مساله دوگان لاگرانژی </span></span></span><span style="color:black;"><span style="font-family:b zar;"><span style="font-size:12.0pt;">به دو زیر مساله کوچک‌تر‌ تبدیل می‌شود. سپس با استفاده از الگوریتم زیرگرادیان یک جواب نزدیک به</span></span></span><span style="color:black;"><span style="font-family:b zar;"><span style="font-size:12.0pt;"> بهینه برای مساله اولیه حاصل می‌شود. در انتها با بررسی مدل پیشنهاد شده بر روی یک شبکه کوچک و نیز بر روی شبکه خراسان، جواب مساله برای زوج‌های مبدأ و مقصد مختلف و با درنظرگرفتن پارامترهای متفاوت تعیین می‌شود.</span></span></span> In this paper, a constrained shortest path problem (CSP) in a network is investigated, in which some special plans for each link with corresponding pre-determined costs as well as reduction values in the link travel time are considered. The purpose is to find a path and selecting the best plans on its links, to improve the travel time as most as possible, while the costs of conducting plans do not exceed the available budget. Using the Lagrangian relaxation approach, some constraints of the problem are relaxed and the Lagrangian dual problem is decomposed into two smaller sub-problems. Then, by applying the sub-gradient algorithm, a near optimal solution is determined for the original problem. Finally, by considering the proposed model on a small-sized network and on Khorasan state network, solutions for different origin-destination pairs with different parameters are determined. شبکه حمل‌ونقل, مساله کوتاه‌ترین مسیر مقید, روش دوگان لاگرانژی, روش زیرگرادیان. Transportation Network, Constrained Shortest Path Problem, Lagrangian Dual Method, Sub-gradient Method. 39 57 http://jamlu.lahijan.iau.ir/browse.php?a_code=A-11-991-2&slc_lang=fa&sid=1 S. Safari سکینه صفری 10031947532846006777 10031947532846006777 No Department of Applied Mathematics, Hakim Sabzevari University, Sabzevar, Iran دانشگاه حکیم سبزواری، دانشکده ریاضی و علوم کامپیوتر، گروه ریاضی کاربردی، سبزوار M. Zaferanieh مهدی زعفرانیه 10031947532846006778 10031947532846006778 Yes Department of Applied Mathematics, Hakim Sabzevari University, Sabzevar, Iran دانشگاه حکیم سبزواری، دانشکده ریاضی و علوم کامپیوتر، گروه ریاضی کاربردی، سبزوار M. Abareshi مریم ابارشی 10031947532846006779 10031947532846006779 No Department of Applied Mathematics, Hakim Sabzevari University, Sabzevar, Iran دانشگاه حکیم سبزواری، دانشکده ریاضی و علوم کامپیوتر، گروه ریاضی کاربردی، سبزوار E. L. Rahimi ابراهیم لعل رحیمی 10031947532846006780 10031947532846006780 No Department of Applied Mathematics, Hakim Sabzevari University, Sabzevar, Iran دانشگاه حکیم سبزواری، دانشکده ریاضی و علوم کامپیوتر، گروه ریاضی کاربردی، سبزوار