基于深度强化学习的深圳市急救车调度算法

doi:10.19678/j.issn.1000-3428.0061931

计算机工程 ›› 2022, Vol. 48 ›› Issue (9): 298-304. doi: 10.19678/j.issn.1000-3428.0061931

基于深度强化学习的深圳市急救车调度算法

吴仍裕¹, 周强¹, 于海龙^2,4, 王亚沙^3,4

1. 深圳市急救中心, 广东深圳 518000;
2. 北京大学信息科学技术学院, 北京 100871;
3. 北京大学软件工程国家工程研究中心, 北京 100871;
4. 北京大学高可信软件技术教育部重点实验室, 北京 100871

收稿日期:2021-06-16 修回日期:2021-10-05 发布日期:2021-10-26
作者简介:吴仍裕(1970—),男,主治医师,主研方向为急救与灾害应急管理;周强(通信作者),主任医师、硕士;于海龙,博士研究生;王亚沙,教授、博士。
基金资助:
深圳市“医疗卫生三名工程”项目（SZSM201911005）。

Ambulance Dispatching Algorithm in Shenzhen Based on Deep Reinforcement Learning

WU Rengyu¹, ZHOU Qiang¹, YU Hailong^2,4, WANG Yasha^3,4

1. Shenzhen Center for Prehospital Care, Shenzhen, Guangdong 518000, China;
2. School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China;
3. National Engineering Research Center for Software Engineering, Peking University, Beijing 100871, China;
4. Key Lab of High Confidence Software Technologies, Ministry of Education, Peking University, Beijing 100871, China

Received:2021-06-16 Revised:2021-10-05 Published:2021-10-26

摘要/Abstract

摘要： 在院前急救领域中，急救反应时间是指患者拨打急救电话后，急救车到达现场的时间。传统急救车调度算法未全面考虑急救环境的动态性和复杂性因素，导致模型优化的急救反应时间与实际情况存在偏差。将急救车调度问题建模成马尔科夫决策过程，构建基于深度强化学习的急救车调度算法。以多层感知机作为评分网络结构，通过将急救站的动态信息映射为各个急救站的得分，确定急救车被调往各急救站的概率。同时，结合急救车调度的动态决策特点，利用强化学习中演员-评论家框架下的近端策略优化算法改进评分网络参数。在深圳市急救中心真实急救数据集上的实验结果表明，相比Fixed、DSM、MEXCLP等算法，该算法在每个急救事件中的急救反应时间平均缩短约80 s，并且在10 min内急救车的平均到达比例为36.5%，能够实时地将急救车调度到合适的急救站。

关键词: 强化学习, 神经网络, 急救车调度, 动态调度, 马尔科夫决策过程

Abstract: In prehospital emergency, the emergency response time refers to the time when the ambulance arrives at the scene after the patient dials the emergency phone number.The traditional ambulance dispatching algorithm does not fully consider the dynamics and complexity factors of the emergency environment, resulting in the deviation between the optimization emergenay response time of the model and the actual situation.The ambulance dispatching problem is modeled as a Markov Decision Process (MDP), and an ambulance dispatching algorithm based on deep reinforcement learning is constructed.The multilayer perceptron is used as the scoring network structure, and the dynamic information of the emergency station is mapped to the scores of each emergency station to determine the probability of the ambulance being transferred to each emergency station.Combined with the dynamic decision-making characteristics of ambulance dispatching, the Proximal Policy Optimization (PPO) algorithm under the Actor-Critic framework in reinforcement learning is used to improve the parameters of the scoring network.The experimental results for an actual emergency dataset of the Shenzhen center for prehospital care show that compared with the Fixed, DSM, MEXCLP, and other algorithms, the emergency response time of this algorithm in each emergency event is shortened by approximately 80 s on average, and the average arrival proportion of emergency vehicles within 10 min is 36.5%.The ambulances are dispatched to the appropriate emergency stations in real time.

Key words: reinforcement learning, neural network, ambulance dispatching, dynamic dispatching, Markov Decision Process(MDP)

中图分类号:

TP391

吴仍裕, 周强, 于海龙, 王亚沙. 基于深度强化学习的深圳市急救车调度算法[J]. 计算机工程, 2022, 48(9): 298-304.

