Percentage of trip legs

(1)

Improved methods to deduct trip legs and mode from travel surveys using wearable GPS devices: A case study from the

Greater Copenhagen area

samt anvendelse af GPS data i PhD afhandling Trafikdage 2015

Thomas Kjær Rasmussen DTU Transport

tkra@transport.dtu.dk

(2)

Agenda

• Artikel om bearbejdning af rå GPS datasæt

– Dataindsamling og metode til bearbejdning af store datasæt

• Anvendelse af bearbejdet GPS data (PhD projekt)

– Repræsentation af pålidelighed af rejsetid (Prato et al., 2014) – Stor-skala validering af ny rutevalgsmodel og løsningsmetode

(Watling et al., 2015; Rasmussen et al., 2015cd)

(3)

Improved methods to deduct trip legs and mode from travel surveys using wearable GPS devices:

a case study from the Greater Copenhagen Area

Rasmussen, T.K., Ingvardson, J.B., Halldórsdóttir, K., Nielsen, O.A., 2015

Computers, Environment and Urban Systems, doi:

10.1016/j.compenvurbsys.2015.04.001.

(4)

Motivation

• RP datakilde som tillader meget detaljeret repræsentation af individer og familiers rejsemønstre

• Billig indsamlingsmetode, få krav til respondenter

• Teknologiske udvikling har muliggjort indsamling på individ-niveau og over flere dage

• De genererede datasæt er meget store

• Større tilgængelighed af disaggregeret netværksinformation

• Artiklen bidrager med introduktion og validering af en automatisk

metode til efterbehandling af rå GPS data

(5)

• Første trin er baseret på Schüssler and Axhausen (2009)

• Identifikation af transportmiddel (mode): trinvis proces der anvender avancerede GIS analyser

• Map matching: Avanceret branch and bound algoritme

Metode

(6)

Metode

(7)

Filtrering, identifikation af ture og turben

• Baseret på Schüssler & Axhausen (2009)

• Kalibrering af parametre

– Filtering (cleaning) af rådata

• Min. 4 synlige satellitter med HDOP ≤ 4

• Begrænsning på højde samt maksimal accelleration og hastighed

– Identifikation af aktiviteter

• Tidsforskel ≥120s, eller

• Hastighed ≤0.01m/s i mindst 60s, eller

• Begrænset bevægelse inden for lille område i mindst 60s

– Identifikation af turben

• Antager gang mellem turben: lav hastighed og accelleration

• Identificerede turben: minimum længde på 90-120s

(8)

Metode

(9)

Identifikation af transportmiddel

• Trinvis proces der kombinerer fuzzy logic og avancerede GIS

analyser

(10)

Jernbane (Rail proximity)

• Jernbanespor deler typisk ikke tracé med anden infrastruktur, f.eks. i Hovedstadsområdet

• Heuristik til klassificering af turben med jernbane

– Nærhed til jernbanenetværk: ≥ 75% af observationer inden for 25m

– Mindste længde af turben: 250m

Turben information Dato:

Starttid:

Sluttid:

Turlængde:

Antal observationer:

Antal obs. inden for 25m:

09-11-2011 16:07:01 16:22:53 15 min 52 sek 947

924

(11)

Fuzzy logic regler

• Inddel hastigheds- og accelerationsprofiler i intervaller

(12)

Fuzzy logic regler

• Inddel hastigheds- og accelerationsprofiler i intervaller; fastlæg transportmiddel vha. heuristiske regler

(13)

Fuzzy logic regler

• Inddel hastigheds- og accelerationsprofiler i intervaller; fastlæg transportmiddel vha. heuristiske regler

(14)

Fuzzy logic regler

• Inddel hastigheds- og accelerationsprofiler i intervaller; fastlæg

transportmiddel vha. heuristiske regler

(15)

Buslinjeanalyse (Bus line alignment)

• Sandssynlig bustur:

i) GPS enhed standser ved stor andel af busstop på en buslinje, og ii) Turben starter/ender nær busstop på denne buslinje

• 3-trin algoritme

– Nærhed til busstop: Identifikation af busstop for hvilke GPS enheden er i nærheden (25m) i mindst 10 sekunder

– For hver buslinje: Beregn andel mellem stop identificeret ovenfor og

samlet antal passerede busstop. Hvis andelen er høj og adskillige busstop passeret: marker buslinje som potentiel linje

