Modifications of the Frank –Wolfe algorithm in the problem of finding the equilibrium distribution of traffic flows

Ignashin I.N., Yarmoshik D.V.
 pdf (773K)

The paper presents various modifications of the Frank–Wolfe algorithm in the equilibrium traffic assignment problem. The Beckman model is used as a model for experiments. In this article, first of all, attention is paid to the choice of the direction of the basic step of the Frank–Wolfe algorithm. Algorithms will be presented: Conjugate Frank–Wolfe (CFW), Bi-conjugate Frank–Wolfe (BFW), Fukushima Frank –Wolfe (FFW). Each modification corresponds to different approaches to the choice of this direction. Some of these modifications are described in previous works of the authors. In this article, following algorithms will be proposed: N-conjugate Frank–Wolfe (NFW), Weighted Fukushima Frank–Wolfe (WFFW). These algorithms are some ideological continuation of the BFW and FFW algorithms. Thus, if the first algorithm used at each iteration the last two directions of the previous iterations to select the next direction conjugate to them, then the proposed algorithm NFW is using more than $N$ previous directions. In the case of Fukushima Frank–Wolfe, the average of several previous directions is taken as the next direction. According to this algorithm, a modification WFFW is proposed, which uses a exponential smoothing from previous directions. For comparative analysis, experiments with various modifications were carried out on several data sets representing urban structures and taken from publicly available sources. The relative gap value was taken as the quality metric. The experimental results showed the advantage of algorithms using the previous directions for step selection over the classic Frank–Wolfe algorithm. In addition, an improvement in efficiency was revealed when using more than two conjugate directions. For example, on various datasets, the modification 3FW showed the best convergence. In addition, the proposed modification WFFW often overtook FFW and CFW, although performed worse than NFW.

Keywords: Conjugate Frank–Wolfe, Weighted Fukushima Frank–Wolfe, N-conjugate Frank–Wolfe
Citation in English: Ignashin I.N., Yarmoshik D.V. Modifications of the Frank –Wolfe algorithm in the problem of finding the equilibrium distribution of traffic flows // Computer Research and Modeling, 2024, vol. 16, no. 1, pp. 53-68
Citation in English: Ignashin I.N., Yarmoshik D.V. Modifications of the Frank –Wolfe algorithm in the problem of finding the equilibrium distribution of traffic flows // Computer Research and Modeling, 2024, vol. 16, no. 1, pp. 53-68
DOI: 10.20537/2076-7633-2024-16-1-53-68
URL: http://crm-en.ics.org.ru/journal/article/3433/
Creative Commons License This work is licensed under a Creative Commons Attribution-NoDerivs 3.0 Unported License.

Indexed in Scopus

Full-text version of the journal is also available on the web site of the scientific electronic library eLIBRARY.RU

The journal is included in the Russian Science Citation Index

The journal is included in the RSCI

International Interdisciplinary Conference "Mathematics. Computing. Education"

Copyright © 2009–2024 Institute of Computer Science