Link to the University of Pittsburgh Homepage
Link to the University Library System Homepage Link to the Contact Us Form

A distributed approach for robust, scalable, and flexible dynamic ridesharing

Hajari, Hadi (2021) A distributed approach for robust, scalable, and flexible dynamic ridesharing. Doctoral Dissertation, University of Pittsburgh. (Unpublished)

Download (2MB) | Preview


This dissertation provides a solution to dynamic ridesharing problem, a NP-hard optimization problem, where a fleet of vehicles move on a road network and ridesharing requests arrive continuously. The goal is to optimally assign vehicles to requests with the objective of minimizing total travel distance of vehicles and satisfying constraints such as vehicles’ capacity and time window for pick-up and drop-off locations. The dominant approach for solving dynamic ridesharing problem is centralized approach that is intractable when size of the problem grows, thus not scalable. To address scalability, a novel agent-based representation of the problem, along with a set of algorithms to solve the problem, is proposed. Besides being scalable, the proposed approach is flexible and, compared to centralized approach, more robust, i.e., vehicle agents can handle changes in the network dynamically (e.g., in case of a vehicle breakdown) without need to re-start the operation, and individual vehicle failure will not affect the process of decision-making, respectively. In the decentralized approach the underlying combinatorial optimization is formulated as a distributed optimization problem and is decomposed into multiple subproblems using spectral graph theory. Each subproblem is formulated as DCOP (Distributed Constraint Optimization Problem) based on a factor graph representation, including a group of cooperative agents that work together to take an optimal (or near-optimal) joint action. Then a min-sum algorithm is used on the factor graph to solve the DCOP. A simulator is implemented to empirically evaluate the proposed approach and benchmark it against two alternative approaches, solutions obtained by ILP (Integer Linear Programming) and a greedy heuristic algorithm. The results show
that the decentralized approach scales well with different number of vehicle agents, capacity of vehicle agents, and number of requests and outperforms: (a) the greedy heuristic algorithm in terms of solution quality and (b) the ILP in terms of execution time.


Social Networking:
Share |


Item Type: University of Pittsburgh ETD
Status: Unpublished
CreatorsEmailPitt UsernameORCID
Hajari, Hadihah86@pitt.eduhah860000-0003-1237-2947
ETD Committee:
TitleMemberEmail AddressPitt UsernameORCID
Thesis AdvisorKarimi, Hassan
Committee MemberMunro,
Committee MemberLewis,
Committee MemberRubinstein,
Date: 8 September 2021
Date Type: Publication
Defense Date: 19 May 2021
Approval Date: 8 September 2021
Submission Date: 8 June 2021
Access Restriction: No restriction; Release the ETD for access worldwide immediately.
Number of Pages: 117
Institution: University of Pittsburgh
Schools and Programs: School of Computing and Information > Information Science
Degree: PhD - Doctor of Philosophy
Thesis Type: Doctoral Dissertation
Refereed: Yes
Uncontrolled Keywords: Dynamic Ridesharing, Decentralized Approach, Combinatorial Optimization, Spectral Graph Theory
Date Deposited: 08 Sep 2021 13:22
Last Modified: 08 Sep 2021 13:22


Monthly Views for the past 3 years

Plum Analytics

Actions (login required)

View Item View Item