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

محورهای موضوعی : آمار

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

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

تاریخ دریافت : 1399/04/29 تاریخ پذیرش : 1400/06/05 تاریخ انتشار : 1400/11/01

کلید واژه: 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.

منابع و مأخذ:

[۱] جاهدی، صدیقه و پیوند، مرادعلی، یک الگوریتم تکراری برای مسایل تعادل تعمیم یافته، نامساوی تغییراتی و نقطه ثابت مبتنی بر روش گرادیان افزوده، مجله پژوهش‌های نوین در ریاضی، دوره 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.