Models of Competition for Intelligent Transportation Infrastructure: Parking, Ridesharing, and External Factors in Routing Decisions

Daniel Calderone

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2017-101
May 12, 2017

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2017/EECS-2017-101.pdf

Competition underlies much of the complexity of modern transportation systems and accurately modeling the incentives transportation users face is critical in designing the smart cities of tomorrow. In this work, we extend traditional non-atomic routing games to model several different scenarios relevant to modern cities. In Chapter 2, we review results on continuous population potential games and routing games and discuss linear programming interpretations of individual drivers’ decisions and their relationship to the Wardrop equilibria. We include discussion of the variable demand case and upper bounds on the price of anarchy. In Chapter 3, we combine an observable queueing game with a routing game to develop a queue-routing game useful for modeling traffic circling looking for parking in urban centers. We use this framework to model several parking situations in downtown Seattle. In Chapter 4, we discuss connections between linear programming formulations of shortest path problems and linear programming formulations of Markov decision processes (MDPs). We use these connections to motivate a stochastic population game we call a Markov decision process routing game where each infinitesimal agent solves an MDP as opposed to a shortest path problem. We develop this game in the infinite-horizon, average-cost case and in the finite-horizon, total-cost case. We comment on connections with traditional routing games as well as other stochastic population game formulations such as mean field games. Paralleling results for traditional routing games, we derive upper bounds on the price of anarchy and comment on the existence of Braess paradox. We apply this framework to model ridesharing drivers competing for fares and to develop a model of circling traffic competing for street parking. Finally, in Chapter 5, we consider a bi-criterion routing game where drivers consider travel time along with some external factor. Preference for this external factor is represented by general distribution over a type parameter that can be supported both above and below zero. We develop the appropriate equilibrium concept and show how this framework can be used to model the transportation data market, drivers’ interest in their location privacy, and commuters comparing two different commuting options. In Chapter 6, we conclude and make final comments on modeling considerations and future research directions.

Advisor: S. Shankar Sastry


BibTeX citation:

@phdthesis{Calderone:EECS-2017-101,
    Author = {Calderone, Daniel},
    Title = {Models of Competition for Intelligent Transportation Infrastructure: Parking, Ridesharing, and External Factors in Routing Decisions},
    School = {EECS Department, University of California, Berkeley},
    Year = {2017},
    Month = {May},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2017/EECS-2017-101.html},
    Number = {UCB/EECS-2017-101},
    Abstract = {Competition underlies much of the complexity of modern transportation systems and accurately modeling the incentives transportation users face is critical in designing the smart cities of tomorrow. In this work, we extend traditional non-atomic routing games to model several different scenarios relevant to modern cities. In Chapter 2, we review results on continuous population potential games and routing games and discuss linear programming interpretations of individual drivers’ decisions and their relationship to the Wardrop equilibria. We include discussion of the variable demand case and upper bounds on the price of anarchy. In Chapter 3, we combine an observable queueing game with a routing game to develop a queue-routing game useful for modeling traffic circling looking for parking in urban centers. We use this framework to model several parking situations in downtown Seattle. In Chapter 4, we discuss connections between linear programming formulations of shortest path problems and linear programming formulations of Markov decision processes (MDPs). We use these connections to motivate a stochastic population game we call a Markov decision process routing game where each infinitesimal agent solves an MDP as opposed to a shortest path problem. We develop this game in the infinite-horizon, average-cost case and in the finite-horizon, total-cost case. We comment on connections with traditional routing games as well as other stochastic population game formulations such as mean field games. Paralleling results for traditional routing games, we derive upper bounds on the price of anarchy and comment on the existence of Braess paradox. We apply this framework to model ridesharing drivers competing for fares and to develop a model of circling traffic competing for street parking. Finally, in Chapter 5, we consider a bi-criterion routing game where drivers consider travel time along with some external factor. Preference for this external factor is represented by general distribution over a type parameter that can be supported both above and below zero. We develop the appropriate equilibrium concept and show how this framework can be used to model the transportation data market, drivers’ interest in their location privacy, and commuters comparing two different commuting options. In Chapter 6, we conclude and make final comments on modeling considerations and future research directions.}
}

EndNote citation:

%0 Thesis
%A Calderone, Daniel
%T Models of Competition for Intelligent Transportation Infrastructure: Parking, Ridesharing, and External Factors in Routing Decisions
%I EECS Department, University of California, Berkeley
%D 2017
%8 May 12
%@ UCB/EECS-2017-101
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2017/EECS-2017-101.html
%F Calderone:EECS-2017-101