狠狠撸

A car sharing auction
with temporal-spatial OD connection
conditions
Yusuke Hara (The University of Tokyo)
Eiji Hato (The University of Tokyo)
22nd International Symposium on Transportation and Traffic Theory
@ Northwestern University

A core problem of
Transportation and Traffic Theory
1. Bottleneck model (Vickrey, 1969)
– travel behavior: departure time choice
– policy: congestion charging
2. Traffic Assignment
– UE (Beckmann,1956), SUE (Daganzo and Sheffi, 1977),
Hyperpath (Spiess and Florian, 1989; Bell, 2009)
– travel behavior: route choice
– policy: pricing of links for system optimum (Henderson, 1985)
3. Tradable permit scheme
– Akamatsu (2007), Yang and Wang (2011), Wu et al. (2012),
Nie and Yin (2013), Wada and Akamatsu (2013)
– travel behavior: route choice and departure time choice
– policy: market mechanism for optimal allocation
2
The Negative Externality of people’s trips is
an important problem for transportation system.

What is the cause of the negative externality?
3
1. Capacity of transportation system
2. Users use the same transport facility simultaneously
Road network Mobility service
t = 1
t = 2
t = 3
t = 1
t = 2
t = 3
Link capacity of each road link is fixed. Service capacity of each OD and
time slot depends on vehicle paths.
μ
Link capacity
(aggregate capacity)
Vehicle capacity
(disaggregate capacity)

What is the cause of the negative externality?
4
1. Capacity of transportation system
2. Users use the same transport facility simultaneously
3. Flexible OD of mobility services generates negative/positive
externalities.
t = 1
t = 2
t = 3
t = 1
t = 2
negative externality
positive externality
“Sharing a vehicle by more than one person” is not essential.
“Connecting trips temporally and spatially” is essential.
The important point of mobility sharing

Our Concept
5
bottleneck network
service
with “knots”
link capacity
single OD
aggregate capacity
multi aggregate OD
disaggregate capacity
multi disaggregate OD
temporal-spatial
connection condition
Designing mobility sharing auction mechanism considering
temporal-spatial OD connection condition.
Research Objective
= “knot”

Our approach
6
Fundamental Theory for mobility services with “knots”
Service Implementation in real world
and Travel Behavior Analysis for tradable permit
Transportation ECO
Point System
Probe Person System
Bicycle Tradable
Permits System
Bicycle Sharing
System
GPS data
travel diary data
give point
use by point
settlement
booking
use by permit
trade by point
settlement
stock management
Today’s presentation
Hara and Hato (Transportation, 2017)

Setting1: the Assumption of Transportation Services
7
We don’t consider the delay effect.
1
2 3
4
時間
空間ネットワーク
利用時間枠
t = 1
利用時間枠
t = 2
利用時間枠
t = 3
利用時間枠
t = 4
t = 1 t = 2 t = 3 t = T
: port node
: OD pair pq
Ii?
Tt ? Lpq ?
: user i
: time slot t
Nqp ?,
We assume the following statements.
1. Mobility sharing means car sharing in this study.
2. A trip can be done in a time slot.
3. There is no delay.
4. The number of vehicle is μ and each vehicle can move independently.
temporal-spatial network time slot
time slot
time slot
time slot
time slot
time

