Context-Aware Path Ranking in Road Networks

Ranking paths becomes an increasingly important functionality in many transportation services, where multiple paths connecting a source-destination pair are offered to drivers. We study ranking such paths under specific contexts, e.g., at a departure time and for a specific driver. More specifically, we model ranking as a regression problem where we assign a ranking score to each path with the help of historical trajectories. The intuition is that if a driver's trajectory used path P at time t, we consider this as an evidence that path P is preferred by the driver at time t, thus should have a higher ranking score than other paths connecting the same source and destination. To solve the regression problem, we first propose an effective training data enriching method to obtain a compact and diversified set of training paths using historical trajectories, which provides a data foundation for efficient and effective learning. Next, we propose a multi-task learning framework that considers features representing both candidate paths and contexts. Specifically, a road network embedding is proposed to embed paths into feature vectors by considering both road network topology and spatial properties, such as distances and travel times. By modeling different departure times as a temporal graph, graph embedding is used to embed departure times into feature vectors. The objective function not only considers the discrepancies on ranking scores but also the reconstruction errors of the spatial properties of the paths, which in turn improves the final ranking estimation. Empirical studies on a substantial trajectory data set offer insight into the designed properties of the proposed framework, indicating that it is effective and practical in real world settings.