AI Success Stories
KMB: Bus Timetabling
Project Summary:
- client: Kowloon Motor Bus Company
- application: bus timetabling
- AI technology: constraint programming
Introduction
Our unique AI timetabling and scheduling algorithms allow us to generate bus timetables and duty assignments in seconds compared with hours required by traditional systems. Our software has been proven to produce better results for all the different route types operated by the largest privately held Bus Company in the world - the Kowloon Motor Bus Company.
Timetabling and duty assignments are difficult operations research problems. CityU has developed a unique algorithm that combines both processes into one using constraint-based and heuristic-based optimization
Our Client
The Kowloon Motor Bus Company (KMB) is the world's largest privately held Bus Company and has been serving Hong Kong for over 66 years since 1933. KMB employs over 7,500 bus drivers and operates over 3,800 buses that service more than 380 routes. KMB has always aimed at providing safe, reliable, and timely bus services to the public of Hong Kong.
Business Needs
To meet public transportation demands of a highly dynamic and vibrant city like Hong Kong, the Bus Company must constantly adjust its bus timetables and routes to support the growing and changing needs of Hong Kong. Previously, KMB was using an aging bus timetabling system that was installed over a decade ago. Unfortunately, that system was not able to capture all the operational constraints and needs of the expanding company. It was also inefficient, requiring close to a day to schedule one route through an iterative trial-and-error process.
Since KMB places great emphasis on providing top quality service to their customers, it worked with us in 1997 to design an alternative algorithm that can both provide timely service to citizens and can maximize the productivity of their vehicles.
AI Technology
Using advanced AI constraint-based optimization techniques, we designed a timetabling algorithm in 1998 that automatically schedules buses for different types of bus routes. Due to KMB's unique operational needs, bus timetabling must be performed together with duty assignment; a very complex and computationally intensive problem. We were able to design a whole new type of algorithm that solves this complexity while reducing computing time. On average a timetable is produced within less than 30 seconds! Our algorithms were tested on all the different types of routes operated by KMB and have shown to produce better results than manual approaches.
Business Benefits
Having the ability to automatically produce bus timetables in seconds
provides a Bus Company with extreme flexibility in coping with changing
business needs as well as customer demands. This ability also allows a
Bus Company to compare and analyze different operational scenarios to
find timetables that best optimize their operations.
More Info:
- Whitepaper
-
Chun, H.W. and H.C. Chan,
"The Design of a Multi-Tiered Bus Timetabling System,"
In Proceedings of the Twelfth
International Conference on Industrial and Engineering Applications of
Artificial Intelligence and Expert Systems, Cairo, May 1999.
