En algoritm för pålitliga rutter i kollektivtrafiken

Sammanfattning: I kollektivtrafiken uppstår det ofta förseningar. Det kan skapa frustration hos kollektivtrafikanvändarna som planerat en resa som innehåller byten och de missar anslutningen för att turen till bytespunkten ankom sent. Detta arbete har som syfte att skapa en ruttplaneringsalgoritm för kollektivtrafikanvändarna som löser det pålitliga ruttproblemet genom att planera pålitliga och attraktiva rutter i kollektivtrafiken. Denna ruttplaneringsalgoritm är intressant för användaren för att denne med viss säkerhet ska hinna med ett byte i hennes resrutt. Detta kan också vara användbart för en aktör inom kollektivtrafiken när denne vill sätta rätt priser, eller resegarantier för att kunna garantera deras kunder att de kan utföra sina resor som planerat. Algoritmen opererar på ett tidsexpanderande nätverk där noderna representerar både en tid och hållplats. Algoritmen undersöker pålitligheten av de k kortaste rutterna i nätverket. Om någon rutt har ett byte med för kort väntetid så att bytet klassas som opålitligt så genereras en ny väg från bytespunkten så att det finns mer väntetid. Ett byte klassas som opålitligt då den förväntade förseningen tillsammans med en minsta bytestid överstiger väntetiden på hållplatsen. Den kortaste av de pålitliga rutterna som algoritmen har hittat presenteras för användaren. Om restiden för en pålitlig rutt är för lång så blir den resan oattraktiv för en kollektivtrafikanvändare och då väljs den snabbaste av de opålitliga rutterna istället att presenteras för användaren. För att testa algoritmen så byggdes först ett nätverk av tidtabellsdata för kollektivtrafiken i Norrköping. Därefter valdes fyra testresor ut som algoritmen skulle få testas på. Start och sluthållplatserna för testresorna hade olika ankomst- och avgångsfrekvenser. Ett antal experiment konstruerades där olika parametrar och resor skulle variera för att kunna analysera hur algoritmen planerade resor därefter. Två olika lognormala fördelningsfunktioner på ankomstförsening testades, konfidensgrader, en parameter Y som anger hur mycket längre en pålitlig rutt får vara än den sabbaste opålitliga rutten. Samt en parameter K som anger hur många rutter algoritmen ska undersöka. Konfidensgraderna användes på de lognormala fördelningsfunktionerna för att få ut en förväntad försening till en bytespunkt. Den ena fördelningsfunktionen gav kortare förväntad försening än den andra vilket gjorde att restiderna blev kortare för den ena än för den andra. Med en högre konfidensgrad så blev restiderna i genomsnitt längre förutom några undantagsfall, vilket berodde på hur algoritmen söker resor i nätverket. Med ett högre värde på Y så accepterades högre restider för pålitliga rutter. I vissa fall spelade inte Y någon roll eftersom algoritmen lyckades hitta pålitliga rutter som hade samma restid som den snabbaste opålitliga rutten. Slutligen, i experimenten av K blev resultatet att de flesta pålitliga resor hittades bland de tio första resorna som algoritmen undersökte