یک الگوریتم جدید برای مسائل نامساوی تغییراتی با کاربرد در مسأله تعادل ترافیک نامتقارن
محورهای موضوعی : آمار
مراد علی پیوند
1
,
صدیقه جاهدی
2
,
حمید رضا ملکی سروستانی
3
1 - دانشکده علوم پایه، دانشگاه یاسوج، یاسوج، ایران
2 - دانشکده ریاضی، دانشگاه صنعتی شیراز، شیراز، ایران
3 - دانشکده ریاضی، دانشگاه صنعتی شیراز، شیراز، ایران
کلید واژه: Column generation, Extragradient method, Khobotov algorithm, Path flow,
چکیده مقاله :
در این مقاله یک الگوریتم تصویر دوگامی مبتنی بر روش گرادیان افزوده برای حل مسائل نامساوی تغییراتی معرفی نموده و به اثبات قضیه همگرایی الگوریتم پیشنهادی، می‌پردازیم. یکی از پارامترهایی که کارایی و دقت الگوریتم‌های تصویر را تعیین می‌کند انتخاب اندازه گام الگوریتم است. این انتخاب وابسته به ویژگی‌های انقباضی نگاشتی است که در الگوریتم به ناحیه شدنی تصویر می‌شود. اگر به عنوان نمونه ثابت لیپ شیتز مشخص نباشد در انتخاب اندازه گام الگوریتم دچار مشکل می‌شویم. در الگوریتم پیشنهادی نیاز به دانستن ثابت لیپ شیتز برداشته شده است و روشی ارائه گردیده که انتخاب اندازه گام را آسان می‌کند. مسأله تعادل شبکه ترافیک نامتقارن را به صورت یک مسأله نامساوی تغییراتی روی فضای جریان مسیرهای شبکه مدل‌سازی نموده و با توجه به ساختار تجزیه‌پذیر مجموعه شدنی این مدل، حالت تعادل شبکه ترافیک را با استفاده ازالگوریتم پیشنهادی به دست می‌آوریم. در نهایت، نتایج عددی حاصل از اجرای این الگوریتم را بر روی شبکه ترافیک آزمایشی سایوکس فال ارائه می‌کنیم.
In this paper, we introduce a double projection algorithm based on extragradient method for solving the variational inequality problems and we prove the convergence theorem of proposed algorithm. One of the parameters that determine the efficiency and accuracy of the projection method is a properly selected step size. This selection is based on the contractive properties of operator which is projected on the feasible region. For example, if the Lipschitz constant is not known, we have trouble choosing step size of the algorithm. The proposed algorithm eliminates the need to know the Lipschitz constant and provides a method that facilitates step size selection.We formulate the asymmetric traffic equilibrium problem as a variational inequality on the path flows space. According to the decomposable structure of the feasible set of this model, we obtain the traffic network equilibrium state, by using the proposed algorithm. Finally, we present the numerical results of using this algorithm on the Sioux-Falls test traffic network.
