摘要
本文考虑了道路信息外业采集的任务要求,人车混采的采集方式以及路网特性等方面,为道路信息采集人员的路径规划建立了满足人车混采约束的整数规划模型;提出了分阶段的转化算法,将其逐步转化为有限时间容量限制的弧路径问题(TCARP)。TCARP问题是一种NP-hard问题,精确求解算法无法在合理时间内得到问题的最优解,因此本文设计了求解TCARP问题的两种快速启发式算法TPS和TUH及其随机化版本;考虑到实际采集问题的大规模特性,在两种快速启发式算法的基础上构造GRASP-PA寻优算法。最后分别结合不同规模的基准算例和实际采集算例证明了本文所构造的算法的有效性。
Traffic Maps play an important role in daily life.The various kinds of travel planning navigation and driverless cars need high-precision and timely updated map to provide accurate positioning and path planning reference.The collection of road information is the most significant way for map companies to update maps ensuring the accuracy of road data.Due to the development of the city and the rapid change of road information,there is an urgent need to update the maps frequently.In order to program the paths of road information collection efficiently and scientifically so as to save the collection cost and improve the collection efficiency,considering the requirement of road information field collection,collection methods of mixed mapping and road network characteristics,a mixed integer programming model with the objective function of minimizing the total acquisition costs is established for the path planning of road information collection.Then,a staged transformation algorithm is proposed and used to gradually transform it into the Time Capacitated Arc Routing Problem(TCARP).TCARP is an NP-hard problem that the exact algorithm can not get the optimal solution in a reasonable time,so in this paper two fast heuristic algorithms,TPS and TSH,are designed for TCARP problem,and the randomized implementation of the two algorithms,R-TPS and R-TUH is proposed.Based on the GRASP framework,the GRASP-PA algorithm is constructed combining with these two algorithms as the initial solution.Unlike the traditional local search operator,a time-saving search process,Partion-Adjust(PA),is constructed to make it more suitable for the large-scale TCARP problem.Then,the benchmark instances and large-scale road information collection examples in City provided by a map supplier are used to prove the effectiveness of constructive heuristic algorithms and GRASP-PA algorithm mentioned above.On all the benchmark instances,TPS and TUH algorithms can give a definite solution with good quality in less than 0.01 s on average,which demonstrates the validity of the two constructive heuristic algorithms in application scenarios requiring real-time routing decisions.On the large-scale road information collection instances on mixed network,collection methods of mixed mapping are completed,verifying the effectiveness of our phased solution algorithm.The results show that for large-scale collection examples,the GRASP-PA algorithm performs a good trade-off performance between computing time and solution quality compared with previous randomization methods and local search operators.The models and algorithms constructed in this paper can provide methodological support for more application scenarios of arc path optimization similar to road information acquisition.
作者
许保光
常嘉欣
高敏刚
XU Bao-guang;CHANG Jia-xin;GAO Min-gang(Institutes of Science and Development,Chinese Academy of Sciences,Beijing 100190,China;School of Public Policy and Management,University of Chinese Academy of Sciences,Beijing 100049,China;University of Chinese Academy of Sciences,Beijing 100049,China)
出处
《中国管理科学》
CSSCI
CSCD
北大核心
2022年第4期218-227,共10页
Chinese Journal of Management Science
基金
国家自然科学基金资助重大项目(72134004)。
关键词
时间容量限制
弧路径优化
道路信息采集
启发式算法
time capacitated
arc routing problem
road information collection
heuristic algorithm
