Algorithmen fur¨ Routenplanung

INSTITUT FUR THEORETISCHE INFORMATIK · ALGORITHMIK · PROF. DR. DOROTHEA WAGNER

Algorithmen fur Routenplanung18. Vorlesung, Sommersemester 2016

Ben Strasser | 4. Juli 2016

KIT – Universitat des Landes Baden-Wurttemberg undnationales Großforschungszentrum in der Helmholtz-Gemeinschaft

www.kit.edu

http://www.kit.edu

Zuge vs Straße

Bisher: Auto auf StraßeJetzt: Zuge auf Schiene(oder Flugzeuge, Schiffe, . . .alles mit festem Fahrplan)

Fahrplanauskunft genanntAnwendungen:

http://www.bahn.dehttp://www.kvv.de. . .

Ben Strasser – Algorithmen fur RoutenplanungFolie 2 – 4. Juli 2016

Institut fur Theoretische InformatikLehrstuhl Algorithmik

http://www.bahn.de

http://www.kvv.de

Zuge vs Straße

Bisher: Auto auf StraßeJetzt: Zuge auf Schiene(oder Flugzeuge, Schiffe, . . .alles mit festem Fahrplan)

Fahrplanauskunft genanntAnwendungen:

http://www.bahn.dehttp://www.kvv.de. . .



http://www.bahn.de

http://www.kvv.de

Fahrplanauskunft

Transport for London August 2011

Key to symbols Explanation of zones

1

3

45

6

2

7

8

9

Station in both zones



Station in Zone 9

Station in Zone 6

Station in Zone 5

Station in Zone 3Station in Zone 2

Station in Zone 1

Station in Zone 4

Station in Zone 8

Station in Zone 7

Station closed

Riverboat services

AirportTramlink

Interchange stations

Step-free access from street to platform

Step-free access from street to train

National Rail

Blackfriars

Check before you travel

Key to lines

Bank Waterloo & City line open 0615 until 2148 Mondays to Fridays and 0800 until 1830 Saturdays. Closed Sundays and Public Holidays---------------------------------------------------------------------------Blackfriars Underground station closed until late 2011---------------------------------------------------------------------------Camden Town From 1300 until 1730 Sundays open for interchange and exit only---------------------------------------------------------------------------Canary Wharf Step-free interchange between Underground, Canary Wharf DLR and Heron Quays DLR stations at street level---------------------------------------------------------------------------Cannon Street Open until 2100 Mondays to Fridays. Closed Saturdays and Sundays---------------------------------------------------------------------------Heron Quays Step-free interchange between Heron Quays and Canary Wharf Underground station at street level---------------------------------------------------------------------------Hounslow West Step-free access for wheelchair users only---------------------------------------------------------------------------Tottenham Northern line trains will not Court Road stop at Tottenham Court Road until late 2011 ---------------------------------------------------------------------------Turnham Green Served by Piccadilly line trains early mornings and late evenings only---------------------------------------------------------------------------Victoria Major escalator refurbishment works until early 2012. Use nearby stations or alternative routes---------------------------------------------------------------------------Waterloo Waterloo & City line open 0615 until 2148 Mondays to Fridays and 0800 until 1830 Saturdays. Closed Sundays and Public Holidays---------------------------------------------------------------------------West India Quay Not served by DLR trains from Bank towards Lewisham before 1900 on Mondays to Fridays---------------------------------------------------------------------------

Northern

Metropolitan

Victoria

District

Circle

Central

Bakerloo

DLR

London Overground

Piccadilly

Waterloo & City

Jubilee

Hammersmith & City

River Thames

A

B

C

D

E

F

1 2 3 4 5 6 7 8 9

1 2 3 4 5 76 8 9

A

B

C

D

E

F

2 2

22

2

5

8 8 6

2

4

4

65

41

3

2

43

3

36 3 1

1

3

3

59 7 7Special fares apply

5

5

4

4

4

AmershamChorleywood

Mill Hill East

Rickmansworth

Perivale

KentishTown West

CamdenRoad

Dalston Kingsland

Wanstead Park

Vauxhall

Hanger Lane

Edgware

Burnt Oak

Colindale

Hendon Central

Brent Cross

Golders Green

West Silvertown

Pontoon Dock

London City Airport

Woolwich Arsenal

King George V

Hampstead

Belsize Park

Chalk Farm

Chalfont &Latimer

Chesham

New Cross Gate

Moor Park

NorthwoodNorthwoodHills

Pinner

North Harrow

Custom House for ExCeL

Prince Regent

Royal Albert

Beckton Park

Cyprus

Gallions Reach

Beckton

Watford

Croxley

Fulham Broadway

LambethNorth

HeathrowTerminal 4

Harrow-on-the-Hill

KensalRise

BethnalGreen

Westferry

SevenSisters

Blackwall

BrondesburyPark

HampsteadHeath

HarringayGreen Lanes

LeytonstoneHigh Road

LeytonMidland Road

Hackney Central

NorthwickPark

PrestonRoad

RoyalVictoria

WembleyPark

Rayners Lane

Watford High Street

RuislipGardens

South Ruislip

Greenford

Northolt

South Harrow

Sudbury Hill

Sudbury Town

Alperton

Pimlico

Park Royal

North Ealing

Acton Central