– Hvis turben starter/slutter inden for 100m af et busstop på de ovenfor markerede ruter: klassificer turben som bus

(16)

Faktisk bustur Faktisk biltur

Turinformation

Dato: 09‐11‐2011

Starttid: 16:41:24

Sluttid: 16:53:18

Turlængde: 11 min 54 sec

Overlap med buslinje # stops Hit%

200S 2/2 100%

300S 2/2 100%

68 14/19 74%

Stop begyndelse: 68

Stop destination: 200S/300S/68

Turinformation

Dato: 09‐11‐2011

Starttid: 06:42:26

Sluttid: 06:49:07

Turlængde: 6 min 41 sec

Overlap med buslinje # stops Hit%

161 3/5 60%

Stop begyndelse: Intet

Stop destination: Intet

(17)

Metode

(18)

Map matching

• Der identificeres mange korte turben som ikke er faktiske turben

– Gåture til kaffemaskinen, ‘scatter’ etc.

– Disse fjernes ved map matching til detaljerede netværk

0%

10%

20%

30%

40%

50%

Percentage of trip legs

Distance [km]

Before Map Matching

After Map Matching

Travel diary

(19)

• Der identificeres mange korte turben som ikke er faktiske turben

– Gåture til kaffemaskinen, ‘scatter’ etc.

– Disse fjernes ved map matching til detaljerede netværk

Map matching

(20)

Metode

(21)

Feedback algoritme

• I første omgang klassificeres nogle turben og transportmidler forkert

• Feedback algoritme til at rette dette

– Sekvens af transportmiddel

• 2 turben

• 3 turben

– Turben splittes på motorvej eller rampe

Turben Farve v^max,95[m/s] a^max,95[m/s²] Klassificeret

1 Blå 14.2 0.53 Car

2 Grøn 3.1 0.16 Walk

3 Lilla 29.8 0.81 Car

(22)

Case studie: Hovedstadsområdet

• Komplekst multi-modalt netværk

– Gang, cykel, bus, bil, tog

– Detaljerede digitale repræsentationer tilgængelige

• GPS data indsamlet blandt 183 personer

– Hver person bar GPS enhed under alle ture foretaget i løbet af 3 dage – Tilhørende turdagbog for 1 af de 3 dage

– GPS log hvert sekund

(23)

Resultater

Obs.

Algoritme Gang Cykel Bus Bil Tog Ikke-ture Confidens rate

Gang 75 5 1 1 - 3 88,2%

Cykel 1 100 - 5 - - 94,3%

Bus - - 29 - - - 100,0%

Bil 1 7 7 151 1 4 88,3%

Tog - - - - 33 - 100,0%

Andet 1 1 - 1 - - -

Total 78 113 37 158 34 7 90,9%

92,4%

(68,8%)

Total (alle) 192 134 37 167 34 -

Succes rate 96,2% 88,5% 78,4% 95,6% 97,1% -

Succes rate (alle) 39,1% 74,6% 78,4% 90,4% 97,1% -

(24)

Resultater

Obs.

Gang 75 5 1 1 - 3 88,2%

Cykel 1 100 - 5 - - 94,3%

Bus - - 29 - - - 100,0%

Bil 1 7 7 151 1 4 88,3%

Tog - - - - 33 - 100,0%

Andet 1 1 - 1 - - -

Total 78 113 37 158 34 7 90,9%

92,4%

(68,8%)

Total (alle) 192 134 37 167 34 -

Succes rate 96,2% 88,5% 78,4% 95,6% 97,1% -

Succes rate (alle) 39,1% 74,6% 78,4% 90,4% 97,1% -

• Den foreslåede algoritme

– Genererer høj succes rate for alle transportmidler

(25)

Resultater

Obs.

Gang 75 5 1 1 - 3 88,2%

Cykel 1 100 - 5 - - 94,3%

Bus - - 29 - - - 100,0%

Bil 1 7 7 151 1 4 88,3%

Tog - - - - 33 - 100,0%

Andet 1 1 - 1 - - -

Total 78 113 37 158 34 7 90,9%

92,4%

(68,8%)

Total (alle) 192 134 37 167 34 -

Succes rate 96,2% 88,5% 78,4% 95,6% 97,1% -

Succes rate (alle) 39,1% 74,6% 78,4% 90,4% 97,1% -

• Den foreslåede algoritme

– Forbedrer success raterne for bus fra 37,8% til 78,4% og for tog fra 24,2% til 97.1% ifht. Schüssler & Axhausen (2009)

