基于多旅行商问题的应急设施服务区划分模型

交通运输系统工程与信息 ›› 2020, Vol. 20 ›› Issue (5): 205-211.

基于多旅行商问题的应急设施服务区划分模型

赵星^*，吉康，申珂

河海大学土木与交通学院，南京 210098

收稿日期:2020-05-19 修回日期:2020-08-22 出版日期:2020-10-25 发布日期:2020-10-26
作者简介:赵星（1986-），女，重庆人，副教授，博士.
基金资助:
中央高校基本科研业务费专项资金/ Fundamental Research Funds for the Central Universities of Ministry of Education of China(B200202072).

A Service Area Division Model for Emergency Facilities Based on Multiple Traveling Salesman Problem

ZHAO Xing, JI Kang, SHEN Ke

College of Civil and Transportation Engineering, Hohai University, Nanjing 210098, China

Received:2020-05-19 Revised:2020-08-22 Online:2020-10-25 Published:2020-10-26

摘要/Abstract

摘要：

基于多旅行商问题，增设集散中心需求及应急服务设施资源容量约束条件，以最小化遍历区域内全部集散中心的综合旅行时间成本为优化目标，构建一种应急设施服务区划分模型，确定各应急设施的服务区范围.设计一种复合算法求解模型，首先基于P-中值选址模型的优化理念，形成初始方案；继而加入禁忌搜索算法，结合LKH求解器对模型进行迭代优化求得最优解.基于宁波市北仑区实际拓扑网络进行案例分析，验证了模型和求解方法的有效性.

关键词: 交通工程, 应急物资调度, 多旅行商问题, 服务区划分, 突发事件

Abstract:

This paper develops a service area division model for emergency facilities based on the multiple traveling salesman problem. The model aims at minimizing the overall time cost of traversing all distribution centers. With constraints on the demand of distribution centers and the capacity of emergency facilities, the service area of each emergency facility can be determined. A hybrid algorithm is designed to obtain the optimal solution. Based on the P-median location model, an initial feasible solution is generated. The Tabu Search algorithm is then applied to search for the optimal solution combining with the LKH solver. A case study based on the realistic network topology of Beilun District, Ningbo, is carried out to verify the effectiveness of the proposed model and solution method.

Key words: traffic engineering, emergency resource scheduling, multiple traveling salesman problem, service area division, emergencies

中图分类号:

U491.1

赵星，吉康，申珂. 基于多旅行商问题的应急设施服务区划分模型[J]. 交通运输系统工程与信息, 2020, 20(5): 205-211.

ZHAO Xing, JI Kang, SHEN Ke. A Service Area Division Model for Emergency Facilities Based on Multiple Traveling Salesman Problem[J]. Journal of Transportation Systems Engineering and Information Technology, 2020, 20(5): 205-211.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.tseit.org.cn/CN/abstract/abstract20136.shtml

http://www.tseit.org.cn/CN/Y2020/V20/I5/205

参考文献

[1] 胡大伟, 陈希琼, 高扬. 定位—路径问题综述[J]. 交通运输工程学报, 2018, 18(1): 111- 129. [HU D W, CHEN X Q, GAO Y. Review on location- routing problem[J]. Journal of Traffic and Transportation Engineering, 2018, 18(1): 111-129.]

[2] PAN A P. A constructive genetic algorithm for the Pmedian location problem of typhoon emergency shelter in China coastal rural areas[J]. Key Engineering Materials, 2011, 480-481(9): 1215-1220.

[3] 郭鹏辉, 朱建军, 王翯华. 考虑异质物资合车运输的灾后救援选址—路径—配给优化[J]. 系统工程理论与实践, 2019, 39(9): 2345- 2360. [GUO P H, ZHU J J, WANG S H. Location- routing- allocation problem with consolidated shipping of heterogeneous relief supplies in post-disaster rescue[J]. Systems Engineering-Theory & Practice, 2019, 39(9): 2345-2360.]

[4] STEVEN A, HERTONO G F, HANDARI B D. Implementation of clustered ant colony optimization in solving fixed destination multiple depot multiple traveling salesman problem[C]. International Conference on Informatics and Computational Sciences (ICICoS), 2017.

[5] LIU M, ZHAO L. Optimization of the emergency materials distribution network with time windows in anti- bioterrorism system[J]. International Journal of Innovative Computing, Information & Control: IJICIC, 2009, 5(11): 3615-3624.

[6] ALENCAR R C, SANTANA C J, BASTOS- FILHO C J A. Optimizing routes for medicine distribution using team ant colony system[C]. International Conference on Hybrid Intelligent Systems, Springer, 2018.

[7] 任刚, 华璟怡, 张志云, 等. 基于反向车道与冲突消除的疏散网络优化设计[J]. 中国公路学报, 2015, 28(3): 88-93. [REN G, HUA J Y, ZHANG Z Y, et al. Optimal evacuation network design with contraflow and conflict elimination strategy[J]. China Journal of Highway and Transport, 2015, 28(3): 88-93.]

[8] LOIS A, ZILIASKOPOULOS A. Large neighborhood heuristic algorithm for multivehicle dial-a-ride problem with time windows[C]. Transportation Research Board, 2008.

[1]	林建新, 刘博, 赵霞, 张蕾. 基于混合约束自编码器的机动车工况智能构建方法[J]. 交通运输系统工程与信息, 2022, 22(2): 109-116.
[2]	戢晓峰, 耿昭师. 山区双车道公路货车碰撞预测的双变量冲突极值模型[J]. 交通运输系统工程与信息, 2022, 22(2): 230-238.
[3]	张建波, 孙建平, 徐春玲, 郭镜霞, 温慧敏, 宋国华. 考虑交通运行条件影响的驾驶员特征聚类[J]. 交通运输系统工程与信息, 2022, 22(2): 330-336.
[4]	马景峰, 任刚, 李豪杰, 曹奇, 杜建玮. 电动自行车与机动车事故严重性影响因素分析[J]. 交通运输系统工程与信息, 2022, 22(2): 337-348.
[5]	宗芳, 王猛, 贺正冰. 考虑多车影响的分子动力学智能网联跟驰模型[J]. 交通运输系统工程与信息, 2022, 22(1): 37-48.
[6]	马小龙, 余强, 刘建蓓. 基于路侧毫米波雷达的车辆碰撞概率计算方法[J]. 交通运输系统工程与信息, 2022, 22(1): 57-66.
[7]	廖鹏, 唐铁桥. 基于车辆动力传动和转向系统的换道轨迹优化策略[J]. 交通运输系统工程与信息, 2022, 22(1): 98-105.
[8]	刘永红, 罗霞, 胡剑鹏. 考虑临时和预约需求的共享泊位动态分配方法[J]. 交通运输系统工程与信息, 2022, 22(1): 171-181.
[9]	袁振洲, 郭曼泽, 彭泳鑫, 杨洋. 基于梯度关联规则的老年行人交通事故风险识别[J]. 交通运输系统工程与信息, 2022, 22(1): 195-208.
[10]	张玉婷, 陈波佑, 张双焱, 闫学东, 李晓梦. 抵近信控交叉口分心驾驶识别模型[J]. 交通运输系统工程与信息, 2022, 22(1): 217-224.
[11]	宋浪, 王健, 杨滨毓, 安实. 连续流交叉口左转非机动车交通组织创新设计[J]. 交通运输系统工程与信息, 2022, 22(1): 225-233.
[12]	白婧荣, 唐伯明, 孙宗元, 毕辉云, 向恬君. 毗邻互通立交特长隧道驾驶负荷研究[J]. 交通运输系统工程与信息, 2022, 22(1): 301-310.
[13]	郭彦茹, 罗志雄, 王家川, 何方. 数据驱动的共享单车停放区规划方法研究[J]. 交通运输系统工程与信息, 2021, 21(6): 9-16.
[14]	李君羡, 沈宙彪, 童文聪, 吴志周. 基于分类车头时距的城市道路大型车影响分析[J]. 交通运输系统工程与信息, 2021, 21(6): 55-62.
[15]	卢凯, 周志洁, 张勇刚, 赵世杰, 徐广辉. 面向单向交通路网的绿波协调设计方法[J]. 交通运输系统工程与信息, 2021, 21(6): 74-83.