Optimal route planning for hitchhiking

Abstract

In this thesis, we considered a problem of optimal route planning for hitchhikers. We formalized the hitchhiker's problem and proposed a graph-based model to represent the set of all possible travel options for a hitchhiker. We developed a hitchhiking traffic model with simulated traffic and proposed pick-up locations on a country scale. We formalized hitchhiker's route planning strategy which includes stochastic and time-dependent waiting times as path program and developed a route recommender system to find the optimal path program for a given source, destination, time. We included various objective functions for optimal path programs such as expected travel time or minimising maximum possible travel time. We applied various heuristics to construct graphs of reduced size while preserving optimal path programs and our experiments for selected countries have proved to be a significant improvement in query running times while preserving optimal travel time. We analysed how various spatial factors influence the success of hitchhikers at certain pick-up locations, making some of them more suitable and thus having less waiting time. We crawled a large dataset of hitchhiking locations from Hitchwiki website and analysed multiple features such as road type or distance to amenities. Finally, we developed a classification model to estimate suitable pick-up locations. Our findings will be a basis of long-distance ridesharing application system that includes hitchhiking.