Thanks to recent developments in ride-hailing transit services throughout the world, the peer-to-peer (P2P) ride-matching problem has been actively considered in academia in recent years. P2P ride-matching not only reduces travel costs for riders but also benefits drivers by saving them money in exchange for their additional travel time. However, assigning riders to drivers in an efficient way is a complex problem that requires focusing on maximizing the benefits for both riders and drivers. This study aims to formulate a multi-driver multi-rider (MDMR) P2P ride-matching problem, based on rational preferences and cost allocation for both driver and rider, which also allows riders to transfer between multiple drivers for their travels if needed. Tabu Search (TS) for system-optimal ride-matching and a Greedy Matching (GM) algorithm for stable ride-matching were developed to solve ride-matching cases. The results show that the developed algorithm can successfully solve the proposed P2P MDMR ride-matching problem. MDMR P2P ride-matching can be used in areas where not much demand for ride-sharing exists, or for long-distance travel. Also it can be applied to designs for a more efficient on-demand transit network which can allow for transfers between routes. Moreover, the comparison of results between two implemented approaches shows that system-optimal centralized ride-matching can bring more cost savings for all participants in the system, although it may not always be stable when riders and drivers can choose their ride-matching for their own maximum benefit.
DaileyD. J.LoseffD.MeyersD.Seattle Smart Traveler: Dynamic Ridematching on the World Wide Web. Transportation Research Part C: Emerging Technologies, Vol. 7, No. 1, 1999, pp. 17-32. https://doi.org/10.1016/S0968-090X(99)00007-8.
2.
OrdóñezF.DessoukyM. M.Dynamic Ridesharing. In Leading Developments from INFORMS Communities (BattaR.PengJ., eds.), the Institute for Operations Research and the Management Sciences, Catonsville, MD, 2017, pp. 212–236.
3.
MohamedM. J.RyeT.FonzoneA.Operational and Policy Implications of Ridesourcing Services: A Case of Uber in London, UK. Case Studies on Transport Policy, Vol. 7, No. 4, 2019, pp. 823–836. https://doi.org/10.1016/j.cstp.2019.07.013.
4.
LiuX.TitheridgeH.YanX.WangR.TanW.ChenD.ZhangJ.A Passenger-to-Driver Matching Model for Commuter Carpooling: Case Study and Sensitivity Analysis. Transportation Research Part C: Emerging Technologies, Vol. 117, 2020, p. 102702. https://doi.org/10.1016/j.trc.2020.102702.
5.
AshkrofP.de Almeida CorreiaG. H.CatsO.van AremB.Understanding Ride-Sourcing Drivers’ Behaviour and Preferences: Insights from Focus Groups Analysis. Research in Transportation Business & Management, Vol. 37, 2020, p. 100516. https://doi.org/10.1016/j.rtbm.2020.100516.
6.
CordeauJ.-F.LaporteG.The Dial-a-Ride Problem: Models and Algorithms. Annals of Operations Research, Vol. 153, No. 1, 2007, pp. 29–46. https://doi.org/10.1007/s10479-007-0170-8.
7.
BraekersK.CarisA.JanssensG. K.Exact and Meta-Heuristic Approach for a General Heterogeneous Dial-a-Ride Problem with Multiple Depots. Transportation Research Part B: Methodological, Vol. 67, 2014, pp. 166–186. https://doi.org/10.1016/j.trb.2014.05.007.
8.
MassonR.LehuédéF.PétonO.The Dial-a-Ride Problem with Transfers. Computers & Operations Research, Vol. 41, 2014, pp. 12–23. https://doi.org/10.1016/j.cor.2013.07.020.
9.
NickkarA.LeeY.-J.Optimal Automated Demand Responsive Feeder Transit Operation and Its Impact. Final Report. Urban Mobility & Equity Center, Morgan State University, Baltimore, MD, 2018.
10.
LeeY.-J.MeskarM.NickkarA.SahebiS.Development of an Algorithm for Optimal Demand Responsive Relocatable Feeder Transit Networks Serving Multiple Trains and Stations. Urban Rail Transit, Vol. 5, No. 3, 2019, pp. 186–201. https://doi.org/10.1007/s40864-019-00109-z.
11.
BerbegliaG.CordeauJ.-F.LaporteG.Dynamic Pickup and Delivery Problems. European Journal of Operational Research, Vol. 202, No. 1, 2010, pp. 8–15. https://doi.org/10.1016/j.ejor.2009.04.024.
12.
MasoudN.JayakrishnanR.A Real-Time Algorithm to Solve the Peer-to-Peer Ride-Matching Problem in a Flexible Ridesharing System. Transportation Research Part B: Methodological, Vol. 106, 2017, pp. 218–236. https://doi.org/10.1016/j.trb.2017.10.006.
13.
MasoudN.JayakrishnanR.A Decomposition Algorithm to Solve the Multi-Hop Peer-to-Peer Ride-Matching Problem. Transportation Research Part B: Methodological, Vol. 99, 2017, pp. 1–29. https://doi.org/10.1016/j.trb.2017.01.004.
14.
HerbawiW.WeberM.The Ridematching Problem with Time Windows in Dynamic Ridesharing: A Model and a Genetic Algorithm. Presented at IEEE Congress on Evolutionary Computation, Brisbane, QLD, 2012.
15.
StiglicM.AgatzN.SavelsberghM.GradisarM.The Benefits of Meeting Points in Ride-Sharing Systems. Transportation Research Part B: Methodological, Vol. 82, 2015, pp. 36–53. https://doi.org/10.1016/j.trb.2015.07.025.
16.
AgatzN. A. H.EreraA. L.SavelsberghM. W. P.WangX.Dynamic Ride-Sharing: A Simulation Study in Metro Atlanta. Transportation Research Part B: Methodological, Vol. 45, No. 9, 2011, pp. 1450–1464. https://doi.org/10.1016/j.trb.2011.05.017.
17.
BoyacıB.ZografosK. G.GeroliminisN.An Optimization Framework for the Development of Efficient One-Way Car-Sharing Systems. European Journal of Operational Research, Vol. 240, No. 3, 2015, pp. 718–733. https://doi.org/10.1016/j.ejor.2014.07.020.
18.
TafreshianA.MasoudN.Trip-Based Graph Partitioning in Dynamic Ridesharing. Transportation Research Part C: Emerging Technologies, Vol. 114, 2020, pp. 532–553. https://doi.org/10.1016/j.trc.2020.02.008.
19.
SilvaB. C. H.FernandesI. F. C.GoldbargM. C.GoldbargE. F. G.Quota Travelling Salesman Problem with Passengers, Incomplete Ride and Collection Time Optimization by Ant-Based Algorithms. Computers & Operations Research, Vol. 120, 2020, p. 104950. https://doi.org/10.1016/j.cor.2020.104950.
20.
WangX.AgatzN.EreraA.Stable Matching for Dynamic Ride-Sharing Systems. Transportation Science, Vol. 52, No. 4, 2018, pp. 850–867. https://doi.org/10.1287/trsc.2017.0768.
21.
MaR.YaoL.SongL.JinM.A Novel Algorithm for Peer-to-Peer Ridesharing Match Problem. Neural Computing and Applications, Vol. 31, No. 1, 2019, pp. 247–258. https://doi.org/10.1007/s00521-018-3733-5.
22.
AydinO. F.GokasarI.KalanO.Matching Algorithm for Improving Ride-Sharing by Incorporating Route Splits and Social Factors. Plos One, Vol. 15, No. 3, 2020, p. e0229674. https://doi.org/10.1371/journal.pone.0229674.
23.
Di FebbraroA.GattornaE.SaccoN.Optimization of Dynamic Ridesharing Systems. Transportation Research Record: Journal of the Transportation Research Board, 2013. 2359: 44–50.
24.
NourinejadM.RoordaM. J.Agent Based Model for Dynamic Ridesharing. Transportation Research Part C: Emerging Technologies, Vol. 64, 2016, pp. 117–132. https://doi.org/10.1016/j.trc.2015.07.016.
25.
KucharskiR.CatsO.Exact Matching of Attractive Shared Rides (ExMAS) for System-Wide Strategic Evaluations. Transportation Research Part B: Methodological, Vol. 139, 2020, pp. 285-310. https://doi.org/10.1016/j.trb.2020.06.006.
26.
NourinejadM.RamezaniM.Ride-Sourcing Modeling and Pricing in Non-Equilibrium Two-Sided Markets. Transportation Research Part B: Methodological, Vol. 132, 2020, pp. 340-357. https://doi.org/10.1016/j.trb.2019.05.019.
27.
BalardinoA. F.SantosA. G.Heuristic and Exact Approach for the Close Enough Ridematching Problem. Springer International Publishing, Cham, 2016.
28.
NajmiA.ReyD.RashidiT. H.Novel Dynamic Formulations for Real-Time Ride-Sharing Systems. Transportation Research Part E: Logistics and Transportation Review, Vol. 108, 2017, pp. 122–140. https://doi.org/10.1016/j.tre.2017.10.009.
29.
YangH.QinX.KeJ.YeJ.Optimizing Matching Time Interval and Matching Radius in On-Demand Ride-Sourcing Markets. Transportation Research Part B: Methodological, Vol. 131, 2020, pp. 84–105. https://doi.org/10.1016/j.trb.2019.11.005.
30.
KumarP.KhaniA.An Algorithm for Integrating Peer-to-Peer Ridesharing and Schedule-Based Transit System for First Mile/Last Mile Access. Transportation Research Part C: Emerging Technologies, Vol. 122, 2021, p. 102891. https://doi.org/https://doi.org/10.1016/j.trc.2020.102891.
31.
GhoseiriK.HaghaniA.HamedM.Real-Time Rideshare Matching Problem. Mid-Atlantic Universities Transportation Center, College Park, MD, 2010.
32.
QianX.ZhangW.UkkusuriS. V.YangC.Optimal Assignment and Incentive Design in the Taxi Group Ride Problem. Transportation Research Part B: Methodological, Vol. 103, 2017, pp. 208–226. https://doi.org/10.1016/j.trb.2017.03.001.
33.
PengZ.ShanW.JiaP.YuB.JiangY.YaoB.Stable Ride-Sharing Matching for the Commuters with Payment Design. Transportation, Vol. 47, No. 1, 2020, pp. 1–21. https://doi.org/10.1007/s11116-018-9960-x.
34.
ÖzkanE.Joint Pricing and Matching in Ride-Sharing Systems. European Journal of Operational Research, Vol. 287, No. 3, 2020, pp. 1149–1160. https://doi.org/10.1016/j.ejor.2020.05.028.
XuH.OrdóñezF.DessoukyM.A Traffic Assignment Model for a Ridesharing Transportation Market. Journal of Advanced Transportation, Vol. 49, No. 7, 2015, pp. 793–816. https://doi.org/10.1002/atr.1300.
37.
XuH.PangJ.-S.OrdóñezF.DessoukyM.Complementarity Models for Traffic Equilibrium with Ridesharing. Transportation Research Part B: Methodological, Vol. 81, 2015, pp. 161–182. https://doi.org/10.1016/j.trb.2015.08.013.
38.
SchuetzP.CaflischA.Multistep Greedy Algorithm Identifies Community Structure in Real-World and Computer-Generated Networks. Physical Review E, Vol. 78, No. 2, 2008, p. 026112. https://doi.org/10.1103/PhysRevE.78.026112.
39.
CalvoR. W.de LuigiF.HaastrupP.ManiezzoV.A Distributed Geographic Information System for the Daily Car Pooling Problem. Computers & Operations Research, Vol. 31, No. 13, 2004, pp. 2263–2278. https://doi.org/10.1016/S0305-0548(03)00186-2.
40.
DuanR.PettieS.Linear-Time Approximation for Maximum Weight Matching. Journal of the ACM (JACM), Vol. 61, No. 1, 2014, pp. 1–23. https://doi.org/10.1145/2529989.
41.
BeiX.ZhangS.Algorithms for Trip-Vehicle Assignment in Ride-Sharing. Proc., 32nd AAAI Conference on Artificial Intelligence, New Orleans, LA, 2018.
42.
ChenW.MesM.SchuttenM.QuintJ.A Ride-Sharing Problem with Meeting Points and Return Restrictions. Transportation Science, Vol. 53, No. 2, 2019, pp. 401–426. https://doi.org/10.1287/trsc.2018.0832.
43.
WangX.DessoukyM.OrdonezF.A Pickup and Delivery Problem for Ridesharing Considering Congestion. Transportation Letters, Vol. 8, No. 5, 2016, pp. 259–269. https://doi.org/10.1179/1942787515Y.0000000023.
44.
IRS. 2021 Standard Mileage Rates. International Foundation of Employee Benefit Plans, Brookfield, WI, 2020.
