traveling cyclist 574

math & cycling

die hier beschriebene aufgabe stellt eine symbiose zwischen mathematik und sport her. mit mathematischen methoden wird eine optimierte route zwischen den 573 gemeinden niederöstereichs berechnet, die mit dem rennrad in mehreren etappen abgefahren wird. die idee basiert auf dem traveling salesman problem, nur dass der salesman ein radfahrer ist, und die reisestrecke tatsächlich zu bewältigen ist.

die karte links zeigt die 23 etappen. jeder schwarze punkt entspricht dem zentrum einer gemeinde. koordinaten und radverbindungen werden mit der directions service api von google maps im travel mode bicycling ermittelt. basierend auf den so gewonnenen daten wird die kürzeste route mit lkh, version 2.0.9 berechnet. die detailplanung und etappeneinteilung erfolgt mit komoot.de. abgefahren wird die route mit meinem radley helium slx mit übersetzung 36-52/11-28.

contact: michael@kenn.at

introduction

reisen sind in pandemiezeiten schwierig, auch radreisen. deshalb habe ich nach einer aufgabenstellung gesucht, die längere radetappen ermöglicht ohne weit anreisen zu müssen. herausgekommen ist dabei das traveling cyclist problem 574, eine symbiose aus mathematik und rennradfahren.

es sollen die 573 gemeinden niederösterreichs mit dem rennrad abgefahren werden. der grundgedanke folgt dem traveling salesman problem (tsp), d.h. es soll ein möglichst kurzer, zusammenhängender weg durch alle niederösterreichischen gemeinden gefunden werden. start und ziel ist wien, deshalb 574.

was das hier gestellte traveling cyclist problem (tcp) vom klassischen tsp unterscheidet sind (neben der tatsache, dass die route auch gefahren werden muss) eine reihe sinnvoller nebenbedingungen. als distanz zwischen zwei gemeinden gilt nicht die luftlinie sondern die kürzeste asphaltierte radroute die auf große straßen verzichtet. diese distanz darf auch asymmetrisch sein, d.h. der weg von A nach B muss nicht gleich lang sein dem weg von B nach A. die gesamte strecke soll in 23 etwa gleichlange segmente unterteilt werden, die in tagesetappen bewältigbar sind. um nicht die gesamte strecke auf einmal fahren zu müssen sollen diese etappen jeweils bei bahnhöfen oder schnellbahnstationen mit bestmöglicher verbindung nach wien enden und gleichzeit startort für die nächste etappe sein.

das directions service von google maps liefert neben radwegdistanzen auch voraussichtliche reisezeit und höhenmeter zwischen den gemeinden. diese information soll nicht in die optimierung eingehen, höhenmeter sind radfahrtechnisch ausdrücklich willkommen.

als besondere herausforderung hat sich die definition des zentrums einer gemeinde herausgestellt, insbesonders weil sich die 573 gemeinden niederösterreichs in nochmals 3040 katastralgemeinden untergliedern. nur für 116 gemeinden ist in wikipedia explizit ein hauptort ausgewiesen. aktuell verwende ich im allgemeinen die koordinaten des gemeindeamts als definition für das zentrum einer gemeinde.

eine weitere schwierigkeit besteht darin, dass die optimierte streckenführung einige sackgassen beinhaltet. in diesen fällen wird die strecke so umgeplant dass, wo möglich, das zentrum der gemeinde nicht angefahren sondern durchfahren wird. wenn irgendwie möglich soll keine straße, auch nicht in entgegengesetzter richtung, doppelt befahren werden.

ein letzter wesentlicher punkt ist die bedingung, dass die strecke zur gänze uneingeschränkt mit rennrad befahrbar sein muss. das betrifft im wesentlichen fähren, die nicht verwendet werden dürfen. in der detailplanung war ich bemüht stufen, kuhgatter, schotterpassagen, fahrverbote und ähnliches zu vermeiden.

summary

• die zentren der 573 gemeinden niederösterreichs sollen mit rennrad chronologisch durchfahren werden
• die gesamtstrecke soll möglichst kurz sein, höhenmeter und zeit sind egal, berge willkommen
• die route soll mit rennrad befahrbar sein und weitgehend auf hauptstraßen verzichten - kein schotter
• die einzelnen etappen sollen als tagesetappen durchführbar sein und guten anschluß ans schienennetz haben
• fähren sind nicht erlaubt, jeder meter muss gefahren werden
• die route soll mathematisch positiv (gegen den uhrzeigersinn) von wien nach wien führen und über keine straße doppelt führen

execution

abgefahren bin ich die 23 etappen zwischen 26.märz und 10.juli 2021. auf der eigentlichen route habe ich dabei laut sigma rox gps 11.0 insgesamt 3817.88 kilometer und 45931 höhenmeter in 147:41:12 stunden (schnitt 25.85km/h) absolviert. dabei habe ich 66564 kcal verbrannt. auf 7 etappen wurde ich zumindest teilweise begleitet.

mit ausnahme der 9.etappe großgöttfritz - waldhausen, die wir zu zweit mit auto organisieren mussten, habe ich zur an- und abreise zu den etappenorten ausschließlich rad und bahn benutzt. für an- und abreise zu bahnhöfen habe ich zusätzlich 112.26 kilometer in wien und 175.07 kilometer in niederösterreich zurückgelegt. daraus ergibt sich eine durchschnittliche tagesleistung von 178.49 kilometer. insgesamt haben sich mit der öbb vorteilscard 66 kosten von €411.30 für transport ergeben.

post processing

eine liste von anmerkungen und aktuell noch offenen punkten die strecke betreffend findet sich hier.
eine provisorisches roadbook findet sich hier. distanzen und höhenmeter sind aktuell noch mit matlab interpoliert und ungenau.
for developers: coordinates, road points, distance matrix, parameter files, ... demnächst.