Path Clustering based on a Novel Dissimilarity Function for Ride-Sharing Recommenders

Ride-sharing practice represents one of the possible answers to the traffic congestion problem in today's cities. In this scenario, recommenders aim to determine similarity among different paths with the aim of suggesting possible ride shares. In this paper, we propose a novel dissimilarity function between pairs of paths based on the construction of a shared path, which visits all points of the two paths by respecting the order of sequences within each of them. The shared path is computed as the shortest path on a directed acyclic graph with precedence constraints between the points of interest defined in the single paths. The dissimilarity function evaluates how much a user has to extend his/her path for covering the overall shared path. After computing the dissimilarity between any pair of paths, we execute a fuzzy relational clustering algorithm for determining groups of similar paths. Within these groups, the recommenders will choose users who can be invited to share rides. We show and discuss the results obtained by our approach on 45 paths.