(26)

• Den foreslåede algoritme

– Forbedrer success raterne for bus fra 37,8% til 78,4% og for tog fra 24,2% til 97.1% ifht. Schüssler & Axhausen (2009)

– Formår at fjerne ikke-ture (180 før map matching), men også mange faktiske gåture

Resultater

Obs.

Gang 75 5 1 1 - 3 88,2%

Cykel 1 100 - 5 - - 94,3%

Bus - - 29 - - - 100,0%

Bil 1 7 7 151 1 4 88,3%

Tog - - - - 33 - 100,0%

Andet 1 1 - 1 - - -

Total 78 113 37 158 34 7 90,9%

92,4%

(68,8%)

Total (alle) 192 134 37 167 34 -

Succes rate 96,2% 88,5% 78,4% 95,6% 97,1% -

Succes rate (alle) 39,1% 74,6% 78,4% 90,4% 97,1% -

(27)

Følsomhedsanalyse

• Test indikerer at metoden generelt ikke er følsom overfor mindre ‘fejl’ i parametre og grænseværdier

– Andel af obs. i nærheden af jernbane, afstand til jernbane, min. turlængde

– Specifikation af fuzzy logic regler og intervaller

– Andel af busstop standset ved og minimum stoppetid

– Krav til minimum andel af tur der map matches korrekt

• Dvs. metode kan overføres på tværs af case-studier med mindre

justeringer af parametre

(28)

Konklusion

• Introduktion og validering af metode til behandling af store GPS datasæt

– Forbedrer resultater ved at udnytte disaggregeret repræsentation af infrastruktur

– Avancerede GIS analyser genererer store forbedringer for især bus og tog

– Mere detaljeret map matching netværk vil formentlig reducere antallet af fjernede faktiske ture

• Metoden muliggør brug af GPS i stor-skala undersøgelser af

transportvaner, og giver derved mulighed for bedre at kunne

forstå og forudse transportadfærd

(29)

Traffic assignment models in large-scale applications

Ph.D. afhandling, feb. 2015

Thomas Kjær Rasmussen

(30)

Baggrund

• Trafikmodeller bliver stadigt mere disaggregerede for at kunne repræsentere individer og deres rejsemønstre mere realistisk

• Potentialet udnyttes kun ved integration af modelkomponenter på fuldt disaggregeret niveau

• Udviklingen af de disaggregerede modeller muliggøres af øget adgang til

– Individbaseret data – Større regnekraft

– Mere effektive algoritmer

(31)

Målsætning

• Fokus på anvendelse i virkelige modeller, dvs. netudlægning (traffic assignment) i stor-skala modeller og anvendelse af stor- skala data

• Formålet er at addressere de potentialer og udfordringer der opstår i en fuldt disaggregeret tilgang

– Introduktion og evaluering af en disaggregeret

valgsætgenereringsmetode for multi-modale netværk

– Undersøge muligheden for at identificere detaljeret tur-information fra rå GPS data

– Undersøge muligheden for at bruge RP data til at fastlægge værdien af trængsel samt værdien af pålidelighed

– Undersøge muligheden for at generere teoretisk konsistent SUE- lignende trafikfordeling blandt ikke-universelle valgsæt i ligevægt

(32)

Artikelproduktion

• 6 (7) artikler

– 1 under review; Rasmussen et al. (2015a)

– 4 publiseret; Rasmussen et al. (2015b), Prato et al. (2014), Watling et al. (2015), Rasmussen et al. (2015c)

– 1 under færdiggørelse; Rasmussen et al. (2015d)

(33)

Timetable-based simulation method for choice set generation in large-scale public transport networks

Rasmussen, T.K., Anderson, M.K., Prato, C.G., Nielsen, O.A., 2015

Genindsendt efter anden review runde til Transportmetrica A: Transport Science

(34)

Estimating Value of Congestion and of Reliability from Observation of Route Choice Behavior of Car Drivers

Prato, C.G., Rasmussen, T.K., Nielsen, O.A., 2014

Transportation Research Record: Journal of the Transportation Research Board, 2412, 20-27

Vinder af 2014 TRB Pyke Johnson Award

(35)

Motivation

• Trængselstid samt rejsetidens pålidelighed har stor indflydelse på rejsevaner

– Relevant at beregne værdien af disse for at få bedre forståelse og repræsentation af transportadfærd

• Værdien af trængsel samt pålidelighed er blevet undersøgt uafhængigt i primært SP studier

– der er konsensus omkring vigtigheden af at inkludere pålidelighed samtidig med fri rejsetid og trængselstid

– Mean-variance samt scheduling modeller giver sammenlignelige værdier for værdien af pålidelighed

• Studiet bidrager med introduktion og anvendelse af RP-baseret

metode der inkluderer både værdien af trængsel og pålidelighed

(36)

Metode

Indsamling af RP data om rutevalg

GPS dataindsamling

Klargøring af data til estimation af model

Map matching, dobbelt stokastisk valgsætgenerering, beregning af mål for pålidelighed og databearbejdning

Estimation af værdi af trængsel og værdi af pålidelighed

Estimation af mixed og ikke-mixed Path-Size Correction Logit modeller og beregning af tidsværdier

(37)

Metode: data og databearbejdning

• LTM netværk

– 34.251 kanter

– Fri rejsetid samt trængselstid på kanter tilgængeligt for 10 tidsbånd vha. LTM netudlægning

• Observationer

– 169 bilførere med GPS enheder, 17.115 ruter map matched til LTM netværket

– Adskillige observationer på hver kant: beregning af mål for pålidelighed af rejsetid

(38)

• Valgsætgenerering

– Dobbelt stokastisk method

– 100 ruter genereres, unikke identificeres

– Beregning af variable til estimeringen (fri rejsetid, trængselstid, mål for pålidelighed, omkostning, sving, path-size korrektion)

• Model estimation

– Nyttefunktion

– Non-mixed og mixed Path-Size Correction Logit

Metode: valgsætgenerering og model estimation

costcos

i fft i congt i trel i i left i right i i

V   fft  congt   trel  t   left   right 

 

exp exp

n

i psc i

i

j psc j

j C

V psc

P V psc





 

 

 

  ^{ }

exp exp

n

i psc i

i

j psc j

j C

V psc

P f d

V psc

   





 

  

(39)

• Mixed Path-Size Correction Logit

Resultater

Myldretid Udenfor myldretid

Variable Estimat t-test estimat t-test

Fri rejsetid (μ) -0.739 -13.26 -1.060 -15.12

Fri rejsetid (σ) 0.259 2.10 0.161 2.53

Trængselstid (μ) -0.348 -5.53 -0.831 -11.94

Trængselstid (σ) 0.309 2.36 0.186 2.13

Pålidelighed (μ) -0.189 -6.90 -0.653 -17.84

Pålidelighed (σ) 0.381 3.07 0.243 3.57

Omkostning -0.256 -3.25 -0.299 -5.64

Venstresving -0.665 -32.76 -0.644 -44.11

Højresving -0.467 -27.63 -0.455 -38.24

Path-Size 0.929 16.92 0.897 24.64

Antal observationer 5759 7964

Null log-likelihood -15607.99 -23987.90

Endelig log-likelihood -8774.47 -15914.37

Justeret rho-square 0.437 0.336

(40)

• Mixed Path-Size Correction Logit

Resultater

Mål middel Std. afv. Middel Std. afv.

VOT fri rejsetid (DKr/t) 115.64 30.43 70.38 11.37 VOT trængselstid (DKr/t) 173.27 54.75 88.91 16.68 Værdi af pålidelighed (DKr/t) 208.45 82.45 107.51 26.54

Værdi af trængsel ratio 1.50 1.26

Værdi af pålidelighed ratio 1.53 1.49

(41)

• Mixed Path-Size Correction Logit

• VOT samt værdi af pålidelighed højere i myldretiden

Resultater

(42)

• Mixed Path-Size Correction Logit

• VOT samt værdi af pålidelighed højere i myldretiden

• Værdi af trængsel ratio højere i myldretiden

– Den beregnede værdi er i overensstemmelse med værdier fundet i SP/RP studier

Resultater

(43)

• Mixed Path-Size Correction Logit

• VOT samt værdi af pålidelighed højere i myldretiden

• Værdi af trængsel ratio højere i myldretiden

– Den beregnede værdi er i overensstemmelse med værdier fundet i SP/RP studier

• Værdi af pålidelighed ratio varierer ikke med kørselsforhold og trængsel når der tages hensyn til gns. trængselsniveau

Resultater

(44)

Konklusion