South Acton

Ealing Broadway

Watford Junction

West Ruislip

Bushey

Carpenders Park

Hatch End

North Wembley

West Brompton

Ealing Common

South Kenton

Kenton

Wembley Central

Kensal Green

Queen’s Park

Gunnersbury

Kew Gardens

Richmond

Stockwell

Bow Church

Stonebridge Park

Harlesden

Camden Town

Willesden Junction

Headstone Lane

Parsons Green

Putney Bridge

East Putney

Southfields

Wimbledon Park

Wimbledon

Island Gardens

Greenwich

Deptford Bridge

South Quay

Crossharbour

Mudchute

Heron Quays

West India Quay

Elverson Road

Oakwood

Cockfosters

Southgate

Arnos Grove

Bounds Green

Theydon Bois

Epping

Debden

Loughton

Buckhurst Hill

WalthamstowQueen’s Road

Woodgrange Park

Leytonstone

Leyton

Wood Green

Turnpike Lane

Manor House

Stanmore

Canons Park

Queensbury

Kingsbury

High Barnet

Totteridge & Whetstone

Woodside Park

West Finchley

Finchley CentralWoodford

South Woodford

Snaresbrook

Hainault

Fairlop

Barkingside

Newbury Park

East Finchley

Highgate

Archway

Devons Road

Langdon Park

All Saints

Tufnell Park

Kentish Town

Neasden

Dollis Hill

Willesden Green

South Tottenham

Swiss Cottage

ImperialWharf

Brixton

Kilburn

West Hampstead

Blackhorse Road

Acton Town

CanningTown

Finchley Road

Highbury &Islington

Canary Wharf

Stratford

StratfordInternational

FinsburyPark

Elephant & Castle

Stepney Green

Barking

East Ham

Plaistow

Upton Park

Poplar

West Ham

Upper Holloway

PuddingMill Lane

Kennington

Borough

Elm ParkDagenham

East

DagenhamHeathway

Becontree

Upney

Heathrow Terminal 5

Finchley Road& Frognal

Crouch Hill

Northfields

Boston Manor

South Ealing

Osterley

Hounslow Central

Hounslow East

Clapham North

Oval

Clapham Common

Clapham South

Balham

Tooting Bec

Tooting Broadway

Colliers Wood

South Wimbledon

Arsenal

Holloway Road

Caledonian Road

Morden

West Croydon

HounslowWest

Hatton Cross

HeathrowTerminals 1, 2, 3

ClaphamJunction

WestHarrow

Brondesbury CaledonianRoad &

Barnsbury

TottenhamHale

WalthamstowCentral

HackneyWick

Homerton

WestActon

Limehouse EastIndia

Crystal Palace

ChiswickPark

RodingValley

GrangeHill

Chigwell

Redbridge

GantsHill

Wanstead

NorthGreenwichfor The O2

Ickenham

TurnhamGreen

Uxbridge

Hillingdon Ruislip

GospelOak

Mile End

Bow Road

Bromley-by-Bow

Upminster

Upminster Bridge

Hornchurch

Norwood Junction

Sydenham

Forest Hill

Anerley

Penge West

Honor Oak Park

Brockley

Harrow &Wealdstone

Cutty Sark for Maritime Greenwich

Ruislip Manor

Eastcote

Wapping

Shadwell

New Cross

CanadaWater

Surrey Quays

Whitechapel

Lewisham

Kilburn Park

Regent’s Park

KilburnHigh Road

EdgwareRoad

SouthHampstead

GoodgeStreet

Shepherd’s BushMarket

Goldhawk Road

Hammersmith

Bayswater

Warren Street

Aldgate

Euston

Farringdon

BarbicanRussellSquare

Kensington(Olympia)

MorningtonCrescent

High StreetKensington

Old Street

St. John’s Wood

Green Park

BakerStreet

NottingHill Gate

Victoria

AldgateEast

Blackfriars

Mansion House

Cannon Street

OxfordCircus

BondStreet

TowerHill

Westminster

PiccadillyCircus

CharingCross

Holborn

Tower Gateway

Monument

Moorgate

Leicester Square

London Bridge

St. Paul’s

Hyde Park Corner

Knightsbridge

StamfordBrook

RavenscourtPark

WestKensington

NorthActon

HollandPark

Marylebone

Angel

Queensway MarbleArch

SouthKensington

Earl’sCourt

SloaneSquare

Covent Garden

LiverpoolStreet

GreatPortland

Street

Bank

EastActon

ChanceryLane

LancasterGate

Warwick AvenueMaida Vale

Fenchurch Street

Paddington

BaronsCourt

GloucesterRoad St. James’s

Park Temple

Latimer Road

Ladbroke Grove

Royal Oak

Westbourne Park

Bermondsey

Rotherhithe

ShoreditchHigh Street

Dalston Junction

Haggerston

Hoxton

Wood Lane

Shepherd’sBush

WhiteCity

King’s CrossSt. Pancras

EustonSquareEdgware

Road

Southwark

Embankment

Stratford High Street

Abbey Road

Star Lane

Waterloo

TottenhamCourt Road

Canonbury



Wirrwarr

Auf der Straße:Etablierte Formalisierung: Kurzester Weg durch GraphEtablierte Terminologie: Jeder redet von Knoten und KantenEtablierte Testinstanz: Die meisten testen auf DIMACS-Europa

Auf der Schiene:Kaum zwei Paper wirklich vergleichbarJeder benennt die Sachen verschiedenDetails der Problemstellung sind oft verschiedenTestinstanz unterschieden sich starkDennoch: Interessante algorithmische ProblemstellungenVersuch es in der Vorlesung es halbwegs konsistent zu halten(nicht immer moglich)



Wirrwarr

Auf der Straße:Etablierte Formalisierung: Kurzester Weg durch GraphEtablierte Terminologie: Jeder redet von Knoten und KantenEtablierte Testinstanz: Die meisten testen auf DIMACS-Europa

Auf der Schiene:Kaum zwei Paper wirklich vergleichbarJeder benennt die Sachen verschiedenDetails der Problemstellung sind oft verschiedenTestinstanz unterschieden sich starkDennoch: Interessante algorithmische ProblemstellungenVersuch es in der Vorlesung es halbwegs konsistent zu halten(nicht immer moglich)



Die Eingabe: Der Fahrplan

Ein Fahrplan besteht aus:StopsConnectionsTripsFußwege



Die Eingabe: Stops

Stops sind Positionen an denen ein Fahrgast stehen kannBeispiel:

Karl-Wilhelm-PlatzKarlstor. . .

Jeder Stop s hat eine minimale Umstiegszeit change time(s)

Zwischen ankommenden und abfahrend Zuge muss mindestenschange time(s) Zeit sein um umsteigen zu konnen

Aber:Sind Doppelstops wie Kronenplatz (Kaiserstraße) undKronenplatz (Fritz-Erler-Str.) ein oder zwei Stops?Ist der Hauptbahnhof ein Stop oder ist jedes Gleis ein Stop?Mehr dazu spater



Die Eingabe: Connections

Eine Connection c ist ein Zug der zwischen zwei Stops fahrt undnicht haltBesteht aus:

Abfahrtsstop-ID cdepstop

Ankunftsstop-ID carrpstop

Abfahrtszeit cdeptime

Ankunftszeit carrtime

Trip-ID ctripid (siehe nachste Folie)

Beispiel:S-Bahn vom Europaplatz zur HerrenstraßeS-Bahn von der Herrenstraße zum MarktplatzAber nicht: S-Bahn vom Europaplatz zum Marktplatz(da die S-Bahn in der Herrenstraße halt)



Die Eingabe: Trip

Ein Trip ist eine Folge von Connections die vom selben Zugbedient werdenBeispiel:

Die S1 die um 15:55 am Marktplatz ankommtConnection A vom Europaplatz zur Herrenstraße und ConnectionB von der Herrenstraße zum Marktplatz konnen zum selben TripgehorenAber nicht: Die S1(nicht alle S1-Fahrten werden vom selben Zug bedient)



Die Eingabe: Fußwege

Ein Fußweg ist eine gerichtete Kante zwischen zwei StopsBesteht aus:

AbfahrtsstopAnkunftsstopLaufzeit

Beispiele:Kante zwischen Hauptbahnhof-Gleise und Hauptbahnhof-VorplatzKante zwischen Kronenplatz (Kaiserstraße) und Kronenplatz(Fritz-Erler-Str.)Kante zwischen Europaplatz und Herrenstraße



Wann darf ich Umsteigen?

Kaum zwei Paper betrachten das selbe UmstiegsmodellViele Realwelt-Instanzen haben unterschiedliche ModelleViele Paper ignorieren FußwegeBei anderen sind Umstiegszeiten alle 0Großes Wirrwarrund leider machen die Fußweg-Details algorithmisch großeUnterschiede



Umstiege bei uns

Wennich von Stop A nach Stop B undvon Stop B nach Stop C laufen darfdann darf ich auch von A nach C laufen

Von Stop A nach Stop B ist es nie langer als ein Umweg ubereinen weiteren Stop CDie Umstiegszeit an einem Stop A ist kurzer als jeder Pfad derbei A beginnt und bei A endet

Aquivalente SichtweiseStops sind partitioniertFur jede Partition gibt es eine vollstandige kurzeste Wege-MatrixJede Matrix erfullt DreieckungleichungMatrix-Diagonale sind Umstiegszeiten



Umstiege bei uns

Wennich von Stop A nach Stop B undvon Stop B nach Stop C laufen darfdann darf ich auch von A nach C laufen

Von Stop A nach Stop B ist es nie langer als ein Umweg ubereinen weiteren Stop CDie Umstiegszeit an einem Stop A ist kurzer als jeder Pfad derbei A beginnt und bei A endet

Aquivalente SichtweiseStops sind partitioniertFur jede Partition gibt es eine vollstandige kurzeste Wege-MatrixJede Matrix erfullt DreieckungleichungMatrix-Diagonale sind Umstiegszeiten



Umstiege bei unsWir wollen quadratische Matrizen klein haltenWir wollen deswegen wenige Fußwege haben

Macht aus Kronenplatz (Kaiserstraße) und Kronenplatz(Fritz-Erler-Str.) am besten ein Stop Kronenplatz mitUmstiegszeitGleise am Bahnhof sind ein Stop mit entsprechenderUmstiegszeitBahnhof-Vorplatz und Bahnhof-Halle sind zu weit voneinanderweg→ Hier ist ein Fußweg sinnvollKeine Fußwege zwischen benachbarten Stops

Wenn ich vom Europaplatz zur Herrenstraße laufen darf,dann darf ich auch zum Marktplatz weiterlaufenund von da zum Kronenplatzund von da zum Mendelsonplatz. . .und auf einmal sind wir am Hauptbahnhof und haben einegigantische Fußweg-Matrix



Umstiege bei unsWir wollen quadratische Matrizen klein haltenWir wollen deswegen wenige Fußwege habenMacht aus Kronenplatz (Kaiserstraße) und Kronenplatz(Fritz-Erler-Str.) am besten ein Stop Kronenplatz mitUmstiegszeit

Gleise am Bahnhof sind ein Stop mit entsprechenderUmstiegszeitBahnhof-Vorplatz und Bahnhof-Halle sind zu weit voneinanderweg→ Hier ist ein Fußweg sinnvollKeine Fußwege zwischen benachbarten Stops




Umstiege bei unsWir wollen quadratische Matrizen klein haltenWir wollen deswegen wenige Fußwege habenMacht aus Kronenplatz (Kaiserstraße) und Kronenplatz(Fritz-Erler-Str.) am besten ein Stop Kronenplatz mitUmstiegszeitGleise am Bahnhof sind ein Stop mit entsprechenderUmstiegszeit

Bahnhof-Vorplatz und Bahnhof-Halle sind zu weit voneinanderweg→ Hier ist ein Fußweg sinnvollKeine Fußwege zwischen benachbarten Stops




Umstiege bei unsWir wollen quadratische Matrizen klein haltenWir wollen deswegen wenige Fußwege habenMacht aus Kronenplatz (Kaiserstraße) und Kronenplatz(Fritz-Erler-Str.) am besten ein Stop Kronenplatz mitUmstiegszeitGleise am Bahnhof sind ein Stop mit entsprechenderUmstiegszeitBahnhof-Vorplatz und Bahnhof-Halle sind zu weit voneinanderweg→ Hier ist ein Fußweg sinnvoll

Keine Fußwege zwischen benachbarten StopsWenn ich vom Europaplatz zur Herrenstraße laufen darf,dann darf ich auch zum Marktplatz weiterlaufenund von da zum Kronenplatzund von da zum Mendelsonplatz. . .und auf einmal sind wir am Hauptbahnhof und haben einegigantische Fußweg-Matrix



Umstiege bei unsWir wollen quadratische Matrizen klein haltenWir wollen deswegen wenige Fußwege habenMacht aus Kronenplatz (Kaiserstraße) und Kronenplatz(Fritz-Erler-Str.) am besten ein Stop Kronenplatz mitUmstiegszeitGleise am Bahnhof sind ein Stop mit entsprechenderUmstiegszeitBahnhof-Vorplatz und Bahnhof-Halle sind zu weit voneinanderweg→ Hier ist ein Fußweg sinnvollKeine Fußwege zwischen benachbarten Stops




Die Ausgabe: Journeys

Ein Leg ist ein Paar (c1, c2) von Einstiegs-Connection c1 undAusstiegs-Connection c2, so dass c1 und c2 im selben Trip sitzenund c2 nach c1 abfahrtEine Journey ist eine alternierende Folge von Legs undFußwegen oder UmstiegenZwei aufeinanderfolgende Legs in einer Journey mussen

Am selben Stop A ankommen und abfahren und die Umstiegszeitan A respektierenBei A ankommen und bei B abfahren und die Laufzeit einesFußwegs von A nach B respektieren

Es darf auf ein Fußweg am Anfang und Ende einer JourneygebenEine Journey darf auch nur aus einem Fußweg bestehenZwei direkt aufeinanderfolgende Fußwege sind wegenDreieckungleichung nie sinnvoll



Problem der fruhesten Ankunft

Eingabe:FahrplanStartstop sZielstop tStartzeit τ

Ausgabe:Journey von s nach t die nach τ abfahrt

Optimierungsfunktion:Minimiere Ankunftszeit an t




Problem der fruhesten Ankunft entspricht am ehesten kurzestenWege Problem in GraphenKurzestes Wege Problem in Graphen ist nutzlichIst das Problem der fruhesten Ankunft nutzlich?



Problem der fruhesten AnkunftBetrachte folgenden Fahrplan

A B C

D

E

F

8:00→9:00 14:00→15:00

9:30→10:00 12:30→13:00

10:30→11:00 11:30→12:00

unds = At = Bτ = 8:00

Optimale Journeys sind:A→ B → CA→ B → D → E → F → B → C

Den zweiten will man sicher nicht haben



Problem der fruhesten AnkunftBetrachte folgenden Fahrplan

A B C

D

E

F

8:00→9:00 14:00→15:00

9:30→10:00 12:30→13:00

10:30→11:00 11:30→12:00

unds = At = Bτ = 8:00

Optimale Journeys sind:A→ B → CA→ B → D → E → F → B → C

Den zweiten will man sicher nicht haben




Betrachte folgenden Fahrplan

A B C8:00→9:00 14:00→15:00

12:00→13:00

unds = At = Bτ = 8:00

Optimale Journeys sind:A@8→ B → C@15A@12→ B → C@15

Den ersten will man auch nicht haben




Betrachte folgenden Fahrplan

A B C8:00→9:00 14:00→15:00

12:00→13:00

unds = At = Bτ = 8:00

Optimale Journeys sind:A@8→ B → C@15A@12→ B → C@15

Den ersten will man auch nicht haben



Mehrere Kriterien und Eindeutigkeit

Auf der Straße:Einfache klare Zielfunktion: Minimiere ReisezeitLosung in der Regel eindeutig

Auf der Schiene:Zielfunktion unklar, meistens minimiert man in irgendeinerKombination:

AnkunftszeitAnzahl an Umstiegen

Oft gibt es mehrere optimale JourneysNur letzte Connection legt Ankunftszeit festViele “aquivalente” Umstiege



Weitere Kriterien

Weitere KriterienOft mochte man weitere Kriterien optimierenBeispiel:

Preis minimierenLaufwege minimierenUnsicherheit minimieren

Aber: Jedes weitere Kriterium macht das Gesamtproblemschwieriger



Probleme beim Kriterium Preis

Oft gewunscht, kann aber niemand genau losen

Wie berechne ich den Preis einer gegeben Journey?Genaue Preispolitik oft intransparentGenaue Berechnung scheitert oft aus politischen GrundenOptimierung also nicht moglich

Preise manchmal absurdVerkehrsverbund-Tickets oft billiger als DB-TicketsVerkehrsverbund-Tickets konnen nicht immer in Bahnen gelostwerden die durch einen Verkehrsverbund fahren“optimale” Journey steigt also an Verbundsgrenzen aus um neuesTicket zu losen

Oft approximiert man den Preis durchdie Distanzdie Zugklassen (ICE vs IC vs Regio)durch die Anzahl an traversierten Tarifwaben




Oft gewunscht, kann aber niemand genau losenWie berechne ich den Preis einer gegeben Journey?

Genaue Preispolitik oft intransparentGenaue Berechnung scheitert oft aus politischen GrundenOptimierung also nicht moglich



















Kriterien Kombinieren

Man kann mehrere Kriterien im Pareto-Sinn optimierenHinter einem Pareto-Trade-Off Punkt konnen sich mehrereJourneys verbergenMochte man alle oder nur eine Journey pro Pareto-Trade-OffPunkt?Hinweis: Bei zu vielen Kriterien konnen die Pareto-Menge sehrgroß werden, selbst bei nur einer Journey pro Punkt

Man kann die Kriterien ordnenBeispiel: Unter allen Journeys mit fruhester Ankunft wahle eine mitminimaler Anzahl an TransfersKombination mit Runden moglich: z.B. Ankunft um 10:00 und 10:01zum selben Zeitpunkt runden

Man kann lineare Kombinationen betrachtenBeispiel:Ein Transfer ist aquivalent zu einer 10 Minuten spaterenAnkunft















Profile

Oft kennt der Fahrgast seine genaue Abfahrtszeit nicht→ Profil-Anfragen losen

Eingabe:Minimale Abfahrtszeit τmin

Maximale Ankunftszeit τmax

Ausgabe:Alle Journeys

mit einer Abfahrtszeit nach τmin undeiner Ankunftszeit vor τmax

die fur irgendeinen Startzeitpunkt optimal sindBei mehreren Journeys die bezuglich aller Kriterien gleich sindreicht eine



Profile

Oft kennt der Fahrgast seine genaue Abfahrtszeit nicht→ Profil-Anfragen losen

Eingabe:Minimale Abfahrtszeit τmin

Maximale Ankunftszeit τmax

Ausgabe:Alle Journeys

mit einer Abfahrtszeit nach τmin undeiner Ankunftszeit vor τmax

die fur irgendeinen Startzeitpunkt optimal sindBei mehreren Journeys die bezuglich aller Kriterien gleich sindreicht eine



Profile

Profilsuchen kann man als Pareto-Optimierung auffassenWir wollen alle Journeys finden, so dass:

Abfahrtszeit am Start maximiert wirdund Ankunftszeit am Ziel minimiert wird

mit Nebenbedingung:Nicht vor τmin abfahrenNicht nach τmax ankommen



Instanzen

Auf der StraßeGroße integrierte Instanzen seit Jahren verfugbarDIMACS GraphenOpenStreetMap Graphen

Auf der SchieneViele winzige GTFS-Fahrplane offen

General/Google Transit Feed Specification

In Europa wird eher HAFAS verwendetFormat von HaConOft sind Daten nicht offen

Keine große offene integrierte Instanz verfugbarWir haben Zugriff auf alte bahn.de Daten, allerdings mit NDA undnur fur Forschung



Instanzen

Auf der StraßeGroße integrierte Instanzen seit Jahren verfugbarDIMACS GraphenOpenStreetMap Graphen

Auf der SchieneViele winzige GTFS-Fahrplane offen

General/Google Transit Feed Specification

In Europa wird eher HAFAS verwendetFormat von HaConOft sind Daten nicht offen

Keine große offene integrierte Instanz verfugbarWir haben Zugriff auf alte bahn.de Daten, allerdings mit NDA undnur fur Forschung



Instanzen

Realwelt Daten oft fehlerhaftErster Schritt: Datenfehler beseitigenBeispiele fur Datenfehler:

Zuge in die Vergangenheit cdep time > carr time

Instentane Zuge, d.h., cdep time = carr time

Schleifen, d.h., cdep stop = carr stop

Instentane Trips mit Connections a, b, c wo,adep time = bdep time = cdep time = . . .Stops die nie erreicht werdenStops wo man hinkommt aber nicht mehr weg. . .



Zeit-Expandierter Graph




Idee1 Baue aus dem Fahrplan einen Graph2 Wende Dijkstras Algorithmus auf diesen Graphen an




Knoten stellen Paare von raumlichen und zeitliche Positioneneines Fahrgasts darBeispiel:

Am Marktplatz um 8:00In der dritten Fahrt der S1 um 9:00Aber nicht: Am Marktplatz(zeitliche Komponente fehlt)Aber nicht: In der S1(zeitliche Komponente fehlt)Und nicht: Um 10:00(ortliche Komponente fehlt)

Problem: Unendliche viele Knoten da Zeit kontinuierlich istIdee: Nur Knoten an Zeitpunkten an denen etwas passiert




Knoten stellen Paare von raumlichen und zeitliche Positioneneines Fahrgasts darBeispiel:

Am Marktplatz um 8:00In der dritten Fahrt der S1 um 9:00Aber nicht: Am Marktplatz(zeitliche Komponente fehlt)Aber nicht: In der S1(zeitliche Komponente fehlt)Und nicht: Um 10:00(ortliche Komponente fehlt)

Problem: Unendliche viele Knoten da Zeit kontinuierlich istIdee: Nur Knoten an Zeitpunkten an denen etwas passiert



Zeit-Expandierter GraphFur jede Connection erstellen wir drei Knoten:

Die Stehe-Am-Stop-Knoten (cdepstop, cdeptime) und(carrstop, carrtime + changetime(carrstop))Den Sitze-Im-Zug-Knoten (ctripid, cdeptime)

Zeitgleiche Stehe-Am-Stop-Knoten werden zusammengefasst

Jeder (nicht zusammengefasste) Knoten hat bis zu zweiausgehende KantenFur Stehe-Am-Stop-Knoten:

Einstiegs-Kante: von (cdepstop, cdeptime) nach (ctripid, cdeptime)Warte-Kante: von (s, τ1) nach (s, τ2) wobei s ein Stop ist und τ1

und τ2 zwei aufeinander folgende ZeitpunkteFur Sitze-Im-Zug-Knoten:

Ausstiegs-Kante: von (ctripid, cdeptime) nach(carrstop, carrtime + changetime(carrstop)) istSitzen-Bleiben-Kante: von (t , τ1) nach (t , τ2) wobei t ein Trip istund τ1 und τ2 zwei aufeinander folgende Zeitpunkte



Zeit-Expandierter GraphFur jede Connection erstellen wir drei Knoten:

Die Stehe-Am-Stop-Knoten (cdepstop, cdeptime) und(carrstop, carrtime + changetime(carrstop))Den Sitze-Im-Zug-Knoten (ctripid, cdeptime)

Zeitgleiche Stehe-Am-Stop-Knoten werden zusammengefasst

Jeder (nicht zusammengefasste) Knoten hat bis zu zweiausgehende KantenFur Stehe-Am-Stop-Knoten:

Einstiegs-Kante: von (cdepstop, cdeptime) nach (ctripid, cdeptime)Warte-Kante: von (s, τ1) nach (s, τ2) wobei s ein Stop ist und τ1

und τ2 zwei aufeinander folgende ZeitpunkteFur Sitze-Im-Zug-Knoten:

Ausstiegs-Kante: von (ctripid, cdeptime) nach(carrstop, carrtime + changetime(carrstop)) istSitzen-Bleiben-Kante: von (t , τ1) nach (t , τ2) wobei t ein Trip istund τ1 und τ2 zwei aufeinander folgende Zeitpunkte




cdepstop carrstop cdeptime carrtime ctripid

A B 8 9 αB C 9 10 αB D 9 10 βB D 10 11 γ

stop s changetime(s)

A 0.5B 0.3C 0.2D 0.1





A B 8 9 αB C 9 10 αB D 9 10 βB D 10 11 γ


A 0.5B 0.3C 0.2D 0.1

(α, 8) (B, 9.3)

(B, 9)

(B, 10)

(D, 11.1)

(β, 9)

(A, 8)

(α, 9)(C, 10.2)

(γ, 10)

(D, 10.1)

Alle Knoten; (B,9) wurde zusammengefasst





A B 8 9 αB C 9 10 αB D 9 10 βB D 10 11 γ


A 0.5B 0.3C 0.2D 0.1

(α, 8) (B, 9.3)

(B, 9)

(B, 10)

(D, 11.1)

(β, 9)

(A, 8)

(α, 9)(C, 10.2)

(γ, 10)

(D, 10.1)

Sitzen-Bleiben-Kanten





A B 8 9 αB C 9 10 αB D 9 10 βB D 10 11 γ


A 0.5B 0.3C 0.2D 0.1

(α, 8) (B, 9.3)

(B, 9)

(B, 10)

(D, 11.1)

(β, 9)

(A, 8)

(α, 9)(C, 10.2)

(γ, 10)

(D, 10.1)

Warte-Kante





A B 8 9 αB C 9 10 αB D 9 10 βB D 10 11 γ


A 0.5B 0.3C 0.2D 0.1

(α, 8) (B, 9.3)

(B, 9)

(B, 10)

(D, 11.1)

(β, 9)

(A, 8)

(α, 9)(C, 10.2)

(γ, 10)

(D, 10.1)

Einstiegs-Kanten





A B 8 9 αB C 9 10 αB D 9 10 βB D 10 11 γ


A 0.5B 0.3C 0.2D 0.1

(α, 8) (B, 9.3)

(B, 9)

(B, 10)

(D, 11.1)

(β, 9)

(A, 8)

(α, 9)(C, 10.2)

(γ, 10)

(D, 10.1)

Ausstiegs-Kanten




(α, 8) (B, 9.3)

(B, 9)

(B, 10)

(D, 11.1)

(β, 9)

(A, 8)

(α, 9)(C, 10.2)

(γ, 10)

(D, 10.1)

Azyklischer Graph, da in der Zeit vorwarts gerichtetKanten werden mit Zeitdifferenz gewichtetGrad-1-Knoten konnen wegkontrahiert werden

Es gibt eine Konstruktion mit 2 Knoten pro ConnectionAber: Viele kleine Sonderfalle in AlgorithmenMachen wir nicht in der Vorlesung



Zeit-Expandierter GraphExpandierte Fußwege

Fur einen Fußweg von A nach B der Lange ` mussen mehrereKanten eingefugt werdenKante zwischen (A, x) und (B, y) wenn y − x ≥ ` und

Es keinen Knoten (A, p) gibt mit y − p ≥ ` und p > x gibtEs keinen Knoten (B, q) gibt mit q − x ≥ ` und q < y gibt

Beispiel mit ` = 1






Beispiel mit ` = 1(A, 3)

(A, 5)

(A, 6)

(A, 7)

(B, 3)

(B, 5)

(B, 6)

(B, 8)






Beispiel mit ` = 1(A, 3)

(A, 5)

(A, 6)

(A, 7)

(B, 3)

(B, 5)

(B, 6)

(B, 8)




Fußweg-ExplosionBei m Fußwege und c Connections konnen wir Θ(cm) Kantenkriegen⇒ Fußwege in der Modellierung sparsam verwenden

Initiale & Finale FußwegeExpandierte Fußwege decken nur Fußwege zwischen zwei LegsabInitiale und finale Fußwege sind Sonderfalle in Algorithmen



Dijkstras Algorithmus im Zeit-ExpandiertenGraph




Eingabe:Startstop sStartzeit τs

Zielstop tAusgabe:

Ankunftszeit τt



Problem der fruhesten AnkunftIdee:

Dijkstras Algorithmus auf zeit-expandiertem GraphKantengewichte ist die ZeitdifferenzErster Knoten von s nach τs ist erster Knoten in QueueErster Stehe-Am-Stop-Knoten von t der aus der Queuegenommen wird hat Ankunftszeit

Beispiel:mit s = A, t = C, τs = 8

τt = 10.2






(α, 8) (B, 9.3)

(B, 9)

(B, 10)

(D, 11.1)

(β, 9)

(A, 8)

(α, 9)(C, 10.2)

(γ, 10)

(D, 10.1)

τt = 10.2






(α, 8) (B, 9.3)

(B, 9)

(B, 10)

(D, 11.1)

(β, 9)

(A, 8)

(α, 9)(C, 10.2)

(γ, 10)

(D, 10.1)

τt = 10.2






(α, 8) (B, 9.3)

(B, 9)

(B, 10)

(D, 11.1)

(β, 9)

(A, 8)

(α, 9)(C, 10.2)

(γ, 10)

(D, 10.1)

τt = 10.2






(α, 8) (B, 9.3)

(B, 9)

(B, 10)

(D, 11.1)

(β, 9)

(A, 8)

(α, 9)(C, 10.2)

(γ, 10)

(D, 10.1)

τt = 10.2






(α, 8) (B, 9.3)

(B, 9)

(B, 10)

(D, 11.1)

(β, 9)

(A, 8)

(α, 9)(C, 10.2)

(γ, 10)

(D, 10.1)

τt = 10.2






(α, 8) (B, 9.3)

(B, 9)

(B, 10)

(D, 11.1)

(β, 9)

(A, 8)

(α, 9)(C, 10.2)

(γ, 10)

(D, 10.1)

τt = 10.2






(α, 8) (B, 9.3)

(B, 9)

(B, 10)

(D, 11.1)

(β, 9)

(A, 8)

(α, 9)(C, 10.2)

(γ, 10)

(D, 10.1)

τt = 10.2






(α, 8) (B, 9.3)

(B, 9)

(B, 10)

(D, 11.1)

(β, 9)

(A, 8)

(α, 9)(C, 10.2)

(γ, 10)

(D, 10.1)

τt = 10.2






(α, 8) (B, 9.3)

(B, 9)

(B, 10)

(D, 11.1)

(β, 9)

(A, 8)

(α, 9)(C, 10.2)

(γ, 10)

(D, 10.1)

τt = 10.2



Initiale Fußwege

Problem:Initiale Fußwege werden nicht immer beachtet

Angepasster Algorithmus:Finde ersten Knoten von s nach τs und fuge ihn mit Gewicht 0 indie QueueFur jeden ausgehenden Fußweg (s, x) mit Lange `:

Finde ersten Knoten von x nach τs + ` fuge ihn mit Gewicht ` in dieQueue



Initiale Fußwege

Problem:Initiale Fußwege werden nicht immer beachtet

Angepasster Algorithmus:Finde ersten Knoten von s nach τs und fuge ihn mit Gewicht 0 indie QueueFur jeden ausgehenden Fußweg (s, x) mit Lange `:

Finde ersten Knoten von x nach τs + ` fuge ihn mit Gewicht ` in dieQueue



Finale FußwegeProblem:

Finale Fußwege werden nicht immer beachtet

Angepasster Algorithmus:Idee: global Array D, D[x ] ist die Fußwegdistanz von x zu tFulle D bei Programmstart mit∞Vor Dijkstras Algorithmus:

Iteriere uber alle eingehenden Kanten von t und setze Dund setze D[t ] = 0

Nach Dijkstras Algorithmus:Iteriere uber alle eingehenden Kanten von t und setze D auf∞zuruckund setze D[t ] =∞

Wahrend Dijkstras Algorithmus:Wenn Stehe-Am-Stop-Knoten (x , τ) aus der Queue genommenwird:Wenn τ + D[x ] 6=∞ dann wurde ein Weg gefunden




Finale Fußwege werden nicht immer beachtetAngepasster Algorithmus:

Idee: global Array D, D[x ] ist die Fußwegdistanz von x zu tFulle D bei Programmstart mit∞

Vor Dijkstras Algorithmus:Iteriere uber alle eingehenden Kanten von t und setze Dund setze D[t ] = 0







Idee: global Array D, D[x ] ist die Fußwegdistanz von x zu tFulle D bei Programmstart mit∞Vor Dijkstras Algorithmus:






















Mehrere Kriterien

Um mehrere Kriterien im Pareto-Sinn zu optimieren kann maneine Erweiterung von Dijkstras Algorithmus einsetzen

Grobe WiederholungJeder Knoten hat eine Menge genannt Bag von LabelBags enthalten nur nicht dominierte LabelDie Queue verwaltet Label



Spateste Abfahrtszeit

Ziel:Wir wollen unter allen Journeys die so fruh wie moglichankommen eine wahlen die so spat wie moglich abfahrt

Option 1:Zwei Anfragen:

Erste bestimmt die fruheste AnkunftszeitZweite arbeitet auf Ruckwartsgraph und bestimmt spatesteAbfahrtszeit

Option 2:Mach eine Profilanfrage

















PfadextraktionZiel:

Finde Journey und nicht nur Ankunftszeit

Option 1:Speichere Vorgangerzeiger an jedem KnotenErgibt nur ein Pfad

Option 2:Bestimme Vorgangerknoten uber DistanzenSei d(x) die Distanz an Knoten xJeder Knoten y mit Kante (y , x) und d(y) + `(y , x) = d(x) istgultiger KnotenIteriere uber eingehende Kanten um alle oder nur ein y zubestimmenKann genutzt werde um ein Pfad zu findenKann auch alle Pfade findenAchtung: Es kann sehr viele optimale Pfade geben



PfadextraktionZiel:

Finde Journey und nicht nur AnkunftszeitOption 1:

Speichere Vorgangerzeiger an jedem KnotenErgibt nur ein Pfad




PfadextraktionZiel:

Finde Journey und nicht nur AnkunftszeitOption 1:

Speichere Vorgangerzeiger an jedem KnotenErgibt nur ein Pfad




Profile

Eingabe:Startstop sminimale Abfahrtszeit τmin

Zielstop tmaximale Ankunftszeit τmax

Ausgabe:Menge an optimalen Journeys die

von s nach t fahren undnach τmin abfahren undvor τmax ankommen



Profile

Einfache algorithmische Anpassung:Fuge alle Knoten (s, τ) fur jedes τmin ≤ τ ≤ τmax mit Gewicht 0 indie QueuePrune die Suche an allen Knoten die spater als τmax sindExtrahiere den Pfad fur jeden Knoten (t , τ) fur jedesτmin ≤ τ ≤ τmax

Kombinationen:Bei mehreren Kriterien: Fuhre Pfadextraktion fur jedes LabeldurchBei initialen und finalen Fußwegen: Anpassungen analog



Profile

Einfache algorithmische Anpassung:Fuge alle Knoten (s, τ) fur jedes τmin ≤ τ ≤ τmax mit Gewicht 0 indie QueuePrune die Suche an allen Knoten die spater als τmax sindExtrahiere den Pfad fur jeden Knoten (t , τ) fur jedesτmin ≤ τ ≤ τmax

Kombinationen:Bei mehreren Kriterien: Fuhre Pfadextraktion fur jedes LabeldurchBei initialen und finalen Fußwegen: Anpassungen analog



Literatur I

Evangelia Pyrga, Frank Schulz, Dorothea Wagner, and Christos Zaroliagis.Efficient models for timetable information in public transportation systems.ACM Journal of Experimental Algorithmics, 12(2.4):1–39, 2008.



Documents

Algorithmen fur¨ Routenplanung