Hajari, Hadi
(2021)
A distributed approach for robust, scalable, and flexible dynamic ridesharing.
Doctoral Dissertation, University of Pittsburgh.
(Unpublished)
Abstract
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.
Share
| Citation/Export: |
|
| Social Networking: |
|
Details
| Item Type: |
University of Pittsburgh ETD
|
| Status: |
Unpublished |
| Creators/Authors: |
|
| ETD Committee: |
|
| 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 |
| URI: |
http://d-scholarship.pitt.edu/id/eprint/41268 |
Metrics
Monthly Views for the past 3 years
Plum Analytics
Actions (login required)
 |
View Item |
![[feed]](/images/feed-icon-32x32.png){kind=icon}