Shortest path algorithms for PSR group

Design Team Members: Jean-Thomas Hardy

Supervisor: Paul H. Calamai

Background

Advanced traveler information systems are part of the growing multi-billion dollars Intelligent Transport Systems (ITS) industry. The focus of the ITS industry is the development of faster, safer and quieter transportation systems. Improvements in transportation systems translate in sizable economic impact for local economies by decreasing travel times for goods and people and generally increasing the efficiency of good transfers.

Project description

PSR Group is developing Open Road, an Advanced Traveler Information System for the city of Toronto. The purpose of this project is to develop optimization algorithms to perform point-to-point optimization within Open Road. Point-to-point optimization is the main decision making tool for end-users. By providing the shortest path between user-defined locations, Open Road helps end-users in making wise travel decisions. These decisions are based on integrated real-time traffic data obtained from different traffic monitoring systems in the Greater Toronto Area.

Open Road, and its optimization functionality, were unveiled at the World Congress on ITS in November. The development of efficient optimization algorithms is very important prior to commercial release of Open Road in order to reach a broad user base. The remainder of this workshop will be spent on increasing the efficiency of the developed algorithms.

Design methodology

A thorough review of optimization approaches in modern transportation applications and interaction with leading experts in the field of dynamic shortest path optimization has yielded a promising list of algorithms. Implementation of these leading-edge algorithms is expected to reduce optimization times by a factor of 5 in comparison with the current algorithms, thus drastically enhancing the experience of end-users, especially for those who do not benefit from the performance of high-end computers.