数理解析研究所講究録
第 1773 巻 2012 年 1-12

1

ロバスト Wardrop 均衡問題と二次錐相補性問題への変換
伊藤 好彦 ，
高橋 仁 ，
林 俊介

概要(京都大学)

与えられた交通ネットワークに対して，出発地と目的地のべア，および各々のペアに対する交通需要が与えられたとき，各ルートにおける交通量の均衡状態として知られるのが Wardrop 均衡である．

Wardrop 均衡とは，いずれのドライバーも，自分だけがルートを変更することにより，所要時間を減少させることができない状態であり，このような均衡状態は Wardrop の等時間配分原理によって特徴づけられる．Wardrop 均衡の概念は，すべてのドライバーが交通ネットワークのすべての情報 (所要時間関

数のパラメータなど)をもち，それ自体がすべてのドライバーの共通認識であるという前提の下で意味をなす．しかし，現実においては，その前提が必ずしも満たされるとは限らない．そこで，本報告書では，各ドライバーが不確実な情報のト- で起こり得る最悪のケースを想定し，それに基づいて自分のルートを選択するものと考える．そして，そのときに得られる均衡状態をロバスト Wardrop 均衡と定義する．本報告書では，ドライバーの目的地までの所要時間関数に不確実性を組み込み，その不確実性の下
でロバスト Wardrop 均衡問題を定式化する．さらに，不確実性を表す集合が 2 ノルムで表されるとき，
ロバスト Wardrop 均衡問題を二次錐相補性問題という既存の手法 (平滑化ニュートン法など) で解くことのできるクラスの問題に再定式化する．最後に，具体的に与えられた交通ネットワークに対して，ロ

バスト Wardrop 均衡問題を計算機で実際に解き，不確実性集合の違いに対するロバスト Wardrop 均衡

解の変化を調べる．

1

Introduction

Since the $1930s$ , the automobiles have been widely used all over the world because of the economic
growth and the technological and scientific development. In order to make the automobile traffic more
efficient, we need to design roadway infrastructures such as highways, traffic signals, and toll roads.
When we build new roads or decide new tolls on a traffic network, we need to forecast the traffic
flow to estimate the effect due to such decisions. In general, all drivers are supposed to select the routewith the minimum cost from the origin to the destination. In other words, the routes with positive
traffic flow have the minimum cost, and more costly routes are not used. This flow distribution principle is called Wardrop’s user equilibrium principle [20]. Also, the problem of finding a flow patternsatisfying Wardrop‘s user equilibrium principle is called the Tkaffic Assignment Problem (TAP). The
TAP is formulated as mathematical programming problems such as a linear or nonlinear optimization problem, Variational Inequality Problem (VIP), Mixed Complementarity Problem (MCP), andNonlinear Complementarity Problem (NCP) [1, 2, 4, 11, 17, 18].
In order to formulate the TAP as a mathematical programming problem, it is important to model
the cost on each route appropriately. When the route cost function is expressed as the sum of road*1
costs, the route cost function is called additive [1, 4, 17, lS]. Otherwise, it is called non-additive [2, 11].
In the TAP, we suppose that each user has complete information on the traffic network and canchoose a route with minimum cost by using that information. However, in the real traffic network, eachuser estimated cost can be often incorrect due to various uncertainties such as weather changeabilityor traffic accidents. Therefore he $/she$ may choose a route with non-minimal cost, and the flow basedon Wardrop‘s user equilibrium principle does not necessarily express the real network flow.
For the traffic model in which the drivers do not know the complete information on the network,
the new concept called the robust Wardrop equilibrium [14, 15, 19] attracts much attention recently.
In the robust Wardrop equilibrium, we assume that each driver can estimate the (uncertainty set” inwhich the uncertain data of his $/her$ route cost function are contained, and then choose $his/her$ routewith taking the value of the worst (route) cost function into consideration. In other words, each driver
$s$

$*1$

The road in a traffic network corresponds to the link in a directed graph. For more detail, see Section 2.

2chooses his $/her$ route based on the robust optimization policy [3, 6, 5, 13]. The traffic assignment
problem based on the robust Wardrop equilibrium is called a robust TAP, which we will mainly discussin the paper.
The robust Wardrop equilibrium has been studied by some researchers so far.
and StierMoses [14, 15] defined the robust Wardrop equilibrium for the restrictive case where each user’s costfunction can be expressed as the sum of two terms: (1) the term depending on the flow but not involving
any uncertainty and (2) the term not depending on the flow but involving some uncertainty. They
showed that, when the uncertainty set in each route cost functions is polyhedral, the robust TAP canbe formulated as an NCP. On the other hand, Takahashi [19] defined the robust Wardrop equilibrium
for more general route cost functions without
and Stier-Moses’ restriction. Moreover, heshowed that the robust TAP can be reformulated as a Second-Order Cone Complementarity Problem(SOCCP) [8, 10, 12, 16], when the route cost function is additive, the link cost function is linear andseparable , and the uncertain set is ellipsoidal. Also Takahashi showed that the robust TAP can bereformulated as an MCP when the uncertainty set is defined by means of the -norm.
For the traffic model with uncertain cost functions, Zhang, Chen and Sumalee [21] studied anothermathematical approach called a stochastic TAP. They assumed that the uncertain data in the costfunctions follow some stochastic distribution, and reformulated the stochastic TAP as a stochastic
complementarity problem that can be solved by using the expected residual minimization method.
Although Zhang et al. discuss the robustness of the obtained stochastic TAP solution, the meaningof “robust“ is essentially different from that in the “robust“ TAP model. The robustness in Zhang etal.’s study means that the obtained stochastic TAP solution does not vary so much if the actual valueof the stochastic data varies in some degree. On the other hand, the robustness for the robust TAP
comes from the “robust optimization”, by which each driver chooses his $/her$ route.
In this paper, we consider the robust Wardrop equilibrium in [14, 15, 19] to TAPs with more general
uncertainty structures. In [19], Takahashi only considered the case where the link cost functions intraffic network are linear and separable, whereas we study the robust TAP without such a linearity
and separability assumption. We also provide the condition for the existence of a robust Wardrop
equilibrium, and reformulate the robust TAP as an SOCCP when the uncertainty set is ellipsoidal.
This paper is organized as follows. In Section 2.1, we describe the traffic model and Wardrop‘s user
equilibrium without uncertainty, and formulate the TAP based on the traffic model and Wardrop‘suser equilibrium. In Section 2.2, we recall background of some equilibrium problems such as SOCCP,
MCP, and NCP. In Section 2.3, we formulate the TAP as an NCP and an MCP. Moreover we provide
the condition for the existences of a solution for TAP. Section 3 is the main section of this paper. In
Section 3.1, we define the robust Wardrop equilibrium, and formulate the robust TAP as an MCP.
Furthermore we show the condition for the existence of a solution of the robust TAP. In Section
3.2, we formulate the robust TAP with an ellipsoidal uncertainty set as an SOCCP. In Section 4, we
observe the property of equilibria for robust TAPs by means of numerical experiments. In Section 5,
we conclude this paper with some remarks.
Throughout the paper, we use the following notations and definitions:denotes the 2-norm$:=\sqrt{z^{T}z}$denotes the cardinality of S.
denotes
defined byfor a vector . For a given set $S,$
the n-dimensional Euclidean space.
denotes the set of $m\cross n$ real matrices. For a finite set$N$ and $z=(z_{1}, z_{2,\ldots,|N|}z)$ , we write $z=[z_{i}]_{i\in N}$ . We often write $z=(x, y)$ for. For thevectors and of the same dimension,means $a^{T}b=0$ .
$Ord6\tilde{n}ez$$Ord6\overline{n}ez$$*2$$\infty$$\Vert\cdot\Vert$

$|S|$

$z$

$\Vert z\Vert$$\mathbb{R}^{n}$$\mathbb{R}^{m\cross n}$$[x^{T}, y^{T}]^{T}$

$a$

2

$b$

$a\perp b$

Preliminaries

In this section, we recall some fundamental background on the TAP and some related topics. In
Subsection 2.1, we give a mathematical expression of the TAP by using Wardrop‘s user equilibrium
principle. In Subsection 2.2, we introduce some classes of complementarity problems, which play animportant role in solving TAPs and robust TAPs. In Subsection 2.3, we reformulate the TAP as acomplementarity problem, and study the condition under which TAP solutions exist.
$*2$

The link cost function is said to be separable if its value depends only on the link flow.

3
2.1

Mathematical formulation of traffic assignment problem

In this section, we provide a mathematical formulation of TAP. Consider a directed graphcorresponding to the traffic network, whereand denote the node (vertex or point) set and thelink (edge or arc) set, respectively. In the real traffic network, the nodes correspond to the origins, thedestinations and the intersections, and the links correspond to the roads. $W$ denotes the set which
consists of origin-destination pairs (OD pairs). We assume that graph is strongly connected, that is,$\mathcal{G}=(\mathcal{N}, \mathcal{L})$$\mathcal{N}$$\mathcal{L}$$\mathcal{G}$there exists at least one route for every OD pair $w\in W$ . Let
be the set of all routes between OD
pair $w\in W$ , and $R$. For $r\in R,$
denotes the set of all links contained in .
anddenote the flow of link
and route $r\in R$ , respectively. Let the link and the route
flow vectors be denoted as
and $x:=(x_{1}, x_{2}, \ldots, x_{|R|})$ , respectively.
:
denotes the cost function for route $r\in R$ with variable.
:
denotes the costfunction for link$:= \min_{r\in R_{u)}}f_{r}(x)$ denotes
with variable. For an OD pair $w\in W,$
the minimum route cost.
:denotes the demand function with variable.
Next, we describe Wardrop‘s user equilibrium principle which shows drivers’ behavior in the traffic
network. A route flow vector
is called Wardrop‘s user equilibrium if it satisfies$R_{w}$$:= \bigcup_{w\in W}R_{w}$$x_{r}\in \mathbb{R}$$\mathcal{L}_{r}\subset \mathcal{L}$$r$$y_{l}\in \mathbb{R}$$l\in \mathcal{L}$$y:=(y_{1}, y_{2}, \ldots, y_{|\mathcal{L}|})$$f_{r}$$x\in \mathbb{R}^{|R|}$$y\in R^{|\mathcal{L}|}$$l\in \mathcal{L}$$\lambda_{w}$$\mathbb{R}^{|W|}arrow \mathbb{R}^{|W|}$$d_{w}$$\mathbb{R}^{|R|}arrow \mathbb{R}$$\mathbb{R}^{|\mathcal{L}|}arrow \mathbb{R}$$t_{l}$$\lambda$$:=[\lambda_{w}]_{w\in W}$$x\in \mathbb{R}^{|R|}$$[x_{r}>0\Rightarrow f_{r}(x)\leq f_{r’}(x) \forall r’\in R_{w}]$$r\in R_{w},$$w\in W$.

(2.1)

Wardrop‘s user equilibrium principle states that each driver in the network selects the route withminimum cost. Conversely, the drivers avoid the routes with non-minimum cost. In other words,
under such an equilibrium, the cost of the route with non-zero flow must be less than or equal to otherroutes for the same OD pair, and conversely, any route with non-minimum cost for an OD pair has
no flow.
In addition to Wardrop‘s user equilibrium principle (2.1), the TAP requires the condition thatevery route flow is nonnegative and the sum of route flows for each OD pair is equal to its traffic, that is,demand$x\geq 0$ ,$(w\in W)$ .
(2.2)
$w$

$d_{w}(\lambda)$$x_{r}=d_{w}(\lambda)$$\sum_{r\in R_{\tau}},,$

Combining (2.1) with (2.2), the TAP can be formulated as follows:Findsuch that$(x, \lambda)\in \mathbb{R}^{|R|}\cross \mathbb{R}^{|W|}$$0\leq f_{r}(x)-\lambda_{w}\perp x_{r}\geq 0$$\sum_{r\in R_{?v}}x_{r}=d_{w}(\lambda)$$\lambda_{w}\geq 0$

Findsuch that$(r\in R_{w}, w\in W)$ ,(2.3)$(w\in W)$ ,$(w\in W)$ .

$(x, \lambda)\in \mathbb{R}^{|R|}\cross \mathbb{R}^{|W|}$$0\leq f_{r}(x)-\lambda_{w}\perp x_{r}\geq 0$(2.4)$(w\in W)$ ,$\sum_{r\in R_{w}}x_{r}=d_{w}(\lambda)$$\lambda_{w}\geq 0$$(r\in R_{w}, w\in W)$ ,$(w\in W)$ .

Furthermore, TAP (2.4) can be rewritten equivalently as follows:Findsuch that$(x, \lambda)\in \mathbb{R}^{|R|}\cross \mathbb{R}^{|W|}$$0\leq f(x)-N^{T}\lambda\perp x\geq 0$$Nx-d(\lambda)=0$ ,where function$f$:$\mathbb{R}^{|R|}arrow \mathbb{R}^{|R|}$and matrix$N\in \mathbb{R}^{|W|\cross|R|}$$f(x):=[f_{r}(x)]_{r\in R}$

respectively.

,$\lambda\geq 0$

,

(2.5)

,

are defined by$N_{wr}=\{\begin{array}{l}1 r\in R_{w}0 r\not\in R_{w} ’\end{array}$

(2.6)

4
2.2

Complementarity problems

In this subsection, we introduce some classes of complementarity problems [9]. The complementarity
problem is a kind of equilibrium problem, and has been studied extensively so far since it is mathematically tractable and can be solved efficiently by existing algorithms such as the smoothing Newton
method. In the subsequent sections, we reformulate robust TAPs as complementarity problems.
, NCP and MCP can be
and $F$ :For given functions :$h$$\mathbb{R}^{n}\cross \mathbb{R}^{n}\cross \mathbb{R}^{\nu}arrow \mathbb{R}^{n}\cross \mathbb{R}^{\nu}$$\mathbb{R}^{n}arrow \mathbb{R}^{n}$formulated as

Findsuch that$x\in \mathbb{R}^{n}$

(2.7)

,

$0\leq x\perp h(x)\geq 0$

and

Find
such that$(x, y, \zeta)\in \mathbb{R}^{n}\cross \mathbb{R}^{n}\cross \mathbb{R}^{\nu}$$0\leq x\perp y\geq 0,$(2.8)$F(x, y, \zeta)=0$ ,respectively. Notice that MCP contains NCP as a subclass since NCP (2.7) reduces to MCP (2.8) bysetting $F(x, y, \zeta);=y-h(x)$ .
The second-order cone complementarity problem (SOCCP) [8, 10, 12, 16] is a more general classof complementarity problems written as follows:Findsuch that

where $F$ :second-order cones, that is,-dimensional second-order cone$\mathbb{R}^{n}\cross \mathbb{R}^{n}\cross \mathbb{R}^{l}$ノ$arrow \mathbb{R}^{n}\cross \mathbb{R}^{\nu}$$(x, y, \zeta)\in \mathbb{R}^{n}\cross \mathbb{R}^{n}\cross \mathbb{R}^{l\text{ノ}}$$\mathcal{K}\ni x\perp y\in \mathcal{K}$

,

(2.9)

$F(x,$ $y,$ $()=0$ ,is the Cartesian product of several
is a given function, andwith $n=n_{1}+n_{2}+\cdots+n_{m}$ , and theis defined as$\mathcal{K}$$\mathcal{K}=\mathcal{K}^{n_{1}}\cross \mathcal{K}^{n_{2}}\cross\cdots\cross \mathcal{K}^{n_{m}}$$n_{i}$$\mathcal{K}^{n_{i}}\subset \mathbb{R}^{n_{a}}$$\mathcal{K}^{n_{t}}=\{(z_{1}, z_{2}^{T})^{T}\in \mathbb{R}\cross \mathbb{R}^{n_{t}-1}|z_{1}\geq\Vert z_{2}\Vert\}$.

Notice that SOCCP contains MCP as a subclass since coincides with the nonnegative orthant when$n_{1}=n_{2}=\cdots=n_{m}=1$ . In this paper, we formulate the robust TAP as an SOCCP of the form$\mathcal{K}$Findsuch that$\zeta\in \mathbb{R}^{\nu}$$\mathcal{K}\ni G(\zeta)\perp H(\zeta)\in \mathcal{K},$$C\zeta=h$(2.10),are givenand:are given functions, andwhere
and $H$ :constants. We can easily see that SOCCP (2.10) can be rewritten as SOCCP (2.9) by letting $x:=G(\zeta)$ ,$:=H(\zeta)$ , and$G$$\mathbb{R}^{\nu}arrow \mathbb{R}^{n}$$C\in \mathbb{R}^{v\cross v}$$\mathbb{R}^{\nu}arrow \mathbb{R}^{n}$$h\in \mathbb{R}^{\nu}$$y$$F(x, y, \zeta):=\{\begin{array}{l}y-H(\zeta)x-G(\zeta)C\zeta-d\end{array}\}$2.3.

Complementarity reformulation of TAP and existence of solution

In this section, we show some relation between TAP (2.5) and NCP (2.7) or MCP (2.8), and discuss
the existence of a TAP solution. In order to formulate the TAP as an NCP,we make the following
assumption.
Assumption A In TAP $(2.5)$ , the following conditions hold:(a) $f(x)\geq 0$ and$d(\lambda)\geq 0$

for any$(x, \lambda)\in \mathbb{R}_{+}^{|R|}\cross \mathbb{R}_{+}^{|W|}$(b) For all $r\in R,$ $f_{r}(x)x_{r}=0$ implies $x_{r}=0$ .

,5Notice that (b) automatically holds if $f(x)>0$ for any
can be rewritten in the form of NCP (2.7).

$x\in \mathbb{R}_{+}^{|R|}$. Under this assumption, TAP (2.5)

Theorem 2.1 [9, Proposition 1.4.6] Suppose that TAP (2.5) satisfies Assumption A. Then, the TAP
can be reformulated as the following $NCP$ equivalently:
Findsuch that$(x, \lambda)\in \mathbb{R}^{|R|}\cross \mathbb{R}^{|W|}$.

(2.11)$0\leq\{\begin{array}{l}f(x)-N^{T}\lambda Nx-d(\lambda)\end{array}\}\perp\{\begin{array}{l}x\lambda\end{array}\}\geq 0$

By using the above NCP reformulation, we can derive a sufficient condition under which there
exists at least one solution of TAP (2.5).

Assumption
that

$B$

$d_{w}(\lambda)\leq M$

In TAP (2.5), functions
for any $w\in W$ and

$f$

and
.

$d$

are continuous. Moreover, there exists $M>0$ such$\lambda\in \mathbb{R}^{|W|}$

Theorem 2.2 [9, Proposition 2.2.14] Suppose that Assumptions 2.1 andat least one solution.

$B$hold. Then, TAP (2.5) has

We have shown that TAP (2.5) reduces to an NCP under Assumption 2.1. On the other hand,
it also reduced to an MCP under another assumption. In the subsequent numerical experiments, inorder to some (robust) TAPs, we apply a smoothing Newton algorithm to this MCP.

Assumption$C$

In TAP (2.5), It follows $f(x)\geq 0$ and $d(\lambda)>0$ for any$(x, \lambda)\in \mathbb{R}_{+}^{|R|}\cross \mathbb{R}_{+}^{|W|}$.

Theorem 2.3 Suppose that TAP $(2.5)$ satisfies Assumption C. Then, the TAP can be reformulated
as the following $MCP$ equivalently:
Findsuch that$(x, \lambda)\in \mathbb{R}^{|R|}\cross \mathbb{R}^{|W|}$$0\leq f(x)-N^{T}\lambda\perp x\geq 0$$Nx=d(\lambda)$

3,(2.12).

Traffic assignment problem based on robust Wardrop’s user equilibrium

In this section, we define the robust TAP and discuss the existence of its solution. We also formulate
the robust TAP with special uncertainty structure as an SOCCP.

3.1

Robust traffic assignment problem and existence of solutions

In this subsection, we provide a mathematical expression of the robust TAP, and study the existenceof a robust Wardrop equilibrium.
Consider the following situation. The cost function
for route $r\in R$ contains uncertain data
. Even though the users cannot estimate the value of accurately, they know that it belongs toa certain compact set . In such a situation, we assume that each user with OD pair chooses aroute with minimum worst cost, i.e., a route such that $r= \arg\min_{r\in R_{w}}\tilde{f}_{r}(x)$ , where$f_{r}^{\hat{u}^{r}}$$\hat{u}^{r}$$\hat{u}^{r}$$U_{r}$$w$$r$$\tilde{f}_{r}(x)$$:= \max\{f_{r}^{\hat{u}^{r}}(x)|\hat{u}^{r}\in U_{r}\}$(3.1)

is called the worst cost function. Moreover, a Wardrop equilibrium with respect to the worst cost$f_{r}(x)$ is called a robust Wardrop equlibrium.

6
Definition 3.1 Let the worst cost function
satisfying$\tilde{f}_{r}$be defined by (3.1). Then, a route flow vector$x\in \mathbb{R}^{|R|}$$(r\in R_{w}, w\in W)$ ,$[x_{r}>0\Rightarrow\overline{f}_{r}(x)\leq\tilde{f}_{r’}(x) \forall r’\in R_{w}]$(3.2)

is called a robust Wardrop equlibreum. Moreover, the problem of finding the robust Wardrop equilibmum
is called a robust TAP, i. e., it is to findsuch that$(x, \lambda)\in \mathbb{R}^{|R|}\cross \mathbb{R}^{|W|}$$0\leq\tilde{f}_{r}(x)-\lambda_{w}\perp x_{r}\geq 0$$(r\in R_{u}, w\in W)$ ,$\lambda_{w}\geq 0$$\sum_{r\in R}x_{r}=d_{w}(\lambda),$$(w\in W)$

(3.3)

.

By using the complementarity reformulation technique in the previous section, we can also show
conditions under which a robust Wardrop equilibrium exists. In what follows, we denote $f(x)$ $:=$.
$[\tilde{f}_{r}(x)]_{r=1}^{|R|}\in \mathbb{R}_{+}^{|R|}$

Assumption $D$ For the robust TAP (3.3), the following four conditions hold:(a) For any$x\in \mathbb{R}_{+}^{|R|}$, there exists(b) For each $r\in R$ , the function$\mathbb{R}_{+}^{|R|}\cross U_{r}$$\hat{u}^{r}\in U_{r}$such that$f_{r}^{\hat{u}^{r}}(x)>0$$h_{r}:\mathbb{R}_{+}^{|R|}\cross U_{r}arrow \mathbb{R}+defined$

for each $r\in R$ .

by$h_{r}(x,\hat{u}^{r})$$:=f_{r}^{\hat{u}^{r}}(x)$is continuous on.

(c) $d(\lambda)>0$ for any$\lambda\in \mathbb{R}_{+}^{|W|}$(d) For each $w\in W$ , function.
$d_{w}(\lambda)$

is continuous and bounded above on

Theorem 3.1 Suppose that Assumption
following $MCP$:

$D$

Find
such that

holds.

$\mathbb{R}^{|W|}$.

Then the robust TAP $(3.3)$ is equivalent to the$(x, \lambda)\in \mathbb{R}^{|R|}\cross \mathbb{R}^{|W|}$$0\leq f(x)-N^{T}\lambda\perp x\geq 0$

,

(3.4)

$Nx-d(\lambda)=0$ .

3.2

SOCCP reformulation for robust TAP with ellipsoidal uncertainty sets

In the previous subsection, we have defined the robust TAP and showed the condition for the existenceof a solution. In this section, we show that the robust TAP can be reformulated as an SOCCP when
the uncertainty sets are described by means of the Euclidean norm.

3.2.1

Robust TAP with general link cost function

In what follows, we assume that each link cost function is expressed as$t_{l}^{\hat{u}}{}^{t}(y)=t_{l}(y)+\hat{u}_{l}\triangle t_{l}(y)$

,

(3.5)

where
:
:
and
are given functions, andparameter. Moreover, we suppose that the uncertain route cost function$\mathbb{R}^{|\mathcal{L}|}arrow \mathbb{R}$$t_{l}$$\triangle t_{l}$$\mathbb{R}^{|\mathcal{L}|}arrow \mathbb{R}$$f_{r}^{\hat{u}^{f}}(x)= \sum_{l\in \mathcal{L}_{r}}t_{l}^{\hat{u}_{l}}(y)$where the uncertainty parameter satisfies
incidence matrix with the $(l, r)$ entry$\hat{u}_{l}\in \mathbb{R}$denotes the uncertainty
is additive, i.e.,$f_{r}^{\hat{u}^{r}}(x)$

(3.6)

,

$\hat{u}^{r}=[\hat{u}_{l}]_{l\in \mathcal{L}}\in \mathbb{R}^{|\mathcal{L}|}$. Now, let$\ovalbox{\tt\small REJECT}_{r}\cdot=\{\begin{array}{l}1 (l\in \mathcal{L}_{r})0 (l\not\in \mathcal{L}_{r}).\end{array}$$M\in \mathbb{R}^{|\mathcal{L}|\cross|R|}$be the link-route7
Then we have $y=Mx$ , which together with (3.5) and (3.6) yields$f_{r}^{\hat{u}^{r}}(x)= \sum_{l\in \mathcal{L}_{r}}t_{l}(Mx)+\hat{u}_{l}\triangle t_{l}(Mx)$

.

(3.7)

Furthermore, we make the following assumption on the uncertainty set

Assumption$E$

Uncertainty set$U_{r}$$\overline{u}^{r}$

Under Assumption
the following lemma.

$E$$D_{r}\in \mathbb{R}^{|\mathcal{L}|\cross|\mathcal{L}}$$\Vert\hat{v}^{r}\Vert\leq\delta_{r},$$(a, b)\in \mathbb{R}^{n}\cross \mathbb{R}^{m}$$P\subset \mathbb{R}^{m}$

$\}$

,

I is a given symmetric positive definite matrix, and, we can represent the worst cost function

Lemma 3.1 Let
be any positive scalar. Let.

is ellipsoidal for each $r\in R$ , i. e.,$\ovalbox{\tt\small REJECT}:=\{\hat{u}^{r}\in \mathbb{R}^{|\mathcal{L}|}|\hat{u}^{r}=\overline{u}^{r}+D_{r}\hat{v}^{r},$whereis a given vector,
given positive scalar.

$U_{r}$

be arbitmry vectors,
be defined by$C\in \mathbb{R}^{m\cross n}$$\tilde{f}_{r}$.

$\max_{p\in R^{m}}\{a^{T}p|p\in P\}=a^{T}b+\delta\Vert C^{T}a\Vert$.

Then we have$f_{r}^{\hat{u}^{r}}$is aexplicitly. To this end, we needbe an arbitrary matrix, and $\delta>0$$P:=\{p\in \mathbb{R}^{m}|p=b+Cq, \Vert q\Vert\leq\delta\}$

Applying Lemma 3.1 to the uncertain route cost
obtain$\delta_{r}$(3.8)

with (3.7) under Assumption$\tilde{f}_{r}(x)=\sum_{l\in \mathcal{L}_{r}}t_{l}(Mx)+\overline{u}_{l}^{r}\triangle t_{l}(Mx)+\delta_{r}\Vert D_{r}diag(M_{r})\triangle t(Mx)\Vert$,$E$, we readily

(3.9)

.
where diagis the diagonal matrix whose diagonal components are given by
By Theorem 3.1, the robust TAP withdefined by (3.9) reduces to MCP (3.4) under Assumption D. However, since $f$ is nondifferentiable, it is difficult to apply existing algorithms to MCP (3.4)
directly. To avoid this difficulty, we reformulate the robust TAP as an SOCCP that contains differentiable functions only.
Let
and $g(x);=[g_{r}(x)]_{r=1}^{|R|}\in \mathbb{R}^{|R|}$ . Then the worst costfunction (3.9) can be expressed explicitly as$M_{lr}(l\in \mathcal{L})$$(M_{r})\in \mathbb{R}^{|\mathcal{L}|\cross|\mathcal{L}|}$$\tilde{f}_{r}(x)$$g_{r}(x):= \sum_{l\in \mathcal{L}_{r}}t_{l}(Mx)+\overline{u}_{l}^{r}\triangle t_{l}(Mx)$$\tilde{f}(x)=g(x)+\{\begin{array}{l}\delta_{1|_{|D_{2}diag(M_{2})\triangle t(Mx)||}^{|D_{1}diag(M_{1})\triangle t(Mx)||}}\delta_{2}|\delta_{|R|}||D_{|R|}diag(M_{|R|})\triangle t(Mx)||\end{array}\}$Moreover, by using an auxiliary variable$s:=[s_{r}]_{r=1}^{|R|}\in \mathbb{R}^{|R|}$.

, MCP (3.4) can be rewritten as thefollowing problem:Findsuch that$(x, \lambda, s)\in \mathbb{R}^{|R|}\cross \mathbb{R}^{|W|}\cross \mathbb{R}^{|R|}$$0\leq g(x)+s-N^{T}\lambda\perp x\geq 0$ ,$s_{r}=\delta_{r}\Vert D_{r}diag(M_{r})\triangle t(Mx)\Vert(r\in R)$$Nx=d(\lambda)$,(3.10).
(3.11)

Furthermore, we can reformulate (3.10) as an SOCCP by the following lemma.

8Lemma 3.2 Let
if there exists a vector

be an arbitmry vector with $k\geq 2$ . Then,such that$(\xi_{1},\xi_{2})\in \mathbb{R}\cross \mathbb{R}^{k-1}$$v\in \mathbb{R}^{k-1}$$\mathcal{K}^{k}\ni\{\begin{array}{l}\xi_{1}\xi_{2}\end{array}\}\perp\{\begin{array}{l}lv\end{array}\}\in \mathcal{K}^{k}$$\xi_{1}=\Vert\xi_{2}\Vert$.

if and only(312)

By Lemma 3.2, problem (3.10) can be reformulated as the following SOCCP:
Findsuch that$(x, \lambda, s, v)\in \mathbb{R}^{|R|}\cross \mathbb{R}^{|W|}\cross \mathbb{R}^{|R|}\cross \mathbb{R}^{|\mathcal{L}||R|}$$0\leq g(x)+s-N^{T}\lambda\perp x\geq 0$$\mathcal{K}^{|\mathcal{L}|+1}\ni[\delta_{r}D_{r}$diag$Nx=d(\lambda)$,$(M_{r})\Delta t(Mx)s_{r}]\perp\{\begin{array}{l}1v^{r}\end{array}\}\in \mathcal{K}^{|\mathcal{L}|+1}$$d$$\mathcal{K}$$C=[o_{|R|(|\mathcal{L}|+1)\cross|R|}^{N}0_{|R|\cross|R|}$$\lambda\in \mathbb{R}^{|W|}$$:=(\mathcal{K}^{1})^{|R|}\cross(\mathcal{K}^{|\mathcal{L}|+1})^{|R|},$$000|\begin{array}{l}RRR\end{array}|\cross(|\begin{array}{l}WWW\end{array}|+|\begin{array}{l}RRR\end{array}|(|\begin{array}{l}\mathcal{L}\mathcal{L}\mathcal{L}\end{array}|+1))]$$F(x, \lambda, s, v):=\{\begin{array}{l}g(x)+s-N^{T}\lambda s_{1}\delta_{1}D_{1}diag(M_{1})\Delta t(Mx)s_{2}\delta_{2}D_{2}diag(M_{2})\Delta t(Mx)|\delta_{|R|}D_{|R|}diag(M_{|R|})\triangle t(Mx)s_{|R|}\end{array}\}$$0_{m}$

3.2.2$0_{m\cross n}$(3.13).

Moreover, if is a constant function, i.e., $d(\lambda)=d$ for any
ten in the form of SOCCP (2.10) with

where
and
respectively.

$(r\in R)$ ,$\zeta$,,, then SOCCP (3.13) can be rewrit$:=(x, \lambda, s, v)\in \mathbb{R}^{|R|+|W|+|R|(|\mathcal{L}|+1)}$$h=\{\begin{array}{l}0_{|R|,d}0_{|R|(|\mathcal{L}|+1)}\end{array}\}$,,$G(x, \lambda, s, v):=\{\begin{array}{l}xlv^{1}1v^{2}|1v^{|R|}\end{array}\}$,are the m-dimensional zero vector and the $(m\cross n)$ -dimensional zero matrix,

Robust TAP with uncertain BPR function

Next we introduce a more concrete link cost function called the U. S. Bureau of Public Roads (BPR)
function [7]. The BPR function
is defined as follows:$t_{l}(y)$$t_{l}(y)=a_{l}(1+b_{l}( \frac{y_{l}}{c_{l}})^{\nu})$

where

are positive scalars. More precisely,

(314)

,

represents the free-flow travel time,
represents the traffic capacity of link , and is usually chosen as anumber between 4 and 5. The BPR function is one of the most popular link cost functions employed ina mathematical model for the traffic network. We suppose that for all routes $r\in R$ , the cost functions$f_{r}(x)$ are additive. Then by using the BPR function, we can express the route cost function as follows:$v,$$a_{l},$$b_{l},$$c_{l}$

represents the congestion factor,$b_{l}$$a_{l}$$l$$c_{l}$$f_{r}(x)= \sum_{l\in \mathcal{L}_{r}}a_{l}(1+b_{l}(\frac{M_{l}x}{c_{l}})^{\nu})$

,

$\nu$

(315)

where
denotes the l-th row vector of the link-route incidence matrix $M$ .
Now we consider the situation where the data in the BPR function (3.14) involve uncertainties.
Then we formulate such a robust TAP as an SOCCP. In the remainder of this section, we supposethat Assumption holds for the uncertainty set.
$M_{l}$$E$

9
Uncertainty in the traffic capacity We consider the situation that the traffic capacity
isuncertain. Specifically we suppose that is expressed aswith nominal and uncertainty$c_{l}$$c_{l}=\overline{c}_{l}+\hat{u}_{l}$$c_{l}$$\overline{c}_{l}$parameter.
Then, the link cost and route cost functions can be expressed as$\hat{u}_{l}\in \mathbb{R}$$t_{l}^{\hat{u}_{l}}(y)=a_{l}(1+b_{l}( \frac{M_{l}x}{\overline{c}_{l}+\hat{u}_{l}})^{\nu})$,$f_{r}^{\hat{u}^{r}}(x)= \sum_{l\in \mathcal{L}_{r}}a_{l}(1+b_{l}(\frac{M_{l}x}{c_{l}+\hat{u}_{l}})^{\nu})$

(316)

(317)

,

respectively. Here we assume thatso that the denominator will not be zero.
In order to obtain the SOCCP reformulation, we had to assume that the uncertain link costfunction is expressed as (3.5). However, functionin (3.16) cannot be written in the form (3.5) ina straightforward manner. We therefore introduce an “approximate link cost function” based on thefirst-order Taylor expansion as follows:$\hat{u}_{l}>-\overline{c}_{l}$$t_{l}^{\hat{u}_{l}}$$t_{l}^{\hat{u}_{l}}(y)$.

(3.18)$:=a_{l}(1+b_{l}( \frac{M_{l}x}{\overline{c}_{l}})^{\nu})-\frac{\iota \text{ノ}a_{l}b_{l}(M_{l}x)^{\nu}}{\overline{c}_{l}^{\nu+1}}\hat{u}_{l}$Also the approximate route cost function can be expressed as$f_{r}^{\hat{u}^{r}}(x)$$:= \sum_{l\in \mathcal{L}_{r}}a_{l}(1+b_{l}(\frac{M_{l}x}{c_{l}})^{\nu})-\sum_{l\in \mathcal{L}_{r}}\frac{\nu a_{l}b_{l}(M_{l}x)^{\nu}}{c_{l}^{\nu+1}}\hat{u}_{l}$Since the uncertainty parameterlet$\hat{u}_{l}$.

(3.19)

is very small in general, this approximation is reasonable. Now,$\triangle t_{l}(y)=-\frac{\nu a_{l}b_{l}(M_{l}x)^{\nu}}{c_{l}^{\nu+1}}$.

Then, (3.18) and (3.19) correspond to (3.5) and (3.7), respectively. Thus, we can reformulate therobust TAP as an SOCCP by using the results of Subsection 3.1.2.

Uncertainty in the free-flow travel time We consider the situation that the free-flow travel timeis uncertain. Specifically we suppose that is expressed aswith nominal value anduncertainty parameter. Then, the link and route cost functions can be expressed as$a_{l}$$a_{l}$$a_{l}=\overline{a}_{l}+\hat{u}_{l}$$\overline{a}_{l}$$\hat{u}_{l}\in \mathbb{R}$$t_{l}^{\hat{u}_{l}}(y)= \overline{a}_{l}(1+b_{l}(\frac{y_{l}}{c_{l}})^{v})+\hat{u}_{l}(1+b_{l}(\frac{y_{l}}{c_{l}})^{\nu})$(3.20),$f_{r}^{\hat{u}^{r}}(x)= \sum_{l\in \mathcal{L}_{r}}\overline{a}_{l}(1+b_{l}(\frac{M_{l}x}{c_{l}})^{\nu})+\sum_{l\in \mathcal{L}_{r}}\hat{u}_{l}(1+(\frac{M_{l^{X}}}{c_{l}})^{v})$,(3.21)

respectively. Let$\triangle t_{l}(y):=1+(\frac{M_{l^{X}}}{c_{l}})^{\nu}$Then (3.20) and (3.21) correspond to (3.5) and (3.7), respectively. Thus, we can reformulate therobust TAP as an SOCCP by using the results in Subsection 3.2.1.

10
4

Numerical experiments

In this section, we introduce two specific traffic models with uncertainty set of various sizes in thecost functions defined by (3.14) and (3.15). We try to compute robust Wardrop equilibria by using
the SOCCP reformulation approach studied in Section 3.2 and observe their properties. Throughout
this section, we let the uncertainty set $U_{r}(r\in R_{w})$ be given by$U_{r}:=\{\hat{u}^{r}\in \mathbb{R}^{|E|}|\Vert\hat{u}^{r}\Vert\leq\rho_{w}\}$

(4.1)

,

where
is a positive constant for each $w\in W$ . Notice that OD pair is identified for each $r\in R$ .
Also, we consider the case with $\nu=4$ in the cost functions defined by (3.14) and (3.15).
For solving the SOCCPs, we apply the Newton-type method that uses a smoothing technique [12].
All programs are coded in MATLAB $2010a$ and run on a machine with Intel\copyright Core i5 $430M2.27GHz$
CPU and 4. $00GB$ memories.
$\rho_{w}$Relationship between size of uncertainty sets and robust Wardrop equilibria
We consider the traffic model illustrated in Figure 1. Each node denotes an origin, a destination,
and an intersection, and each link denotes a road connecting the nodes. The set of OD pairs is given
by $W$ $:=\{w_{1}, w_{2}\}$ , where $w_{1}=(1arrow 5)$ and $w_{2}=(2arrow 6)$ . The demands forareandgiven by $d_{w_{1}}=d_{w2}=10$ . We suppose that the demands do not depend on . We give the routes$r\in R=R_{w_{1}}\cup R_{w2}$ , and the coefficients, andof the link functions (3.14) as shown in Table
1 and 2, respectively. Now we consider the case where onlyis uncertain with uncertainty set
expressed by (4.1). Therefore, we use (3.20) and (3.21) as the link cost function and the route costfunction with uncertainty, respectively. In this experiment, we varyfrom 0.001 to 5, and fix
at 0.001, and compute a robust Wardrop equilibrium for each
. Then, we observe the route flow
and the minimum costat the obtained equilibria of the robust TAPs.
Table 3 shows the obtained values ofandat the equilibrium for each
. Fromthe table, we can observe that, as
increases,
andget larger, but
gets smaller. On the, asother hand, as toincreases,
get smaller, but
andgets larger. We can interpretthese results as follows: Let us consider the drivers who belong to the OD pair $w_{1}\in W$ . In Figure 1,
has only one link 1, while
has three links 2, 3 and 4, that is, routeis more complicated than
. In such a situation, drivers may think that more complicated routes involve more uncertainty andrequire higher costs than simple routes, and therefore avoid using route . Thus the result of thisexperiment well reflect such driver estimation for uncertainty.
$w_{2}$$w_{1}$$\lambda$$a_{l},$$b_{l}$$c_{l}$$U_{r}$$a_{l}$$\rho_{w_{1}}$$\rho_{w_{2}}$$\rho_{w_{1}}$$\{x_{r}\}_{r\in R}$$\lambda_{w}$$\{x_{r}\}_{r\in R}$$\rho_{w_{1}}$$w_{2}$$r_{1}$$\rho_{w_{1}}$$\{\lambda_{w}\}_{w\in W}$$x_{r_{1}}$$x_{r_{4}}$$\rho_{w_{1}}$$\lambda_{w_{1}}$$\lambda_{w_{2}}$$r_{2}$$x_{r_{2}}$$x_{r_{3}}$$r_{2}$$r_{1}$$r_{2}$$s$

Figure 1: The network in section 4

References[1] Aashtiani, H. Z. and Magnanti, T. L.: Equilibria on a Congested Thransportation Network, SIAM
Joumal on Algebmic and Discrete Methods, Vol. 2 (1981), 213-226.

11

Table 1: Relation of OD pairs, routes and links in Figure 1

Table 2: Coefficients of link cost functions

Table 3: Uncertainty size, obtained route flow and minimum cost $(\rho_{w_{2}}=0.001)$$\overline{|\rho_{w_{1}}\Vert x_{r_{1}}|x_{r_{2}}|x_{r_{3}}|x_{r_{4}}\Vert\lambda_{w_{1}}|\lambda_{w_{2}}|}$

12[2] Agdeppa, R. P., Yamashita, N. and Fukushima, M.: The traffic equilibrium problem with nonadditive costs and its monotone mixed complementarity problem formulation, Transportation
Research , Vol. 41 (2007), 862-874.
$B$[3] Averbakh, I. and Zhao, Y. B.: Explicit reformulations for robust optimization problems withgeneral uncertainty sets, SIAM Joumal on optimization, Vol. lS (2007), 1436-1466.

[4] Beckmann, M., McGuire, C. and Winsten, C.: Studies in the Economics of Tmnsportation, Yale
University Press, 1956.
[5] Ben-Tal, A., Ghaoui, L. E. and Nemirovski, A.: Robust optimization, Princeton Univ Press, 2009.

[6] Ben-Tal, A. and Nemirovski, A.: Robust convex optimization, Mathematics of Opemtions Research, Vol. 23 (1998), 769-805.

[7] Bureau of Public Roads, : Traffic Assignment Manual, U.S. Department of Commerce, Urban
Planning Division, Washington, DC, 1964.
[S] Chen, J. S., Chen, X. and Tseng, P.: Analysis of nonsmooth vector-valued functions associatedwith second-order cones, Mathematical Progmmming, Vol. 101 (2004), 95-117.
[9] Facchinei, F. and Pang, J.-S.: Finite-Dimensional Variational Inequalities and Complementarity
Problems, I and II, Springer, 2003.

[10] Fukushima, M., Luo, Z. Q. and Tseng, P.: Smoothing functions for second-order-cone complementarity problems, SIAM Journal on optimization, Vol. 12 (2002), 436-460.
[11] Gabriel, S. A. and Bernstein, D.: The traffic equilibrium problem with nonadditive path costs,
Tmnsportation Science, Vol. 31 (1997), 337-348.
[12] Hayashi, S., Yamashita, N. and Fukushima, M.: A combined smoothing and regularization method
for monotone second-order cone complementarity problems, SIAM Joumal on optimization,
Vol. 15 (2005), 593-615.
[13] Nishimura, R., Hayashi, S. and Fukushima, M.: SDP reformulation for robust optimization problems based on nonconvex QP duality, Technical report 2009-014, Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University, 2009.
[14], F. and Stier-Moses, N. E.: Robust wardrop equilibrium, Network Control and Optimization, Vol. 4465 (2007), 247-256.

$Ord6\tilde{n}ez$, F. and Stier-Moses, N. E.: Wardrop Equilibria with Risk-Averse Users, Transportation[15] Ord
Science, Vol. 44 (2010), 63-86.
$6\tilde{n}ez$[16] Pan, S. and Chen, J. S.: A damped Gauss-Newton method for the second-order cone complementarity problem, Applied Mathematics and optimization, Vol. 59 (2009), 293-318.
[17] Patriksson, M.: Traffic Assignment Pmblems: Models and Methods, V.S.P. Intl Science, 1994.
[18] Sheffi, Y.: Urban Transportation Networks: Equilibnum Analysis with Mathematical Progmmming Methods, Prentice Hall, 1985.
[19] Takahashi, H.: Robust Wardrop equilibria for traffic model with uncertainty, Bachelor Thesis (inJapanese), Applied Mathematics and Physics Course in the School of Informatics and Mathematical Science, Faculty of Engineering, Kyoto University, 2010.
[20] Wardrop, J. G.: Some theoretical aspects of road traffic research, Proceedings of Institute of Civil
Engineers Part II, Vol. 1 (1952), 325-378.
[21] Zhang, C., Chen, X. and Sumalee, A.: Robust Wardrop‘s user equilibrium assignment understochastic demand and supply: Expected residual minimization approach, Transportation Research , Vol. doi: 10. $1016/j$ .trb.2010.09.008.
$B$