The problem of
mobile sequential recommendation is to suggest a route connecting a set of
pick-up points for a taxi driver so that he/she is more likely to get
passengers with less travel cost. Essentially, a key challenge of this problem
is its high computational complexity. In this paper, we propose a novel dynamic
programming based method to solve the mobile sequential recommendation problem
consisting of two separate stages: an offline pre-processing stage and an
online search stage. The offline stage pre-computes potential candidate
sequences from a set of pick-up points. A backward incremental sequence generation
algorithm is proposed based on the identified iterative property of the cost
function. Simultaneously, an incremental pruning policy is adopted in the
process of sequence generation to reduce the search space of the potential
sequences effectively. In addition, a batch pruning algorithm is further
applied to the generated potential sequences to remove some non-optimal
sequences of a given length. Since the pruning effectiveness keeps growing with
the increase of the sequence length, at the online stage, our method can
efficiently find the optimal driving route for an unloaded taxi in the
remaining candidate sequences. Moreover, our method can handle the problem of
optimal route search with a maximum cruising distance or a destination
constraint. Experimental results on real and synthetic data sets show that both
the pruning ability and the efficiency of our method surpass the
state-of-the-art methods. Our techniques can therefore be effectively employed
to address the problem of mobile sequential recommendation with many pick-up
points in real-world applications.
No comments:
Post a Comment