Smart transit systems for evensmarter travellers
Jan-Dirk Schmöcker
schmoecker@trans.kuciv.kyoto-u.ac.jp

Overview• Part 1: Single line, bus bunching• Part 2a: Transit Route choice as game• Part 2b: Notes on extension to all choices fromO to D
• Conclusions/ current work
2

Bus bunching766

Bus stop (distance)

Bus stop (distance)

7

5

54

43

3

2

2

1

1000

10203040

TimeWithout delay

5060

0102030405060Time
Initial delay for 2nd bus at stop 03

Bus bunching4Likely passenger stop arrival patterns
with RTI

5

Influence of boarding rate on bunching

If the boarding rate is low, the service can be severely
disrupted even without exogenous delays
6Influence of boarding rate on bunching7

Conclusion:• RTI “disturbs” passenger arrival patterns• This means the system can be much easierperturbed - Even without exogenous delay• Holding strategies become even more
important8

p.s. on control strategies• All holding strategies introduce delays• One control strategy is “the unfriendly busdriver”: Go to the back bus, I am leaving.

9Part 2: Route choice in transit
networks
Finchley Rd.

82

Bus hyperpath for thesame OD
Marble ArchkerBa

Royal Albert
HalleeGrGreenBaker St.

10ParkSt.

Tube hyperpath from
Finchley Road
to Imperial CollegeLondon

Finchley Sta.

nrk
Pa

sin
gt
on

Imperial
CollegeSo
ut
hKen

South Kensington

Victoria & AlbertMuseum Choosing a hyperpath consists of two steps■ Defining a set of paths■ Defining the selection criteria of a specific path74

13 113Oxford St.

414

Spiess and Florian “Optimal strategies”• Spiess and Florian (1989) proposed that passengers
board the first line among a set of attractive lines at aboarding node i.
• Finding the optimal path set can be presented as alinear program where the objective is to find thestrategy that minimises the expected waiting time.
pa ( Ai ) fa

faAi

w( Ai ) afaAia11Games and route choice• “Hyperpaths” have also been applied in other contexts• Risk-averse assignment leads to the creation of a set ofpaths in order to minimise the maximum travel cost
• Route choice as a game against single or multiple“demons” have been introduced to find worst casescenarios.
– Bell (2000): Router vs. demon to find critical links– Cassir and Bell (2000) : Extension to multiple travellers– Cassir et al (2003): Tree spoiler to investigate reliability of
specific Ods– Szeto et al (2007): Extension to multiple (independent)
demons12

Proposition: S&F = game• The risk-averse traveller, who fears a maximum delay ofda = 1/fa on any link should use the S &F path split
probabilities, independent of the travel time on any
downstream link ca, and include all links that are notdominated by any other link.
• Note the difference in interpretation:– S&F– Here::

1/fa is the expected waiting time
1/fa is the maximum link delay

13

Proof (1)• The risk averse traveller fears that a line might bedelayed by up to da, this can be described as agame with following pay-off matrix:
q1

q2

…

qk

…

qn

p1

u1 + d1

u1

…

u1

…

u1

p2

u2

u2 + d2

…

u2

…

u2

...

…

…

…

…

…

…

pk

ukuk…

uk + dk

…

uk

...

…

…

…

…

…

…

pn

unun…

un

…

un + dn• ..leading to following optimisation problem:
Minp Maxq

aAi

ua pa  qa pa da14

Proof (2)• The travellers is hence to choose a (mixed) strategy pthat minimises his feared cost of travel λi.
Min λi so thatp1(u1 + d1)
p1u1
…
p1u1

+ p2u2+ p2(u2+d2)+…
+ p2u2

+…
+…
+…
+…

+ pkuk+ pkuk+…
+ pk(uk+dk)

= g1
= g2
= …
= gk

 λi
 λi
 λi λip1 + p2 + …. + pk = 1
pi > 0 i = 1,…, k• Following the expected value principle at the saddle
point the costs of all used strategies will be equal.
15

Proof of proposition 1 (3)• …hence solving the set of equations wlog for p1
leads topa = p1 (d1/da) a=2,…,kand

p1 + p1 (d1/d2) + p1 (d1/d3) + …+ p1 (d1/dk) = 1• Solving for p1 leads to:
qedp1 1d11
 a 1,.., k da16

