Enjoy the most beautiful scene now: a memetic algorithm to solve two-fold time-dependent arc orienteering problem

摘要

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 paper, targeting a more realistic AOP, we allow both scenic score (utility) and travel time (cost) values on each arc of the road network are time-dependent (2TD-AOP), and propose a memetic algorithm to solve it. To be more specific, within the given travel time budget, 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, local-improvement-based mutation and crossover operations. 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.