Advisor:

Dr. Pascal Van Hentenryck, H. Milton Stewart School of Industrial and Systems Engineering, Georgia Tech

Thesis Committee:

Dr. Mathieu Dahan, H. Milton Stewart School of Industrial and Systems Engineering, Georgia Tech

Dr. Alan Erera, H. Milton Stewart School of Industrial and Systems Engineering, Georgia Tech

Dr. Pinar Keskinocak, H. Milton Stewart School of Industrial and Systems Engineering, Georgia Tech

Dr. Antoine Legrain, , Department of Mathematical and Industrial Engineering, Polytechnique Montréal

Date and Time: Wednesday, July 27th, 2022, at 1pm (EDT)

Location: Main 126

Meeting Link: Click here to join Teams meeting

Abstract: 

Public transit agencies are increasingly exploring mobility options to supplement their traditional rail, bus, and streetcar offerings [1, 2]. One such option is Demand Response Service, “any non-fixed route system of transporting individuals that requires advanced scheduling by the customer” [3]. These Demand Response Services present challenging design and operations problems, including fleet sizing, network design, and dispatching. In this thesis, we present optimization-based techniques centered around one such operational problem: vehicle dispatching.

In Chapter 2, we review the real-time dial-a-ride problem, a vehicle routing problem with pickups and deliveries, deviation, and capacity constraints, and present a dispatching algorithm, M-RTRS, which provides service guarantees, serving all customers with a small number of vehicles while minimizing wait times. In a computational study, we show that this algorithm scales to over 30,000 requests per hour, providing an effective way to support large-scale ride-sharing services in dense cities.

In Chapter 3, we introduce an approach for vehicle dispatching, A-RTRS, that tightly integrates a state-of-the-art dispatching algorithm, a machine-learning model to predict zone-to-zone demand over time, and a model predictive control optimization to relocate idle vehicles. This is shown to decrease the average wait time of passengers in a computational study.

In Chapter 4, we present a relocation algorithm designed to address two challenges faced when deploying a real-world real-time dial-a-ride service. The first, a lack of historic data, as initial adoption may be slow, and accumulating the amount of data needed for the machine learning approach to demand prediction presented in Chapter 3 may be impractical. The second, that vehicles may be restricted in the locations that they may idle, which must be considered when relocating them. In a computational study, we show this approach yields similar average wait time decreases to A-RTRS.