Stochastic vehicle routing on SUMO

Abstract

Shortest path finding has always been a popular topic for many researchers from different fields, particularly the automobile field. Often, users are concerned with finding a path that takes the shortest travel time. However, there are many factors that will affect the time taken to reach the destination. Researchers had proposed stochastic shortest path finding algorithms in hope to solve the problem effectively. This project aims to implement an already proposed data driven stochastic vehicle routing algorithm on SUMO, which is a traffic simulator. The objective of the simulator is to provide visual demonstration of the algorithm to the stakeholders who have no technical background. The simulator will also help the researcher to improve on the algorithm. The simulator will piece multiple factors together to provide a more realistic simulation which will help the researcher to visualize unforeseen situations or problems that would not be noticeable without a simulator. The proposed algorithm determines a path which maximizes the probability of arriving on time given a deadline, by reformulating the original problem into a cardinality minimization problem. L1 norm minimization is then applied to solve the cardinality minimization problem. After the reformulation, the problem becomes a mixed integer linear programming problem, which solutions are well studied and available.