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

作     者：Chao CHEN Liping GAO Xuefeng XIE Zhu WANG Chao CHEN;Liping GAO;Xuefeng XIE;Zhu WANG

作者机构：School of Computer ScienceChongqing UniversityChongqing 400044China School of Computer ScienceNorthwestern Polytechnical UniversityXi'an 710072China 

出 版 物：《Frontiers of Computer Science》 (中国计算机科学前沿（英文版）)

年 卷 期：2020年第14卷第2期

页      面：364-377页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：the National Key Research and Development Project of China(2017YFB1002000) the National Natural Science Foundation of China(Grant Nos.61602067 and 61872050) the Fundamental Research Funds for the Central Universities(2018cdqyjsj0024) the Chongqing Basic and Frontier Research Program(cstc2018jcyj AX0551) the Frontier Interdisciplinary Research Funds for the Central Universities(106112017cdjqj188828) 

主　　题：arc orienteering problem two-fold timedependent scenic score travel time memetic algorithm 

摘      要：Traditional route planners commonly focus on finding the shortest path between two points in terms of travel distance or time over road ***,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 *** 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 *** 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 *** the phase of the local search,each path is improved via chromosome selection,local-improvement-based mutation and crossover ***,we evaluate the proposed memetic algorithm in both synthetic and real-life datasets extensively,and the experimental results demonstrate that it outperforms the baselines.