针对当前土地利用监管外业核查难以快速、准确地遍历所有待核查地块等问题,进行了土地核查路径规划与目标导航定位技术研究。提出了基于改进蚁群算法的土地核查路径规划与目标导航问题的三阶段求解方法,即“先分群,再搜索阶段最优路径,最后实现全局最优路径规划”,将大区域的多辆车路径规划问题简化为小范围单辆车路径规划与目标导航,利用改进蚁群算法求解出土地核查全局最优路径和导航信息。在此基础上对扬州市面积约6 600 km2范围内580个待核查图斑开展土地核查,利用该算法将外业核查车辆行驶路程由2 250 km缩短为1 683.3 km,缩短了25.2%。精准的目标导航方法较采用商用导航仪提高了工作效率和核查目标导航的准确性。
Abstract
In view of the problem that it was difficult for land management staffs to fast and accurately find and reach all land parcels need to be inspected in land use inspection work, the technique of land use inspection routing plan and object navigation was studied. A three-stage ant colony algorithm for land inspection routing plan and target navigation was presented, i.e. “first, clustering targets, then searching local optimal path, at last realizing global optimum path”. The three-stage ant colony algorithm simplified multiple vehicle routing and targets navigation in a large area to sole vehicle routing and targets navigation in a small area, and searched the land supervision global optimal routing and navigation information based on improved ant colony algorithm. The experiment showed that, through surveying 580 pattern spots in 6 600 km2, the method improved vehicle-miles of travel from 2 250 km to 1 683.3 km, shorten by 25.2%. At the same time this accurate object navigation enhanced work efficiency and veracity if compared to exacting commercial navigator method.
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
参考文献
[1] Gupta A, Ravi R. Technical note-approximation algorithms for VRP with stochastic demands[J].Operations research, 2012, 60(1): 123-127.
[2] Lin C H, Choy K L, Ho G T S, et al. Survey of green vehicle routing problem: past and future trends[J].Expert systems with applications, 2014, 41(4): 1118-1138.
[3] Suzuki Y. A variable-reduction technique for the fixed-route vehicle-refueling problem[J].Computers and industrial engineering, 2014, 67(1): 204-215.
[4] Bortfeldt A, Homberger J. Packing first, routing second-a heuristic for the vehicle routing and loading problem[J].Computers and operations research, 2013, 40(3): 873-885.
[5] Figliozzi M A. An iterative route construction and improvement algorithm for the vehicle routing problem with soft time windows[J].Transportation research part C: emerging technologies, 2010, 18(5): 668-679.
[6] Lenstra J K,Kan A R.Complexity of vehicle routing and scheduling problems[J]. Networks, 1981(11): 221-227.
[7] Laporte G. The vehicle routing problem: An overview of exact and approximate algorithms[J]. European journal of operational research, 1992, 59(3): 345-358.
[8] Taillard É, Badeau P, Gendrean M, et al. A tabu search heuristic for the vehicle routing problem with soft time windows[J].Transportation science, 1997, 31(2): 170-186.
[9] Reed M. An ant colony algorithm for the multi-compartment vehicle routing problem[J].Applied soft computing journal, 2014, 15: 169-176.
[10] Wu X D. A two stage ant colony optimization algorithm for the vehicle routing problem with time windows[J].International journal of advancements in computing technology, 2012, 4(1): 485-491.
[11] 周生伟,蒋同海,张荣辉.改进遗传算法求解VRP问题[J].计算机仿真,2013,30(12):140-143.
Zhou S W, Jiang T H, Zhang R H. Improved genetic algorithm for VRP[J].Journal of computer simulation, 2013, 30(12): 140-143.
[12] 黄敏芳,胡祥培,王征,等. 车辆路径问题的三阶段求解方法研究[J].管理科学,2009,22(3): 37-46.
Huang M F, Hu X P, Wang Z, et al. A three-stage intelligent solution approach to Vehicle Routing Problem[J]. Journal of management science, 2009, 22(3): 37-46.
[13] Stutzle T,Hoos H. Max-min ant system and local search for the traveling salesman problem[C]// IEEE International conference on evolutionary computation and evolutionary programming conference. New York: IEEE Press,1997:309-314.
[14] 刘霞,杨超.最小-最大车辆路径问题的蚁群算法[J].解放军理工大学学报(自然科学版),2012,13(3):336-341.
Liu X, Yang C. Min-min vehicle routing problem based on colony algorithm[J].Journal of PLA University of Science and Technology(natural science edition), 2012, 13(3):336-341.
[15] Bullnheimer B,Hartl R F,Strauss C. A new rank based Version of the ant system: a computational study[J]. Central European journal for operation research and economics, 1999, 7(1):25-38.
[16] 张涛,胡佳研,李福娟,等.基于ASRank和MMAS的蚁群算法求解飞机指派问题[J].管理工程学报,2012,26(2):148-153.
Zhang T, Hu J Y, Li F J, et al. Ant colony algorithm based on the ASRank and MMAS for the aircraft assigning problem[J].Journal of industrial engineering and engineering management, 2012, 26(2):148-153.
[17] 张涛,田文馨,张玥杰,等. 基于剩余装载能力的蚁群算法求解同时送取货车辆路径问题[J].控制理论与应用,2009,26(5):546-549.
Zhang T, Tian W X, Zhang Y J, et al. A residual-loading-capacity-based ant colony system for the vehicle routing problem with simultaneous delivery and pickup[J]. Control theory & applications, 2009, 26(5):546-649.
[18] 丁秋雷,胡祥培,李永先.求解有时间窗的车辆路径问题的混合蚁群算法[J].系统工程理论与实践,2007,27(10):98-103.
Ding Q L, Hu X P, Li Y X. A hybrid ant colony system for vehicle routing problem with time windows[J]. Journal of systems engineering-theory & practice, 2007,27(10):98-103.
基金
收稿日期:2015-01-20 修回日期:2015-08-01
基金项目:国家国土资源公益性行业科研专项项目(201211028-6)
第一作者:王志杰(stampabc@126.com),讲师,博士。
引文格式:王志杰,单文龙. 基于三阶段蚁群算法的土地利用核查路径规划与目标导航[J]. 南京林业大学学报(自然科学版),2016,40(1):142-146.
PDF(2174645 KB)
