Smart City Gnosys

Smart city article details

Title	The Multi-Vehicle Ride-Sharing Problem
ID_Doc	56095
Authors	Luo K.; Agarwal C.; Das S.; Guo X.
Year	2022
Published	WSDM 2022 - Proceedings of the 15th ACM International Conference on Web Search and Data Mining
DOI	http://dx.doi.org/10.1145/3488560.3498449
Abstract	Ride-sharing is one of the most popular models of economical and eco-friendly transportation in modern smart cities, especially when riding hybrid and electric vehicles. Usually multiple passengers with similar itineraries are grouped together, which significantly reduces travel cost (or time), road congestion, and traffic emissions. In this paper, we study the ride-sharing problem where each vehicle is shared by exactly $łambda$ riders for any fixed $łambda>0$, and the goal is to minimize the total travel distance. The min-cost ride-sharing problem is intractable even in the case of exactly two riders sharing a vehicle \citeBeiZ18-carsharing, and hence we can only hope for an approximate solution. We propose a novel two-phase algorithm: a hierarchical grouping phase that partitions requests into disjoint groups of fixed size, followed by an assignment of request groups to individual vehicles and planning a feasible route for each vehicle. This is the first non-trivial approximation algorithm for the ride-sharing problem with vehicle capacity larger than two. We verify the efficacy of our algorithm on both synthetic and realworld datasets. Our experimental results show that, the ride-sharing scheme produced by our algorithm not only has small total travel distance compared to state-of-the-art baselines, but also enjoys a small makespan and total latency, which crucially relate to each single rider's traveling time. This suggests that our algorithm also enhances rider experience while being energy-efficient. © 2022 Owner/Author.
Author Keywords	Approximation algorithm; Ride-sharing

Similar Articles

Id	Similarity	Authors	Title	Published
18636	0.896	Gavalas D.; Konstantopoulos C.; Pantziou G.	Design And Management Of Vehicle-Sharing Systems: A Survey Of Algorithmic Approaches	Smart Cities and Homes: Key Enabling Technologies (2016)
1880	0.889	Magsino E.R.; Ching G.R.C.; Espiritu F.M.M.; Go K.D.	A Game Theory-Based Pricing Technique For Ridesharing Pairings	1st International Conference in Advanced Innovation on Smart City, ICAISC 2023 - Proceedings (2023)
2507	0.88	Yatnalka G.P.; Narman H.S.	A Matching Model For Vehicle Sharing Based On User Characteristics And Tolerated-Time	HONET-ICT 2019 - IEEE 16th International Conference on Smart Cities: Improving Quality of Life using ICT, IoT and AI (2019)
37504	0.879	Altshuler T.; Altshuler Y.; Katoshevski R.; Shiftan Y.	Modeling And Prediction Of Ride Sharing Utilization Dynamics	Applied Swarm Intelligence (2024)
5758	0.872	Anagnostopoulos T.; Ramson S.R.J.	A Vehicle Ride-Sharing Algorithm Assessing Passenger Satisfaction According To Spatial, Temporal, And Social Behavior Context Based On Real Data Sources	Future Transportation, 5, 2 (2025)
24104	0.872	Radakovic D.; Singh A.; Varde A.S.; Lal P.	Enriching Smart Cities By Optimizing Electric Vehicle Ride-Sharing Through Game Theory	Proceedings - International Conference on Tools with Artificial Intelligence, ICTAI, 2022-October (2022)
58122	0.871	Oualhaj O.A.; Azougaghe A.; Naja A.; Mabrouk A.	Towards Efficient Urban Network Mobility: A Cloud-Based Ride-Sharing System	20th International Wireless Communications and Mobile Computing Conference, IWCMC 2024 (2024)
1995	0.867	Sun Y.; Mu C.; Sun J.; He Y.	A Greedy Algorithm-Based Approach For Dynamic Carpooling Matching And Route Selection In Ride-Hailing	Proceedings - 2023 19th International Conference on Mobility, Sensing and Networking, MSN 2023 (2023)
10234	0.864	Xu W.; Xu Z.; Peng J.; Liang W.; Liu T.; Jia X.; Das S.K.	Approximation Algorithms For The Team Orienteering Problem	Proceedings - IEEE INFOCOM, 2020-July (2020)
13395	0.863	Turoń K.	Car-Sharing Systems In Smart Cities: A Review Of The Most Important Issues Related To The Functioning Of The Systems In Light Of The Scientific Research	Smart Cities, 6, 2 (2023)