Setting 2: Supplier, Users and the Capacity limit
8
We assume that service supplier is the player to maximize social welfare by
operating vehicle effectively. The supplier tackles an unbalanced demand problem
between ports by allocating users to permits satisfying temporal-spatial OD
connected condition at all time slot.
the setting of service supplier
vehicle capacity limit μ
Vehicle capacity limit means the number of vehicles service supplier has.
Service supplier can issue permits depending on the vehicle capacity limit.
{ }1,0)( ?txi
pq is a discrete variable. If user i is allocated to a permit
to use vehicle between OD pq at time slot t, this variable is 1.
Otherwise this variable is 0.
Users have the value of permits and the value of each permit is different by time
slot and OD pair. Users determine the value by their OD demand, their desired
usage timeslot, their value of time and so on.
the setting of users and users’ value of permit

Setting 3: Temporal-Spatial OD connection Condition
9
時間
空間ネットワーク
利用時間枠
t
)1( -txi
pq
利用時間枠
t ?1
)(txi
qp
?? -
i p
i
pq tx )1(
??i p
i
qp tx )(
q
q
Meeting temporal-spatial OD connection condition is
satisfying the following equation for any node q.
time
time slot
time slot

Example of the Setting
User
ID
OD
value
(t = 1)
value
(t = 2)
value
(t = 3)
A 1→2 90 80 70
B 1→2 60 70 80
C 2→1 70 80 70
D 2→3 70 60 50
E 3→1 50 60 70
10
Users’ demand and value of permit
Example network
port 1
port 2
port 3
A trip-connected path allocation {A, D, E}
A trip-connected path allocation {A, C, B}
Sum of values
(Social Welfare)
is 220.
t=1
t=2
t=3
t=1
t=2
t=3
A
D
E
A
C
B
Sum of values
(Social Welfare)
is 250.

Permits Allocation of Social Optimum
? optimization problem to maximize the sum of users’ values[SO]
11
single demand condition
capacity limit
temporal-spatial OD connection
each user’s permits allocation
If users bid their true values, service supplier only has to solve this
optimization problem [SO] and social optimum is achieved.
However, if users bid their false values strategically, it is difficult to
maximize social welfare. Therefore, we need a mechanism to
make users bid true values.

VCG Mechanism for Mobility Sharing
12
Vickrey–Clarke–Groves Mechanism satisfy efficiency and strategy-proofness.
We extend VCG mechanism for mobility sharing permits.
1. All users bid on the permits, which becomes the users’ demand.
2. Auctioneers decide the allocation of permits in order to maximize the sum
of bidding values under temporal-spatial OD connection conditions and
capacity limit conditions
3. Winners must pay for the permits and the price is the winner’s externality,
which is the decrease in optimal social welfare when she is included in the
auction. The price is called “Vickrey payments”.
VCG mechanism for mobility sharing permit
Under this mechanism, users have an incentive to bid their true values
because they cannot get the larger utilities by telling a lie than the
utilities by telling truth.
Therefore, supplier can solve the optimization problem and the social
optimum is achieved.

The example of Vickrey payments
13
A
C
B
Social Welfare = 250
Social Welfare except A = 160
User
ID
OD
value
(t = 1)
value
(t = 2)
value
(t = 3)
A 1→2 90 80 70
B 1→2 60 70 80
C 2→1 70 80 70
D 2→3 70 60 50
E 3→1 50 60 70
90
80
80
D
E
B
Social Welfare without A = 210
70
60
80
Maximum Social Welfare Allocation Maximum Social Welfare
Allocation without A
?"
? = ? 0, ?("
? ?("
(?)
The payment of user i
Maximum Social Welfare
without i in the bidders set
Maximum
Social Welfare
except i’s value
?,
? = 210 – 160 = 50
The Vickrey payment is
the negative externality of
user A’s usage.

The Solution Method of Single-Minded Bid Case
? The winner determination problem [SO] is included in
combinatorial optimization problems. And these
problems are NP-hard in general.
? First, we assume that users bid for only 1 timeslot permit.
? Users will bid for the most variable timeslot permit for
them.
? This assumption is single-minded bids in combinatorial
auction.
? Computational effort is small.
? In this case, we can interpret the price by the dual
problem.
14

Linear relaxation is identical to LP
15
? In single-minded bidder setting, the social optimization problem is
redefined by the following equations:
subject to
Since the constraint coefficient matrix is totally unimodular, the solution
of the linear relaxation problem [SO-SMB] is identical to that of the LP
problem [SO-SMB-LP] (see Hoffman and Kruskan (1956))
linear relaxation
Solving LP problem is
much easier than IP problem !

Vickrey payments decomposition
? From the dual problem of [SO-SMB],
16
usage fee to leave p at t income to arrive at q at t+1
1) Vickrey payments are decomposed into the payment for the previous user and
the income from the following user
2) Vickrey payments between the same OD pairs and time slots are the same price
3) Users leave their origin as consumers and arrive at their destination as suppliers.
4) What they consume (or supply) is the opportunity to use mobility sharing.
?-.(?) = ?- ? ? ?. ? + 1 ??
t
t+1
usage fee
income

