An Efficient Trust-Oriented Trip Planning Method in Road Networks

In recent years, Location-Based Services (LBSs) have been widely applied, and many websites provide LBSs which allow users to make trip planning with multiple activities on the Trip to meet their different demands (e.g., Distance, location, service, etc.). However in most studies, trip planning just focuses on finding the shortest trip that goes through many services during visiting many locations (e.g., Restaurant, gas station, and bank). In this paper, we take the trust of services provided at the POI into consideration among the trip, proposing an Efficient Trust-Oriented Trip Planning Method (ETOTP) in Road Networks, ETOTP for short. In a geographical trip planning, given a set points of interest (POIs) which may have many constraints (i.e., The category of the POI, and the trust of POI), the goal of this paper is to find an effective trip that (1) starts at a given location S, (2) ends at a given location D, (3) visits the POIs with the given categories, and (4) satisfies the trust requirements of the services. Since ETOTP covers the NP-Complete Multi-Constrained Path Selection (MCP) problem, it is NP-Complete as well. Therefore, it is a challenging problem to efficiently deliver a route with the required services and trust. Hence, in this work we propose three approximation algorithms for the ETOTP and conduct the experiments on a synthetic dataset in a real road network. The experimental results demonstrate that our proposed method can plan a trip having the shortest distance with higher trust values and good efficiency.