Design of a route generating algorithm for demand-responsive public bus services - QC-158

Preferred Disciplines: Transportation/Traffic Engineering, Civil Engineering, Urban Planning, Computer Science, Software Engineering, Mathematics Optimization (PhD or Post-Doc)
Project length: 2 years (4 units)
Approx. start date: September 2018
Location: Montreal, QC
No. of Positions: 1
Preferences: University of Waterloo iTSS Lab, École Polytechnique de Montréal, University of Toronto, Concordia University, Carleton University, McGill University, Dalhousie University, University of Calgary, University of Alberta, Ryerson University, Queen’s University 
Company: Anonymous

About Company:

We are developing a universal public bus platform that would enable any transit agency to provide on-demand bus services using their existing vehicle infrastructure. Riders will be able to make trip requests on our mobile app, and dynamic bus routes will be created based on these demands. To shorten travel time, riders will be grouped onto buses based on similar origins/destinations and consolidated bus stops will be used to reduce pick-up/drop-off time. Transit agencies will be able to reduce operational costs and vehicle emissions, while providing their customers with a quicker, more flexible service built around their schedules. 

Summary of Project:

We are looking to redesign or iterate upon our current algorithm used to generate dynamic bus routes based on rider trip requests. It must receive passenger trip requests, dispatch buses that simultaneously meet passenger schedules, and follow the shortest possible routes. This algorithm must account for a variety of different use cases and optimization parameters. It will be designed in consecutive projects based on functional priority:

  • Project 1: Be able to generate optimized bus routes based on trip requests received in advance (origin, destination, earliest departure time, latest arrival time) and various static parameters set by the transit agencies (vehicle capacity, minimum load factor, maximum walking distance, operating time windows, cost penalty per passenger).
  • Project 2: Be able to generate dynamically changing bus routes in real-time, optimized based on customer requests, real-time traffic data and the optimization parameters listed above.
  • Project 3: Machine learning is incorporated into the route-generating algorithm to predict the demand and dispatch buses to certain areas before the rider trip requests have been entered. This final version must be designed to function over the area of entire city (in contrast to a fixed corridor).

Research Objectives/Sub-Objectives:

  • Research existing solutions in literature, ranking their performance according to our needs and comparing them to our current algorithm prototype
  • Formulate an algorithm to generate routes based on passenger trip requests received in advance and in real-time; it must also incorporate machine learning prediction for anticipating customer demand.
  • Develop a method to determine how the on-demand bus service can be efficiently deployed to maximize coverage and frequency, based on the existing needs of the population and available infrastructure.

Methodology:

    • TBD

    Expertise and Skills Needed:

    Required:

    • Creation of optimization models for transit networks
    • Familiarity with transit network design and operations
    • Familiarity with algorithmic route generation based on shortest path algorithms and heuristics
    • Object-oriented programming skills

    Optional/Preferred:

    • Knowledge of dispatching algorithms for demand-responsive transit services (eg. Paratransit)
    • Experience with transit and traffic simulation software
    • Experience with GIS software

    For more info or to apply to this applied research position, please

    1. Check your eligibility and find more information about open projects.
    2. Interested students need to get the approval from their supervisor and send their CV along with a link to their supervisor’s university webpage by applying through the webform or directly to Noha Gerges (ngerges(at)mitacs.ca).
    Program: