Queue replacement principle for corridor problems with heterogeneous commuters

2025-04-29 0 0 637.75KB 38 页 10玖币

侵权投诉

Queue replacement principle for corridor problems

with heterogeneous commuters

Takara Sakaia,∗, Takashi Akamatsub,∗, Koki Satsukawac,∗

aDepartment of Civil and Environmental Engineering, Tokyo Institute of Technology,

2-12-1 W6-9, Ookayama, Meguro, Tokyo 152-8550, Japan.

bGraduate School of Information Sciences, Tohoku University,

6-6 Aramaki Aoba, Aoba-ku, Sendai, Miyagi 980-8579, Japan.

cInstitute of Transdisciplinary Sciences for Innovation, Kanazawa University,

2B611 Natural Science & Technology Hall, Kakuma-machi, Kanazawa, Ishikawa 920-1192, Japan.

Abstract

This study investigates the theoretical properties of a departure time choice problem considering com-

muters’ heterogeneity with respect to the value of schedule delay in corridor networks. Speciﬁcally, we

develop an analytical method to solve the dynamic system optimal (DSO) and dynamic user equilibrium

(DUE) problems. To derive the DSO solution, we ﬁrst demonstrate the bottleneck-based decomposition

property, i.e., the DSO problem can be decomposed into multiple single bottleneck problems. Subsequently,

we obtain the analytical solution by applying the theory of optimal transport to each decomposed problem

and derive optimal congestion prices to achieve the DSO state. To derive the DUE solution, we prove

the queue replacement principle (QRP) that the time-varying optimal congestion prices are equal to the

queueing delay in the DUE state at every bottleneck. This principle enables us to derive a closed-form DUE

solution based on the DSO solution. Moreover, as an application of the QRP, we prove that the equilibrium

solution under various policies (e.g., on-ramp metering, on-ramp pricing, and its partial implementation)

can be obtained analytically. Finally, we compare these equilibria with the DSO state.

Keywords: departure time choice problem, corridor networks, heterogeneous value of schedule delay, dynamic user

equilibrium, dynamic system optimum

1. Introduction

1.1. Background

The departure time choice problem proposed by Vickrey (1969) describes time-dependent traﬃc con-

gestion as the dynamic user equilibrium (DUE) of commuters’ departure time choices. Many studies have

analyzed the departure time choice problem in the classical framework with a single bottleneck and homo-

geneous commuters, and they have clariﬁed theoretical properties, such as existence, uniqueness and the

closed-form analytical solution (Vickrey,1969;Hendrickson and Kocur,1981;Smith,1984;Daganzo,1985;

Newell,1987;Arnott et al.,1993;Lindsey,2004). These results provide important insights for designing

traﬃc management policies, such as dynamic pricing and on-ramp metering (see Li et al. (2020) for a recent

comprehensive review).

An important property of the single bottleneck model, assuming homogeneous commuters, is that when

time-varying congestion prices mimicking the DUE queueing delay pattern are implemented, bottleneck

congestion is eliminated without changing the arrival time at the destination of each commuter (Vickrey,

∗Corresponding author

Email addresses: sakai.t.av@m.titech.ac.jp (Takara Sakai), akamatsu@plan.civil.tohoku.ac.jp (Takashi Akamatsu),

satsukawa@staff.kanazawa-u.ac.jp (Koki Satsukawa)

Preprint submitted to Elsevier February 15, 2024

arXiv:2210.03357v3 [math.OC] 14 Feb 2024

1969;Arnott,1998). Such a dynamic pricing pattern leads the traﬃc state to a dynamic system optimal

(DSO) state in which the total system cost is minimized (Hendrickson and Kocur,1981;Arnott et al.,1993,

1994;Laih,1994;Akamatsu et al.,2021). Therefore, the optimal pricing pattern can be obtained by observing

the queueing delay pattern in the DUE state. Conversely, the queuing delay pattern in the DUE state can

be obtained from the optimal pricing pattern in the DSO state (Iryo and Yoshii,2007;Akamatsu et al.,2021).

This means that the DUE ﬂow pattern can be derived using the optimal pricing pattern in the DSO state.

Figure 1illustrates this fact by comparing the DSO and DUE states. The horizontal axes in Figure 1(a)-

(d) represent the arrival time t∈ T at the destination of commuters, where Tis the morning rush-hour.

Figure 1(a) represents the cumulative arrival curve ASO(·) and cumulative departure curve DSO(·) for the

DSO state. Because a queue is eliminated in the DSO state, if the free-ﬂow travel time is ignored, the arrival

curve ASO(·) is the same as the departure curve DSO(·). Figure 1(b) shows the optimal pricing pattern pSO(t),

which can be obtained as the optimal Lagrangian multiplier of a linear programming (LP) representing the

DSO problem. Figure 1(d) shows that this optimal pricing pattern equals the queueing delay pattern wUE(t)

in the DUE state. In addtion, Figure 1(c) shows that the departure curve in the DUE state DUE(·) is the same

as that in the DSO state. Based on DUE(·) and wUE(t), the arrival curve in the DUE state AUE(·) can ﬁnally be

obtained as shown in Figure 1(c).

We refer to this remarkable replaceability between the queueing delay and optimal pricing as the queue

replacement principle (QRP).

Deﬁnition 1.1. When the dynamic pricing pattern {pSO(t)}t∈T in the DSO state is equal to the queueing

delay pattern {wUE(t)}t∈T in the DUE state, the QRP holds.

The QRP does not only contribute to obtaining the analytical solution, but it also clariﬁes the eﬃciency and

equity of an optimal pricing scheme from the perspective of welfare analysis. In particula, the QRP shows

that the travel costs of all commuters do not change with/without implementing optimal dynamic pricing.

This means that the QRP is useful for designing an eﬃcient and equitable traﬃc management scheme.

Considering these contributions of the QRP, it plays a pivotal role in analyzing the theoretical properties

in more general settings, such as multiple-bottleneck networks and heterogeneous commuters. For this

problem, Fu et al. (2022) investigated whether QRP holds for the departure time choice problem in corridor

networks with multiple bottlenecks, and they demonstrated that QRP holds under certain assumptions.

However, little is known about whether the QRP holds in the presence of heterogeneous commuters.

1.2. Purpose

This study proves that the QRP holds for corridor problems with heterogeneous commuters who have

diﬀerent values of schedule delay. We prove this QRP condition using the following two-step approach:

we derive the analytical (I) DSO and (II) DUE solutions. In part (I), we ﬁrst formulate the DSO problem as

an LP. We demonstrate that the DSO solution is established according to the bottleneck-based decompo-

sition property. This property enables us to decompose the DSO problem with multiple bottlenecks into

independent single bottleneck problems, which are analytically solvable with the theory of optimal trans-

port (Rachev and R ¨

uschendorf,1998). From this analytical solution, we can derive the optimal congestion

pricing pattern that achieves the DSO state.

In part (II), we investigate whether the queueing delay pattern is equivalent to the optimal pricing

pattern. First, we formulate the DUE problem as a linear complementarity problem (LCP). Subsequently, we

verify that the queueing delay pattern satisﬁes the physical requirements of a queue and that the associated

DUE ﬂow pattern can be constructed using this queuing delay pattern under a certain assumption which

is related to the schedule delay cost function and nonnegative ﬂow condition. From this approach, we ﬁnd

that there exists a DUE solution whose queueing delay pattern equals the optimal pricing pattern, i.e., we

complete the proof of the QRP under the assumption.

This QRP implies a replaceability between commuters’ pricing and queueing costs at all bottlenecks.

We clarify that this replaceability can independently hold at each bottleneck. Speciﬁcally, we focus on the

case in which congestion pricing is only introduced for some bottlenecks. We demonstrate that the asso-

ciated equilibrium can be derived by suitably replacing the queueing and pricing costs at each bottleneck.

time

# vehicles (DSO) # vehicles (DUE)(a)

(b)

(c)

(d)

ASO(·)

DSO(·)AUE(·)DUE(·)

optimal pricing pSO(t) queueing delay wUE(t)

pSO(t)=wUE(t)

wUE(t)

Figure 1: Queue replacement principle in a single bottleneck.

Furthermore, as an application of the obtained results, we show that such replaceability of commuters’

cost holds when on-ramp-based policies are implemented. Speciﬁcally, we consider equilibriums under

on-ramp metering and pricing. We reveal that, at each on-ramp, the optimal pricing pattern equals the

queueing pattern created by metering in equilibrium, just like the QRP. Finally, we investigate eﬃcient

policies by comparing equilibrium under the bottleneck-based and on-ramp-based policies.

1.3. Literature review

For multiple-bottleneck problems, Kuwahara (1990) ﬁrst analyzed the DUE problem in a two-tandem

bottleneck network. Kuwahara (1990) showed a spatio-temporal sorting property of commuters’ arrival

times. In Y-shaped networks with tandem bottlenecks, Arnott et al. (1993) theoretically demonstrated

a capacity-increasing paradox, and Daniel et al. (2009) demonstrated a similar paradox in a laboratory

setting. Lago and Daganzo (2007) studied a similar problem with spillover and merging eﬀects. However,

applying their approach to analyze cases where an arbitrary number of bottlenecks exist is challenging be-

cause they employed the proof-by-cases method, as reported by Arnott and DePalma (2011). To overcome

this limitation, Akamatsu et al. (2015) proposed a transparent formulation of the DUE problem in corri-

dor networks with multiple bottlenecks. They introduced arrival-time-based variables (i.e., Lagrangian

coordinate approach) that facilitate the analysis in corridor networks.1Using the Lagrangian coordinate

approach, Osawa et al. (2018) derived the solution to the DSO problem as part of the long-term location

choice problem. 2Fu et al. (2022) successfully derived the analytical solution to DUE problems in corridor

networks with homogenous commuters.

1Arnott and DePalma (2011); DePalma and Arnott (2012); Li and Huang (2017) examined continuum corridor problems. Unlike

the bottleneck congestion, they focused on ”ﬂow congestion” and showed the relationship between velocity and density using the

LWR-like traﬃc ﬂow model.

2Osawa et al. (2018) considered commuters’ heterogeneity; however, they only discussed the ﬁrst-best traﬃc ﬂow pattern (DSO

problem) because their primary purpose was to obtain long-term policy implications.

For commuters’ heterogeneity, many studies focused on the single bottleneck problem. These studies

are classiﬁed into two categories, depending on how heterogeneity is considered.3One considered the

heterogeneity of the preferred arrival time at the destination as analyzed in Hendrickson and Kocur (1981);

Smith (1984); and Daganzo (1985). They proved the existence and uniqueness of the DUE solution and

showed a regularity of the ﬂow pattern, which is called the ﬁrst-in-ﬁrst-work principle. The other category

considered the heterogeneity of the value of time; this includes Arnott et al. (1988,1992,1994); van den Berg

and Verhoef (2011); Liu et al. (2015); and Takayama and Kuwahara (2017). They presented welfare analysis

and showed that optimal policies can cause inequity in some cases.

In contrast to these studies, our study investigates the departure time choice problems in the corridor

networks with commuters’ heterogeneity concerning the value of schedule delay. Our contributions are

summarized as follows:

(1) Derivation of the analytical DSO solution:

This study constructs a systematic approach to solving the DSO problem. Speciﬁcally, by combining

the bottleneck-based decomposition property and the theory of optimal transport, we show that the

DSO problem can be solved by sequentially solving single bottleneck problems.

(2) Proof of the QRP:

This study investigates the DSO and DUE problems in corridor networks considering commuters’

heterogeneity in terms of the value of schedule delay. We successfully prove that the QRP holds under

certain conditions.

(3) Derivation of the analytical DUE solution:

We derive the analytical DUE solution based on the DSO solution and QRP. Moreover, this contri-

bution implies that the solution to an LCP (DUE problem), which is signiﬁcantly diﬃcult to solve

analytically (Arnott and DePalma,2011;Akamatsu et al.,2015), can be obtained from the solution

to the LP (DSO problem). This is a theoretically/mathematically remarkable ﬁnding, representing a

substantial advancement in the theory of dynamic traﬃc assignment problems.

(4) Derivation of the equilibria under various policies using the QRP:

As an application of Contributions (1)-(3), we show that the equilibria under on-ramp metering and

on-ramp pricing can be derived using the QRP. This fact clariﬁes the theoretical relationships between

bottleneck-based pricing and on-ramp-based policies. Moreover, we focus on cases in which policies

are implemented at certain parts of the network and derive the associated equilibrium solution using

the QRP. This means that the QRP enables us to analyze and characterize such an equilibrium state

that is neither the pure DUE nor the DSO state.

1.4. Structure of this paper

The remainder of this paper is organized as follows: Section 2introduces the network structure and

the heterogeneity of commuters. Section 3presents the formulation of the DSO problem and constructs

the systematic approach for deriving its analytical solution. In Section 4, through the proof of the QRP,

we derive the analytical solution to the DUE problem using the analytical DSO solution. Finally, Section 5

presents the application of the QRP. Section 6concludes this paper. In this paper, all proofs of propositions

are given in the appendix.

3There are a few exceptions. Newell (1987); Lindsey (2004); Hall (2018,2021) belong to both categories because they simultaneously

consider two types of commuters’ heterogeneity.

Ni210

µNµiµ2µ1

{Qi,1, ..., Qi,K}

(a) Corridor network with Norigins and the single destination 0.

βKc(t)

βkc(t)

β1c(t)

preferred arrival time 0

(b) Schedule delay cost functions.

Figure 2: Network and schedule delay cost functions.

2. Model settings

2.1. Networks and commuters

We consider a freeway corridor network consisting of Non-ramps (origin nodes) and a single oﬀ-ramp

(destination node). These nodes are numbered sequentially from the destination node, denoted “0”, to the

most distant origin node N(Figure 2(a)). The set of origin nodes is denoted by N ≡ {1,2,...,N}. The link

connecting node ito node (i−1) is referred to as link i. Each link consists of a single bottleneck segment

and free-ﬂow segment. We refer to the bottleneck on link ias bottleneck i.

Let µibe the capacity of bottleneck i. We also deﬁne µi≡µi−µ(i+1), where µ(N+1) ≡0. A queue is formed

at each bottleneck when the inﬂow rate exceeds the bottleneck capacity. The queue dynamics are modeled

by the standard point queue model along with the ﬁrst-in-ﬁrst-out (FIFO) principle. The free-ﬂow travel

time from origin (and bottleneck) i∈ N to the destination is denoted by di.

From each origin i,Qicommuters enter the network and reach their destination during the morning

rush-hour T. Commuters are treated as a continuum, and the total mass Qiat each origin iis a given

constant. The commuters are also classiﬁed into a ﬁnite number Kof homogeneous groups with respect to

the value of schedule delay. The index set of groups is K={1,2,...,K}. The mass of commuters in group k

departing from origin iis denoted by Qi,k; therefore, Pk∈K Qi,k=Qi. Commuters in group kdeparting from

origin iare referred to as (i,k)-commuters.

The trip cost for each commuter is assumed to be additively separable into free-ﬂow travel, queueing

delay, and schedule delay costs. The schedule delay cost is deﬁned as the diﬀerence between the actual

and preferred arrival times at the destination. We assume that all commuters have the same preferred

arrival time tp=0. The schedule delay cost for group kcommuters who arrive at the destination at time t

is represented by ck(t). We assume that ck(t) is represented by βkc(t), where c(t) is a base schedule delay cost

function with c(tp)=0, which is assumed to be strictly quasi-convex and piecewise diﬀerentiable ∀t∈ T ,

as shown in Figure 2(b). In addtion, we assume dc(t)/dt>−1, ∀t∈ T as in Daganzo (1985); Lindsey (2004).

βk∈(0,1] is a parameter representing the heterogeneity of commuters with βK< ... < β1=1. We also let

βk≡βk−β(k+1), where β(K+1) ≡0.

Because c(t) is strictly convex, for a given time length T, we can deﬁne t−(T) as the unique solution to

the equation c(t)=c(t+T). We deﬁne t+(T) as t+(T)=t−(T)+T. The base schedule delay cost at t−(T) (and

t+(T)) is denoted by c(T) (i.e., c(T)=c(t−(T)) =c(t+(T))). We also deﬁne time set Γ(T) as

Γ(T)≡[t−(T),t+(T)],(1)

where Γ(T) is uniquely determined for T(see Figure 3).

2.2. Formulation in a Lagrangian-like coordinate system

We primarily describe traﬃc variables in a Lagrangian-like coordinate system (Kuwahara and Akamatsu,

1993;Akamatsu et al.,2015,2021). In this system, variables are expressed in association with the arrival

time at the destination, and not at the origin or bottleneck. Such an expression is suitable for considering

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

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

10 玖币 0人已下载

立即下载

摘要：

QueuereplacementprincipleforcorridorproblemswithheterogeneouscommutersTakaraSakaia,∗,TakashiAkamatsub,∗,KokiSatsukawac,∗aDepartmentofCivilandEnvironmentalEngineering,TokyoInstituteofTechnology,2-12-1W6-9,Ookayama,Meguro,Tokyo152-8550,Japan.bGraduateSchoolofInformationSciences,TohokuUniversity,6-6Ara...

展开>> 收起<<

Queue replacement principle for corridor problems with heterogeneous commuters.pdf

共38页,预览5页

还剩页未读，继续阅读

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

Queue replacement principle for corridor problems with heterogeneous commuters

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: