中国管理科学 ›› 2022, Vol. 30 ›› Issue (4): 218-227.doi: 10.16381/j.cnki.issn1003-207x.2020.1020
许保光1, 2, 常嘉欣1, 3, 高敏刚1
收稿日期:
2020-06-02
修回日期:
2020-06-18
出版日期:
2022-04-20
发布日期:
2022-04-26
通讯作者:
高敏刚(1979-),男(汉族),山东泰安人,中国科学院科技战略咨询研究院,副研究员,博士,研究方向:运筹优化及其应用,应急管理,科技战略,Email:mggao@casisd.cn
E-mail:mggao@casisd.cn
基金资助:
XU Bao-guang1,2, CHANG Jia-xin1,3, GAO Min-gang1
Received:
2020-06-02
Revised:
2020-06-18
Online:
2022-04-20
Published:
2022-04-26
Contact:
高敏刚
E-mail:mggao@casisd.cn
摘要: 本文考虑了道路信息外业采集的任务要求,人车混采的采集方式以及路网特性等方面,为道路信息采集人员的路径规划建立了满足人车混采约束的整数规划模型;提出了分阶段的转化算法,将其逐步转化为有限时间容量限制的弧路径问题(TCARP)。TCARP问题是一种NP-hard问题,精确求解算法无法在合理时间内得到问题的最优解,因此本文设计了求解TCARP问题的两种快速启发式算法TPS和TUH及其随机化版本;考虑到实际采集问题的大规模特性,在两种快速启发式算法的基础上构造GRASP-PA寻优算法。最后分别结合不同规模的基准算例和实际采集算例证明了本文所构造的算法的有效性。
中图分类号:
许保光, , 常嘉欣, , 高敏刚. 考虑人车混采的道路信息采集的路径规划研究[J]. 中国管理科学, 2022, 30(4): 218-227.
XU Bao-guang, CHANG Jia-xin, GAO Min-gang. Research on Routing Problems about Road Information Collection Considering Mixed Mapping Method[J]. Chinese Journal of Management Science, 2022, 30(4): 218-227.
[1] 詹红鑫, 王旭坪, 孙自来, 等. 基于邻域搜索的成品油多舱多目标配送路径优化算法研究[J]. 系统工程理论与实践, 2019, 39(10):2660-2675.Zhan Hongxin, Wang Xuping, Sun Zilai, et al. Variable neighborhood search for the multi-objective multi-compartment optimization of refined products distribution[J]. Systems Engineering—Theory & Practice, 2019, 39(10):2660-2675. [2] 郭放, 杨珺, 杨超. 考虑差异化服务时间的多车型电动汽车路径优化与充电策略研究[J]. 中国管理科学, 2019, 27(8):118-128.Guo Fang, Yang Jun, Yang Chao.Study on heterogeneous electric vehicle routing and batterycharging problem with the consideration of differentiated service cost[J]. Chinese Journal of Management Science, 2019, 27(8):118-128. [3] 李进, 傅培华, 李修琳,等. 低碳环境下的车辆路径问题及禁忌搜索算法研究[J]. 中国管理科学, 2015, 23(10):98-106.Li Jin, Fu Peihua, Li Xiulin, et al. Study on vehicle routing problem and tabu search algorithm under low-carbon environment[J]. Chinese Journal of Management Science, 2015, 23(10):98-106. [4] 祁明亮, 秦凯杰, 赵琰. 雪灾救援物资车辆-直升机联合运送的调度问题研究[J]. 中国管理科学, 2014, 22(3):59-67.Qi Mingliang, Qin Kaijie, Zhao Yan. Research on problem of scheduling of helicopter coordinated with vehicle for resources distribution in snowstorm[J]. Chinese Journal of Management Science, 2014, 22(3):59-67. [5] Golden B L, Wong R T. Capacitated arc routing problems[J]. Networks, 1981, 11(3):305-315. [6] 谢秉磊, 李颖, 刘敏. 带临时补充点的融雪剂撒布车辆路径问题[J]. 系统工程理论与实践, 2014, 34(6):1593-1598.Xie Binglei, Li Ying, Liu Min. Vehicle routing problem with temporary supplementary points for spreading deicing salt[J]. Systems Engineering—Theory & Practice, 2014, 34(6):1593-1598. [7] Gáspár, László, Bencze Z. Salting route optimization in hungary[J]. Transportation Research Procedia, 2016, 14:2421-2430. [8] Mourao M C, Pinto L S. An updated annotated bibliography on arc routing problems[J]. Networks, 2017,70(3): 144-194. [9] Pieter Vansteenwegen, Wouter Souffriau, Kenneth Srensen. Solving the mobile mapping van problem: A hybrid metaheuristic for capacitated arc routing with soft time windows[J]. Computers and Operations Research,2010,37(11): 1870-1876. [10] De Armas J, Keenan P, Juan A A, et al. Solving large-scale time capacitated arc routing problems: From real-time heuristics to metaheuristics[J]. Annals of Operations Research,2019, 273(1-2): 135-162. [11] KEENAN P: Technical Report. UCD Business School, University College Dublin. http://mis…, 2005. [12] Stern H I, Dror M. Routing electric meter readers[J]. Computers & Operations Research, 1979, 6(4):209-223. [13] Groves G, Roux J L, Vuuren J H V. Network service scheduling and routing[J]. International Transactions in Operational Research,2004, 11(6):613-643. [14] Luo He, Zhang Peng, Wang Jiajie, et al. Traffic patrolling routing problem with drones in an urban road system[J]. Sensors (Basel), 2019, 19(23):5164. [15] Marzolf F, Trepanier M, Langevin A. Road network monitoring: Algorithms and a case study[J]. Computers & Operations Research, 2006, 33(12):3494-3507. [16] Belenguer J M, Benavent E, Lacomme P, et al. Lower and upper bounds for the mixed capacitated arc routing problem[J]. Computers & Operations Research, 2006, 33(12):3363-3383. [17] Mourao M C, Amado L. Heuristic method for a mixed capacitated arc routing problem: A refuse collection application[J]. European Journal of Operational Research, 2005, 160(1):139-153. [18] Bautista J, Fernandez E, Pereira J. Solving an urban waste collection problem using ants heuristics[J]. Computers & Operations Research, 2008, 35(9):3020-3033. [19] Corberán , Laporte G. Arc routing. Problems, methods, and applications[M]. PA, USA: Sociaty for Industrial and Applied Mathenatics, 2015. [20] Edmonds J, Johnson E L. Matching, Euler tours and the Chinese postman[J]. Mathematical Programing, 1973, 5(1):80-91. [21] Whlk S, Laporte G. Computational comparison of several greedy algorithms for the minimum cost perfect matching problem on large graphs[J]. Computers & Operations Research, 2017, 87:107-113. [22] Resende M G, Ribeiro C C. GRASP: Greedy randomized adaptive search procedures[M]∥Search methodologies, Springer, 2014:287-312. [23] Golden B L, Dearmon J S, Baker E K. Computational experiments with algorithms fora class of routing problems[J]. Computers & Operations Research, 1983, 10(1):47-59. [24] Pearn W L. Approximate solutions for the capacitated arc routing problem[J]. Computers & Operations Research, 1989, 16(6): 589-600. [25] Ulusoy. The fleet size and mix problem for capacitated arc routing[J]. European Journal of Operational Research, 1985, 22(3): 329-337. [26] Bartolini E, Cordeau J, Laporte G. An exact algorithm for the capacitated arc routing problem with deadheading demand[J]. Informs, 2013, 61(2): 315-327. [27] Liu M, Singh H K, Ray T. Application specific instance generator and a memetic algorithm for capacitated arc routing problems[J]. Transportation Research Part C: Emerging Technologies, 2014, 43: 249-266. |
[1] | 赵雪峰, 吴伟伟, 吴德林, 时辉凝, 廉莹, 赵德从. 基于TPCBoost模型的新型交通服务定价研究—以纽约网约车为实例[J]. 中国管理科学, 2022, 30(10): 210-223. |
[2] | 李坚飞, 孙梦霞, 李蓓. 零售服务供应链动态演化中存在“质量桥”吗?[J]. 中国管理科学, 2022, 30(8): 130-142. |
[3] | 苏兵, 周佳其, LIN Guohui, 姬浩, 徐阳. 应急救援物资紧缺的两级配送路径选择研究[J]. 中国管理科学, 2022, 30(8): 155-163. |
[4] | 张艳辉, 高云帆. 在线声誉水平对消费者关注度的影响:对大众点评的实证分析[J]. 中国管理科学, 2022, 30(8): 277-286. |
[5] | 代建生, 刘悦. 公平偏好和销售努力下供应链期权契约协调[J]. 中国管理科学, 2022, 30(7): 20-30. |
[6] | 黄肖玲, 陈焕平, 高晓楠, 王丹, 刘进平, 陈继红. 需求可拆分Milk-run与 Supply-hub协同的汽车零部件入厂物流优化[J]. 中国管理科学, 2022, 30(7): 59-68. |
[7] | 胡玉真, 李倩倩, 江山. 跨境电商企业海外仓选址多目标优化研究[J]. 中国管理科学, 2022, 30(7): 201-209. |
[8] | 刘洋, 邓前前, 樊治平, 张琦. 网约车平台峰时补贴策略研究[J]. 中国管理科学, 2022, 30(7): 210-220. |
[9] | 孙彩虹, 李肖依, 于辉. 跨国双向供应链物流合作模型分析[J]. 中国管理科学, 2022, 30(6): 66-76. |
[10] | 周正龙, 简昕格. 零售商嵌入专业技术的营销策略研究[J]. 中国管理科学, 2022, 30(6): 77-86. |
[11] | 李延晖, 廖康, 徐璐. 电商平台与服务提供商的用户隐私信息管理策略研究[J]. 中国管理科学, 2022, 30(6): 157-166. |
[12] | 舒嘉, 丁溢, 倪文君. 管理科学与工程理论与方法突破若干重点前沿领域[J]. 中国管理科学, 2022, 30(5): 27-30. |
[13] | 黄诗童, 赵希男, 周岩. 面向动态评价的长效机制及其构建研究[J]. 中国管理科学, 2022, 30(5): 180-191. |
[14] | 王婧怡, 佘金凤, 董双. 基于SVN的重大工程组织安全行为价值网络及驱动路径研究[J]. 中国管理科学, 2022, 30(5): 275-286. |
[15] | 汪平, 张丽君, 孙鲁平. 参照依赖的消费者选择及其建模方法回顾与展望[J]. 中国管理科学, 2022, 30(4): 119-131. |
阅读次数 | ||||||
全文 |
|
|||||
摘要 |
|
|||||
|