Optimizing intermodal transportation networks at scale via column generation Benedikt Lienkamp1and Maximilian Schiﬀer2 1TUM School of Management Technical University of Munich 80333 Munich Germany

2025-04-29 0 0 1.32MB 25 页 10玖币

侵权投诉

Optimizing intermodal transportation networks at scale via column generation

Benedikt Lienkamp1and Maximilian Schiﬀer2

1TUM School of Management, Technical University of Munich, 80333 Munich, Germany

benedikt.lienkamp@tum.de

2TUM School of Management & Munich Data Science Institute,

Technical University of Munich, 80333 Munich, Germany

schiﬀer@tum.de

Abstract

In light of the need for design and analysis of intermodal transportation systems, we propose

an algorithmic framework to determine the system optimum of an intermodal transportation

system. To this end, we model an intermodal transportation system by combining two core

principles of network optimization – layered-graph structures and (partially) time-expanded net-

works – to formulate our problem on a graph that allows us to implicitly encode problem speciﬁc

constraints related to intermodality. This enables us to solve a standard integer minimum-cost

multi-commodity ﬂow problem to obtain the system optimum for an intermodal transporta-

tion system. To solve this integer minimum-cost multi-commodity ﬂow problem eﬃciently, we

present a column generation approach to ﬁnd continuous minimum-cost multi-commodity ﬂow

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 ﬁlter and an admissible distance

approximation to utilize the A∗algorithm for solving the pricing problems. We show the eﬃ-

ciency 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 ﬁlter and by

up to additional 90% through the use of the A∗-based pricing algorithm.

Keywords: column generation; multi-commodity ﬂow; intermodal transportation

arXiv:2210.09190v1 [math.OC] 17 Oct 2022

1 Introduction

Multi-commodity network ﬂow (MCNF) problems have been vividly studied during the last decades

and have been applied to various real-world domains. Among others, they have been extensively used

to model communication and transportation systems. Here, exact algorithms have been developed

to solve medium scale problems, e.g., for message routing (Barnhart et al. 2000) and heuristic

algorithms have been proposed to quickly obtain good quality solutions for large scale problems,

e.g., for general linear minimum-cost MCNF problems (Salimifard & Bigharaz 2022). This state of

the art has been used during the last years to study transportation systems as it suﬃces for medium

scale problem sizes or mesoscopic system analyses.

However, recent developments in the transportation sector, e.g., the advent of mobility as a service,

intermodal trips, autonomous vehicles, ride-hailing, and ride-pooling require in-depth analyses of the

resulting complex transportation systems at scale. In this context, an optimization-based analysis

of the transportation system’s optimum is of interest, as future intermodal transportation systems

with autonomous elements allow for more control and are thus amenable for the integration of

optimal routing decisions. Determining system optimal solutions in such a context requires to solve

MCNF problems that signiﬁcantly exceed problem sizes that have so far been solved to optimality.

Additionally, the intermodal structure of future transportation systems needs to be considered.

Against this background, we revisit the state of the art on solving MCNF problems for trans-

portation systems. We aim to develop a column generation-based algorithm to ﬁnd system optima

of intermodal transportation networks and improve upon the current state of the art in terms of

computational tractability and scalability. In the remainder of this section, we ﬁrst review related

literature, before we deﬁne our contributions and the paper’s organization.

1.1 Related Literature

MCNF models have been used to model a variety of problems, amongst others in communication

(Ouorou et al. 2000; Lin 2001; Wagner et al. 2007), logistics (Erera et al. 2005; Al-Khayyal & Hwang

2007; Psaraftis 2011), and transportation systems (Ayar & Yaman 2012; Paraskevopoulos et al. 2016;

Zhang et al. 2019). Besides these research ﬁelds, MCNF models also ﬁnd application in ﬁnancial

ﬂows (Yang & Kim 2015), evacuation planning (Pyakurel & Dhamala 2017), production services

(Atamtürk & Zhang 2007), and traﬃc control (Bertsimas & Patterson 2000), which shows the great

versatility of MCNF models. Various heuristics, approximations, and exact solution methods have

been used to solve diﬀerent variants of MCNF problems.

The most prominent heuristic methods to solve MCNF problems are genetic algorithms (Khouja

et al. 1998; Alavidoost et al. 2018), simulated annealing (Yaghini et al. 2012; Moshref-Javadi &

Lee 2016), and tabu search (Ghamlouche et al. 2003; Crainic et al. 2006). Various approximation

methods exist for diﬀerent types of network ﬂow formulations. Lagrangian-based methods proved to

