StructRide: A Framework to Exploit the Structure Information of Shareability Graph in Ridesharing

Jiexi Zhan , Yu Chen , Peng Cheng , Lei Chen , Wangze Ni , Xuemin Lin · 2024

Read StructRide: A Framework to Exploit the Structure Information of Shareability Graph in Ridesharing by Jiexi Zhan , Yu Chen , Peng Cheng , Lei Chen , Wangze Ni , Xuemin Lin (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-06335.txt.

Introduction

Jiexi Zhan and colleagues mine rider sharing graphs to group shared rides better, in work from 2024. Shared rides cut traffic jams, exhaust fumes, and per rider trip costs at once. Past matching tools skip how riders link with each other, trading speed for match quality.

Their frame builds a graph where riders join when a shared trip could serve both. A sharing loss score picks groups whose left out riders still pair well later. The core method then solves live matching fast on that graph structure. Two real data sets show big speed gains over the best prior tools. Served request counts also rose, by up to half in the best runs.

Catalog record

CREATORJiexi Zhan , Yu Chen , Peng Cheng , Lei Chen , Wangze Ni , Xuemin Lin
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE75 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-06335

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

StructRide: A Framework to Exploit the Structure Information of Shareability Graph in Ridesharing Thanks: *Wangze Ni is also with The State Key Laboratory of Blockchain and Data Security; Hangzhou High-Tech Zone (Binjiang) Institute of Blockchain and Data Security. Jiexi Zhan , Yu Chen , Peng Cheng , Lei Chen , Wangze Ni , Xuemin Lin Abstract Ridesharing services play an essential role in modern transportation, which significantly reduces traffic congestion and exhaust pollution. In the ridesharing problem, improving the sharing rate between riders can not only save the travel cost of drivers but also utilize vehicle resources more efficiently. The existing online-based and batch-based methods for the ridesharing problem lack the analysis of the sharing relationship among riders, leading to a compromise between efficiency and accuracy. In addition, the graph is a powerful tool to analyze the structure information between nodes. Therefore, in this paper, we propose a framework, namely StructRide, to utilize the structure information to improve the results for ridesharing problems. Specifically, we extract the sharing relationships between riders to construct a shareability graph. Then, we define a novel measurement, namely shareability loss, for vehicles to select groups of requests such that the unselected requests still have high probabilities of sharing with other requests. Our SARD algorithm can efficiently solve dynamic ridesharing problems to achieve dramatically improved results. Through extensive experiments, we demonstrate the efficiency and effectiveness of our SARD algorithm on two real datasets. Our SARD can run up to 72.68 times faster and serve up to 50% more requests than the state-of-the-art algorithms. I Introduction Recently, ridesharing has become a popular public transportation choice, which greatly reduces energy and relieves traffic pressure. In ridesharing, a driver can serve different riders simultaneously once riders can share parts of their trips and there are enough seats for them. The ridesharing service providers (e.g., Uber [ 1 ] , Didi [ 2 ] ) are constantly pursuing better service quality, such as higher service rate [ 3 , 4 , 5 ] , lower total travel distance [ 6 , 7 , 5 ] , or higher total revenue [ 8 , 9 ] . For ridesharing platforms, vehicle-request matching and route planning are two critical issues to address. With a set of vehicles and requests, vehicle-request matching filters out a set of valid candidate requests for each vehicle, while route planning targets on designing a route schedule for a vehicle to pick up and drop off the assigned requests. If a vehicle can serve two requests on the same trip, we call that they have a shareable relationship. The structure information of graphs reveal key properties (e.g., k -core [ 10 , 11 ] , k -truss [ 12 , 13 ] , clique [ 14 , 15 ] ), aiding in specific applications (e.g., community discovery [ 16 , 17 , 18 ] , anomaly detection [ 19 , 20 ] and influential analysis [ 21 , 22 ] ). In ridesharing problems, the shareable relationships form a shareability graph [ 23 , 24 , 25 , 26 , 27 , 28 ] , where each node represents a request and each edge indicates that the connected requests can share part of their trips. However, to the best of our knowledge, no existing works have targeted improving service quality by utilizing the structural properties of the shareability graph in ridesharing problems. TABLE I: Requests Release Detail. request source destination release time deadline r_{1} a d 0 30 r_{2} c f 1 19 r_{3} b e 2 21 r_{4} c g 3 21 (a) Road Network (b) Shareability Graph Fig. 1: A Motivation Example In real platforms, vehicles and requests often arrive dynamically. Existing works on ridesharing can be summarized into two modes: the online mode [ 29 , 30 , 31 , 6 , 7 , 32 ] and batch mode [ 27 , 33 , 34 , 35 ] . The state-of-the-art operator for the online mode is insertion [ 32 , 31 , 36 , 34 , 37 ] , which inserts the requests’ sources and destinations into proper positions of the vehicle’s route without reordering its current schedule, minimizing the increase in the total travel cost. Batch-based methods [ 27 , 33 , 38 , 39 , 34 ] first package the incoming requests into groups, then assign a vehicle with a properly designed serving-schedule for each group of requests. We illustrate our motivation with Example 1 . The existing approaches have their shortcomings. Insertion operator is fast but only achieve the local optimal schedule for a request. The batch-based methods can achieve better results than online methods for a period of a relatively long time (e.g., one day), but their time complexities are much higher than insertion (e.g., RTV [ 27 ] requires costly bipartite matching). Can we have a more efficient batch-based approach to achieve better results for a relatively long period? In this paper, we exploit the graph structures in the shareability graph of requests to achieve better results for ridesharing services. Example 1 . Suppose there are two vehicles, w_{1} and w_{2} , and four requests, r_{1} to r_{4} , on a ridesharing platform. The sources, destinations, release times, and deadlines of the requests are listed in Table I . As shown in Figure 1(a) , the vehicles are initially located at points a and c on the road network with seven vertices, each with a capacity of three. In the online-based solution [ 29 , 30 , 31 , 6 , 7 , 32 ] , r_{2} will be inserted into the existing schedule of r_{1} of w_{1} with a scheduled route \langle a,c,f,d\rangle at time 1. This results in r_{4} not being served as it cannot be inserted into the planned route \langle c,b,e\rangle of w_{2} , which serves r_{3} . Although it can provide better scheduling, the existing batch-based methods [ 27 , 38 , 39 , 34 , 5 ] list all possible request combinations or vehicle-request pair, and run the time-consuming global matching. Instead of considering all request combinations, we can heuristically achieve good dispatch result by investigating the shareability graph shown in Figure 1(b) . We construct the graph by connecting the requests that can share a vehicle, so the request with a larger degree has more sharing opportunities. If we give higher priority to grouping the requests with lower degree, r_{4} will first share w_{2} with r_{2} , then r_{3} will share w_{1} with r_{1} . All the requests can be served with scheduled routes \langle a,b,e,d\rangle and \langle c,f,g\rangle for w_{1} and w_{2} , respectively. In this paper, we propose StructRide, a well-tailored batch-based framework to exploit the structure information of requests’ shareability graph in ridesharing systems. The achieved results are significantly improved (e.g., higher service rates and lower travel distances) under just a slight delay of response time. To the best of our knowledge, we are the first to integrate traditional allocation algorithms with graph analyses of the shareability graph in ridesharing problems, which is also the key insight of our StructRide framework. In StructRide, we first propose a fast shareability graph builder that efficiently extracts shareable relationships between requests through

Read the complete text