Non-pool-based line planning: a practical analysis of the FPT algorithm tw-lines

Non-pool-based line planning: a practical analysis of the FPT algorithm tw-lines Oliver Bachtler (RPTU Kaiserslautern-Landau) joint work with Irene Heinrich (TU Darmstadt), Philine Schiewe (Aalto University), and Constantin Seebach (RPTU Kaiserslautern-Landau) Euro Working Group on Transportation, 2024 Public Transport Optimisation strategic planning network design line planning tactical planning timetabling vehicle scheduling operational planning rescheduling stop skipping By Mario Roberto Duran Ortiz Mariordo - Own work, CC BY 3.0, https://commons.wikimedia.org/w/index.php?curid=3681079 Oliver Bachtler Non-pool-based line planning: a practical analysis of tw-lines EWGT 2024 1 / 13 Public Transport Optimisation strategic planning network design line planning tactical planning timetabling vehicle scheduling operational planning rescheduling stop skipping By Mario Roberto Duran Ortiz Mariordo - Own work, CC BY 3.0, https://commons.wikimedia.org/w/index.php?curid=3681079 Oliver Bachtler Non-pool-based line planning: a practical analysis of tw-lines EWGT 2024 1 / 13 Public Transport Optimisation strategic planning network design line planning tactical planning timetabling vehicle scheduling operational planning rescheduling stop skipping By Mario Roberto Duran Ortiz Mariordo - Own work, CC BY 3.0, https://commons.wikimedia.org/w/index.php?curid=3681079 Oliver Bachtler Non-pool-based line planning: a practical analysis of tw-lines EWGT 2024 1 / 13 Public Transport Optimisation strategic planning network design line planning tactical planning timetabling vehicle scheduling operational planning rescheduling stop skipping By Mario Roberto Duran Ortiz Mariordo - Own work, CC BY 3.0, https://commons.wikimedia.org/w/index.php?curid=3681079 Oliver Bachtler Non-pool-based line planning: a practical analysis of tw-lines EWGT 2024 1 / 13 Public Transport Optimisation strategic planning network design line planning tactical planning timetabling vehicle scheduling operational planning rescheduling stop skipping By Mario Roberto Duran Ortiz Mariordo - Own work, CC BY 3.0, https://commons.wikimedia.org/w/index.php?curid=3681079 Oliver Bachtler Non-pool-based line planning: a practical analysis of tw-lines EWGT 2024 1 / 13 Line Planning Neumarkt Leyendeckerstr. Akazienweg Wolffsohnstr. Westfriedhof Ollenhauerring Nußbaumerstr. Subbelrather Str. / Gürtel Liebigstr. Hans-Böckler-Platz/ Bf West Körnerstr. Piusstr. Bonn Severinsbrücke Drehbrücke Poller Kirchweg Raiffeisenstr. Poll Salmstr. Poll Baumschulenweg Westhoven Kölner Str. Westhoven Berliner Str. Ensen Gilgaustr. Ensen Kloster Porz Steinstr. Porz Markt Rosenhügel Vingst Ostheim Autobahn Steinweg Porzer Str. Rath/Heumar Röttgensweg Schönhauser Str. Bayenthalgürtel Chlodwigplatz HürthKalscheuren Bonner Wall Godorf Bf Wesseling Nord Wesseling Süd Urfeld Rodenkirchen Bf Siegstr. Michaelshoven Geestemünder Str. Fordwerke Süd Fordwerke Mitte Fordwerke Nord Niehl Nord Von-Sparr-Str. Mülheim Berliner Str. Im Weidenbruch Am Emberg Leuchterstr. Buchforst Waldecker Str. Buchheim Herler Str. Buchheim Frankfurter Str. Wichheimer Str. Maria-Himmelfahrt-Str. Holweide Vischeringstr. Neufelder Str. (Krankenhaus Holweide) Dellbrück Mauspfad Dellbrück Hauptstr. Appellhofplatz (Breite Str.) Appellhofplatz (Zeughaus) Christophstr./ Mediapark Kartäuserhof Eifelstr. Heinrich-Lübke-Ufer Ulrepforte Zülpicher Platz Weißhausstr. Arnulfstr. Weyertal Dürener Str./ Gürtel Wüllnerstr. Zülpicher Str./ Gürtel Gleueler Str./ Gürtel Mommsenstr. Melaten Berrenrather Str./ Gürtel Euskirchener Str. Lindenburg (Universitätsklinik) Poststr. Dasselstr. /Bf Süd Efferen Kiebitzweg HürthHermülheim Fischenich Brühl-Vochem Brühl Nord Brühl Mitte Universität Bf Mülheim Pohligstr. Eifelplatz Herthastr. Gottesweg Fuldaer Str. Sportpark Höhenberg Kalker Friedhof Merheim Flehbachstr. Lustheide Refrath Kippekausen Frankenforst Neuenweg Kölner Str. Im Hoppenkamp Maarweg Clarenbachstift Eupener Str. Alter Militärring RheinEnergieSTADION Junkersdorf Mohnweg Bahnstr. Weiden Zentrum Weiden Römergrab Brahmsstr. Stüttgenhof Haus Vorst Marsdorf Frechen Kirche Frechen Bf Mühlengasse Frechen Rathaus Lenauplatz Iltisstr. Margaretastr. Rektor-Klein-Str. Alter Flughafen Butzweilerhof IKEA Am Butzweilerhof Odenthaler Str. Merkenich Mitte Schaffrathsgasse Zollstockgürtel Rhein Gutenbergstr. Barbarossaplatz Weinsbergstr./ Gürtel Melatengürtel 16 18 1 9 15 3 12 1 7 1 4 7 RB 38 RE 8 RB 27 RE 1 (RRX), 9 S19 Bedburg Aachen Düren Mönchengladbach Müngersdorf Technologiepark Lövenich FrechenKönigsdorf Pulheim RB 24 RE 12, 22 RB 26, 48 RE 5 (RRX) Kierberg Köln Süd Brühl Erftstadt Euskirchen Gerolstein Bonn Remagen RE 7 RE 6 (RRX) S11 S 6 Volkhovener Weg Blumenberg Wilhelm-Sollmann-Str. Scheibenstr. Nesselrodestr. Boltensternstr. Zoo / Flora Reichenspergerplatz Breslauer Platz / Hbf Dom / Hbf Suevenstr. Deutz Technische Hochschule Kalk Post Kalk Kapelle Köln Hbf Florastr. Lohsestr. Rathaus Deutzer Freiheit Amsterdamer Str./ Gürtel Kinderkrankenhaus Mollwitzstr. Escher Str. Neusser Str./ Gürtel Geldernstr./ Parkgürtel Dormagen Dormagen Chempark Düsseldorf Neuss Tarifgrenze Krefeld Neuss Buchforst Holweide Duckterath Dellbrück Trimbornstr. RE 7 RB 48 S 6 RE 1 (RRX), 5 (RRX) Opladen Leichlingen LEV-Manfort Wuppertal Solingen Stammheim LEV Chempark LEV Mitte LEV-Küppersteg Düsseldorf RB 25 Rösrath Hoffnungsthal Frankfurter Str. RösrathStümpen Steinstr. Airport Businesspark Porz Porz-Wahn Spich Troisdorf RE 8 RB 27 S 12, 19 RE 9 Bonn-Beuel Neuwied Bonn BN-Bad Godesberg Siegburg Hennef Au (Sieg) Gummersbach Lüdenscheid Betzdorf Siegen Chorweiler Nord Meerfeldstr. Longericher Str. Heimersdorf Herforder Str. Altonaer Platz Longerich Mauritiuskirche Moltkestr. Venloer Str. / Gürtel Ehrenfeld Tarifgrenze Tarifgrenze Tarifgrenze Tarifgrenze Tarifgrenze Tarifgrenze Tarifgrenze Tarifgrenze Tarifgrenze Tarifgrenze Tarifgrenze Tarifgrenze Eifelwall/ Stadtarchiv Bf Deutz /LANXESS arena LEV-Rheindorf Stegerwaldsiedlung Koelnmesse Messe/Deutz RE 12, 22 RB 24, 26, 38 5 Heumarkt 12 Zollstock Südfriedhof 7Frechen-Benzelrath 19 Klettenbergpark 1Weiden West 9 Sülz Hermeskeiler Platz 17 Sürth Bf 5 Sparkasse Am Butzweilerhof 3 Görlinger-Zentrum 13 Sülzgürtel 7Zündorf 9Königsforst 4Schlebusch 4Bocklemünd 15 Chorweiler 12 Merkenich 16 Niehl Sebastianstr. S 11 Bergisch Gladbach S 12 Horrem RB 38 RB 25 Hansaring 318 Thielenbruch 1 Bensberg 17 Severinstr. 15 Ubierring RE 6 (RRX) Köln / Bonn Flughafen Sülzburgstr. Universitätsstr. Friesenplatz Longerich Friedhof S 6 Nippes S 6 Worringen Rudolfplatz Bf Deutz/ Messe Rochusplatz Brück Mauspfad Wesseling Aachener Str./ Gürtel S 12 Köln West 14 Keupstr. 1914 Ebertplatz Slabystr. 1813 18 13 Mülheim Wiener Platz Grünstr. Tarifgrenze 5 18 16 1 9 7 1 9 1 11 1 9 7 7 7 7 5 5 5 4 3 4 3 16 18 16 18 18 18 13 13 13 13 13 16 4 3 12 12 15 19 19 12 15 19 12 15 15 4 14 4 3 17 16 16 16 9 9 R E 6 ( R R X ) , 7 RE 1 ( RRX) , 8, 9 RB 2 7, 3 8 S 1 2 , 19 S 6, 1 1 R B 2 4 , 2 6 , 4 8 RE 8, RB 27 RE 1 (RRX), RB 38 RE 8, 9 RE 6 (RRX), RB 27 S 12 RB 25, S 19 RE 1 (RRX), 5 (RRX), 7 S 6,11 S 6 RB 48 14 14 14 R E 5 ( R R X ) , 1 2 , 2 2 118 118 118 18 3 18 N 2024 Bahnen in Köln Rail Services Cologne Infos zur Sanierung der Mülheimer Brücke www.kvb.koeln/bruecke Nach Ende der Sanierung der Mülheimer Brücke werden die Linien 118, 14, 19 entfallen und die Linien 13 und 18 fahren den regulären Linienweg. Information on the renovation of the Mülheim Bridge www.kvb.koeln/bridge After the completion of the renovation of the Mülheim Bridge lines 118, 14 and 19 will be cancelled and lines 13 and 18 will operate on the regular route. Endhaltestelle terminus Merkenich alternative Endhaltestelle alternative terminus Niehl Nord Stand: 2024-04 www.kvb.koeln 0800 6 504030 (free of charge from all German telephone networks) (kostenlos aus allen deutschen Netzen) Regionalbahn regional transit RB RE S-Bahn rail rapid transit S kein barrierefreier Zugang an mind. einer Linie (gilt nur für Straßenbahnen) no barrier-free access on at least one line (only applies to trams) unterirdische Stadtbahnlinie tram / light railway 12 oberirdische Stadtbahnlinie tram / light railway 12 Ersatzbuslinie während der Sanierung der Mülheimer Brücke Replacement bus route during the renovation of the Mülheim Bridge 118 P+R-Platz park and ride Tarifgrenze fare zone boundary Baustelle construction https://www.kvb.koeln/fahrtinfo/liniennetzplaene.html Oliver Bachtler Non-pool-based line planning: a practical analysis of tw-lines EWGT 2024 2 / 13 Line Planning Neumarkt Leyendeckerstr. Akazienweg Wolffsohnstr. Westfriedhof Ollenhauerring Nußbaumerstr. Subbelrather Str. / Gürtel Liebigstr. Hans-Böckler-Platz/ Bf West Körnerstr. Piusstr. Bonn Severinsbrücke Drehbrücke Poller Kirchweg Raiffeisenstr. Poll Salmstr. Poll Baumschulenweg Westhoven Kölner Str. Westhoven Berliner Str. Ensen Gilgaustr. Ensen Kloster Porz Steinstr. Porz Markt Rosenhügel Vingst Ostheim Autobahn Steinweg Porzer Str. Rath/Heumar Röttgensweg Schönhauser Str. Bayenthalgürtel Chlodwigplatz HürthKalscheuren Bonner Wall Godorf Bf Wesseling Nord Wesseling Süd Urfeld Rodenkirchen Bf Siegstr. Michaelshoven Geestemünder Str. Fordwerke Süd Fordwerke Mitte Fordwerke Nord Niehl Nord Von-Sparr-Str. Mülheim Berliner Str. Im Weidenbruch Am Emberg Leuchterstr. Buchforst Waldecker Str. Buchheim Herler Str. Buchheim Frankfurter Str. Wichheimer Str. Maria-Himmelfahrt-Str. Holweide Vischeringstr. Neufelder Str. (Krankenhaus Holweide) Dellbrück Mauspfad Dellbrück Hauptstr. Appellhofplatz (Breite Str.) Appellhofplatz (Zeughaus) Christophstr./ Mediapark Kartäuserhof Eifelstr. Heinrich-Lübke-Ufer Ulrepforte Zülpicher Platz Weißhausstr. Arnulfstr. Weyertal Dürener Str./ Gürtel Wüllnerstr. Zülpicher Str./ Gürtel Gleueler Str./ Gürtel Mommsenstr. Melaten Berrenrather Str./ Gürtel Euskirchener Str. Lindenburg (Universitätsklinik) Poststr. Dasselstr. /Bf Süd Efferen Kiebitzweg HürthHermülheim Fischenich Brühl-Vochem Brühl Nord Brühl Mitte Universität Bf Mülheim Pohligstr. Eifelplatz Herthastr. Gottesweg Fuldaer Str. Sportpark Höhenberg Kalker Friedhof Merheim Flehbachstr. Lustheide Refrath Kippekausen Frankenforst Neuenweg Kölner Str. Im Hoppenkamp Maarweg Clarenbachstift Eupener Str. Alter Militärring RheinEnergieSTADION Junkersdorf Mohnweg Bahnstr. Weiden Zentrum Weiden Römergrab Brahmsstr. Stüttgenhof Haus Vorst Marsdorf Frechen Kirche Frechen Bf Mühlengasse Frechen Rathaus Lenauplatz Iltisstr. Margaretastr. Rektor-Klein-Str. Alter Flughafen Butzweilerhof IKEA Am Butzweilerhof Odenthaler Str. Merkenich Mitte Schaffrathsgasse Zollstockgürtel Rhein Gutenbergstr. Barbarossaplatz Weinsbergstr./ Gürtel Melatengürtel 16 18 1 9 15 3 12 1 7 1 4 7 RB 38 RE 8 RB 27 RE 1 (RRX), 9 S19 Bedburg Aachen Düren Mönchengladbach Müngersdorf Technologiepark Lövenich FrechenKönigsdorf Pulheim RB 24 RE 12, 22 RB 26, 48 RE 5 (RRX) Kierberg Köln Süd Brühl Erftstadt Euskirchen Gerolstein Bonn Remagen RE 7 RE 6 (RRX) S11 S 6 Volkhovener Weg Blumenberg Wilhelm-Sollmann-Str. Scheibenstr. Nesselrodestr. Boltensternstr. Zoo / Flora Reichenspergerplatz Breslauer Platz / Hbf Dom / Hbf Suevenstr. Deutz Technische Hochschule Kalk Post Kalk Kapelle Köln Hbf Florastr. Lohsestr. Rathaus Deutzer Freiheit Amsterdamer Str./ Gürtel Kinderkrankenhaus Mollwitzstr. Escher Str. Neusser Str./ Gürtel Geldernstr./ Parkgürtel Dormagen Dormagen Chempark Düsseldorf Neuss Tarifgrenze Krefeld Neuss Buchforst Holweide Duckterath Dellbrück Trimbornstr. RE 7 RB 48 S 6 RE 1 (RRX), 5 (RRX) Opladen Leichlingen LEV-Manfort Wuppertal Solingen Stammheim LEV Chempark LEV Mitte LEV-Küppersteg Düsseldorf RB 25 Rösrath Hoffnungsthal Frankfurter Str. RösrathStümpen Steinstr. Airport Businesspark Porz Porz-Wahn Spich Troisdorf RE 8 RB 27 S 12, 19 RE 9 Bonn-Beuel Neuwied Bonn BN-Bad Godesberg Siegburg Hennef Au (Sieg) Gummersbach Lüdenscheid Betzdorf Siegen Chorweiler Nord Meerfeldstr. Longericher Str. Heimersdorf Herforder Str. Altonaer Platz Longerich Mauritiuskirche Moltkestr. Venloer Str. / Gürtel Ehrenfeld Tarifgrenze Tarifgrenze Tarifgrenze Tarifgrenze Tarifgrenze Tarifgrenze Tarifgrenze Tarifgrenze Tarifgrenze Tarifgrenze Tarifgrenze Tarifgrenze Eifelwall/ Stadtarchiv Bf Deutz /LANXESS arena LEV-Rheindorf Stegerwaldsiedlung Koelnmesse Messe/Deutz RE 12, 22 RB 24, 26, 38 5 Heumarkt 12 Zollstock Südfriedhof 7Frechen-Benzelrath 19 Klettenbergpark 1Weiden West 9 Sülz Hermeskeiler Platz 17 Sürth Bf 5 Sparkasse Am Butzweilerhof 3 Görlinger-Zentrum 13 Sülzgürtel 7Zündorf 9Königsforst 4Schlebusch 4Bocklemünd 15 Chorweiler 12 Merkenich 16 Niehl Sebastianstr. S 11 Bergisch Gladbach S 12 Horrem RB 38 RB 25 Hansaring 318 Thielenbruch 1 Bensberg 17 Severinstr. 15 Ubierring RE 6 (RRX) Köln / Bonn Flughafen Sülzburgstr. Universitätsstr. Friesenplatz Longerich Friedhof S 6 Nippes S 6 Worringen Rudolfplatz Bf Deutz/ Messe Rochusplatz Brück Mauspfad Wesseling Aachener Str./ Gürtel S 12 Köln West 14 Keupstr. 1914 Ebertplatz Slabystr. 1813 18 13 Mülheim Wiener Platz Grünstr. Tarifgrenze 5 18 16 1 9 7 1 9 1 11 1 9 7 7 7 7 5 5 5 4 3 4 3 16 18 16 18 18 18 13 13 13 13 13 16 4 3 12 12 15 19 19 12 15 19 12 15 15 4 14 4 3 17 16 16 16 9 9 R E 6 ( R R X ) , 7 RE 1 ( RRX) , 8, 9 RB 2 7, 3 8 S 1 2 , 19 S 6, 1 1 R B 2 4 , 2 6 , 4 8 RE 8, RB 27 RE 1 (RRX), RB 38 RE 8, 9 RE 6 (RRX), RB 27 S 12 RB 25, S 19 RE 1 (RRX), 5 (RRX), 7 S 6,11 S 6 RB 48 14 14 14 R E 5 ( R R X ) , 1 2 , 2 2 118 118 118 18 3 18 N 2024 Bahnen in Köln Rail Services Cologne Infos zur Sanierung der Mülheimer Brücke www.kvb.koeln/bruecke Nach Ende der Sanierung der Mülheimer Brücke werden die Linien 118, 14, 19 entfallen und die Linien 13 und 18 fahren den regulären Linienweg. Information on the renovation of the Mülheim Bridge www.kvb.koeln/bridge After the completion of the renovation of the Mülheim Bridge lines 118, 14 and 19 will be cancelled and lines 13 and 18 will operate on the regular route. Endhaltestelle terminus Merkenich alternative Endhaltestelle alternative terminus Niehl Nord Stand: 2024-04 www.kvb.koeln 0800 6 504030 (free of charge from all German telephone networks) (kostenlos aus allen deutschen Netzen) Regionalbahn regional transit RB RE S-Bahn rail rapid transit S kein barrierefreier Zugang an mind. einer Linie (gilt nur für Straßenbahnen) no barrier-free access on at least one line (only applies to trams) unterirdische Stadtbahnlinie tram / light railway 12 oberirdische Stadtbahnlinie tram / light railway 12 Ersatzbuslinie während der Sanierung der Mülheimer Brücke Replacement bus route during the renovation of the Mülheim Bridge 118 P+R-Platz park and ride Tarifgrenze fare zone boundary Baustelle construction https://www.kvb.koeln/fahrtinfo/liniennetzplaene.html Oliver Bachtler Non-pool-based line planning: a practical analysis of tw-lines EWGT 2024 2 / 13 Cost-minimal Line Planning ▶Apublic transport network (PTN) is an undirected graph. ▶Aline is a simple path in the PTN. ▶Aline concept (L,f)consists of a set of lines Ltogether with frequencies f. Problem ▶Given a PTN with frequencies fmin e,fmax e ▶find a line concept (L,f)that satisfies fmin e≤X ℓ∈L:e∈E(ℓ) fℓ≤fmax e ▶minimising the cost X ℓ∈L fℓ·costℓ =X ℓ∈L fℓ·cfix +X e∈E(ℓ) ce fℓ1=2fℓ2=4 [2,4] [3,6] [4,5] [1,5] [1,4] [1,2] [2,4] [0,3] Oliver Bachtler Non-pool-based line planning: a practical analysis of tw-lines EWGT 2024 3 / 13 Solving the line planning problem ▶Line planning as an IP: min X ℓ∈P costℓ·fℓ fmin e≤X ℓ∈P :e∈E(ℓ) fℓ≤fmax e∀e∈E ▶Simplified by heuristic line pools P⊆ P. ▶tree: uses paths in MSTs between leaves or high-degree vertices. ▶k-sp: uses the kshortest paths between each OD pair and prunes nested lines. ▶number of lines in pool: tree 1-sp 2-sp |P| 66 22 61 16750 Oliver Bachtler Non-pool-based line planning: a practical analysis of tw-lines EWGT 2024 4 / 13 Solving the line planning problem ▶Line planning as an IP: min X ℓ∈P costℓ·fℓ fmin e≤X ℓ∈P :e∈E(ℓ) fℓ≤fmax e∀e∈E ▶Simplified by heuristic line pools P⊆ P. ▶tree: uses paths in MSTs between leaves or high-degree vertices. ▶k-sp: uses the kshortest paths between each OD pair and prunes nested lines. ▶number of lines in pool: tree 1-sp 2-sp |P| 66 22 61 16750 Oliver Bachtler Non-pool-based line planning: a practical analysis of tw-lines EWGT 2024 4 / 13 Solving the line planning problem ▶Line planning as an IP: min X ℓ∈P costℓ·fℓ fmin e≤X ℓ∈P:e∈E(ℓ) fℓ≤fmax e∀e∈E ▶Simplified by heuristic line pools P⊆ P. ▶tree: uses paths in MSTs between leaves or high-degree vertices. ▶k-sp: uses the kshortest paths between each OD pair and prunes nested lines. ▶number of lines in pool: tree 1-sp 2-sp |P| 66 22 61 16750 Oliver Bachtler Non-pool-based line planning: a practical analysis of tw-lines EWGT 2024 4 / 13 Solving the line planning problem ▶Line planning as an IP: min X ℓ∈P costℓ·fℓ fmin e≤X ℓ∈P:e∈E(ℓ) fℓ≤fmax e∀e∈E ▶Simplified by heuristic line pools P⊆ P. ▶tree: uses paths in MSTs between leaves or high-degree vertices. ▶k-sp: uses the kshortest paths between each OD pair and prunes nested lines. ▶number of lines in pool: tree 1-sp 2-sp |P| 66 22 61 16750 Oliver Bachtler Non-pool-based line planning: a practical analysis of tw-lines EWGT 2024 4 / 13 Solving the line planning problem ▶Line planning as an IP: min X ℓ∈P costℓ·fℓ fmin e≤X ℓ∈P:e∈E(ℓ) fℓ≤fmax e∀e∈E ▶Simplified by heuristic line pools P⊆ P. ▶tree: uses paths in MSTs between leaves or high-degree vertices. ▶k-sp: uses the kshortest paths between each OD pair and prunes nested lines. ▶number of lines in pool: tree 1-sp 2-sp |P| 66 22 61 16750 Oliver Bachtler Non-pool-based line planning: a practical analysis of tw-lines EWGT 2024 4 / 13 Solving the line planning problem ▶Line planning as an IP: min X ℓ∈P costℓ·fℓ fmin e≤X ℓ∈P:e∈E(ℓ) fℓ≤fmax e∀e∈E ▶Simplified by heuristic line pools P⊆ P. ▶tree: uses paths in MSTs between leaves or high-degree vertices. ▶k-sp: uses the kshortest paths between each OD pair and prunes nested lines. ▶number of lines in pool: tree 1-sp 2-sp |P| 66 22 61 16750 Oliver Bachtler Non-pool-based line planning: a practical analysis of tw-lines EWGT 2024 4 / 13 Solving the line planning problem ▶Line planning as an IP: min X ℓ∈P costℓ·fℓ fmin e≤X ℓ∈P:e∈E(ℓ) fℓ≤fmax e∀e∈E ▶Simplified by heuristic line pools P⊆ P. ▶tree: uses paths in MSTs between leaves or high-degree vertices. ▶k-sp: uses the kshortest paths between each OD pair and prunes nested lines. ▶number of lines in pool: tree 1-sp 2-sp |P| 66 22 61 16750 Oliver Bachtler Non-pool-based line planning: a practical analysis of tw-lines EWGT 2024 4 / 13 Solving the line planning problem ▶Line planning as an IP: min X ℓ∈P costℓ·fℓ fmin e≤X ℓ∈P:e∈E(ℓ) fℓ≤fmax e∀e∈E ▶Simplified by heuristic line pools P⊆ P. ▶tree: uses paths in MSTs between leaves or high-degree vertices. ▶k-sp: uses the kshortest paths between each OD pair and prunes nested lines. ▶number of lines in pool: tree 1-sp 2-sp |P| 66 22 61 16750 Oliver Bachtler Non-pool-based line planning: a practical analysis of tw-lines EWGT 2024 4 / 13 Solving the line planning problem ▶Line planning as an IP: min X ℓ∈P costℓ·fℓ fmin e≤X ℓ∈P:e∈E(ℓ) fℓ≤fmax e∀e∈E ▶Simplified by heuristic line pools P⊆ P. ▶tree: uses paths in MSTs between leaves or high-degree vertices. ▶k-sp: uses the kshortest paths between each OD pair and prunes nested lines. ▶number of lines in pool: tree 1-sp 2-sp |P| 66 22 61 16750 Oliver Bachtler Non-pool-based line planning: a practical analysis of tw-lines EWGT 2024 4 / 13 Solving the line planning problem ▶Line planning as an IP: min X ℓ∈P costℓ·fℓ fmin e≤X ℓ∈P:e∈E(ℓ) fℓ≤fmax e∀e∈E ▶Simplified by heuristic line pools P⊆ P. ▶tree: uses paths in MSTs between leaves or high-degree vertices. ▶k-sp: uses the kshortest paths between each OD pair and prunes nested lines. ▶number of lines in pool: tree 1-sp 2-sp |P| 66 22 61 16750 Oliver Bachtler Non-pool-based line planning: a practical analysis of tw-lines EWGT 2024 4 / 13 tw-lines [HSS23] Idea: generate all simple paths implicitly Sketch (for a tree): iℓ ir er c1 jr c1,c2 Oliver Bachtler Non-pool-based line planning: a practical analysis of tw-lines EWGT 2024 5 / 13 tw-lines [HSS23] Idea: generate all simple paths implicitly Sketch (for a tree): iℓ ir er c1 jr c1,c2 Oliver Bachtler Non-pool-based line planning: a practical analysis of tw-lines EWGT 2024 5 / 13 tw-lines [HSS23] Idea: generate all simple paths implicitly Sketch (for a tree): iℓ ir er c1 jr c1,c2 Oliver Bachtler Non-pool-based line planning: a practical analysis of tw-lines EWGT 2024 5 / 13 tw-lines [HSS23] Idea: generate all simple paths implicitly Sketch (for a tree): iℓ ir er c1 jr c1,c2 Oliver Bachtler Non-pool-based line planning: a practical analysis of tw-lines EWGT 2024 5 / 13 tw-lines [HSS23] Idea: generate all simple paths implicitly Sketch (for a tree): iℓ ir er c1 jr c1,c2 Oliver Bachtler Non-pool-based line planning: a practical analysis of tw-lines EWGT 2024 5 / 13 tw-lines [HSS23] Idea: generate all simple paths implicitly Sketch (for a tree): iℓ ir er c1 jr c1,c2 Oliver Bachtler Non-pool-based line planning: a practical analysis of tw-lines EWGT 2024 5 / 13 tw-lines [HSS23] Idea: generate all simple paths implicitly Sketch (for a tree): iℓ ir er c1 jr c1,c2 Oliver Bachtler Non-pool-based line planning: a practical analysis of tw-lines EWGT 2024 5 / 13 Outline Line Planning Computational Experiments Circular cities Graphs of low tree-width Oliver Bachtler Non-pool-based line planning: a practical analysis of tw-lines EWGT 2024 6 / 13 Experiment setup Instances ▶PTNs: circular cities (3-5 spokes, at least 2 rings, up to 90 vertices, total: 195) and low-treewidth graphs ▶ce: edge length in drawing ▶cfix: in {10,25,50}(circular cities), 10 |E|Pe∈Ece(low-treewidth graphs) Neumarkt Leyendeckerstr. Akazienweg Wolffsohnstr. Westfriedhof Ollenhauerring Nußbaumerstr. Subbelrather Str. / Gürtel Liebigstr. Hans-Böckler-Platz/ Bf West Körnerstr. Piusstr. Bonn Severinsbrücke Drehbrücke Poller Kirchweg Raiffeisenstr. Poll Salmstr. Poll Baumschulenweg Westhoven Kölner Str. Westhoven Berliner Str. Ensen Gilgaustr. Ensen Kloster Porz Steinstr. Porz Markt Rosenhügel Vingst Ostheim Autobahn Steinweg Porzer Str. Rath/Heumar Röttgensweg Schönhauser Str. Bayenthalgürtel Chlodwigplatz HürthKalscheuren Bonner Wall Godorf Bf Wesseling Nord Wesseling Süd Urfeld Rodenkirchen Bf Siegstr. Michaelshoven Geestemünder Str. Fordwerke Süd Fordwerke Mitte Fordwerke Nord Niehl Nord Von-Sparr-Str. Mülheim Berliner Str. Im Weidenbruch Am Emberg Leuchterstr. Buchforst Waldecker Str. Buchheim Herler Str. Buchheim Frankfurter Str. Wichheimer Str. Maria-Himmelfahrt-Str. Holweide Vischeringstr. Neufelder Str. (Krankenhaus Holweide) Dellbrück Mauspfad Dellbrück Hauptstr. Appellhofplatz (Breite Str.) Appellhofplatz (Zeughaus) Christophstr./ Mediapark Kartäuserhof Eifelstr. Heinrich-Lübke-Ufer Ulrepforte Zülpicher Platz Weißhausstr. Arnulfstr. Weyertal Dürener Str./ Gürtel Wüllnerstr. Zülpicher Str./ Gürtel Gleueler Str./ Gürtel Mommsenstr. Melaten Berrenrather Str./ Gürtel Euskirchener Str. Lindenburg (Universitätsklinik) Poststr. Dasselstr. /Bf Süd Efferen Kiebitzweg HürthHermülheim Fischenich Brühl-Vochem Brühl Nord Brühl Mitte Universität Bf Mülheim Pohligstr. Eifelplatz Herthastr. Gottesweg Fuldaer Str. Sportpark Höhenberg Kalker Friedhof Merheim Flehbachstr. Lustheide Refrath Kippekausen Frankenforst Neuenweg Kölner Str. Im Hoppenkamp Maarweg Clarenbachstift Eupener Str. Alter Militärring RheinEnergieSTADION Junkersdorf Mohnweg Bahnstr. Weiden Zentrum Weiden Römergrab Brahmsstr. Stüttgenhof Haus Vorst Marsdorf Frechen Kirche Frechen Bf Mühlengasse Frechen Rathaus Lenauplatz Iltisstr. Margaretastr. Rektor-Klein-Str. Alter Flughafen Butzweilerhof IKEA Am Butzweilerhof Odenthaler Str. Merkenich Mitte Schaffrathsgasse Zollstockgürtel Rhein Gutenbergstr. Barbarossaplatz Weinsbergstr./ Gürtel Melatengürtel 16 18 1 9 15 3 12 1 7 1 4 7 RB 38 RE 8 RB 27 RE 1 (RRX), 9 S19 Bedburg Aachen Düren Mönchengladbach Müngersdorf Technologiepark Lövenich FrechenKönigsdorf Pulheim RB 24 RE 12, 22 RB 26, 48 RE 5 (RRX) Kierberg Köln Süd Brühl Erftstadt Euskirchen Gerolstein Bonn Remagen RE 7 RE 6 (RRX) S11 S 6 Volkhovener Weg Blumenberg Wilhelm-Sollmann-Str. Scheibenstr. Nesselrodestr. Boltensternstr. Zoo / Flora Reichenspergerplatz Breslauer Platz / Hbf Dom / Hbf Suevenstr. Deutz Technische Hochschule Kalk Post Kalk Kapelle Köln Hbf Florastr. Lohsestr. Rathaus Deutzer Freiheit Amsterdamer Str./ Gürtel Kinderkrankenhaus Mollwitzstr. Escher Str. Neusser Str./ Gürtel Geldernstr./ Parkgürtel Dormagen Dormagen Chempark Düsseldorf Neuss Tarifgrenze Krefeld Neuss Buchforst Holweide Duckterath Dellbrück Trimbornstr. RE 7 RB 48 S 6 RE 1 (RRX), 5 (RRX) Opladen Leichlingen LEV-Manfort Wuppertal Solingen Stammheim LEV Chempark LEV Mitte LEV-Küppersteg Düsseldorf RB 25 Rösrath Hoffnungsthal Frankfurter Str. RösrathStümpen Steinstr. Airport Businesspark Porz Porz-Wahn Spich Troisdorf RE 8 RB 27 S 12, 19 RE 9 Bonn-Beuel Neuwied Bonn BN-Bad Godesberg Siegburg Hennef Au (Sieg) Gummersbach Lüdenscheid Betzdorf Siegen Chorweiler Nord Meerfeldstr. Longericher Str. Heimersdorf Herforder Str. Altonaer Platz Longerich Mauritiuskirche Moltkestr. Venloer Str. / Gürtel Ehrenfeld Tarifgrenze Tarifgrenze Tarifgrenze Tarifgrenze Tarifgrenze Tarifgrenze Tarifgrenze Tarifgrenze Tarifgrenze Tarifgrenze Tarifgrenze Tarifgrenze Eifelwall/ Stadtarchiv Bf Deutz /LANXESS arena LEV-Rheindorf Stegerwaldsiedlung Koelnmesse Messe/Deutz RE 12, 22 RB 24, 26, 38 5 Heumarkt 12 Zollstock Südfriedhof 7Frechen-Benzelrath 19 Klettenbergpark 1Weiden West 9 Sülz Hermeskeiler Platz 17 Sürth Bf 5 Sparkasse Am Butzweilerhof 3 Görlinger-Zentrum 13 Sülzgürtel 7Zündorf 9Königsforst 4Schlebusch 4Bocklemünd 15 Chorweiler 12 Merkenich 16 Niehl Sebastianstr. S 11 Bergisch Gladbach S 12 Horrem RB 38 RB 25 Hansaring 318 Thielenbruch 1 Bensberg 17 Severinstr. 15 Ubierring RE 6 (RRX) Köln / Bonn Flughafen Sülzburgstr. Universitätsstr. Friesenplatz Longerich Friedhof S 6 Nippes S 6 Worringen Rudolfplatz Bf Deutz/ Messe Rochusplatz Brück Mauspfad Wesseling Aachener Str./ Gürtel S 12 Köln West 14 Keupstr. 1914 Ebertplatz Slabystr. 1813 18 13 Mülheim Wiener Platz Grünstr. Tarifgrenze 5 18 16 1 9 7 1 9 1 11 1 9 7 7 7 7 5 5 5 4 3 4 3 16 18 16 18 18 18 13 13 13 13 13 16 4 3 12 12 15 19 19 12 15 19 12 15 15 4 14 4 3 17 16 16 16 9 9 R E 6 ( R R X ) , 7 RE 1 ( RRX) , 8, 9 RB 2 7, 3 8 S 1 2 , 19 S 6, 1 1 R B 2 4 , 2 6 , 4 8 RE 8, RB 27 RE 1 (RRX), RB 38 RE 8, 9 RE 6 (RRX), RB 27 S 12 RB 25, S 19 RE 1 (RRX), 5 (RRX), 7 S 6,11 S 6 RB 48 14 14 14 R E 5 ( R R X ) , 1 2 , 2 2 118 118 118 18 3 18 N 2024 Bahnen in Köln Rail Services Cologne Infos zur Sanierung der Mülheimer Brücke www.kvb.koeln/bruecke Nach Ende der Sanierung der Mülheimer Brücke werden die Linien 118, 14, 19 entfallen und die Linien 13 und 18 fahren den regulären Linienweg. Information on the renovation of the Mülheim Bridge www.kvb.koeln/bridge After the completion of the renovation of the Mülheim Bridge lines 118, 14 and 19 will be cancelled and lines 13 and 18 will operate on the regular route. Endhaltestelle terminus Merkenich alternative Endhaltestelle alternative terminus Niehl Nord Stand: 2024-04 www.kvb.koeln 0800 6 504030 (free of charge from all German telephone networks) (kostenlos aus allen deutschen Netzen) Regionalbahn regional transit RB RE S-Bahn rail rapid transit S kein barrierefreier Zugang an mind. einer Linie (gilt nur für Straßenbahnen) no barrier-free access on at least one line (only applies to trams) unterirdische Stadtbahnlinie tram / light railway 12 oberirdische Stadtbahnlinie tram / light railway 12 Ersatzbuslinie während der Sanierung der Mülheimer Brücke Replacement bus route during the renovation of the Mülheim Bridge 118 P+R-Platz park and ride Tarifgrenze fare zone boundary Baustelle construction https://www.kvb.koeln/fahrtinfo/liniennetzplaene.html Oliver Bachtler Non-pool-based line planning: a practical analysis of tw-lines EWGT 2024 7 / 13 Experiment setup Instances ▶PTNs: circular cities and low-treewidth graphs (width 2-4, up to 770 vertices, total: 43) ▶ce: edge length in drawing ▶cfix: in {10,25,50}(circular cities), 10 |E|Pe∈Ece(low-treewidth graphs) Jaakko Sakari Reinikainen (Ulayiti), CC BY-SA 3.0, http://creativecommons.org/licenses/by-sa/3.0/, via Wikimedia Commons Oliver Bachtler Non-pool-based line planning: a practical analysis of tw-lines EWGT 2024 7 / 13 Running times of tw-lines on circular cities Oliver Bachtler Non-pool-based line planning: a practical analysis of tw-lines EWGT 2024 9 / 13 Running times of tw-lines on circular cities Oliver Bachtler Non-pool-based line planning: a practical analysis of tw-lines EWGT 2024 9 / 13 Running times of the heuristics on circular cities Treewidth 3 Oliver Bachtler Non-pool-based line planning: a practical analysis of tw-lines EWGT 2024 10 / 13 Running times of the heuristics on circular cities Treewidth 4 Oliver Bachtler Non-pool-based line planning: a practical analysis of tw-lines EWGT 2024 10 / 13 Running times of the heuristics on circular cities Treewidth 5 Oliver Bachtler Non-pool-based line planning: a practical analysis of tw-lines EWGT 2024 10 / 13 Solution quality on low-treewidth graphs Treewidth 2 Oliver Bachtler Non-pool-based line planning: a practical analysis of tw-lines EWGT 2024 11 / 13 Solution quality on low-treewidth graphs Treewidth 3 Oliver Bachtler Non-pool-based line planning: a practical analysis of tw-lines EWGT 2024 11 / 13 Solution quality on low-treewidth graphs Treewidth 4 Oliver Bachtler Non-pool-based line planning: a practical analysis of tw-lines EWGT 2024 11 / 13 Running times of tw-lines on low-treewidth graphs Oliver Bachtler Non-pool-based line planning: a practical analysis of tw-lines EWGT 2024 12 / 13 Summary We saw that: ▶tw-lines can do line planning on all lines. ▶It achieves better solutions than approaches based on line pool generation. ▶Its running time is comparable to the heuristics or better for small tree-width. Future work ▶Expand tw-lines to terminals. ▶Incorporate passenger routing. Contact: [email protected] Neumarkt Leyendeckerstr. Akazienweg Wolffsohnstr. Westfriedhof Ollenhauerring Nußbaumerstr. Subbelrather Str. / Gürtel Liebigstr. Hans-Böckler-Platz/ Bf West Körnerstr. Piusstr. Bonn Severinsbrücke Drehbrücke Poller Kirchweg Raiffeisenstr. Poll Salmstr. Poll Baumschulenweg Westhoven Kölner Str. Westhoven Berliner Str. Ensen Gilgaustr. Ensen Kloster Porz Steinstr. Porz Markt Rosenhügel Vingst Ostheim Autobahn Steinweg Porzer Str. Rath/Heumar Röttgensweg Schönhauser Str. Bayenthalgürtel Chlodwigplatz HürthKalscheuren Bonner Wall Godorf Bf Wesseling Nord Wesseling Süd Urfeld Rodenkirchen Bf Siegstr. Michaelshoven Geestemünder Str. Fordwerke Süd Fordwerke Mitte Fordwerke Nord Niehl Nord Von-Sparr-Str. Mülheim Berliner Str. Im Weidenbruch Am Emberg Leuchterstr. Buchforst Waldecker Str. Buchheim Herler Str. Buchheim Frankfurter Str. Wichheimer Str. Maria-Himmelfahrt-Str. Holweide Vischeringstr. Neufelder Str. (Krankenhaus Holweide) Dellbrück Mauspfad Dellbrück Hauptstr. Appellhofplatz (Breite Str.) Appellhofplatz (Zeughaus) Christophstr./ Mediapark Kartäuserhof Eifelstr. Heinrich-Lübke-Ufer Ulrepforte Zülpicher Platz Weißhausstr. Arnulfstr. Weyertal Dürener Str./ Gürtel Wüllnerstr. Zülpicher Str./ Gürtel Gleueler Str./ Gürtel Mommsenstr. Melaten Berrenrather Str./ Gürtel Euskirchener Str. Lindenburg (Universitätsklinik) Poststr. Dasselstr. /Bf Süd Efferen Kiebitzweg HürthHermülheim Fischenich Brühl-Vochem Brühl Nord Brühl Mitte Universität Bf Mülheim Pohligstr. Eifelplatz Herthastr. Gottesweg Fuldaer Str. Sportpark Höhenberg Kalker Friedhof Merheim Flehbachstr. Lustheide Refrath Kippekausen Frankenforst Neuenweg Kölner Str. Im Hoppenkamp Maarweg Clarenbachstift Eupener Str. Alter Militärring RheinEnergieSTADION Junkersdorf Mohnweg Bahnstr. Weiden Zentrum Weiden Römergrab Brahmsstr. Stüttgenhof Haus Vorst Marsdorf Frechen Kirche Frechen Bf Mühlengasse Frechen Rathaus Lenauplatz Iltisstr. Margaretastr. Rektor-Klein-Str. Alter Flughafen Butzweilerhof IKEA Am Butzweilerhof Odenthaler Str. Merkenich Mitte Schaffrathsgasse Zollstockgürtel Rhein Gutenbergstr. Barbarossaplatz Weinsbergstr./ Gürtel Melatengürtel 16 18 1 9 15 3 12 1 7 1 4 7 RB 38 RE 8 RB 27 RE 1 (RRX), 9 S19 Bedburg Aachen Düren Mönchengladbach Müngersdorf Technologiepark Lövenich FrechenKönigsdorf Pulheim RB 24 RE 12, 22 RB 26, 48 RE 5 (RRX) Kierberg Köln Süd Brühl Erftstadt Euskirchen Gerolstein Bonn Remagen RE 7 RE 6 (RRX) S11 S 6 Volkhovener Weg Blumenberg Wilhelm-Sollmann-Str. Scheibenstr. Nesselrodestr. Boltensternstr. Zoo / Flora Reichenspergerplatz Breslauer Platz / Hbf Dom / Hbf Suevenstr. Deutz Technische Hochschule Kalk Post Kalk Kapelle Köln Hbf Florastr. Lohsestr. Rathaus Deutzer Freiheit Amsterdamer Str./ Gürtel Kinderkrankenhaus Mollwitzstr. Escher Str. Neusser Str./ Gürtel Geldernstr./ Parkgürtel Dormagen Dormagen Chempark Düsseldorf Neuss Tarifgrenze Krefeld Neuss Buchforst Holweide Duckterath Dellbrück Trimbornstr. RE 7 RB 48 S 6 RE 1 (RRX), 5 (RRX) Opladen Leichlingen LEV-Manfort Wuppertal Solingen Stammheim LEV Chempark LEV Mitte LEV-Küppersteg Düsseldorf RB 25 Rösrath Hoffnungsthal Frankfurter Str. RösrathStümpen Steinstr. Airport Businesspark Porz Porz-Wahn Spich Troisdorf RE 8 RB 27 S 12, 19 RE 9 Bonn-Beuel Neuwied Bonn BN-Bad Godesberg Siegburg Hennef Au (Sieg) Gummersbach Lüdenscheid Betzdorf Siegen Chorweiler Nord Meerfeldstr. Longericher Str. Heimersdorf Herforder Str. Altonaer Platz Longerich Mauritiuskirche Moltkestr. Venloer Str. / Gürtel Ehrenfeld Tarifgrenze Tarifgrenze Tarifgrenze Tarifgrenze Tarifgrenze Tarifgrenze Tarifgrenze Tarifgrenze Tarifgrenze Tarifgrenze Tarifgrenze Tarifgrenze Eifelwall/ Stadtarchiv Bf Deutz /LANXESS arena LEV-Rheindorf Stegerwaldsiedlung Koelnmesse Messe/Deutz RE 12, 22 RB 24, 26, 38 5 Heumarkt 12 Zollstock Südfriedhof 7Frechen-Benzelrath 19 Klettenbergpark 1Weiden West 9 Sülz Hermeskeiler Platz 17 Sürth Bf 5 Sparkasse Am Butzweilerhof 3 Görlinger-Zentrum 13 Sülzgürtel 7Zündorf 9Königsforst 4Schlebusch 4Bocklemünd 15 Chorweiler 12 Merkenich 16 Niehl Sebastianstr. S 11 Bergisch Gladbach S 12 Horrem RB 38 RB 25 Hansaring 318 Thielenbruch 1 Bensberg 17 Severinstr. 15 Ubierring RE 6 (RRX) Köln / Bonn Flughafen Sülzburgstr. Universitätsstr. Friesenplatz Longerich Friedhof S 6 Nippes S 6 Worringen Rudolfplatz Bf Deutz/ Messe Rochusplatz Brück Mauspfad Wesseling Aachener Str./ Gürtel S 12 Köln West 14 Keupstr. 1914 Ebertplatz Slabystr. 1813 18 13 Mülheim Wiener Platz Grünstr. Tarifgrenze 5 18 16 1 9 7 1 9 1 11 1 9 7 7 7 7 5 5 5 4 3 4 3 16 18 16 18 18 18 13 13 13 13 13 16 4 3 12 12 15 19 19 12 15 19 12 15 15 4 14 4 3 17 16 16 16 9 9 R E 6 ( R R X ) , 7 RE 1 ( RRX) , 8, 9 RB 2 7, 3 8 S 1 2 , 19 S 6, 1 1 R B 2 4 , 2 6 , 4 8 RE 8, RB 27 RE 1 (RRX), RB 38 RE 8, 9 RE 6 (RRX), RB 27 S 12 RB 25, S 19 RE 1 (RRX), 5 (RRX), 7 S 6,11 S 6 RB 48 14 14 14 R E 5 ( R R X ) , 1 2 , 2 2 118 118 118 18 3 18 N 2024 Bahnen in Köln Rail Services Cologne Infos zur Sanierung der Mülheimer Brücke www.kvb.koeln/bruecke Nach Ende der Sanierung der Mülheimer Brücke werden die Linien 118, 14, 19 entfallen und die Linien 13 und 18 fahren den regulären Linienweg. Information on the renovation of the Mülheim Bridge www.kvb.koeln/bridge After the completion of the renovation of the Mülheim Bridge lines 118, 14 and 19 will be cancelled and lines 13 and 18 will operate on the regular route. Endhaltestelle terminus Merkenich alternative Endhaltestelle alternative terminus Niehl Nord Stand: 2024-04 www.kvb.koeln 0800 6 504030 (free of charge from all German telephone networks) (kostenlos aus allen deutschen Netzen) Regionalbahn regional transit RB RE S-Bahn rail rapid transit S kein barrierefreier Zugang an mind. einer Linie (gilt nur für Straßenbahnen) no barrier-free access on at least one line (only applies to trams) unterirdische Stadtbahnlinie tram / light railway 12 oberirdische Stadtbahnlinie tram / light railway 12 Ersatzbuslinie während der Sanierung der Mülheimer Brücke Replacement bus route during the renovation of the Mülheim Bridge 118 P+R-Platz park and ride Tarifgrenze fare zone boundary Baustelle construction https://www.kvb.koeln/fahrtinfo/liniennetzplaene.html Jaakko Sakari Reinikainen (Ulayiti), CC BY-SA 3.0, http://creativecommons.org/licenses/by-sa/3.0/, via Wikimedia Commons Oliver Bachtler Non-pool-based line planning: a practical analysis of tw-lines EWGT 2024 13 / 13