• Metode til udnyttelse af den stigende mængde af tilgængeligt GPS-baseret rejsetidsinformation til bedre forståelse og

repræsentation af transportadfærd

• Giver evidens om værdien af forskellige rejsetidskomponenter

• Estimerer nyttefunktioner som kan udnyttes direkte i

trafikmodeller (traffic assignment models) og derved øge deres

realisme

(45)

Stochastic user equilibrium with equilibrated choice sets: Part I – Model formulations under alternative distributions and restrictions

Watling, D.P., Rasmussen, T.K., Prato, C.G., Nielsen, O.A., 2015 Transportation Research Part B: Methodological, 77, 166-181

Stochastic user equilibrium with equilibrated choice sets: Part II – Solving the restricted SUE for the logit family

Rasmussen, T.K., Watling, D.P., Prato, C.G., Nielsen, O.A., 2015 Transportation Research Part B: Methodological, 77, 146-165

Stochastic User Equilibrium with Equilibrated Choice Sets: Part III – Model reformulation to include Thresholds on costs and large-scale application

Under færdiggørelse

(46)

Motivation

• Nuværende modellers teoretiske grundlag

– (deterministic) User Equilibrium models (DUE) – Stochastic User Equilibrium models (SUE)

• DUE tillader kun brug af ruter med minimum omkostning, hvilket ikke er adfærdsmæssigt realistisk men attraktivt idet sættet af muligt

anvendte ruter defineres implicit

• SUE funderet på nytteteori (random utility theory), hvilket gør den adfærdsmæssigt realistisk men typisk kræver at alle mulige ruter skal anvendes

• For stor-skala modeller approksimeres SUE ofte blandt et præ- specificeret valgsæt

• Studiet bidrager med introduktion og validering af en ny type model som muliggør SUE lignende trafikfordeling blandt valgsæt i ligevægt

(47)

DUE og SUE

• DUE

– Stærk antagelse omkring komplet viden hos rejsende og modellør – Indbygget skelnen mellem potentielt anvendte og bestemt ikke-

benyttede ruter: alle rejsende oplever præcis den samme omkostning – Attraktiv i stor-skala modeller

• SUE

– Ikke komplet viden hos rejsende og modellør – Baseret på nytteteori med nytteoptimering

– Opfattet nytte følger typisk en ubegrænset kontinuert fordeling, hvilket leder til anvendelse af alle ruter

– Ikke attraktiv i stor-skala modeller

(48)

• DUE

– Stærk antagelse omkring komplet viden hos rejsende og modellør – Indbygget skelnen mellem potentielt anvendte og bestemt ikke-

benyttede ruter: alle rejsende oplever præcis den samme omkostning – Attraktiv i stor-skala modeller

• SUE

– ikke komplet viden hos rejsende og modellør – random utility model med nytteoptimering

– Opfattet nytte følger typisk en ubegrænset kontinuert fordeling, hvilket leder til anvendelse af alle ruter

– Ikke attraktiv I stor-skala modeller

• Behov for nye betingelser (conditions) at opfylde, som tillader

• implicit skelnen mellem afgjort ubenyttede ruter og ruter der muligvis benyttes

• Forbindelse til nytteteori i trafikfordelingen

DUE and SUE

C₄=30.0 C₁=15.0

C₂=15.0

C₃=15.1

0 0,1 0,2 0,3

0 10 20 30 40

Probability Density

Travel cost c_r

Density r=1, r=2 Density, r=3 Density, r=4

(49)

Conditions og ligevægtsmodel

• Φ-Restricted Stochastic User Conditions

– For each OD movement:

I. the proportion of travellers on any used path is equal to the probability that that path has a perceived utility greater than or equal to the perceived utility of all alternative used paths;

II. the ‘reference cost’ is a value uniquely defined by some relationship Φ to the travel costs on the used paths;

III. the travel cost which would be experienced by a traveller on any unused path is greater than or equal to the reference cost as defined in ii).

• Φ-Restricted Stochastic User Equilibrium (RSUE(Φ))



 



mr 0 m mr m mr m

x   r R^  x  d P c x R^



 



 

0 :

mr m mr ms m m

x   r R  c   c x s R  ξ

(50)

RSUE(Φ) formuleringer

• RSUE(min):

– Logisk kombination af DUE og SUE

– Tillader at brugte ruter kan være dyrere end en ubenyttet rute – Beregningsmæssigt attaktiv, idet en mulig løsning er nem at

verificere