Negative price
? In this mechanism, there is negative price.
? This mechanism generates the negative
price and efficient allocation naturally.
札者
間帯
負条
901
U:
算機
にそ
す．
ポート1 ポート2
図–8 OD 需要が偏った場合
表–4 OD 需要が偏った場合の入札者集合
入札者 OD v(t = 1) v(t = 2) v(t = 3)
1 1 → 2 95 90 85
2 1 → 2 82 92 72
3 1 → 2 74 86 61
4 1 → 2 60 80 92
5 2 → 1 30 20 10
個人の支払額は
P1
= (82 + 20 + 92) ? (20 + 92) = 82
P5
= (95) ? (95 + 92) = ?92
P4
= (95 + 20 + 72) ? (95 + 20) = 72
となる．これは第 1 項がその個人が入札しなかった場合
の評価値を最大とする割当て時の評価値の総和を表し
ており，入札者 ID = 5 がいない場合は ID = 1 がポー．
ポート1 ポート2
入札者 OD v(t = 1) v(t = 2) v(t = 3)
1 1 → 2 95 90 85
2 1 → 2 82 92 72
3 1 → 2 74 86 61
4 1 → 2 60 80 92
5 2 → 1 30 20 10
P1
= (82 + 20 + 92) ? (20 + 92) = 82
P5
= (95) ? (95 + 92) = ?92
P4
= (95 + 20 + 72) ? (95 + 20) = 72
ており，入札者 ID = 5 がいない場合は ID = 1 がポー
2000 5000 10000
20 50 100
20
10
20
10
20
10
図–7 大規模計算時間の比較
，ポート数 50，時間帯枠数 t = 10，(3) 入札者
人，車両台数 ? = 20，ポート数 100，時間帯
の計算時間を示す．また，それぞれ非負条
約条件式の数は (1)2181，(2)5451，(3)10901
算には OS: Windowa 7 Professional, CPU:
i7-2620M (2.7GHz), メモリ 8GB の計算機
に発生させた評価値?OD 分布をもとにそ
ースで 10 回実施した平均値を図–7 に示す．
均 (1)0.18 [sec], (2)0.63 [sec], (3)1.81 [sec]
題ない実行時間である．勝者決定問題を解
用権価格としての Vickrey payments を計算
あるが，これも各勝者を入札者集合から抜
入札者 OD v(t = 1) v(t = 2) v(t = 3)
1 1 → 2 95 90 85
2 1 → 2 82 92 72
3 1 → 2 74 86 61
4 1 → 2 60 80 92
5 2 → 1 30 20 10
P1
= (82 + 20 + 92) ? (20 + 92) = 82
P5
= (95) ? (95 + 92) = ?92
P4
= (95 + 20 + 72) ? (95 + 20) = 72
ており，入札者 ID = 5 がいない場合は ID = 1 がポー
ト 1 からポート 2 へ移動した後，車両がポート 1 へ戻
ることができないため，t = 2, 3 の時間帯に利用され
ないことを表している．しかし，入札者 ID = 5 が存在
することで車両がポート 1 へ戻り，入札者 ID = 4 が利
The payment of each userusers
Port 1 Port 2
17

