TY - JOUR
T1 - Column generation for solving large scale multi-commodity flow problems for passenger transportation
AU - Lienkamp, Benedikt
AU - Schiffer, Maximilian
N1 - Publisher Copyright:
© 2023 Elsevier B.V.
PY - 2024/4/16
Y1 - 2024/4/16
N2 - In light of the need for design and analysis of intermodal transportation systems, we propose an algorithmic framework to optimize respective passenger flows from a system perspective. To this end, we model an intermodal transportation system by combining two core principles of network optimization – layered-graph structures and (partially) time-expanded networks – to formulate our problem on a graph that allows us to implicitly encode problem specific constraints related to intermodality. This enables us to solve a standard integer minimum-cost multi-commodity flow problem to obtain the passenger flow system optimum for an intermodal transportation system. To solve this problem efficiently, we present a column generation approach to find continuous minimum-cost multi-commodity flow solutions, which we combine with a price-and-branch procedure to obtain integer solutions. To speed up our column generation, we further develop a pricing filter and an admissible distance approximation to utilize the A* algorithm for solving the pricing problems. We show the efficiency of our framework by applying it to a real-world case study for the city of Munich, where we solve instances with up to 56,295 passengers to optimality, and show that the computation time of our algorithm can be reduced by up to 60% through the use of our pricing filter and by up to additional 90% through the use of our A*-based pricing algorithm.
AB - In light of the need for design and analysis of intermodal transportation systems, we propose an algorithmic framework to optimize respective passenger flows from a system perspective. To this end, we model an intermodal transportation system by combining two core principles of network optimization – layered-graph structures and (partially) time-expanded networks – to formulate our problem on a graph that allows us to implicitly encode problem specific constraints related to intermodality. This enables us to solve a standard integer minimum-cost multi-commodity flow problem to obtain the passenger flow system optimum for an intermodal transportation system. To solve this problem efficiently, we present a column generation approach to find continuous minimum-cost multi-commodity flow solutions, which we combine with a price-and-branch procedure to obtain integer solutions. To speed up our column generation, we further develop a pricing filter and an admissible distance approximation to utilize the A* algorithm for solving the pricing problems. We show the efficiency of our framework by applying it to a real-world case study for the city of Munich, where we solve instances with up to 56,295 passengers to optimality, and show that the computation time of our algorithm can be reduced by up to 60% through the use of our pricing filter and by up to additional 90% through the use of our A*-based pricing algorithm.
KW - Multi-commodity flows
KW - Passenger transportation
KW - Routing
UR - http://www.scopus.com/inward/record.url?scp=85175262746&partnerID=8YFLogxK
U2 - 10.1016/j.ejor.2023.09.019
DO - 10.1016/j.ejor.2023.09.019
M3 - Article
AN - SCOPUS:85175262746
SN - 0377-2217
VL - 314
SP - 703
EP - 717
JO - European Journal of Operational Research
JF - European Journal of Operational Research
IS - 2
ER -