• RSUE(max):

– Ingen ubenyttet rute er billigere end den dyreste benyttede rute – Ikke ligeså attraktiv rent beregningsmæssigt, men en mulig løsning

kan verificeres ved brug af standardværktøjer



^{^c^ms

 

^{: s R}^m^}; ^m



^min



^c^ms

^{ }

^:^{s R}^m



 x   ξ  x  



^{^c^ms

 

^{: s R}^m^}; ^m



^max



^c^ms

^{ }

^:^{s R}^m



 x   ξ  x  

(51)

Udbygning af RSUE(Φ)

• Den 2. RSUE(Φ) condition sikrer at der ikke er nogle ikke anvendte ruter der er attraktiv

• Der er ingen condition der sikrer at alle anvendte ruter er attraktive

• Udbygning af RSUE modellen der hindrer at ingen anvendte ruter

er uattraktive

(52)

Restricted Stochastic User with Threshold conditions (RSUT(Φ,Ω))

• For each OD movement m=1, 2,..., M:

I. the proportion of travellers on any used path is equal to the probability that that path has a perceived utility greater than or equal to the perceived utilities on all alternative used paths;

II. the ‘external reference cost’ is a value uniquely defined by some relationship Φ to the actual travel costs on the used paths;

III. the actual travel cost which would be experienced by a traveller on any unused path is greater than or equal to the external reference cost as defined in ii);

IV. the ‘internal reference cost’ is a value uniquely defined by some relationship  to the actual travel costs on the used paths;

V. the actual travel cost on any used path is less than or equal to the internal reference cost as defined in iv).

(53)

• For each OD movement m=1, 2,..., M:

I. the proportion of travellers on any used path is equal to the probability that that path has a perceived utility greater than or equal to the perceived utilities on all alternative used paths;

II. the ‘external reference cost’ is a value uniquely defined by some relationship Φ to the actual travel costs on the used paths;

III. the actual travel cost which would be experienced by a traveller on any unused path is greater than or equal to the external reference cost as defined in ii);

IV. the ‘internal reference cost’ is a value uniquely defined by some relationship  to the actual travel costs on the used paths;

V. the actual travel cost on any used path is less than or equal to the internal reference cost as defined in iv).

Restricted Stochastic User with Threshold

conditions (RSUT(Φ,Ω))

(54)

Restricted Stochastic User Equilibrium with Threshold (RSUET(Φ,Ω))

• Given Φ and Ω then the route flow x  G is a RSUET(Φ,Ω) if and only if for all r  R

_m

and m = 1,2,…,M:

• Specifikation af Ω-funktion:

– ikke-negativ grænseværdi:

– Relativ til ruten med lavest omk.:

– En kombinatiton:

– …



 





^c^ms ^:^s ^R^m ^;^^m



^^m ^min

^

^c^ms ^{ }^:^s ^R^m

^

 x     x  



 





^c^ms ^:^s ^R^m ^;^^m



^^m

 x   



 





^c^ms ^:^s ^R^m ^{; ,}^{ }^m ^m



^^m ^^m ^min

^

^c^ms^{ }^:^s ^R^m

^

 x      x  

 

^{ }

 

^{ }

 

0 ( ) : ;

mr m mr m mr m mr ms m m

x   r R  x  d P c x R  c x   c x s R  ς

 



 



0 { };

mr m mr ms m m

x   r R^  c x   c x : s R ^ ξ

(55)

Restricted Stochastic User Equilibrium with Threshold (RSUET(Φ,Ω))

• Given Φ and Ω then the route flow x  G is a RSUET(Φ,Ω) if and only if for all r  R

_m

and m = 1,2,…,M:

• Specifikation af Ω-funktion:

– Ikke-negativ grænseværdi:

– Relativ til ruten med lavest omk.:

– En kombination:

– …



 





^c^ms ^:^s ^R^m ^;^^m



^^m ^min

^

^c^ms^{ }^:^s ^R^m

^

 x     x  



 





^c^ms ^:^s ^R^m ^;^^m



^^m

 x   



 





^c^ms ^:^s ^R^m ^{; ,}^{ }^m ^m



^^m ^^m ^min

^

^c^ms^{ }^:^s ^R^m

^

 x      x  

 

^{ }

 

^{ }

 

0 ( ) : ;

mr m mr m mr m mr ms m m

x   r R  x  d P c x R  c x   c x s R  ς

 



 



0 { };

mr m mr ms m m

x   r R^  c x   c x : s R ^ ξ

(56)

RSUET(Φ, Ω) algoritme

• Der eksisterer algoritmer til stor-skala brug af DUE

– Effektive, undgår simulering

– Konvergens kan verificeres vha. GAP mål

• Der eksisterer algoritmer til stor-skala brug af SUE

– Approximation af SUE

– eksplicit/implicit valgsætgenerering

– Anvender ofte simulation i genereringen af nye ruter og/eller når trafikken fordeles

• RSUET(Φ,Ω) algoritme skal være hurtig, generisk og undgå

simulering, ligesom konvergens skal være nem at verificere

(57)

Algoritmens ramme

• Rute-baseret algoritme

– RSU conditions og RSUE model er formuleret på ruteniveau – Nyttefunktionen til fordeling af trafikken kan inkludere rute-

afhængige variable

– Hukommelsesforbrug til at gemme ruter er ikke et problem i moderne computere

(58)

Algoritme

• Step 0: Initialisation

• Step 1: Column generation phase. Øg valgsættet på ‘systematisk’ vis således at den anden condition er opfyldt når konvergeret

• Step 2: Restricted master problem phase. Fordel flow mellem anvendte ruter ifølge valgmodel, således at den første condition er opfyldt når konvergeret

• Step 3: Network loading phase. Lav netværksudlægning af trafikken og få den resulterende kanttrafik, kantomkostninger og ruteomkostninger

• Step 4: Threshold condition phase. Check om grænseværdi er overskredet for noget OD-par. Fjern overskridende ruter, redistribuer trafikken og lav netværksudlægning

• Step 5: Convergence evaluation phase. Anvend et konsistent konvergensmål til at undersøge hvorvidt begge conditions er opfyldt inden for et vis toleranceområde.

Hvis ikke: Retur til step 1.

(59)

• Valgsæt vokser ‘systematisk’

• Relaterer til den anden RSUE condition

Algoritme : Column generation phase

Step 1 Column generation phase. Let k_m,n-1 denote the current number of unique paths in the choice set of used paths for OD-pair m=1, 2,..., M in iteration n-1.

For RSUET(min,Ω):

For each origin, perform a shortest path search to all destinations based on actual link travel costs

. If for any OD- pair m=1, 2,..., M a new unique path i is generated, add it to the choice set

with flow

For RSUET(Φ,Ω):

For each OD-pair mϵM, based on actual link travel costs , check for a new route to add to the choice set by applying some path generation method which supports the fulfilment of the Φ operator. If for any OD- pair m=1, 2,..., M a new unique path i is generated, add it to the choice

set with flow if

several routes possible, add only the shortest one.

For RSUET(max,Ω):

Perform k_{m, n-1}-shortest path search for each OD-pair m=1, 2,..., M based on actual link travel costs If for any OD-pair m=1, 2,..., M a new unique path i is generated among the k generated paths, add it to the choice set with flow

if several new unique paths are generated, add only the shortest one.

 1 a n

t f _

,

Rm n

, 1 0.

xmi n_ 

, 1 0;

xmi n_ 

,

Rm n

,

Rm n

 1 a n

t f _

 1 .

a n

t f _

,

Rm n

, 1 0;

xmi n_ 

(60)

• Inner assignment component

– Ordinære rute-baserede SUE metoder til fordeling af trafik

– Effektive rute-baserede DUE metoder til fordeling af trafik, under anvendelse af transformeret omkostning for closed-form Logit lignende valgmodeller

– Relaterer til den første RSUE condition

• Averaging schemes

– MSA, MSWA, Self-regulated averaging, Armijo, …

Algoritme: Restricted Master Problem phase

Step 2 Restricted master problem phase. Given the choice sets for all m=1, 2,..., M, apply the selected inner assignment component and averaging scheme to find the new flow solution X_n.

 

( ) exp ( )

mr mr mr

c x  x   c x

,

Rm n

(61)

Step 4 Setm=1

Step 4.1 For each route r in the choice set , check whether the threshold condition c_mr(X_n) ≤ ({c_ms(x) : s  s }; _m ) is violated. If any route r violates this condition, and if n≥K_min, then flag the route that violates the threshold condition the most.

Step 4.2 If no route is flagged by Step 4.1 and if m<M, set m=m+1 and return to Step 4.1. If no routes are flagged by Step 4.1 and if m=M, continue to Step 4.3. If a route r is flagged by Step 4.1, remove the route from the choice set and redistribute flow x_mr,n among the remaining currently-used routes s

