A Dantzig-Wolfe decomposition-based algorithm for capacitated passenger assignment problem with time-varying demand in high-speed railway networks. (December 2022)

• Record Type: Journal Article
• Authors: Wu, Runfa; Shi, Feng; Zhao, Shuo; Xu, Guangming; Yang, Hai
• Is Part Of: Transportation research. Volume 145(2022)
• Publication Date: 2022-12
• Subjects: High-speed railway -- Passenger assignment -- Time-varying demand -- Capacity constraint -- Dantzig-Wolfe decomposition method; Transportation -- Periodicals; Transportation -- Technological innovations -- Periodicals; 388.011
• DOI: 10.1016/j.trc.2022.103909
• Languages: English
• ISSNs: 0968-090X

Abstract

Highlights: Deal with the schedule-based HSR passenger flow assignment problem for large-scale HSR networks with explicit consideration of continuous time-varying passenger demand and tight capacity constraints. Establish the assignment model by destination-based arc flow variables and propose the Dantzig-Wolfe decomposition-based reformulation and algorithmic framework to reduce the memory requirement regardless of demand discretization precision in the master problem. Design an efficient method incorporating the "rooftops" method to solve the sub-problem. This method is an effective technique to tackle the continuous time-varying demand, and its computational complexity improvement for solving sub-problem speeds up the entire solution process. Prove the convergence of the passenger flow assignment solution with discrete demand would converge to that with continuous demand when the increasing discretization number tends to infinity. Investigate the computational efficiency and solution quality of the proposed algorithm by three practical cases with different scales. Abstract: This paper proposes an algorithm for solving the schedule-based passenger assignment problem, with explicit consideration of continuous time-varying demand and tight capacity constraints for large-scale high-speed railway (HSR) networks. We construct the space–time travel network and formulate the assignment model by destination-based arc flow variables, then design a Dantzig-Wolfe (D-W) decomposition-based algorithm to solve the large-scale model of this problem with less memory requirement and computational complexity. The sub-problem in each iteration can be solved as a single-source (destination) minimum cost flow problem without capacity constraint by the "rooftops" method, which provides an effective technique to tackle both continuous and discrete time-varying demand in the assignment problem. It is further demonstrated that the assignment solutions for discrete time-varying demand can converge to that for continuous time-varying demand with the increase of demand discretization number. Three real case studies with different HSR network scales show that the proposed algorithm is efficient in memory and computational complexity, especially when highly accurate solutions for passenger assignment on large-scale HSR networks are needed.