be very eﬃcient at solving MCNF problems and ﬁnd their application in solving multi-commodity

capacitated ﬁxed charge network design problems (Crainic et al. 2001) and minimum-cost MCNF

problems (Retvdri et al. 2004).

The two most prominent exact approaches to solve MCNF problems are branching and decom-

position methods. Branching problems build on the idea of branch-and-bound (B&B) (Lawler

& Wood 1966) and have been used to solve integer MCNF problems (see, e.g., Brunetta et al.

2000). Decomposition methods were developed by Dantzig & Wolfe (1960) and used, for example,

by Barnhart et al. (1994) to solve message routing problems, formulating them as minimum-cost

MCNF problems and solving them via column generation (CG). Barnhart et al. (2000) utilize the

branch-and-price (B&P) algorithm (Barnhart et al. 1998), a combination of CG and B&B, to solve

integer MCNF problems. Here, the authors applied bounds provided by solving linear programs,

using column-and-cut generation at nodes of the branch-and-bound tree in combination with cuts,

generated at each node in the B&B tree, to mitigate symmetry eﬀects.

In general, MCNF models have recently been used to model transportation systems, e.g., au-

tonomous Mobility-on-Demand (AMoD) systems in congested road networks (Rossi et al. 2018)

and to study the interaction of AMoD with the public transportation system (Salazar et al. 2019)

on a mesoscopic level. We refer to Salimifard & Bigharaz (2022) for an extensive overview of

applications and solution methods for MCNF problems.

Dynamic ﬂows add a time dimension to static network ﬂow problems and allow ﬂow values on

arcs to change over time. In dynamic network ﬂow models for traﬃc optimization, the size of the

underlying graph can be a limiting factor for the model’s granularity or time horizon. To address the

problem of exponential growth in dynamic networks, Boland et al. (2017) introduced the concept of

partially time-expanded networks to service network design problems. In partially time-expanded

networks, not all timesteps are included in the network graph, which allows for iterative reﬁnement

to obtain a reduced graph size. Besides a reduced size of the underlying graph, multiple methods

exist to speed up computation time in large network ﬂow models. For an extensive overview of

dynamic network ﬂow problems, we refer to Skutella (2009).

In summary, various optimization approaches exist to solve MCNF problems for diﬀerent problem

settings. So far, using an MCNF model to optimize intermodal passenger transport has only been

done on a mesoscopic level (Salazar et al. 2019). Analysis of passenger transport in large trans-

portation networks on a microscopic level is often done via simulation (Ziemke et al. 2019), which

is not amenable for optimization. To the best of the authors’ knowledge, there exists no optimiza-

tion framework that is capable of determining the system optimum of an intermodal transportation

system on a microscopic level.

1.2 Contribution

To close the research gap outlined above, we propose an algorithmic framework to determine the

system optimum of an intermodal transportation system. Speciﬁcally our contribution is four-fold:

First, we model an intermodal transportation system by combining two core principles of network

optimization, layered-graph structures and (partially) time-expanded networks, which allows us to

implicitly encode problem speciﬁc constraints related to intermodality. This enables us to solve a

standard integer minimum-cost MCNF problem to determine the system optimum for an intermodal

transportation system. Second, to solve the integer minimum-cost MCNF problem eﬃciently, we

present a CG approach to ﬁnd continuous minimum-cost MCNF solutions, which we combine with

a price-and-branch (P&B) procedure to obtain integer solutions. To speed up our CG approach,

we develop a pricing ﬁlter and an admissible distance approximation to utilize the A∗algorithm for

solving the pricing problems. Third, we show the eﬃciency 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 ﬁlter and by up to additional 90% through the use of the A∗-based

pricing algorithm. Fourth, we open this algorithmic framework as open source code for further

research.

1.3 Organization

The remainder of this paper is structured as follows. We specify our problem setting in Section 2

and develop our methodology in Section 3. In Section 4 we describe a case study for the public

transportation system for the city of Munich. We use this case study in Section 5 to present

numerical results that show the eﬃciency of our algorithmic framework. Section 6 concludes this

paper by summarizing its main ﬁndings.

2 Problem Setting

We study optimal passenger routing in a large intermodal capacitated transportation system with

ﬁxed vehicle routes, e.g., bus, subway, and tram lines. An instance of our problem consists of a

schedule of ﬁxed vehicle routes in a transportation system and a set of passengers. The vehicle

schedules contain information about the stops of each route, arriving times at its stops, and the

capacity of the operating vehicle. Each passenger is associated with a transportation request,

