Back to search

Georgia Institute of Technology

Optimizing ride matches for dynamic ride-sharing systems

Abstract

dc:description.abstract

Ride-share systems, which aim to bring together travelers with similar itineraries and time schedules, may provide significant societal and environmental benefits by reducing the number of cars used for personal travel and improving the utilization of available seat capacity. Effective and efficient optimization technology that matches drivers and riders in real-time is one of the necessary components for a successful ride-share system. The research conducted in this dissertation formally defines dynamic or real-time ride-sharing, identifies optimization problems for finding best sets of ride-share matches in a number of operational scenarios, develops approaches for solving ride-share optimization problems, and tests the concepts via a simulation study of work trips in the Atlanta metropolitan area. The first chapter introduces the motivation of the ride-sharing problem and briefly defines the dynamic ride-sharing system. In Chapter 2, we systematically outline the optimization challenges that arise when developing technology to support ride-sharing and survey the related operations research models in academic literature. In Chapter 3, we develop optimization-based approaches for finding ride-share matches in a standard problem setting, with the goal of minimizing the total system-wide vehicle miles incurred by system users. To assess the merits of our methods we present a simulation study based on 2008 travel demand data from metropolitan Atlanta. The simulation results indicate that the use of sophisticated optimization methods instead of simple greedy matching rules substantially improves the performance of ride-sharing systems. Furthermore, even with relatively low participation rates, it appears that sustainable populations of dynamic ride-sharing participants may be possible even in relatively sprawling urban areas with many employment centers. In Chapter 4, we consider a more sophisticated ride-share setting where participants may be unlikely to accept ride-share matches if they are not stable. Generically, a set of matches between riders and drivers is defined as stable if no rider and driver, currently matched to others, would prefer to be matched together. This notion of stability is similar to that of the stable marriage problem. We develop notions of stable ride-share matching in a variety of settings, and develop approaches for finding stable (or nearly-stable) solutions. Computational results are used to compare system performance under various levels of matching stability. A system with unstable matching assignments is simulated over two months in which participants are likely to reject the system's assignment if a private arrangement between individuals could bring better benefits. The simulation results indicate that the total savings generated by a ride-sharing system deteriorate with unstable matching assignments and that enforcing stability constraints in matching models is beneficial. In Chapter 5, we consider another set of more sophisticated ride-share matching settings where participants are not assumed to accept each match to which they are assigned. In such settings, it may be useful to present users with a menu of possible ride-share matches from which they can choose. We develop models and solution approaches to jointly present multiple options to participants based on a complete bipartite graph structure. This research could serve as a building block for future work on the dynamic ride-sharing problem.

Degree

thesis:*
Department dc:contributor.department
Industrial and Systems Engineering
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2013

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Wang, Xing
Advisor dc:contributor.advisor
  • Erera, Alan L.
Committee members dc:contributor.committeemember
  • Johnson, Ellis L.
  • Sokol, Joel
  • Laval, Jorge
  • Savelsbergh, Martin
  • Agatz, Neils

Subjects

dc:subject × 4

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/47668

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Wang, Xing. Optimizing ride matches for dynamic ride-sharing systems. Georgia Institute of Technology, 2013. http://hdl.handle.net/1853/47668