یک الگوریتم جدید برای مسائل نامساوی تغییراتی با کاربرد در مسأله تعادل ترافیک نامتقارن

الموضوعات :

مراد علی پیوند ¹ , صدیقه جاهدی ² , حمید رضا ملکی سروستانی ³

1 - دانشکده علوم پایه، دانشگاه یاسوج، یاسوج، ایران
2 - دانشکده ریاضی، دانشگاه صنعتی شیراز، شیراز، ایران
3 - دانشکده ریاضی، دانشگاه صنعتی شیراز، شیراز، ایران

تاريخ الإرسال : 28 الأحد , ذو القعدة, 1441 تاريخ التأكيد : 19 الجمعة , محرم, 1443 تاريخ الإصدار : 18 الجمعة , جمادى الثانية, 1443

الکلمات المفتاحية: Column generation, Extragradient method, Khobotov algorithm, Path flow,

ملخص المقالة :

در این مقاله یک الگوریتم تصویر دوگامی مبتنی بر روش گرادیان افزوده برای حل مسائل نامساوی تغییراتی معرفی نموده و به اثبات قضیه همگرایی الگوریتم پیشنهادی، می‌پردازیم. یکی از پارامترهایی که کارایی و دقت الگوریتم‌های تصویر را تعیین می‌کند انتخاب اندازه گام الگوریتم است. این انتخاب وابسته به ویژگی‌های انقباضی نگاشتی است که در الگوریتم به ناحیه شدنی تصویر می‌شود. اگر به عنوان نمونه ثابت لیپ ‌شیتز مشخص نباشد در انتخاب اندازه گام الگوریتم دچار مشکل می‌شویم. در الگوریتم پیشنهادی نیاز به دانستن ثابت لیپ‌ شیتز برداشته شده است و روشی ارائه گردیده که انتخاب اندازه گام را آسان می‌کند. مسأله تعادل شبکه ترافیک نامتقارن را به صورت یک مسأله نامساوی تغییراتی روی فضای جریان مسیرهای شبکه مدل‌سازی نموده و با توجه به ساختار تجزیه‌پذیر مجموعه شدنی این مدل، حالت تعادل شبکه ترافیک را با استفاده ازالگوریتم پیشنهادی به دست می‌آوریم. در نهایت، نتایج عددی حاصل از اجرای این الگوریتم را بر روی شبکه ترافیک آزمایشی سایوکس‌ فال ارائه می‌کنیم.

المصادر:

[۱] جاهدی، صدیقه و پیوند، مرادعلی، یک الگوریتم تکراری برای مسایل تعادل تعمیم یافته، نامساوی تغییراتی و نقطه ثابت مبتنی بر روش گرادیان افزوده، مجله پژوهش‌های نوین در ریاضی، دوره 2، شماره 7، آذر و دی 1395، صفحه 61-76.

 

[2] Facchinei, F., and Pang, J. S., (2003). Finite Dimensional Variational Inequalities and Complementarity Problems, Volume I, II, New York, Springer.

 

[3] Konnov, I. V. and Laitinen, E., (2002). Theory and Application of Variational Inequalities, University of Oulu, ISBN 951- 4242-6688-9.

 

[4] Patriksson, M., (1999). Nonlinear Programming and Variational Inequality Problems, a Unified Approach, Dordrecht, Kluwer Academic Publishers.

 

[5] Korpelevich, G. M., (1976). The extragradient method for finding saddle points and other problems, Matecon, 12, 747- 756.

 

[6] Dafermos, S., (1980). Traffic equilibrium and variational inequalities, Transportation Science, 14, 42-54.

 

[7] Pang, J. S. and Gabriel, S. A., (1993). A robust algorithm for the nonlinear complementary problem, Mathematical Programming, 60, 295-337.

 

[8] Khobotov, E. N. (1987). Modification of the extra-gradient method for solving variational inequalities and certain optimization problems, U.S.S.R. Computational Mathematics and Matematical Physics, 27(5), 120–127.

 

[9] He, B., Liao, L. Z., and Wang, X. (2012). Proximal-like contraction methods for monotone variational inequalities in a unified framework II: General methods and numerical experiments, Computational Optimization and Application, 51 (2), 681– 708.

 

[10] Marcotte, P., (1991). Application of Khobotov’s algorithm to variational inequalities and network equilibrium problem, Information Systems and Operational Research, 29(4), 258–270.

 

[11] Iusem, A. N., (1994). An iterative algorithm for the variational inequality problem, Computational and Applied Mathematics, 13(2), 103-114.

 

[12] Iusem, A. N., and Svaiter, B. F., (1997). A variant of Korpelevich’s method for variational inequalities with a new search strategy, Optimization, 42,309-321.

 

[13] Solodov, M. V. and Svaiter, B. F., (1999). A new projection method for variational inequality problems, SIAM Journal on Control and Optimization, 37(3), 756-776.

 

[14] Solodov, M. V. and Tseng, P., (1996). Modified projection type methods for monotone variational inequalities, SIAM Journal on Control and Optimization, 34(5), 1914-1830.

 

[15] A. Cegielski, (2011) Iterative Methods for Fixed Point Problems in Hilbert Spaces, Springer, London.

 

[16] Tinti, F. (2005). Numerical solution for pseudomonotone variarional inequality problems by extragradient methods, NOIA Variational Analysis and Applications, 79, 1101-1128.

 

[17] Harker, P. T., (1988). Accelerating the convergence of the diagonalization and projection algorithms for flnite-dimensional variational inequalities, Mathematical Programming, 41, 29-59.

[18] Patriksson, M., (2015). The Traffic Assignment Problem: Models and Methods, New York, Dover Publications.

 

[19] Michelot, C., (1986). A finite algorithm for finding the projection of a point onto the canonical simplex of Rⁿ, Journal of Optimization Theory and Applications, 50, 195–200.

 

[20] Bertsekas, D. P. and Gafni, E. M., (1982). Projection methods for variational inequality with application to the traffic assignment problem, Mathematical Programming Study, 17, 139-159.

 

[21] Chen, A., Lee, D. H. and Nie, Y., (2003). conjugate gradient projection algorithm for the traffic assignment problem'', Mathematical and Computer Modelling, 37, 863–878.

 

[22] Nagurney, A. and Zhang, D., (1996). Projected dynamical systems and variational inequalities with applications, Boston, Kluwer.

 

[23] Leventhal, L., Nemhause, G. and Trotter, L., (1972). A column generation algorithm for optimal traffic assignment, Transportation Science, 7, 168-172.

 

[24] Bar-Gera, H., Transportation Network Test Problems, http://www. bgu.ac.il/~bargera/tntp/.

 

[25] Barbara P., Massimo P., and Mauro P., (2007).  A path-based double projection method for solving the asymmetric traffic network equilibrium problem, Optimization Letters, 1, 171–185.