notesum.ai

Published at December 9

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

cs.DB

Released Date: December 9, 2024

Authors: Jiexi Zhan¹, Yu Chen¹, Peng Cheng¹, Lei Chen², Wangze Ni³, Xuemin Lin⁴

Aff.: ¹East China Normal University, Shanghai, China; ²HKUST (GZ), Guangzhou, China; ³HKUST, Hong Kong SAR, China; ⁴Shanghai Jiaotong University, Shanghai, China

Arxiv: http://arxiv.org/pdf/2412.06335v1

Symbol	Description
$R=\{r_{i}\}$	Set of requests.
$W=\{w_{j}\}$	Set of vehicles.
$s_{i},e_{i}$	Source and destination of request $r_{i}$ .
$t_{i},d_{i}$	Release time and deadline of request $r_{i}$ .
$n_{i}$	Number of riders in request $r_{i}$ .
$c_{j}$	Capacity of vehicle $w_{j}$ .
$S_{j}$	Schedule of vehicle $w_{j}$ .
$buf(o_{k})$	Maximum allowed detour time of way-point $o_{k}$ .
$ddl(o_{k})$	Deadline of way-point $o_{k}$ .
$cost(o_{k},o_{l})$	Travel cost between way-points $o_{k}$ and $o_{l}$ .
$p_{r}$	Penalty coefficient for unassigned requests.
$\gamma$	Deadline parameter.
$\mathcal{P}$	Batch of requests.
$\Delta$	Batch time.
$\theta$	Angle between two requests.
$\delta$	Angle threshold for pruning.
$SG$	Sharability graph.
$SLoss(G_{i})$	Shareability loss of group $G_{i}$ .