A Dynamic Tree Algorithm for Peer-to-Peer Ridesharing Matching

Rui Yao () and Shlomo Bekhor ()
Additional contact information
Rui Yao: Technion - Israel Institute of Technology
Shlomo Bekhor: Technion - Israel Institute of Technology

Networks and Spatial Economics, 2021, vol. 21, issue 4, No 2, 837 pages

Abstract: Abstract On-demand peer-to-peer ridesharing services provide flexible mobility options and are expected to alleviate congestion by sharing empty car seats. An efficient matching algorithm is essential to the success of a ridesharing system. The matching problem is related to the well-known dial-a-ride problem, which also tries to find the optimal pickup and delivery sequence for a given set of passengers. In this paper, we propose an efficient dynamic tree algorithm to solve the on-demand peer-to-peer ridesharing matching problem. The dynamic tree algorithm benefits from given ridesharing driver schedules and provides satisfactory runtime performances. In addition, an efficient pre-processing procedure to select candidate passenger requests is proposed, which further improves the algorithm performance. Numerical experiments conducted in a small network show that the dynamic tree algorithm reaches the same objective function values of the exact algorithm, but with shorter runtimes. Furthermore, the proposed method is applied to a larger size problem. Results show that the spatial distribution of ridesharing participants influences the algorithm performance. Sensitivity analysis confirms that the most critical ridesharing matching constraints are the excess travel times. The network analysis suggests that small vehicle capacities do not guarantee overall vehicle-kilometer travel savings.

Keywords: Dynamic tree; Peer-to-peer ridesharing; Matching; Vehicle routing problem (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s11067-021-09523-y Abstract (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:kap:netspa:v:21:y:2021:i:4:d:10.1007_s11067-021-09523-y

Ordering information: This journal article can be ordered from
http://www.springer. ... ce/journal/11067/PS2

DOI: 10.1007/s11067-021-09523-y

Access Statistics for this article

Networks and Spatial Economics is currently edited by Terry L. Friesz

More articles in Networks and Spatial Economics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().