such that information about a trip’s origin and destination coordinates and the departure time

is available. In this setting, we aim to ﬁnd paths for all passengers, such that the sum over all

passenger travel times is minimal and all vehicle capacity constraints are kept. We formalize the

underlying planning problem as follows.

Notation: We consider a set of passengers P={1,2, ..., P }and a set of vehicle route schedules

R={1,2, ..., R}in the transportation system. Each passenger p∈ P is associated with a request

tuple ζp= (op, dp, δp)comprising an origin coordinate op, a destination coordinate dpand a departure

time δp, which is the timestep in which a passenger wants to begin its trip. Every vehicle route

schedule r∈ R contains information about the stops Srof the route, the arriving times Tα

r(s)at

stops s∈ Sr, and the capacity γrof the vehicle operating the route. Implicitly, the arrival times

indicate in which order a route’s stops are visited. Furthermore, we deﬁne S=Sr∈R Sras the set

of all stops of the transportation system and T(s) = Sr∈R Tα

r(s)as the set of all timestep in which

vehicles arrive at stop s∈ S.

Solution: A solution to a problem instance is a set of paths ψ= (φ1, φ2, ..., φP)with one path for

each passenger p∈ P. Every path φpis either a list of tuples [(op, δp),(s1

p, t1

p),(s2

p, t2

p)..., (dp, tnp

p)],

or an empty set ∅if there does not exist a feasible path for passenger p. Here for i∈[1, ..., np−1],

p∈ S is a stop in the transportation system, ti

p∈T(si

p)is a timestep in which a vehicle arrives at

stop si

p, and tnp

p>0is the timestep at which passenger parrives at its destination coordinate.

Objective: Our objective is to minimize the sum of travel times for all passengers p∈ P

min c(ψ) = min X

p∈P

c(φp)(2.1)

Here, c(φp) = tnp

p−δpis the travel time of passenger p∈ P when using path φp. If no feasible

path was found for pasenger p, i.e., φp=∅, we assign c(φp) = ρ, with ρbeing a predeﬁned penalty.

Constraints: A solution ψis feasible if the following constraints hold:

(i) The capacity γrof a vehicle driving route r∈ R is greater than the number of passengers

using the route at each point in time.

(ii) For each tuple pair (si

p, ti

p),(si+1

p, ti+1

p),i∈[1, ..., np−1] in φpwith p∈ P, there

(a) either exists a route r∈ R where the vehicle departs from si

pin timestep ti

pto arrive at

si+1

pin ti+1

pwithout any stopovers,

(b) or the distance between si

pand si+1

pis smaller than a given maximum walking distance

(∆w) and ti+1

p−ti

pis at minimum the time necessary to walk from si

pto si+1

pwith given

walking speed ξ,

p=si+1

pand ti

p> ti+1

(iii) The distance between opand s1

pis smaller than a maximum access distance ∆a.

(iv) The distance between snp−1

pand dpis smaller than a maximum egress distance ∆e.

(v) The time t1

p−δpuntil a vehicle arrives at the ﬁrst stop s1

pwhen a passenger ﬁrst enters the

transportation system is smaller than a given maximum waiting time Υ.

(vi) tnp

p≤δp+tmax, where tmax is the maximum travel time a passenger is allowed to take for its

trip.

Three comments on this problem setting are in order. First, we assume that information about

stops and arrival times at the stops is available for all vehicle routes. This assumption holds for

scheduled transportation modes, e.g., bus, subway, and tram, but does not apply to ride hailing

services. Still, it is possible to include unscheduled transportation modes in our model by adding a

fully connected graph layer. Second, we assume ﬁxed arc capacities with ﬁxed travel times instead of

ﬂow dependent travel times. This approximation is mostly consistent with travel time observations

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

OptimizingintermodaltransportationnetworksatscaleviacolumngenerationBenediktLienkamp1andMaximilianSchier21TUMSchoolofManagement,TechnicalUniversityofMunich,80333Munich,Germanybenedikt.lienkamp@tum.de2TUMSchoolofManagement&MunichDataScienceInstitute,TechnicalUniversityofMunich,80333Munich,Germanysch...

收起<<

Optimizing intermodal transportation networks at scale via column generation Benedikt Lienkamp1and Maximilian Schiﬀer2 1TUM School of Management Technical University of Munich 80333 Munich Germany.pdf

共25页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Optimizing intermodal transportation networks at scale via column generation Benedikt Lienkamp1and Maximilian Schiﬀer2 1TUM School of Management Technical University of Munich 80333 Munich Germany

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: