A note on the New Optimization Model for Traffic Problem (The state-of-the-art optimization technique and future development)

A note

on

the New

optimization

Model for Traffic Problem

Yan Gu*

Xingju

Caia DerenHana David Z.W

Wangb

*

System

optimization Laboratory,

Department

of

_Applied

Mathematics and

_Physics

Graduate School of

_{Informatics, Kyoto}

_University

aSchoo1 of Mathematical

Sciences,

Jiangsu Key Labratory

for

NSLSCS,

Nanjing

Normal

_{University, Nanjing,}

China.

bCorresponAng

author,

School of Civil and Environmental

_Engineering,

Nanyang

Technological

University,

Singapore, Singapore.

1

Introduction

The purpose of thisnoteis twofold:

₍₁₎

to

_give

the

_background

_{in the paper}

_by

Guet al.

₍₂₀₁₆₎

onthe

tri‐level

_optimization

model for

_private

road

_{competition problem}

with traffic

_equilibrium

constraints, and

(2)

to_{summarize the main idea and model in that paper.}

In recent_{years, due}tothe funds

limitation,

there has beena

growing

trend for_governmentstoallow

private participation

in some

_major

public

investments,

especially

for infrastructure

projects,

suchas ex‐

pressways and

highway,

under a_{procurement system} called

build‐operate‐transfer

(BOT) (Roth, 1996).

Underthisscheme, the

_project

_{sponsor is}

_responsible

for

_financing,

construction and

_{operating roads,}

and inretum, should receive therevenuefrom road toll

charge

forsome_{years. After}

that,

the roads will be

transferredtothe_government. The

_major

motivationfor the BOT scheme is that the_governmentdoesnot needto

_spend

_any

_{public funding}

while the

_public

infrastructurecanstill be constructed.

Meanwhile,the

_private

firmscan

_enjoy

a

high potential profit

fromasuccessful BOC

project.

Thereare

many research works in the literature

discussing

the

_problem

of

_{public‐private‐partnership}

in

_{transportation}

infrastructure construction. Givenan

_existing

_transportnetworksystem,toalleviate the traffic

_congestion,

the_governmentdecidesto

_develop

certain number ofnewroads. However,the _governmenthas limited fund andcannotaffordtoinvest in

_building

upall of theseroads, sothe

private

firmsare

_encouraged

to

participate

the

_development

of thesenewroads.

Yang

etal.

₍₂₀₀₉₎

consideredatoll road

competition

under atraffic network of BAT. Therearetwoor moredifferent

_{participating private}

firms and the firmscanmake

theirown

_optimal

decisionsonboth the investment

_(capacity)

and toll

_charges.

The

_{equilibrium problem}

is solved basedonthe

_assumption

that the

_private

firmsdetermine their

operation

strategies

on

multiple

toll

roads inaroad networktomaximize their

_profit.

However,if all thenewroadsarebuilt and

operated by

private

firms under the BOTscheme,aswasassumed in

_Yang

etal.

(2009),

the

_primary

_objectives

of all the

private

firmsaretomaximize their

_profits,

which isdeviated from the

_original

targetof traffic

_congestion

Noting

that

_{only private participation}

in the road

_competition

_problem

may leadtoaless efficient_system

and result inatraffic network

performance

that is deviated fromthe desired social welfare maximization case,it is

imperative

for thegovernmenttounderstand what role the_governmentshould

_play

in the situation of co1nmercialization and

_{private supply}

of road and how the_governmentshould determine the

_optimal

participation

strategy

ensuring

the proper usage of

private

road. In

_Yang

etal.

_(2009),

the_government

_played

aless

_important

role in the_system: not

_being

ableto

_participate

thenewroadconstruction and

_operation,

the govemmentcan

_only

use

_regulations

to_{manage thesystem,}which would be much less efficient in

_achieving

the

_goal

of

_maximizing

social welfare of thesystem.

Ifgovernmentcontrolssometolled

roads,

it is

_possible

toinfluence the

_{operation strategies}

of

_private

roadstoavoid the reduced social

welfare,

andatthesametime_guaranteethe

private enterprises

can

gain

the

_{profit. OUviously,}

theanswertothese

_questions

and issues remainunclear and will be addressed in this

study.

Inthe paper

(Gu

and

_{Cai, 2016),}

we

study

the

problem

that how the_governmentshould takepartin the road

_competition

while

_taking

into consideration ofthe

_private

firns’

_{responsive strategies}

and the travelers’

equilibrium

travel_pattern.It is assumed that the_government

_plans

toconstructcertain number ofnewroads

to

_improve

thetransportnetwork

_performance.

Whilemostof thenew_{roads would be built up}

_by

the

_private

firms under BOTscheme,the_governmentitselfwould also

participate

in the road constructionand

_operation

oncertainnewroads.

_By

doing

so,it will bemoreefficient for the_governmenttoachieve the

_goal

of best

managing

the network trafficand

_maximizing

the socialwelfare,as

_compared

tothecaseof

letting

all the newroads constructed and

operated by only profit‐maximizing private

firms under BOT scheme. Because of

the_targetis that

_basing

on

getting

the social welfaretomake the firms_competetoeach other

_by

themselves. The_governmentdoesn’t_competewith the

_private

firms. It

_plays

asthe

guide

andwants toleadtomore

invest from the firms for the roads while doesn’t let themto_{bid up}

_price.

_Therefor,theone‐shot game and

Stackelberg

game isnot exactsuitable forourmodel.

We

_proposed

atri‐levelmathematical

programming

model formulate this

problem

and proposeaheuris‐

tic

_algorithm

tosolvethis model. The upper level program determines the

optimal

toll tomaximize the social welfare.

Themiddle level describes the

_private

firms’

_optimal

_strategies

ontheir investment

(road capacities)

and

toll

_charge

that maximizes their

_profits

_{in response}tothe

_{government’s}

road toll decision.

In the lower

level,

theuser

equilibrium

traffic

assignment

is

conducted, assuming

all the roadusersmake routechoices

_following

thedeterministicuser

_{equilibrium principle (Wardrop,}

_1952).

Andweformulate it

as afinite‐dimensional variational

_inequality

and solve it

_by

_{projection‐type}

method with BB_stepsize

(He

2

Traffic Network

_Description

Weconsideradirected

transportation

network

G=(N, A)

,

consisting

ofasetN of nodes andasetA of

links whose elementsareordered

_pairs

of distinct nodes.

The

_following

are_{the notations used in this paper:}

v_{a}: the flowonlinka\in A,andv=

(v_{a} : a\in A)^{T}

be thevectorsoflinkflows,

t_{a}: anassociated

flow‐dependent

cost toa,is assumedtobe differentiable and

monotonically increasing

with theamountofflow_{v_{a}},and

t(v)=(t_{a}(v_{a}) : a\in A)^{T}

be thevectorof link travel cost,

W: theset

_{ofOrigin‐Destination}

_(OD)

_pairs,

R_{u}

: thesetof all

_{paths connecting}

OD

_pair

w\in W,and

R=\displaystyle \bigcup_{w\in W}R_{w},

d_{w}

: the traffic demand

_traveling

betweenOD

_pair

w\in W,and d=

(d_{w} : w\in W)^{T}

be thevectorsof OD

demands,

f_{rw}

: the flowon

_{path r\in R_{w}}

of OD

_pair

w\in W,and

f=

(f_{rw} : r\in R_{w}, w\in W)^{T}

be thevectorsof all

path

flows,

c_{rw} : the travelcost

_along

a

path

r\in R_{w}

of OD

pair

w\in W,is thesumof travelcostsonall links that

compnse the

path, i.e,

_{c_{rw}=\displaystyle \sum_{a\in r}t_{a}(v_{a})}

,and

c=(c_{rw} : r\in R_{w}, w\in W)^{T}

be the columnvectors

of

_path

_{travel cost,}

$\mu$_{w}: theminimum

path

costof OD

_pair

w\in W,definedas

$\mu$_{w}=\displaystyle \min\{c_{rw} : r\in R_{w}\}

,and

$\mu$=($\mu$_{w}

:

w\in W)^{T},

$\Delta$:

\triangle=[$\Delta$_{ar}]

be the

link‐path

incidencematrix,where

$\Delta$_{ar}

equals

1 if

path

rincludes linka and 0

otherwise,

$\Lambda$: $\Lambda$=[$\Lambda$_{wr}]

be the

_OD‐path

incidence

matrix,

where

_{$\Lambda$_{wr}}

_equals

1 if

_path

rconnectsOD

_pair

wand 0

3

Model

Formulation

The Whole Model: The

_problem

under considerationcanbe formulatedas:

(Upper level)

\displaystyle \max

W( $\tau$)=(\displaystyle \sum_{w\in W}\int_{0}^{d_{w}}B_{w}( $\omega$)\mathrm{d} $\omega$-\sum_{a\in A}v_{a}t(v_{a})-\sum_{a\in J,a\in K}\frac{1}{ $\beta$} $\eta$ I_{a})- $\rho$\sum_{i\in K}\frac{1}{ $\beta$}$\tau$_{i}v\int 1

)

