A study and implementation of routing algorithms

• Main Author: Looi, Aaron Seng Kit
• Other Authors: Dusit Niyato
• Format: Final Year Project
• Language: English
• Published: 2016
• Subjects: DRNTU::Engineering
• Online Access: http://hdl.handle.net/10356/66651
• Institution: Nanyang Technological University

This Final Year Project seeks to understand the routing methodologies and algorithms in search of an optimal solution to aid in solving the issue of being able to obtain the most optimal path for a vehicle to travel to multiple destinations. Multi-destination routing is a key focus area in the exploration of autonomous driving technologies as well as optimization of Global Positioning System routing to better aid drivers to search for the most optimal path available. This report will investigate 3 areas of interest namely: (1) The Travelling Salesman Problem, (2) Travelling Salesman Path Problem and (3) Probabilistic Travelling Salesman Path Problem. The aim of this project is to have an understanding of routing algorithms and develop some of the algorithms for analysis and improvements to develop constraints applicable to the real world that will enhance the search for an optimal solution to a vehicle routing problem. This project was developed in three stages relating to the 3 areas of interest, in order: (1) Travelling Salesman Problem, (2) Travelling Salesman Path Problem and (3) Probabilistic Travelling Salesman Path Problem. The project includes the development of the algorithms and the results of the implementation for the various algorithms for comparison and further optimization. The foundation algorithms are based on the TSP and can be used in relation to ultimately solve the PTSP optimization which will be able to determine a route resulting in the least amount of travel time taking into account real world constraints such as parking.