Implementation of a stochastic routing service

• Main Author: Yang, Wanqing
• Other Authors: Dusit Niyato
• Format: Final Year Project
• Language: English
• Published: 2015
• Subjects: DRNTU::Engineering::Computer science and engineering::Software::Software engineering
• Online Access: http://hdl.handle.net/10356/62623
• Institution: Nanyang Technological University

This Final Year Project is a collaboration work with BMW Group and the Intelligence Mobility research team at NTU-BMW Future Mobility Lab. It aims to develop a stochastic traffic router to integrate onto BMW’s traffic simulator QTrip, meanwhile assist the team’s visualisation needs on road maps, such as graph clustering. In contrast to conventional shortest path or smallest travel time routing, stochastic routing algorithms recognise the uncertainties of traffic with the goal to maximise the probability of arrival on time. In this project, Cardinality Minimisation and Partial Lagrange Multiplier approaches are used to formulate the stochastic routing problem into Mixed Integer Linear Programming (MILP) and Linear Programming (LP) respectively, and solved by solvers in MATLAB and GAMS. Performance testing is conducted to compare the response time of each solution, and improvement is made on the MATLAB-LP solution to finally make stochastic routing feasible on long distance meanwhile satisfy the performance requirement. In the end, stochastic routing based on clusters is briefly discussed as a future direction beyond this project, both theory and implementation-wise.