Further properties of this zero-sumgame• With pa determined it follows for theexpected game value:f1 ffg   u1   1  u2 2  ...  sn n f1   f i
 fi
 fi
iii

1   f i uii

fii• which is also equivalent to the S&F solution.
• In the same way as for the path split
probabilities the attack probabilities qa canbe found for the Nash equilibrium solution.
17

Equivalence of S&F linear programwith “Multiple local demon game”• Spiess and Florian showed that following LP determines
the optimal hyperpath (with assumptions as before)

Minp ,w  aA ca pa   iI wi
Subject toaAi

pa   aA pa  giipa d a  wi

pa  0• The corresponding Lagrangian function for this LP is:L(p, w, λ, q)= aA ca pa   iI wi   iI  aA qa (wi  pa d a ) i  (g  iIiiaAi

pa   aA pa )i18Equivalence of S&F linear programwith “Multiple local demon game” (2)L(p, w, λ, q)= aA ca pa   iI wi   iI  aA qa (wi  pa d a ) i  (g  iIiiaAipa   aA pa )i

• The primary ↔ dual variables are p ↔ λ and w ↔ q– Ahuja et al (1993) show that the dual variable of linkchoice probabilities p can be interpreted as node potential(as in Proposition 1)– Interpretation of q …to follow• L(p,w,λ,q) is– Minimised with regards to p and w– Maxmised with regards to q and λ– Subject to non-negativity conditions on p and q19

Equivalence of S&F linear programwith “Multiple local demon game” (3)• The interpretation of q is clarified by the dual problem• L(p,w,λ,q) can be transformed intoL(p, w, λ, q)= iI i gi   a (i , j )A pa ((i   j )  ca  qa d a ) iI wi ( aA qa  1)i

• Meaning that the dual problem can be formulated asMaxiI i gi(i   j  qa da )  ca
Subject to q 1 0aAi

qa  0a

Demon Problem:Maximise node costs
subject to qi = 1 ateach node20

Equivalence of S&F linear programwith “Multiple local demon game” (4)• Further, L(p,w,λ,q) can be transformed into

Maxq Minp  aA (ca pa  qa d a pa )Subject toaAi

pa   aA pa  gi

1   aA qai
pa  0i

qa  0• This MaxMin problem gives the mixed strategy Nashequilibrium of a zero sum, non-cooperative gamebetween a network user endeavouring to minimise histravel cost and node specific demons aiming to penalise
the traveller by imposing delays.

21Comparison to single demon game• As pointed out the single demon game has been of
special interest in the network reliability literature.
• The S&F / Multiple local demon game can betransformed into the single demon game by a change inthe demon constrained:

Maxq Minp  aA (ca pa  qa d a pa )Subject toaAi

pa   aA pa  gi

1   aA qapa  0qa  0

ia Aia A22

Observation (can be proven)• Only the single demon game necessarilyincludes the shortest path
– In the multiple local demon game thetraveller might avoid nodes with potentiallylarge delays altogether.
– In the single demon game the total resourceof the demon is limited, meaning that thetraveller should include (at least with a smallprobability) every potentially shortest path.
23

Numerical Example

Multiple local
demonsSingle demon

Link usagepa

qa

pa

qa

L1

0.5

0.46

00

L2 (A-B)

0.5

0.54

10.07

L2(B-C)

0.5

0

0.6

0L3(B-C)

01

0.4

0.53

L3(C-D)

0.08

0.5

0.8

0.40

L4

0.42

0.50.20Game value/
feared travel cost

27.75 min• Shortest
undelayedpath L2(A-B) > L3(B-C-D)
only included
in single
demon game

23.40 min24

Numerical Example (2)Multiple local
demonsSingle demon

Link usage

pa

qa

pa

qa

L1

0.50

0.63

0.5

0.03

L2 (A-B)

0.50

0.37

0.5

0.05

L2(B-C)

0.50

00.3

0L3(B-C)

01

0.2

0.53

L3(C-D)

0.08

0.50

0.4

0.39

L4

0.42

0.50

0.10Game value/
feared travel cost

26.75 min• Only qchanges inMLDG• L1 now also
included inSDG

23.20 min25

Numerical Example (3)Link usage
L1
L2 (A-B)
L2(B-C)
L3(B-C)
L3(C-D)
L4
Game value/
feared travel cost

