Online Cruising Mile Reduction in Large-Scale Taxicab Networks

摘要

In the taxicab industry, a long-standing challenge is how to reduce taxicabs’ miles spent without fares, i.e., cruising miles. The current solutions for this challenge usually depend on passengers to actively provide their locations in advance for pickups. To address this challenge without the burden on passengers, in this paper, we propose a cruising system, , for taxicab drivers to find efficient routes to pick up passengers to reduce cruising miles. According to the real-time pick-up events from nearby taxicabs, characterizes a cruising process with a , and assigns weights on edges of the cruising graph to indicate the utility of cruising corresponding road segments. Our weighting process considers the number of nearby passengers and taxicabs together in real-time, aiming at two scenarios where taxicabs are explicitly or implicitly coordinated with each other. Based on a weighted cruising graph, when a taxicab becomes vacant, provides a distributed online scheduling strategy to obtain and update an efficient cruising route with the minimum length and at least one arriving passenger. We evaluate based on a real-world GPS dataset from a Chinese city Shenzhen with taxicabs. The evaluation results show that assists taxicab drivers to reduce cruising miles by percent on average.