Research On Two-fold Time-dependent Travel Route Planning

Traditional route planners commonly focus on finding the shortest path between two points in terms of travel distance or time over road networks.However,in real cases,especially in the era of smart cities where many kinds of transportation-related data become easily available,recent years have witnessed an increasing demand of route planners that need to optimize for multiple criteria,e.g.,finding the route with the highest accumulated scenic score along(utility)while not exceeding the given travel time budget(cost).Such problem can be viewed as a variant of Arc Orienteering Problem(AOP),which is well-known as an NP-hard problem.In this thesis,targeting a more realistic AOP,we allow both utility and travel time(cost)values on each arc of the road network are time-dependent.This problem is defined as the two-fold time-dependent problem(2TD-AOP).In this thesis,we conduct research on 2TD-AOP and propose two solutions.First,we propose a memetic algorithm to solve it.To be more specific,within the given travel time budget,we find a route with a high cumulative scenic score.It includes two main phases,i.e.,chromosome generation and the local search.In the phase of initiation,for each population,we iteratively add suitable arcs with high scenic score and build a path from the origin to the destination via a complicate procedure consisting of search region narrowing,chromosome encoding and decoding.In the phase of the local search,each path is improved via chromosome selection,mutation and crossover operations.Through the iteration of the population,the proportion of excellent individuals in the population is continuously increased.Then,on the premise of not exceeding the time budget,a route with the highest cumulative scenic score is selected and returned to the user.Finally,we evaluate the proposed memetic algorithm in both synthetic and real-life datasets extensively,and the experimental results demonstrate that it outperforms the baselines.Secondly,we further analyze the shortcomings of the memetic algorithm to solve the 2TD-AOP,and propose a potential arc encoding algorithm to plan a route with a high cumulative utility under the given time budget.This process can be roughly divided into two phases,i.e.,query table establishment and the segment tree generation.The query table records the time division map of all valid road segments.Based on the departure time and travel time budget,the time zone of each road segment is divided into an invalid zone,a critical zone and a valid zone.The critical zone is established in consideration of the time dependence of travel time.The query table avoids repeated judgments on the segment validity during the encoding process.In the phase of the segment tree generation,we propose a decision rule for the potential road segment.By encoding the potential road segment,we generate multiple road segment sequences,then decode them into specific driving routes.Finally we select a route with a high cumulative utility and return it to the user.We evaluate the proposed heuristic algorithm in synthetic datasets,and the experimental results show that our algorithm achieves better route planning results in a shorter running time.