Multiple local
demonsSingle demon

pa
1.00
00000

pa
0.86
0.14
0.08
0.06
0.12
0.03

qa
1.00
0
0.33
0.67
0.5
0.5

24.00 min

qa
0.06
0.01
0
0.53
0.40

• Only single
route in MLDG
• Multiple
routes in SDG(as 24min >travel time on
shortest path)

23.06 min26

Conclusions• The S&F hyperpath concept can be interpreted
as a “multiple local demon game” (MLDG).
– It is the route choice of an intelligent traveller
fearing that “something can go wrong at eachdecision point”.
– The dual variable q is an indicator for the linkimportance• A smart transit system with RTI and line
coordination can reduce the tavellers’ game toa single demon game.
27

Extension: Effects of information ontrip stages
Travel stage

Uninformed,
unfamiliar traveller

Commuter; Local
dynamic information

Ubiquitous Info (Smartphone

Before departure

Look up timetable,
select stop and dep.
time

Select stop and dep. time, possibly complex
alternatives and more complex strategies

At stop

Wait for service

possibly consider moreconnections+ possibly consider
changing stopOn-Board

No decision

possibly adjustalighting point+ possibly change dest.

At Destination

Stick to plan or make an effort to obtain new
information

Possibly revise and coordinate plans; e.g.
adjust pick-up
28

Network Example
Stop B
P1
P2

OriginDestination

Stop A29

Network Example
Stop B

Without hyperpath
consideration

P1
P2

OriginDestination

Stop A30

Network Example
Stop B

With platform
hyperpathconsideration

P1P2Origin
Destination

Stop A
31

Network Example
Stop B

With Route +Platform Hyperpath(ITS: Information atStation entrance)

P1
P2

OriginDestination

Stop A32

Network Example
Stop B

With Walking, Routeand Platform
Hyperpath (SmartPhone)

P1
P2

OriginDestination

Stop A
33

Note on Hyperpath vs Strategy• Through reliable, “dynamic” information on service
departures, route choice decision points move closer
to passenger departure time: At decision point thehyperpath collapses into a single path.
• Therefore for the passenger the hyperpath might notnecessarily become more complex, but only “from amodelling perspective”.

34Overall Conclusions• “Smart transit”, i.e. providing good information allows
the traveller to benefit by less need to be risk-averseand by having wider options• This might in turn help the system• But there is also a danger that the traveller“outsmarts” the system– Headway perturbations– Focus on the shortest route• …requiring possibly even more information andnetwork management
35

Current work connected to the topic…
• Fare structures: Increasingly complex tomanage and attract demand– Zones vs distance based and flat fares– Special discounts: OD pairs, peak times, loyalty
rewards (per day, per month..), Shopping points• Bus bunching and stop layout: in how far can“intelligent design” make a system robust
against delays
36Thank you

schmoecker@trans.kuciv.kyoto-u.ac.jp

37

References and acknowledgements tomy co-authors
Fonzone, A., Schmöcker, J.-D. and Liu, R. (2015). A model of bus bunching underreliability-based passenger arrival patterns. Transportation Research C. Available
from http://dx.doi.org/10.1016/j.trc.2015.05.020.
Schmöcker, J.-D., Sun, W., Liu, R. and Fonzone, A. (2015). Bus Bunching Along a Corridor
Served by Two Lines. Presented at the 6th International Symposium onTransportation Network Reliability (INSTR), August 2015, Nara, Japan.

Fonzone, A. and Schmöcker, J.-D. (2014). Effects of Transit Real-Time Information Usage
Strategies. Transportation Research Records, 2417, 121-129.
Schmöcker, J.-D. (2010). On Decision Principles for Routing Strategies Under Various
Types of Risks. In: Security and Environmental Sustainability of Multimodal Transport.
Edited by: Bell, M.G.H., Hosseinloo, S.H. and Kanturska, U.; Springer, Dordrecht, TheNetherlands.
Schmöcker, J.-D., Bell, M.G.H., Kurauchi, F. and Shimamto, H. (2009). A Game Theoretic
Approach to the Determination of Hyperpaths in Transportation Networks. Selected
Proceedings of the 18th International Symposium on Transportation and Traffic Theory(ISTTT). Hong Kong, July 2009.
38