留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

面向公平分配的时变应急服务覆盖优化

张彤 马帅 沈宏

张彤, 马帅, 沈宏. 面向公平分配的时变应急服务覆盖优化[J]. 武汉大学学报 ● 信息科学版, 2017, 42(12): 1681-1687. doi: 10.13203/j.whugis20150065
引用本文: 张彤, 马帅, 沈宏. 面向公平分配的时变应急服务覆盖优化[J]. 武汉大学学报 ● 信息科学版, 2017, 42(12): 1681-1687. doi: 10.13203/j.whugis20150065
ZHANG Tong, MA Shuai, SHEN Hong. Equity-Oriented Time -Varying Emergency Management Service Coverage Optimization[J]. Geomatics and Information Science of Wuhan University, 2017, 42(12): 1681-1687. doi: 10.13203/j.whugis20150065
Citation: ZHANG Tong, MA Shuai, SHEN Hong. Equity-Oriented Time -Varying Emergency Management Service Coverage Optimization[J]. Geomatics and Information Science of Wuhan University, 2017, 42(12): 1681-1687. doi: 10.13203/j.whugis20150065

面向公平分配的时变应急服务覆盖优化

doi: 10.13203/j.whugis20150065
基金项目: 

国家自然科学基金 41271400

深圳市基础研究计划 JCYJ20140828163633980

2014-昆山高层次创新创业人才 31

详细信息
    作者简介:

    张彤, 博士, 副教授, 主要从事高性能地理计算和空间优化研究。zhangt@whu.edu.cn

  • 中图分类号: P208

Equity-Oriented Time -Varying Emergency Management Service Coverage Optimization

Funds: 

The National Natural Science Foundation of China 41271400

Shenzhen Science & Technology Program JCYJ20140828163633980

2014 Kunshan High-Level Innovative and Entrepreneurial Talents Program 31

More Information
    Author Bio:

    ZHANG Tong, PhD, associate professor, specializes in the high-performance geocomputation and spatial optimization. E-mail: zhangt@whu.edu.cn

  • 摘要: 应急服务需要根据实际情况在城市的某些区位中提前布置,才能保证需求发生时能在规定时间内到达需求位置,提供应急服务。布置区位时,需要根据时变交通条件的变化,适当考虑时空的合理分布,以为城市居民提供较为公平的服务覆盖。传统最大区位覆盖模型较少考虑服务的公平分配,特别是在时变交通和复杂大规模路网条件下,缺乏对公平量度的显式建模。基于目前区域覆盖优化模型的最近进展,扩展了传统最大区位覆盖模型,建立面向公平分配的时变应急服务覆盖模型,提出了相应的启发式高效求解方法。利用武汉市数据进行实验验证,证实模型求解得到的区位配置解较之传统模型,不仅提供了更加公平的应急服务覆盖,也考虑到了时变交通条件,改善了应急资源在时空上的均衡配置水平,整体上提高了应急服务质量。
  • 图  1  不同最大重部署次数约束的求解比较(γ=500)

    Figure  1.  Comparison of Solutions Based on the Constraints of Maximum Redeployment Number

    表  1  对比是否考虑公平目标函数的优化配置结果(MT = 50, γ=500, 所有时段pt = 45)

    Table  1.   Optimal Allocation Result Considering Fair Objective Function (MT=50, γ=500, all Time Interval pt= 45)

    时段覆盖比例/%基尼系数
    考虑公平不考虑考虑公平不考虑
    00:00~03:0090.5791.010.4510.512
    03:00~06:0091.2891.400.4520.521
    06:00~09:0085.0387.970.4600.554
    09:00~12:0089.4590.190.4580.527
    12:00~15:0087.2887.940.4560.515
    15:00~18:0084.1785.080.4690.551
    18:00~21:0084.2284.900.4660.575
    21:00~24:0088.1788.350.4590.538
    下载: 导出CSV

    表  2  CPLEXR与本文算法求解对比

    Table  2.   Comparison of CPLEXR and our Algorithm

    时段覆盖比例差计算时间/s
    CPLEXR本文算法
    00:00~03:000.32%10 103128.0
    03:00~06:000.33%11 356145.2
    06:00~09:001.13%13 568177.0
    09:00~12:000.96%12 559170.3
    12:00~15:001.07%10 874165.2
    15:00~18:000.55%10 785181.5
    18:00~21:000.84%11 982180.3
    21:00~24:000.08%10 095132.7
    下载: 导出CSV
  • [1] Murray A T, O'Kelly M, Church R L. Regional Service Coverage Modeling[J]. Computers and Operations Research, 2008, 35(2):339-355 doi:  10.1016/j.cor.2006.03.004
    [2] Matisziw T, Murray A T. Area Coverage Maximization in Service Facility Siting[J]. Journal of Geographical Systems, 2009, 11:175-189 doi:  10.1007/s10109-009-0081-0
    [3] Murray A T, Wei R. A Computational Approach for Eliminating Error in the Solution of the Location Set Covering Problem[J]. European Journal of Operational Research, 2013, 224:52-64 doi:  10.1016/j.ejor.2012.07.027
    [4] 俞艳, 郭庆胜, 何建华, 等.顾及地理网络特征的城市消防站布局渐进优化[J].武汉大学学报·信息科学版, 2005, 30(4):333-336 http://ch.whu.edu.cn/CN/abstract/abstract2163.shtml

    Yu Yan, Guo Qingsheng, He Jianhua, et al.Gradual Optimization of Urban Fire Station Location Based on Geographical Network Attribute[J].Geomatics and Information Science of Wuhan University, 2005, 30(4):333-336 http://ch.whu.edu.cn/CN/abstract/abstract2163.shtml
    [5] 刘浪, 黄有方, 逄金辉.加权网络应急物资储备点选址方法[J].北京理工大学学报, 2011, 2:244-252 http://www.oalib.com/paper/4587838

    Liu Lang, Huang Youfang, Pang Jinhui. Method of Location Selection of Emergency Material Depot in Weighted Networks[J].Journal of Beijing Institute of Technology, 2011, 2:244-252 http://www.oalib.com/paper/4587838
    [6] 孔云峰.利用GIS与线性规划学校最优学区划分[J].武汉大学学报·信息科学版, 2012, 37(5):513-515 http://ch.whu.edu.cn/CN/abstract/abstract191.shtml

    Kong Yunfeng. Optimal School Allocation Using GIS and Linear Programming[J].Geomatics and Information Science of Wuhan University, 2012, 37(5):513-515 http://ch.whu.edu.cn/CN/abstract/abstract191.shtml
    [7] 李绍琳, 杜清运.利用梯阶中值选址模型进行区域机场群布局适应性研究[J].武汉大学学报·信息科学版, 2012, 37(8):988-991 http://ch.whu.edu.cn/CN/abstract/abstract292.shtml

    Li Shaolin, Du Qingyun. Suitability of Regional Multi-airports Planning by Hierarchical P-Median Location Model[J].Geomatics and Information Science of Wuhan University, 2012, 37(8):988-991 http://ch.whu.edu.cn/CN/abstract/abstract292.shtml
    [8] Schmid V.Solving the Dynamic Ambulance Relocation and Dispatching Problem Using Approximate Dynamic Programming[J]. European Journal of Operational Research, 2012, 219:611-621 doi:  10.1016/j.ejor.2011.10.043
    [9] Saydam C, Rajagopalan H, Sharer E. et al. The Dynamic Redeployment Coverage Location Model[J]. Health Systems, 2013, 2:103-119 doi:  10.1057/hs.2012.27
    [10] Church L, ReVelle C.The Maximal Covering Location Problem[J]. Papers of the Regional Science Association, 1974, 32:101-118 doi:  10.1007/BF01942293
    [11] Deaton A. Analysis of Household Surveys[M]. Baltimore MD:Johns Hopkins University Press, 1997
    [12] Hansen P, Mladenovic N.Variable Neighborhood Search[J]. Computers & Operations Research, 1997, 24(11):1097-1100 doi:  10.1007%2F978-3-319-07153-4_19-1
  • [1] 柳絮, 王坚, 李文.  集成变分模态分解和希尔伯特-黄变换的结构振动时频提取模型 . 武汉大学学报 ● 信息科学版, 2021, 46(11): 1686-1692. doi: 10.13203/j.whugis20200646
    [2] 李仕学, 沈欣, 姚璜, 张过, 刘钰霖.  面向区域成像任务的环月卫星侧摆角优化方法 . 武汉大学学报 ● 信息科学版, 2019, 44(4): 593-600. doi: 10.13203/j.whugis20170145
    [3] 刘坚, 李树林, 陈涛.  基于优化随机森林模型的滑坡易发性评价 . 武汉大学学报 ● 信息科学版, 2018, 43(7): 1085-1091. doi: 10.13203/j.whugis20160515
    [4] 郑肇葆, 郑宏.  反向技术在化学反应优化图像分割中的应用 . 武汉大学学报 ● 信息科学版, 2013, 38(5): 513-516.
    [5] 张昊, 王琪洁, 朱建军, 张晓红.  对钱德勒参数进行时变修正的CLS+AR模型在极移预测中的应用 . 武汉大学学报 ● 信息科学版, 2012, 37(3): 286-289.
    [6] 李海峰, 朱庆, 杨晓霞, 欧阳怡强.  QoS感知的多任务遥感信息服务优化组合非合作博弈模型 . 武汉大学学报 ● 信息科学版, 2010, 35(8): 967-970.
    [7] 李子阳, 郭丽, 顾冲时.  大坝监测资料的时变Kalman预测模型 . 武汉大学学报 ● 信息科学版, 2010, 35(8): 991-995.
    [8] 田晶, 郭庆胜, 冯科, 马盟.  基于信息损失的街道渐进式选取方法 . 武汉大学学报 ● 信息科学版, 2009, 34(3): 362-365.
    [9] 徐昔保, 杨桂山, 张建明.  兰州市城市土地利用优化研究 . 武汉大学学报 ● 信息科学版, 2009, 34(7): 878-881.
    [10] 李斐, 王殊伟, 柯宝贵.  应用聚类分析方法进行实测重力数据的选点优化 . 武汉大学学报 ● 信息科学版, 2009, 34(3): 257-260.
    [11] 邹进贵, 李琴, 王铜, 罗刊.  Helmert方差分量估计理论的优化及其在形变监测网中的应用 . 武汉大学学报 ● 信息科学版, 2009, 34(9): 1076-1079.
    [12] 丛培江, 郑东健, 仲琳.  大坝应力应变监测的多因素时变分析模型 . 武汉大学学报 ● 信息科学版, 2008, 33(9): 914-917.
    [13] 陈子仪, 康立山.  多父体杂交演化算法求解约束优化问题 . 武汉大学学报 ● 信息科学版, 2006, 31(5): 440-443.
    [14] 祝江汉, 李曦, 毛赤龙, 张利宁.  多卫星区域观测任务的侧摆方案优化方法研究 . 武汉大学学报 ● 信息科学版, 2006, 31(10): 868-870.
    [15] 汪孔政.  时变参数PGM(1,1)变形预测模型及其应用 . 武汉大学学报 ● 信息科学版, 2005, 30(5): 456-459.
    [16] 孟令奎, 赵春宇, 林志勇, 黄长青.  基于地理事件时变序列的时空数据模型研究与实现 . 武汉大学学报 ● 信息科学版, 2003, 28(2): 202-207.
    [17] 耿红, 王泽民.  基于灰色线性规划的土地利用结构优化研究 . 武汉大学学报 ● 信息科学版, 2000, 25(2): 167-171.
    [18] 程学光, 胡元明.  葛洲坝船闸计算机决策系统的数学模型设计 . 武汉大学学报 ● 信息科学版, 1992, 17(2): 97-100.
    [19] 黎峻宇, 李浩杰, 姚宜斌, 刘立龙, 张豹, 黄良珂.  . 武汉大学学报 ● 信息科学版, 0, 0(0): 0-0. doi: 10.13203/j.whugis20220193
    [20] 雷雨, 赵丹宁.  附有时变参数的周期项模型在极移预报中的应用 . 武汉大学学报 ● 信息科学版, 0, 0(0): 0-0. doi: 10.13203/j.whugis20200007
  • 加载中
图(1) / 表(2)
计量
  • 文章访问数:  905
  • HTML全文浏览量:  78
  • PDF下载量:  362
  • 被引次数: 0
出版历程
  • 收稿日期:  2016-04-02
  • 刊出日期:  2017-12-05

面向公平分配的时变应急服务覆盖优化

doi: 10.13203/j.whugis20150065
    基金项目:

    国家自然科学基金 41271400

    深圳市基础研究计划 JCYJ20140828163633980

    2014-昆山高层次创新创业人才 31

    作者简介:

    张彤, 博士, 副教授, 主要从事高性能地理计算和空间优化研究。zhangt@whu.edu.cn

  • 中图分类号: P208

摘要: 应急服务需要根据实际情况在城市的某些区位中提前布置,才能保证需求发生时能在规定时间内到达需求位置,提供应急服务。布置区位时,需要根据时变交通条件的变化,适当考虑时空的合理分布,以为城市居民提供较为公平的服务覆盖。传统最大区位覆盖模型较少考虑服务的公平分配,特别是在时变交通和复杂大规模路网条件下,缺乏对公平量度的显式建模。基于目前区域覆盖优化模型的最近进展,扩展了传统最大区位覆盖模型,建立面向公平分配的时变应急服务覆盖模型,提出了相应的启发式高效求解方法。利用武汉市数据进行实验验证,证实模型求解得到的区位配置解较之传统模型,不仅提供了更加公平的应急服务覆盖,也考虑到了时变交通条件,改善了应急资源在时空上的均衡配置水平,整体上提高了应急服务质量。

English Abstract

张彤, 马帅, 沈宏. 面向公平分配的时变应急服务覆盖优化[J]. 武汉大学学报 ● 信息科学版, 2017, 42(12): 1681-1687. doi: 10.13203/j.whugis20150065
引用本文: 张彤, 马帅, 沈宏. 面向公平分配的时变应急服务覆盖优化[J]. 武汉大学学报 ● 信息科学版, 2017, 42(12): 1681-1687. doi: 10.13203/j.whugis20150065
ZHANG Tong, MA Shuai, SHEN Hong. Equity-Oriented Time -Varying Emergency Management Service Coverage Optimization[J]. Geomatics and Information Science of Wuhan University, 2017, 42(12): 1681-1687. doi: 10.13203/j.whugis20150065
Citation: ZHANG Tong, MA Shuai, SHEN Hong. Equity-Oriented Time -Varying Emergency Management Service Coverage Optimization[J]. Geomatics and Information Science of Wuhan University, 2017, 42(12): 1681-1687. doi: 10.13203/j.whugis20150065
  • 城市应急管理需要根据实际情况在城市某些区位上布置医疗救护、抢险、公共安全等应急服务资源, 以便在最短的时间内根据需要达到指定位置, 提供应急服务。在应急服务覆盖规划中, 一般需要在给定有限服务资源的约束下, 通过优化模型, 确定实际部署的服务资源配置区位, 实现对区域空间的最大覆盖。应急服务覆盖优化建模与求解是区域覆盖优化(regional coverage optimization)的一种典型应用问题。决策者希望通过有限的服务设施区位和资源提供最大程度的服务覆盖, 通常的做法是建立空间优化数学模型来描述优化目标和约束条件。该问题是地理信息科学和运筹学的经典问题, 近年来取得了较大的进展, 应用于时空表达、模型建模、求解算法、误差分析和应用等方面[1-3]。国内也出现了一定数量的区域覆盖优化的应用研究, 如消防站布局[4]、应急物资储备[5]、学区划分[6]和机场选址[7]等。这说明该问题正逐渐被不同应用领域关注, 开始体现更大的应用价值。

    传统区域覆盖优化模型重点关注服务设施的初始选址优化, 期望能一次性实现服务覆盖的最大化。在时变交通条件下, 有时需要对应急资源进行动态配置, 如根据未来需求的变化, 将医疗救护车辆和人员预先调动到新的区位, 实现对未来需求的更好覆盖。这种实时或准实时重新配置是近年来应急服务覆盖优化的研究热点[8]

    虽然时变应急服务覆盖已经获得了较多的研究成果, 但是大多数研究仍主要关注覆盖需求最大和重新配置次数最少两个优化目标[8, 9]。对于应急服务设施在空间上的分布, 没有从需求端考虑应急服务设施的可达差异水平, 容易导致城市中心区和人口密集区域可获取的应急资源较多, 而城市边缘和人口较为稀疏的区域的应急资源相对较少甚至没有。因此从社会公平的角度出发, 需要在整体规划和实际运营中考虑到应急需求的时空分布情况, 在建模时考虑服务覆盖公平, 实现应急资源在时空上的均衡配置。公共服务的公平分配在GIS领域已有一定数量的研究。采用类似服务到需求距离绝对或相对偏差的简单指标不适合常见公用服务覆盖优化应用。由于表达和求解的困难, 目前尚未在覆盖优化建模中引入复杂公平量度的研究。

    本文基于目前区域覆盖优化模型的最新进展, 建立面向公平分配的时变应急服务覆盖优化模型, 提出基于可变邻域搜索的启发式高效求解算法。通过武汉市应急救护实例的实验验证, 求解得到的区位配置较之传统模型更好地提供了公平的应急服务覆盖。本文的主要创新点为:首先, 显式地提出了以基尼系数为核心的应急覆盖优化目标函数, 使得覆盖服务的时空分配可以通过调整模型来动态调整;其次, 针对提出的公平应急服务覆盖模型, 开发实现了基于可变邻域搜索的求解算法, 显著提高了求解效率。采用武汉市实际路网、交通数据对模型进行了全面测试, 验证了模型在动态应急服务区位配置问题上的优势。

    • 在给定有限服务资源限制下, 如何求解资源配置的区位, 以实现区域内服务覆盖需求的最大化, 是覆盖优化的核心问题。该问题由Church和ReVelle [10]提出, 称为最大覆盖区位问题(maximal covering location problem, MCLP)。传统MCLP模型没有充分考虑时变交通状态。实际情况中, 服务设施在为邻近需求提供服务的时候, 会受制于不断变化的交通状态, 如拥堵严重的区域, 其服务覆盖范围将会大大缩小。城市应急服务配送通过城市路网进行, 因此配送距离计算受到路网长度等因素影响, 不可以直线欧氏距离计算。本文重点考虑时变条件, 在实现区域最大覆盖的基础上尽量顾及区域公平。根据多时段划分的不同交通条件, 求解应急服务的区位部署和重新配置方案;同时尽量使规划部署的应急服务在时空上更加均衡, 减少需求区域之间的服务覆盖差异。在每天的不同时间段、一周的不同日期、一年的不同季节, 应急需求如医疗急救需求都是动态变化的。应急资源的配送受到交通条件制约, 也会造成实际覆盖范围的动态变化。所以在时变条件下, 一般需要对当前应急服务配置的区位进行一定的调整, 如将救护车辆根据未来的需求和交通情况进行适当移动, 部署到新的区位等, 来实现更好的服务覆盖。但是这种重新配置也会造成应急资源损耗和人员疲惫, 因此需要在服务覆盖最大和重新配置次数之间取得最优的平衡。

      应急服务是一种公共服务资源, 除了应追求区域覆盖的最大化, 还应该在城市的不同需求区域之间取得尽量一致的公平, 保证不同区域的服务响应时间基本一致, 即覆盖优化模型应争取城市区域内所有居民都能享受到较为均衡的应急服务。

      总结以上分析, 面向公平分配的时变应急覆盖优化模型应考虑如下要求:① 在资源有限的约束下, 尽可能多地覆盖应急需求;② 在时间应急服务覆盖优化求解的区位配置下, 不同需求区域应急反应时间的时空分布应尽量均衡, 即城市居民得到的应急服务水平尽量公平;③ 不同交通条件下, 考虑路网约束的覆盖范围变化并相应作出调整。

    • 虽然目前尚无通用的公平量度指标, 但是许多研究选取了收入分配公平评价常用的“基尼系数”(Gini coefficient), 提出了相应的交通可达公平量度指标。基尼系数是基于洛伦兹曲线(Lorenz curve)计算的。洛伦兹曲线是表征某个量化指标在人群中的累积分布函数。以应急医疗救护为例, 如果每个需求分块距离最近应急设施区位的距离(通常用时间表达)都相等, 则应急服务在时空上的分布是完全公平的, 此时洛伦兹曲线表现为一条直线。但实际上, 仅有少数需求分块到最近应急设施区位的距离小于全区域平均值, 大多数分块到最近应急设施的距离会大于平均值, 这说明少部分人比大多数人享受到更好的应急服务覆盖。基尼系数的计算在图形上可表达为洛伦兹曲线与完美公平直线之间的面积除以完美公平直线以下面积的比例。可见, 基尼系数值越高, 实际的洛伦兹曲线与完美公平直线之间的差距就越大, 应急分布在空间上的分配就越不公平。本文的基尼系数计算采用文献[11]中的方法。在实际计算中应考虑每个街区分块的潜在急救需求, 因此本文按照实际的土地利用、人口密度估算急救需求的概率来对该分块进行排序的加权计算。

    • 分时段建立模型是求解时变区域覆盖优化问题的常见方法。分时段模型中, 目前时段与上一个时段相比, 不仅需要满足应急服务覆盖的最大化, 还应该考虑如何尽量减少应急服务资源的移动。本文建模还提出了关注公平的目标, 即整体模型应该保证应急服务在每个时段的空间分配是最公平的。以应急医疗救护为例, 应急需求表现为急救120电话的数量和位置, 而应急服务资源表现为分布在城市中若干等待地点的救护车。假设需要规划的时间范围为T, 均匀等分成多个时段。救护车辆的候选区位集合是J, 急救需求分块集合为I, 每个急救需求分块it时段的需求为ait, 在t时段每个候选区位到需求分块的时间距离表达为djit。本文的目标是在给定有限的p个待部署的区位和V辆救护车限制下, 求得这些救护车的部署区位, 使得时间范围T内, 研究区域的急救需求得到最大程度的覆盖和满足, 即在所有时段tT中, 救护车辆到急救位置的距离满足小于时间阈值S的急救需求数量为最大。同时所有救护服务从待命区位到急救需求现场耗费时间(即应急反应时间)的累积概率分布应该尽可能公平, 即基尼系数尽量小。此外, 从时段t到时段t+1, 从区位j移动到其他区位的救护车辆重部署数量为M j-t(jJ), 从其他区位移动到区位j的重部署数量为M j+t(jJ)。对于时变应急服务覆盖优化问题而言, 这个重部署数量应该限制在一定阈值内, 以免造成救护人员的疲惫和额外开销。

      本文提出一个双目标优化模型来描述面向公平分配的时变应急服务覆盖优化问题。模型变量定义如下:

      iI, 代表应覆盖的需求块状标记;

      jJ, 代表候选应急服务部署区位标记;

      |T|表示T范围内分时段总数;

      ait代表需求区域it时段内的需求数量;

      Dijt为需求分块it时段的应急反应时间(部署在j的救护车行驶到i的时间);

      Ni ={ j | DijtS}, 即需求分块i周围可覆盖i的候选区位j的集合(ij服务半径阈值S范围内);

      NI为研究区域中所有需求分块的数量;

      Di为需求分块i到应急服务的距离(通常用时间表达);

      γ表示公平目标函数的权重;

      pt代表t时段可部署的区位最大数量;

      Vj, t表示t时段j区位容纳的救护车辆的最大数量;

      Vt表示t时段所有区位可部署的救护车辆最大数量;

      MT表示时间T范围内救护车辆重部署的总次数限制;

      Mj+tM j-t分别表示t时刻候选区位j移入和移出的重部署救护车数量;

      zi, j, t表示i区块t时段的一次急救需求被位于j的一辆救护车所满足;

      vj, t表示t时段部署在区位j的救护车数量;

      Vj, t表示区位j可容纳的救护车最大数量;

      $$ {x_{j,t}} = \left\{ \begin{array}{l} {v_{j,t}},t\;时段部署在区位\;j\;的救护车数量\\ 0,j\;在\;t\;时段未部署任何救护车辆 \end{array} \right. $$
      $$ {y_{i,t}} = \left\{ \begin{array}{l} 1,i\;的需求可被至少一辆救护车覆盖\\ 0,i\;的需求未被覆盖 \end{array} \right. $$

      目标函数:

      最大化

      $$ {Z_1} = \sum\limits_{t = 1}^{\left| T \right|} {\sum\limits_{i = 1}^{\left| I \right|} {a_i^t{y_{i,t}}} } $$ (1)
      $$ {Z_2} = \gamma \sum\limits_{t = 1}^{\left| T \right|} {\left[ {1 - {\rm{Gini}}\left( {{N_I},D_i^t} \right)} \right]} $$ (2)

      约束条件

      $$ \sum\limits_{j \in {N_i}} {{x_{j,t}} \ge {y_{i,t}}} ,\;\;\;\;\forall i,j,t $$ (3)
      $$ \sum\limits_{j \in {N_i}} {{z_{i,j,t}} = a_i^t} ,\;\;\;\;\forall i,j,t $$ (4)
      $$ \sum\limits_{t = 1}^{\left| T \right|} {\left( {M_{j + }^t + M_{j - }^t} \right)} \le {M_T},\;\;\;\;\forall j,t $$ (5)
      $$ \sum\limits_{j \in J} {{x_{j,t}}} + \sum {M_{j + }^t} - \sum {M_{j - }^t} = \sum\limits_{j \in J} {{x_{j,t + 1}}} $$ (6)
      $$ \sum\limits_{j \in J} {\frac{{{x_{j,t}}}}{{{v_{j,t}}}} = {p_t}} ,\;\;\;\;\forall j,t $$ (7)
      $$ \sum\limits_{j \in J} {{x_{j,t}}} \le {V_t},\;\;\;\;\forall j,t $$ (8)
      $$ {x_{j,t}} \le {V_{j,t}},\;\;\;\;\forall j,t $$ (9)
      $$ {x_{j,t}} = \left\{ {0,正整数} \right\},\;\;\;\;\forall j,t $$ (10)
      $$ {y_{i,t}} = \left\{ {0,1} \right\},\;\;\;\forall i,t $$ (11)

      目标函数Z1基于传统MCLP模型, 即研究区域在研究时段T中的被覆盖的总体覆盖要取得最大值, Z2的目标则是在所有时段的基尼系数(Gini)总和需要取得最小。对每一个时段, 约束条件(3) 和(4) 确保每个需求分块的急救需求可被附近的救护车辆满足, 约束(5) 限制救护车辆重部署的总数(小于MT), 约束(6) 保证相邻时段救护车辆重部署后的数量保持一致, 约束(7) 确定t时段需要部署的救护车辆待命区位总数, 约束(8) 保证t时段部署的救护车总数不超过可调配的上限, 约束(9) 保证每个区位部署的救护车辆不超过该处许可的限值, 约束(10) 和(11) 限制决策变量的取值。与传统MCLP模型相比, 本文提出的模型不仅显式地体现了公平分配的思想, 还考虑了救护车辆重部署位移来提升不同时段的覆盖水平。

    • 大规模路网约束的时变应急服务覆盖优化模型通常难以取得精确的最优解。运筹学领域对于时变应急服务的重部署问题通常采用启发式求解方法。本文采用基于可变邻域搜索(variable neighborhood search, VNS)[12]的算法迭代计算近似最优解。近似最优解的形式为每个时段救护车辆候选区位的分布以及每个区位上部署的救护车数量。每个解包含若干个区位解, 即每个区位的救护车辆配置数量。

      可变邻域搜索算法从一个初始解出发, 彻底地探索当前最优解每个区位解的邻域, 生成一个随机解。如果在邻域中能找到一个不劣于当前最优解的新解, 则该新解被接受为当前最优解, 并开始探索当前最优解邻域。传统可变邻域搜索算法的初始解是随机产生的, 可能会导致迭代收敛缓慢。本文算法中, 我们让用户输入初始解, 即在地图上点选救护车辆的初始部署区位和数量, 这样, 初始解可以代表一个较为合理的初始区位分布。具体步骤如下。

      首先用户输入初始解, 即t0时刻救护车部署的区位和每个区位的车辆数量, 作为t1时段的初始最优解。这个初始解及之后所有可变邻域搜索的解都需要满足区位容纳救护车数量、该时段部署区位和救护车总数的上限约束。对于每一个时段, 初始解都采用上一个时段的最优解开始调度, 以保持部署的连续性。在可变邻域搜索迭代过程中, 如果相邻两次迭代的变化小于阈值, 则停止迭代。可变邻域搜索时, 先根据当前救护车的部署区位、候选区位集合、最大允许的应急反应时间、需求分块的位置和应急需求数量来计算实际救护覆盖范围。在此基础上, 结合公平权重计算累积目标函数值, 并以此为基础进行当前最优解的搜索和更新。搜索的范围根据路段行程时间的不同而变化, 体现了动态应急服务部署的实际情况。基尼系数的计算基于不同时段和不同交通条件进行, 在时空上考虑应急服务部署的公平分配。

      实现可变邻域搜索的关键是将当前部署的救护车移动到邻域范围内的其他区位, 作为一个可能的解集xt。通过计算新解集的目标函数值来判断是否更新当前最优解xt。这个过程通过在邻域内遍历可能的解集, 基于最大改善算法来寻找最优解。最大改善算法能在当前最优解的邻域空间内利用目标函数值增长最快的方向来寻找新的当前最优解。如果新解的目标函数值比当前解更大, 则采用新解作为新的当前最优解, 并用这个新解的邻域进行新的搜索, 否则继续探索直到遍历整个解集空间。本文在更新最优解的时候, 不仅记录救护车部署的区位, 还记录该区位部署的救护车数量。

    • 实验选取武汉市的实际数据, 包括武汉市道路网络、浮动车、土地利用、主要急救设施分布以及应急电话统计数据等。如图 1所示, 将武汉市主城区道路网络进行基本的化简和拓扑处理, 共17 518个节点和28 101条弧段。浮动车数据采用2009年3月第一周全市11 263辆出租车的GPS轨迹。基于路网数据和经过地图匹配后的浮动车数据, 经过估计计算, 得到了以2 h为间隔的每条路段的平均速度和行程时间。根据现有急诊设施的分布情况, 加上其他交通便捷的区位, 共确定93个候选区位, 并对每个区位设置最大容纳的救护车数量。根据目前武汉市医疗专用急救电话(以下简称120) 和各医院急救设施情况, 将全市救护车任意时段可调配的车辆总数设置为50辆。应急需求分块是基于道路网构成的街区内部, 通过Voronoi图划分, 按照到周围道路距离最近的原则将被道路网围绕的街区划分为若干急救需求分块。由于武汉市人口分布数据只能获取到街道办事处一级, 本文基于土地利用数据, 对住宅区根据道路密度进行插值, 估计每个需求分块的人口数量, 再根据夏季武汉120每天急救数量, 估计每个时段的急求需求。实验的时间范围设置为工作日的周五, 从0点开始均匀分为8个时段。最大的允许应急救护反应时间按照有关急救规定设置为10 min。一整天的需求量设置为300次, 按照时间和估算的人口密度随机分配给各需求分块。实验计算机的配置为CPU Intel(R) Core(TM) i3-2100 CPU @3.10 GHz, 内存8 GB, 操作系统Windows 7 64位, 求解和可视化程序开发基于ArcGIS Engine 10.0。实验结果一般取5次计算的平均值, 整数变量四舍五入取整。

      图  1  不同最大重部署次数约束的求解比较(γ=500)

      Figure 1.  Comparison of Solutions Based on the Constraints of Maximum Redeployment Number

    • 本文首先对是否考虑公平分配的救护车优化配置结果进行比较, 设计实验一。在目标函数(2) 中将γ设置为0, 即可将模型转化为普通的时变应急服务覆盖优化模型。

      覆盖比例是根据时段内可在10 min内得到应急救护的需求数量与总需求数量的比例来计算的。从表 1可知, 对于所有时段, 本文提出的模型在覆盖比例上与不考虑公平的时变应急服务覆盖优化模型非常接近, 但是在时空的公平分配上得到了好的改善。研究还发现, 在早晚高峰(06:00~09:00和15:00~21:00), 由于总体路段行程时间大大延长, 无论是否考虑公平, 覆盖比例都有显著下降。这是因为很多之前可被正常覆盖的需求受到救护车资源的总体限制, 不能在10 min内得到应急救护, 导致基尼系数出现一定程度的增长。

      表 1  对比是否考虑公平目标函数的优化配置结果(MT = 50, γ=500, 所有时段pt = 45)

      Table 1.  Optimal Allocation Result Considering Fair Objective Function (MT=50, γ=500, all Time Interval pt= 45)

      时段覆盖比例/%基尼系数
      考虑公平不考虑考虑公平不考虑
      00:00~03:0090.5791.010.4510.512
      03:00~06:0091.2891.400.4520.521
      06:00~09:0085.0387.970.4600.554
      09:00~12:0089.4590.190.4580.527
      12:00~15:0087.2887.940.4560.515
      15:00~18:0084.1785.080.4690.551
      18:00~21:0084.2284.900.4660.575
      21:00~24:0088.1788.350.4590.538

      考虑公平优化目标对于高峰时段的作用更显著, 基尼系数在早晚高峰的改善都比较明显, 总体上各时段之间的基尼系数变化较小。对于高峰时段, 可以通过增加救护车资源、增加配置区位或增加救护车重部署等手段来改善覆盖能力, 但是都需要耗费额外的人力和物力。

      接着设计实验二以评价算法的求解效率。高效的求解方法对于应急服务调配和重部署非常关键。在求解效率方面, 对比了本文的启发式求解方法和常见的CPLEX12工具。基于武汉市的实际急救数据, CPLEXR工具无法在12 h内得到最优解。因此我们选用汉口地区局部路网进行对比试验。该路网规模大约为全市的1/10, 其余如行程时间、需求和候选区位等从原始数据中截取。从表 2可发现, 基于可变邻域搜索的算法虽然没有取得精确最优解, 但是其区位解对需求的覆盖比例与CPLEXR精确区位解相差较小。对比实验表明, CPLEXR需要接近2 h才能获取第一个最优解, 本文采用的启发式搜索算法在2~3 min内即可得到近似最优解。

      表 2  CPLEXR与本文算法求解对比

      Table 2.  Comparison of CPLEXR and our Algorithm

      时段覆盖比例差计算时间/s
      CPLEXR本文算法
      00:00~03:000.32%10 103128.0
      03:00~06:000.33%11 356145.2
      06:00~09:001.13%13 568177.0
      09:00~12:000.96%12 559170.3
      12:00~15:001.07%10 874165.2
      15:00~18:000.55%10 785181.5
      18:00~21:000.84%11 982180.3
      21:00~24:000.08%10 095132.7

      设计实验三以分析重部署情况。图 1显示了与表 1相同参数设置下的重部署次数与覆盖比例在一天中不同时段的变化情况。随着新时段交通条件和需求水平的变化, 救护车辆可在不同区位之间进行调动, 以提高新时段中急救需求的覆盖比例。当总共重部署次数受到MT = 50的约束时, 实际模型建议的车辆重定位移动一共是38次。而当MT = 90时, 可以执行的重定位移动次数为70。可以清楚地看到, 当重定位移动增加后, 急救服务的覆盖比例有了一定的提高, 尤其是在晚高峰时段。但是重部署过于频繁会导致救护人员的疲劳, 因此需要根据实际情况进行设置。

    • 本文介绍了一种面向公平分配的时变应急服务覆盖优化模型, 通过武汉市实际数据测试表明, 该模型可以较好地考虑不同时段下交通条件造成的覆盖范围变化, 相比传统MCLP模型能更好地实现覆盖服务区位的公平分布;该算法求解迅速, 适合于时变条件下应急服务的在线部署应用。本研究的主要创新点为, 首先, 显式地提出了以基尼系数为核心的应急覆盖优化目标函数, 使得覆盖服务的时空分配可以通过调整模型来动态调整;其次, 针对提出的公平应急服务覆盖模型, 开发实现了基于可变邻域搜索的求解算法, 显著提高了求解效率。采用武汉市实际路网、交通数据对模型进行了全面测试, 验证了模型在动态应急服务区位配置问题上的优势。今后将进一步丰富模型的内容, 如考虑应急资源的繁忙概率、应急需求的在线变化和区位的容纳水平等, 从而更好地模拟实际情况, 建立更完善的应急服务覆盖方案。

参考文献 (12)

目录

    /

    返回文章
    返回