Design And Implementation Of An Activity-constrained Dependency-aware Trip Planning System

With the fast development of geo-positioning technologies and the widespread use of the internet,trip recommendation service is gaining its popularity.Nowadays,mainstream search engine companies have all introduced their own trip recommendation services,such as Microsoft's Bing Map and Auto Navi's AMap.Just typing in our start point and destination,we can get a route from the start point to the destination from these services.By using these services,people can easily find high quality routes through computers or smart phones in real time.Accordingly,travel becomes incredibly convenient and the efficiency of our lives and work is enhanced.High quality trip recommendation relies on efficient trip planning algorithms.Therefore,intensive efforts in both academic and industry communities have been made to study trip planning,and trip planning algorithms for different scenarios have been introduced to meet people's needs.Recently some novel algorithms have been proposed to support activity intention based trip planning,in which trip search is carried out on categorical points of interests(POIs),with a goal to find the trips that can cover needed POIs to support all users' intended activities.However,few methods can allow the activities to be carried out in certain temporal dependency.Obviously,the consideration of temporal dependency makes activity intention based trip planning more practical in use but more challenging in design.To cope with the challenge,we present two activity-constrained dependency-aware trip planning algorithms and basing on them we develop a system called ADT.Specifically,our work covers the following several aspects:(1)We propose a dependency aware algorithm(DA).Precomputation isn't needed byDA,and thus real time searching and real time updating of road network and points of interests are supported.(2)We propose a spatial clustering based algorithm(S C).Benefit from precomputation,the solution routes recommended in S Care shorter than those recommended in DA.(3)We implement a demo system called ADT and carry out some experiments on real data sets to prove the practicability of it.ADT provides service of activity-constrained dependency-aware trip planning and use the graphical user interface to visually show the solution routes.