according to the following: .

Ifm<M, setm=m+1 and return to Step 4.1. Ifm=M, continue.

Step 4.3 If no routes have been removed for any of the M OD-pairs, continue. Else, perform the network loading, compute the link travel costs t_a(f_n), the generalised path travel costs C(X_n) and (if relevant/included) the path-size factors.

Algoritme: Threshold condition phase

,

Rm n

,

Rm n

• Ved at tillade at der kun droppes en rute per iteration og først efter K_min iterationer fås lavere risiko for ‘destabilisering’

• Ingen ruter overskrider grænseværdien ved konvergens, dvs. ingen uattaktive ruter benyttes

,

, , ,

, ms n ms n ms n mr n

m mr n

x x x x

d x

  



(62)

• Udnytte transformerede omkostninger til på konsistent vis at evaluere konvergens

– Første condition (allokering af trafik)

– Anden condition (komposition af valgsæt)

– RSUET(min,Ω):

– RSUE(max,Ω):

Algoritme: Convergence evaluation phase

Step 5 Convergence evaluation phase. If the gap measure consisting of the sum of and is below a pre-specified threshold ξ, Stop. Else, set n=n+1 and return to Step 1.

 

, ,min

1

1 ,

( ) ( )

( )

m

M

mr n mr n m n

Used m r R

n M

mr n mr n m r R

x c c

Rel.Gap

x c

 

 





 

x x

x



 



   

 

, 0

1

, 0

1

min ( ) min ( )

min ( )

m mr m

m mr

M

m r R x mr n r R mr n

Unused m

n M

m r R x mr n

m

d c c

Rel.Gap

d c

    



  



 







x x

x

 



^, ⁰ ^,



1

max ( ) ( )

. ^m ^mr

M

m r R x mr n mr k n

Unused m

d c c

Rel Gap ^ ^{ } ^

 





^x ^x

Used

Rel.Gapn Rel.Gap_n^Unused

(63)

RSUET(min, ∙min), case Sjælland netværk

• Netværk og efterspørgsel

– 3,2 millioner ture, 19 brugerkategorier, 3 køretøjstyper

– 18706 ensrettede kanter, 429 zoner

• Restricted master problem phase

– Nyttefunktion inkluderer fri rejsetid, trængelstid og længde

– MNL og Path-Size Logit (PSL) – inner assignment component

• DUE Path Swap

• Inner Logit – averaging scheme

• Method of Successive Weighted Averages (MSWA)

1 2 ...

d

n d d d

n

  n

  

(64)

RSUET(min, ∙min), case Sjælland netværk

• Threshold condition phase

• 16618 observerede ruter fra GPS spor

• 1169 tællinger på netværket

   



^c^ms ^:^{s R}^m ^;^^m



^^m ^min

^

^c^ms

^{ }

^:^{s R}^m

^

 x     x  

(65)

Resultater

• Ekstremt hurtig konvergens for MNL og PSL RSUET(min,1.2∙min)

• Step-size parameter d har indflydelse på konvergens

• Robust overfor trængselsniveau

– En smule langsommere konvergens – Større valgsæt

– Større effekt af grænseværdi

(66)

Resultater

• Ekstremt hurtig konvergens og meget rimelig valgsætstørrelse

• Sml med GPS data: observerede ruter er generelt repræsenteret

• Sml. med observeret kanttrafik: høj grad af overensstemmelse

• MultiNomial Probit (MNP) ikke konvergeret

– Valgsæt gror forsat – Kanttrafik ikke stabil

Coverage, λ=0.8 Valgsætstørrelse Efficiency index

Ekskluderede ruter

R² kanttrafik Ite 25 Ite 100 Min. Avg. Max.

θ=0.05 0.8431 0.8431 1 2.367 10 0.9859 1165 0.9429

θ=0.1 0.8452 0.8452 1 2.484 10 0.9734 1180 0.9440

θ=0.2 0.8487 0.8487 1 2.695 12 0.9543 1989 0.9441

θ=0.5 0.8535 0.8535 1 2.967 13 0.9338 3784 0.9438

θ=1.0 0.8548 0.8548 1 3.057 13 0.9165 4640 0.9437

MNP SUE 0.8959 0.8959 1 14.894 100 0.6540 - 0.9423