Globally convergent line search algorithm with Euler-based step size-determination method for continuous network design problem

Jian Wang, Xiaozheng He, Srinivas Peeta and Wei Wang

Transportation Research Part B: Methodological, 2022, vol. 163, issue C, 119-144

Abstract: Most solution algorithms for the continuous network design problem (CNDP) follow the line search principle. However, they mainly focus on identifying a feasible descent direction in each iteration. No efficient approaches have been proposed to determine a step size in each iteration to enhance the convergence speed because the equilibrium flows in CNDP are implicit functions of the decision variables. To bridge this gap, this study proposes a norm-relaxed method of feasible direction (NRMFD) algorithm integrated with the Euler-based approximation (EBA) method for the CNDP under user equilibrium (UE). At each iteration, after a feasible descent direction is determined by solving a quadratic program, this algorithm computes a feasible step size to reduce the value of the objective function using the EBA method. The main idea of the EBA method is to adaptively generate a sequence of candidate step sizes and estimate the respective UE link flows and objective function. The feasible step size that reduces the objective function the most is accepted in the NRMFD algorithm to achieve a faster convergence speed. The EBA method is computationally efficient as it linearly approximates the UE solution rather than solving it precisely. The NRMFD algorithm integrated with the EBA method is analytically proved to be globally convergent. Numerical examples indicate that the proposed algorithm can efficiently and effectively solve the CNDP in a few iterations.

Keywords: Continuous network design; Euler's method; Link flow gradient; User equilibrium; Step size determination (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191261522001163
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:transb:v:163:y:2022:i:c:p:119-144

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.trb.2022.07.004

Access Statistics for this article

Transportation Research Part B: Methodological is currently edited by Fred Mannering

More articles in Transportation Research Part B: Methodological from Elsevier
Bibliographic data for series maintained by Catherine Liu ().