The problem of mobile sequential recommendation is presented to suggest a route connecting some 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 dynamical programming based method to solve this problem. Our method consists of two separate stages: an offline pre-processing stage and an online search stage. The offline stage pre-computes optimal potential sequence candidates from a set of pick-up points, and the online stage selects the optimal driving route based on the pre-computed sequences with the current position of an empty taxi. Specifically, for the offline pre-computation, a backward incremental sequence generation algorithm is proposed based on the 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 can also be applied to the generated potential sequences to remove the non-optimal ones of a certain length. Since the pruning effect continuously increases with the increase of the sequence length, our method can search the optimal driving route efficiently in the remaining potential sequence candidates. Experimental results on real and synthetic data sets show that the pruning percentage of our method is significantly improved compared to the state-of-the-art methods, which makes our method can be used to handle the problem of mobile sequential recommendation with more pick-up points and to search the optimal driving routes in arbitrary length ranges.
Lu . @cite_8 introduced a problem of finding optimal trip route with time constraint. They also proposed an efficient trip planning method considering the current position of a user. However, their method uses the score of attractions to measure the preference of a route.
@cite_8
145447398
Short distance trips are crucial for urban mobility and accessibility. They can contribute to integrated transportation (the “last mile” problem), and more generally to urban ad-hoc ride sharing scenarios. Since no transport provider covers short distance trips where demand arises, private car use is flourishing in recent decades, with all the known disadvantages of traffic congestion, resource wastes, air pollution, and insufficient parking space especially in city centers. Taxis are focusing on providing a door-to-door service, but they do not perform well in short distance trip pickup and delivery services. This paper identifies the obstacles, and suggests the empty cruise time of taxis as (a) a feasible solution for the short distance trip problem, and (b) a contribution to develop a short distance trip market for the taxi industry. This empty cruise contribution hypothesis is investigated by testing different models that define ad-hoc matches of passengers and empty cruising taxis. An agent-based simulation is designed to study the match probability by these models. Based on the experimental results it is shown that taxi empty cruise match models have the potential to solve the short distance problem and to develop the taxi short distance trip markets.