s.t.

_{$\tau$_{i}v_{i}\geq $\eta$ I_{i},}

_{i\in K,}

_\langle

2

₎

(Middle level)

(u_{\dot{}}, y_{j})\in S_{l_{2}}^{j},

j\in J

,

(3)

(Lower

level)

(v, d)\in S_{l_{1}}

.

(4)

Notethat A is thesetof all links in the network and

K\subseteq A, J\subseteq A.

4

Heuristic

_Algorithm

Similartothe method in

_solving

the EPEC

_problem,

herewe_proposeaheuristic method for the

_computation

of the tri‐level

_{optimization problem,}

a

_synchronous

iterative method.

Theuser

_{equilibrium problem}

canbe formulatedas afinite‐dimensional Variational

Inequality

(VI)

(Facchinei, 2003).

We describe the reformulated VI

_formally

and then

_adopt

the

_{recently developed projection‐}

typemethod with BB_stepsizetosolve it

(He

etal.

2012).

From

_practical

_point

of

view,

the governmentshould

_adjust

the level of its tolls as less as

_possible.

Therefore we cancontrol the upper iteration number forsomesuitable

figure.

Whileonthe other

hand,

private companies

canmake

appropriate adjustments according

tothe information of the

govemment’s

toll level and the users’

choice,

and choose theirown

optimal strategies.

Wehaveto

_point

outthatthe

_study

of this tri‐level

_optimization

is still in its

_infancy,

andthe

_computation

ofa

global

solution is

difficult,

ifnot

_impossible;

thiscanbe observed from the

special

caseof

solving

Mathematical

_Programs

with

_Equilibrium

Constraints

_(MPEC),

i.e.,the_govemmentdoesnotinvolve in the system.The issue of convergence of the heuristic methods will be addressed in the future

study.

5

Conclusions

Inthis paper,westudied the situation in which the_govemment,

_devoting

tomaximize the social

welfare,

and the

_private

_company,

_urging

for maximum

_profit,

exist in thesameroad network and_operatedifferent tolled roads

_{simultaneously. Envisaging}

that the

_{participation}

of_govemmentinnewroad construction

alongside

goal

of

_maximizing

social

_welfare,

we

_analyzed

the interaction

_relationship

of

_pricing,

road

_capacity

and

competition

and how the road

_capacity

and

_price

aresettled

_{by using}

game theoretical model.

We

_develop

atri‐level modeltodescribe the

_problem.

Aheuristic solution

_algorithm

is

_proposed

to solve the model. The mode results indicate that the model is

_meaningful

asthe fundamental role for the

govemmentistomakeincrease in social welfare.

References

[1] Facchinei,

F.and

_{Pang, J.S.,}

2003. Finite‐Dimensional Variational

_Inequalities

and

_{Complementarity}

Problems.

_{Springer‐Verlag.}

[2] Guo,

X. L. and

_Yang,

H., 2009.

_Analysis

ofabuild_operatetransfer scheme for road

franchising.

Intemational Journal of Sustainable

_{Transportation}

3,312‐338.

[3] He, H.,

Han,D. and

_{Li, Z.,}

2012. Some

_projection

methods with the BB _stepsizes for variational

inequalities.

Journal of

_{Computational}

and

_Applied

Mathematics236,2590‐2604.

[4]

Roth, G.,1996. Roads ina_{market economy.}

_Avebury

_Technical,

_Ashgate

_PuUlishing,

_UK,

_England.

[5] Wardrop,

J.G., 1952. Some theoreticalaspectsof road traffic research.

_Proceedings

of the Institute of Civil

_Engineers,

Pt. II1,325‐378.

[6] Yang,

H., Xiao,F.and

_Huang,

H.,2009. Private road

_competition

and

_equilibrium

with traffic

_equilib‐

rium constraints. Joumal of Advanced

_{Transportation}

36,

169‐185.

System optimization Laboratory

Department

of

_Applied

Mathematics and

_Physics

Graduate School ofInformatics

Kyoto

University

Kyoto

606‐8501 JAPAN