WU Rengyu, ZHOU Qiang, YU Hailong, WANG Yasha. Ambulance Dispatching Algorithm in Shenzhen Based on Deep Reinforcement Learning[J]. Computer Engineering, 2022, 48(9): 298-304.

http://www.ecice06.com/CN/Y2022/V48/I9/298

图/表 6

20221017111548

20221017111551

20221017111555

20221017111600

20221017111604

20221017111607

参考文献

[1] 深圳市急救中心.深圳市急救中心简介[EB/OL].[2021-05-10].http://wjw.sz.gov.cn/szsjjzx/jggk_161338/zxjj_161339/. Shenzhen Center for Prehospital Care.Introduction to Shenzhen center for prehospital care[EB/OL].[2021-05-10].http://wjw.sz.gov.cn/szsjjzx/jggk_161338/zxjj_161339/. (in Chinese)
[2] BLACKWELL T H, KAUFMAN J S.Response time effectiveness:comparison of response time and survival in an urban emergency medical services system[J].Academic Emergency Medicine:Official Journal of the Society for Academic Emergency Medicine, 2002, 9(4):288-295.
[3] DASKIN M S.A maximum expected covering location model:formulation, properties and heuristic solution[J].Transportation Science, 1983, 17(1):48-70.
[4] GENDREAU M, LAPORTE G, SEMET F.Solving an ambulance location model by Tabu search[J].Location Science, 1997, 5(2):75-88.
[5] JI S G, ZHENG Y, WANG Z Y, et al.A deep reinforcement learning-enabled dynamic redeployment system for mobile ambulances[C]//Proceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies.New York, USA:ACM Press, 2019:1-20.
[6] MAXWELL M S, RESTREPO M, HENDERSON S G, et al.Approximate dynamic programming for ambulance redeployment[J].INFORMS Journal on Computing, 2010, 22(2):266-281.
[7] JAGTENBERG C J, BHULAI S, VAN DER MEI R D.An efficient heuristic for real-time ambulance redeployment[J].Operations Research for Health Care, 2015, 4:27-35.
[8] SCHMID V.Solving the dynamic ambulance relocation and dispatching problem using approximate dynamic programming[J].European Journal of Operational Research, 2012, 219(3):611-621.
[9] PAN L, CAI Q P, FANG Z X, et al.A deep reinforcement learning framework for rebalancing dockless bike sharing systems[EB/OL].[2021-05-10].https://arxiv.org/pdf/1802.04592.pdf.
[10] TANG X C, QIN Z T, ZHANG F, et al.A deep value-network based approach for multi-driver order dispatching[C]//Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining.New York, USA:ACM Press, 2019:1780-1790.
[11] QIN Z T, TANG X C, JIAO Y, et al.Deep reinforcement learning for ride-sharing dispatching and repositioning[C]//Proceedings of the 28th International Joint Conference on Artificial Intelligence.Macao, China:[s.n.], 2019:6566-6568.
[12] XU Z, LI Z X, GUAN Q W, et al.Large-scale order dispatch in on-demand ride-hailing platforms:a learning and planning approach[C]//Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining.New York, USA:ACM Press, 2018:905-913.
[13] LIN K X, ZHAO R Y, XU Z, et al.Efficient large-scale fleet management via multi-agent deep reinforcement learning[C]//Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining.New York, USA:ACM Press, 2018:1774-1783.
[14] ZHOU M, JIN J R, ZHANG W N, et al.Multi-agent reinforcement learning for order-dispatching via order-vehicle distribution matching[C]//Proceedings of the 28th ACM International Conference on Information and Knowledge Management.New York, USA:ACM Press, 2019:2645-2653.
[15] WILLIAMS R J.Simple statistical gradient-following algorithms for connectionist reinforcement learning[J].Machine Learning, 1992, 8(3/4):229-256.
[16] SCHULMAN J, WOLSKI F, DHARIWAL P, et al.Proximal policy optimization algorithms[EB/OL].[2021-05-10].https://arxiv.org/pdf/1707.06347.pdf.
[17] SUTTON R S, BARTO A G.Reinforcement learning:an introduction[J].IEEE Transactions on Neural Networks, 1998, 9(5):1054.
[18] TESAURO G.TD-gammon, a self-teaching backgammon program, achieves master-level play[J].Neural Computation, 1994, 6(2):215-219.
[19] BERTSEKAS D P, TSITSIKLIS J N, VOLGENANT A.Neuro-dynamic programming[M].Berlin, Germany:Springer, 2010.
[20] SILVER D, HUANG A, MADDISON C J, et al.Mastering the game of Go with deep neural networks and tree search[J].Nature, 2016, 529(7587):484-489.
[21] PANG Z J, LIU R Z, MENG Z Y, et al.On reinforcement learning for full-length game of StarCraft[C]//Proceedings of the AAAI Conference on Artificial Intelligence.[S.l.]:AAAI Press, 2019:4691-4698.
[22] BIN W.Hierarchical macro strategy model for MOBA game AI[C]//Proceedings of the AAAI Conference on Artificial Intelligence.[S.l.]:AAAI Press, 2019:1206-1213.