The extension for activity chain
? If some users want round trips, our model
framework can be extended easily.
18
14 Hara and Hato / Transportation Research Procedia 00 (2016) 000–000
user assumes that only single trip is worthless and that it is variable to be assigned both ?rst trip and
Hence, only the bundle of ?rst trip and second trip is variable. In this setting, each user i need to report
vi
and the duration ki ∈ N from ?rst trip and second trip.
Under the auction setting, socially optimal allocation maximizes the sum of the assigned user’s valu
derived by the following optimization equation [SO-round]:
max
x
i∈I t∈T pq∈L
vi
pq(t) · xi
pq(t),
subject to
i∈I pq∈L
xi
pq(1) +
q∈N
xS
qq(1) = ?,
?
i∈I p∈N
xi
pq(t ? 1) ? xS
qq(t ? 1) +
i∈I p∈N
xi
qp(t) + xS
qq(t) = 0 t = 2, . . . , T, ?q ∈ N,
t∈T pq∈L
xi
pq(t) ≤ 2, ?i ∈ I
xi
pq(t) ? xi
qp(t + ki) = 0 ?i ∈ I, ?p, q ∈ N, ?t ∈ {1, 2, . . . T ? ki}
xi
pq(t) ∈ {0, 1}, ?i ∈ I, ?pq ∈ L, ?t ∈ T
xS
qq(t) ∈ N. ?q ∈ N, ?t ∈ T
Eqs.(37, 38, 39, 42, and 43) are equivalent to a scenario with only a one-way trip situation. The di?er
i i

The extension for activity chain
? If some users want round trips, our model
framework can be extended easily.
19
t∈T pq∈L
xi
pq(t) ? xi
qp(t + ki) = 0 ?i ∈ I, ?p, q ∈ N, ?t ∈ {1, 2, . . . T ? ki} (41)
xi
pq(t) ∈ {0, 1}, ?i ∈ I, ?pq ∈ L, ?t ∈ T (42)
xS
qq(t) ∈ N. ?q ∈ N, ?t ∈ T (43)
Eqs.(37, 38, 39, 42, and 43) are equivalent to a scenario with only a one-way trip situation. The di?erence is with
respect to the constraint conditions Eqs.(40 and 41). These equations either satisfy both xi
pq(t) = 1 and xi
qp(t + ki) = 1,
or both xi
pq(t) = 0 and xi
qp(t + ki) = 0. The optimization problem [SO-round] is more complex than [SO], but it is only
added to the linear constraint conditions. Therefore, the solution method is same as the original problem.
1
2 3
time slot
t = 3
time slot
t = 2
time slot
t = 1
Time
16
time slot
t = 4
time slot
t = 5
1
2 3
Time
21
20
20
16
18
17
13
Fig. 5. Winners and vehicles’ paths in the round trip case.
To demonstrate the round trip case, we show the users’ bidding value example in Table 3. Thirteen users desire

The solution method in multiple bidding case
? In the case of multiple bidding case,
the LP relaxation is not guaranteed.
? We propose the new solution method by
combining the primal-dual algorithm and
a branch and bound algorithm.
? Finally, we compare the exact solution
(multiple bidding), approximate solution
(single-minded bidding), and First come, first
serve rule.
20

10 20 30 40 50
The number of time slots
Fig. 6. Computational Times of numerical examples.
400 500 600 700 800400 500 600 700 800
0.0000.0010.0020.0030.0040.005
Multiple bidding auction
Single-minded bidding auction
First come, first served
(max value choice)
(logit choice)
(random choice)
Probabilitydensity
Social Welfare
Fig. 7. E?ciency of mobility sharing auction and ?rst come, ?rst serve rule.
Efficiency of mobility sharing auction
and first come, first serve rule
21
Exact
solution
(837)
Approximate
solution
(LP relaxation)
(833)

Conclusions and Future work
? The essence of mobility sharing is the service with
“knots” of trips/paths.
? For satisfying temporal-spatial OD connection
condition, we proposed the mobility sharing auction.
? From the LP relaxation, Vickrey payment is
decomposed into usage fee and income.
? It means mobility sharing is the transaction on “knots”
to exchange the opportunity of vehicles usage.
? For future work, we need to study
– Dynamic mechanism (online auction setting)
– Preference elicitation mechanism for more easier bidding
system because bidding all items is high cognitive cost
for users
– Comparison with other reservation systems and other
mobility services (for example, ride sharing)
22
Thank you for your attention!

狠狠撸

A car sharing auction with temporal-spatial OD connection conditions

Recommended

More Related Content

Similar to A car sharing auction with temporal-spatial OD connection conditions (20)

Recently uploaded (20)

A car sharing auction with temporal-spatial OD connection conditions