关键词: 时间容量限制；弧路径优化；道路信息采集；启发式算法

Abstract: 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.01s 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.

Key words: time capacitated; arc routing problem; road information collection; heuristic algorithm