选择文件类型/文献管理软件名称

选择包含的内容

基于深度强化学习的深圳市急救车调度算法

Ambulance Dispatching Algorithm in Shenzhen Based on Deep Reinforcement Learning

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 6

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	张冠莹, 伊鹏, 李丹, 朱棣, 毛明. 面向大规模网络的服务功能链部署方法[J]. 计算机工程, 2023, 49(8): 122-129.
[2]	靳雁霞, 史志儒, 杨晶, 刘亚变, 乔星宇, 张翎. 布料与精细建模物体间的碰撞检测算法研究[J]. 计算机工程, 2023, 49(7): 269-277.
[3]	曹坪, 杨怀志, 薄一军, 尤嘉, 张淳杰, 李丹勇. 面向低质量裂缝图像的多知识蒸馏分类[J]. 计算机工程, 2023, 49(7): 204-213.
[4]	白明昌. 基于折叠路径聚合的属性网络节点嵌入方法[J]. 计算机工程, 2023, 49(7): 76-84.
[5]	赵世豪, 毛国君, 熊保平, 黄山, 林江宏. 基于图小波卷积神经网络的时空图挖掘模型[J]. 计算机工程, 2023, 49(7): 85-93.
[6]	梅晶, 戴龙宝, 童钊, 邓昕, 王嘉珂. 资源约束下基于Lyapunov优化的自适应卸载算法[J]. 计算机工程, 2023, 49(7): 34-46.
[7]	蔡丽娇, 秦进, 陈双. 远离旧区域和避免回路的强化探索方法[J]. 计算机工程, 2023, 49(7): 118-124.
[8]	张国富, 沈宇锋, 宋晓晓, 苏兆品. 受灾路网抢修队动态调度问题的建模与求解方法[J]. 计算机工程, 2023, 49(6): 300-313.
[9]	廖涛, 孙皓洁, 张顺香. 基于跨度和特征融合的实体关系联合抽取模型[J]. 计算机工程, 2023, 49(6): 107-114.
[10]	于海洋, 景鹏, 张文涛, 谢赛飞, 滑志华, 宋草原. 基于残差与注意力机制的道路裂缝检测U-Net改进模型[J]. 计算机工程, 2023, 49(6): 265-273.
[11]	李强, 仪晋辉, 杜婷婷, 王胜春. 移动边缘计算中基于A3C的依赖任务卸载与资源分配[J]. 计算机工程, 2023, 49(6): 42-52.
[12]	代祖华, 刘园园, 狄世龙. 语义增强的图神经网络方面级文本情感分析[J]. 计算机工程, 2023, 49(6): 71-80.
[13]	沈学利, 田桂源, 姜彦吉, 马琳琳. 基于双阶段Conv-Transformer的时频域语音增强算法[J]. 计算机工程, 2023, 49(6): 123-130.
[14]	金志军, 王浩, 方宝富. 稀疏场景下基于理性好奇心的多智能体强化学习[J]. 计算机工程, 2023, 49(5): 302-309.
[15]	丁子轩, 俞雷, 张娟, 李想, 王新宇. 基于深度残差自适应注意力网络的图像超分辨率重建[J]. 计算机工程, 2023, 49(5): 231-238.

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

基于深度强化学习的深圳市急救车调度算法

Ambulance Dispatching Algorithm in Shenzhen Based on Deep Reinforcement Learning

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 6

参考文献

相关文章 15

编辑推荐

Metrics

本文评价