基于拉格朗日松弛框架的消防站点选址优化方法.pdf
《基于拉格朗日松弛框架的消防站点选址优化方法.pdf》由会员分享,可在线阅读,更多相关《基于拉格朗日松弛框架的消防站点选址优化方法.pdf(6页珍藏版)》请在咨信网上搜索。
1、消防科学与技术2023年 8 月第 42 卷第 8 期应急管理研究基于拉格朗日松弛框架的消防站点选址优化方法曹跃1,李敬2,顾彧3,刘晗3(1.天津市消防救援总队,天津 300090;2.哈尔滨市消防救援支队,黑龙江 哈尔滨 150001;3.煤炭科学研究总院有限公司,北京 100013)摘要:城市火灾可能造成严重的生命财产损失,科学合理的消防站布局可以有效提升消防救援效率并降低系统运行成本。以最小化救援等待损失与消防站点建设成本为目标,将消防车行驶时间作为模型参数,构建消防站固定费用选址的整数规划模型。设计基于拉格朗日松弛框架的精确求解方法,并对算法有效性进行了验证。对天津市津南区消防站布局
2、进行实例优化,并对等待损失成本和消防车行驶时间等参数进行了敏感度分析,为城市消防站点规划提供了更为科学的决策参考。关键词:消防站;选址布局;整数规划模型;消防车行驶时间;拉格朗日松弛方法中图分类号:X913.4;TU998.14 文献标志码:A 文章编号:1009-0029(2023)08-1141-05随着城市化进程不断加快,城市火灾越发频繁、复杂,财产损失增大,人员伤亡数量增多。2022年全国消防救援队伍共接报处置各类警情 209.2万起,共计出动消防救援人员 2 247.2万人次、消防车 401.3万辆次1。重特大火灾发生后,如果消防应急救援力量在短时间内到达灾害地点并及时展开战斗,将有
3、效遏制灾情的发展和蔓延。如何平衡好城市消防规划的可靠性和经济性成为当下研究的热点,国内外学者主要从城市消防资源优化配置和城市消防救援覆盖率评估等两个方面。城市消防配置问题是一个经典的运筹学问题,近年来相关的覆盖模型被广泛应用并且不断发展2。1957年,BERGE C3最先提出了位置集合覆盖模型,旨在解决需求全覆盖条件下的最少设施优化问题,HASHIM M N等4利用这一经典模型研究灾害响应中心选址问题。1974年 CHURCH R 等5提出最大覆盖选址模型,在固定数量设施条件下将覆盖范围最大化。张静等6考虑各需求点的火灾风险等级,引入“部分覆盖”假设,结合最大覆盖选址模型研究消防站选址问题。G
4、ENDREAU M 等7基于前两种模型思想开发出双标准覆盖模型,该模型强调在覆盖所有救援需求点的同时尽可能满足对更多需求点的较短时间内救援。HAKIMI于 1964年提出 P中心模型和 P 平均值模型,前者强调应急救援的公平性,而后者更加注重效率性8-9。YE F等10运用 P中心模型研究中国应急储备仓库建设情况。为了更好地衡量设施的经济性,学者们提出了固定费用模型,该模型综合考虑设施成本和交通浮动成本,旨在通过合理建设设施数量使得总成本最小,该模型不同于之前的模型,设施数量不再作为一个参数或者变量出现在模型中11。NOZICK K L等12利用该模型研究覆盖范围限制下的设施选址问题。于冬梅等
5、13扩展传统无容量限制的固定费用选址模型,从抵御设施中断的视角和提高服务质量的视角建立选址布局网络的双目标优化模型。XIE S 等14考虑消防救援中多车种多站点的联合调度因素,进一步改进了固定费用选址模型,从而提出联合定位和分配优化模型。建标 152-2017 城市消防站建设标准15规定了用于消防站布局规划评估的“面积确定法”,但是该标准同时指出,未来消防站的布局应以响应时间作为第一核心指标,逐步推动我国消防站布局从“面积确定法”向“响应时间确定法”的过渡。随着 GIS 等技术的发展,已有大量学者对“响应时间确定法”开展了初步探索,将消防车行驶时间作为重要依据,对城市消防救援覆盖率进行评估。新
6、的评估方法考虑了实际交通情况,使得评估更加贴近实际情况16。LIU D L 等17利用百度地图数据基于消防车行驶时间,评估娄底市消防站覆盖情况。祝开心等18改进了 LIU D L的模型并对实时路况下的南京市消防覆盖率进行分析。现有的消防站点选址模型大多采用传统的“面积确定法”,对实际道路交通情况考虑不充分,容易造成模型求解结果的误差偏高。笔者建立固定费用选址模型用以优化消防站选址,将消防车行驶时间作为模型参数,并使用拉格朗日松弛算法求解模型,在 1 0003 000的大规模虚拟网络展开验证。最后以天津市津南区消防响应系统为案例,对不同等待损失成本系数和拥堵条件下的消防站点规划布局方案进行敏感度
7、分析,为政府部门的应急响应系统规划和 城市消防站建设标准 等有关标准的修订完善提供决策支撑。1模型描述假设研究区域内所有拟建设消防站地点的集合为 I。对于任意消防站建设地点 iI,其建设成本为 fi。不同的消防站候选点 iI的建设成本 fi也不尽相同,主要取决于建设点的面积大小、土地价格等因素。此外,用 0-1决策变量来描述是否在 i点建设消防站,如式(1)所示。xi=1,在备选地点i建设消防站 0,不在备选地点i建设消防站(1)基金项目:中国煤炭科工集团创新创业资金专项面上项目(2022-MS004)1141Fire Science and Technology,August 2023,Vo
8、l.42,No.8用集合 J来表示所有火灾风险点,即需求点。对于任意需求地点 jJ,因等待而导致的单位时间内损失成本为hj。需求地点的火灾载荷等相关因素决定了权重 hj的大小,从消防站点 iI出发到达需求地点 jJ的所需时间记为 tij。为了刻画消防站点对救援地点的覆盖情况,引入如式(2)所示的 0-1决策变量 yij。yij=1,消防站点i派出车队服务j点 0,消防站点i不派出车队服务j点(2)用上述变量和参数建立一个混合整数规划模型,如式(3)所示。minifixi+ijtijyijhj(3)yij xi,i,jiyij=1,jxi0,1,iyij0,1,i,j其中,目标函数表示在保障救援
9、的前提下,最小化总消防救援成本(消防站建设成本和救援等待成本之和),是等待损失成本系数。约束条件中,yijxi确保只有已建设消防站点才能派出消防车辆进行服务救援;iyij=1,j表示对于任意需求地点,有且仅有一个消防站对其服务;xi 0,1 和 yij 0,1 表示变量均为 0-1决策变量。2拉格朗日松弛算法拉格朗日松弛算法是用于解决整数规划问题的常见算法19-21,它的优点是在最小化问题中,可以通过松弛某些约束将原问题转化为更简单的对偶问题。松弛后的对偶目标函数的值是原问题的下界ZLB,而可行解则为原问题提供了一个上界ZUB,通过不断迭代更新拉格朗日乘子,缩小上界ZLB与下界ZUB的间距,从
10、而实现对原问题的求解。2.1拉格朗日松弛模型首 先 引 入 拉 格 朗 日 乘 子u,将 原 问 题 的 约 束 条 件iyij=1,j松弛到目标函数式,原问题等价转变为如式(4)所示的松弛问题,且满足其他约束条件。z(u)=minx,yifixi+ijtijyijhj+j()-1+iyijuj(4)对拉格朗日乘子u,最大化对偶函数,得到原问题的拉格朗日对偶问题,如式(5)所示。maxuz(u)(5)并满足约束条件 yijx,xi 0,1 和 yij 0,1。2.2子问题求解对z(u)进行化简得式(6)。z(u)=minx,yifixi+ij()tijhj+ujyij-juj(6)对于任意给定
11、u,式(6)可以分解为两步进行求解:(1)设vi=fi+jmin()tijhj+uj,0,若vi 0,则xi=1,否则xi=0。(2)若xi=1,tijhj+uj 0,则yij=0,否则yij=1。2.3可行解构造对偶问题的解不一定满足原问题,需要利用当前信息构造一个原问题的可行解,从而获得并更新原问题的上界。将z(u)的解x*i作为消防站建设状态,原模型的可行解 Zfeasible可以用式(7)模型来描述。Zfeasible=minifix*i+ijtijyijhj(7)yijx*i,i,j满足约束iyij=1,j、yij0,1,i,j。对 于 任 意i,j,当 且 仅 当0 x*itij
12、mintmjx*m=1,m I成立时,yij=1,否则yij=0,即对于任意火灾地点j,只有离它距离最近且建有消防站的选址地点i的yij=1,否则yij=0。令ZUB=minZfeasible,用以记录在计算过程中获得的所有可行解的最小值,并随着迭代不断更新,当迭代停止时,ZUB值即为所求模型的解。2.4拉格朗日乘子更新与迭代对于每一组 uj来说,z(u)都是原问题的下界,为了寻找最优下界maxuz(u),采用次梯度算法,通过不断迭代更新拉格朗日乘子uj。乘子更新公式如式(8)所示。uk+1j=ukj+Sn(-1+iyij)(8)步长 Sn的更新公式如式(9)所示,其中 为控制参数。Sn=()
13、ZUB-z()uj()-1+iyij2,0 2(9)通过不断迭代,上下界之间的间距会不断缩小,一般采用相对间隙ZUB-ZLBZUB判断解的质量,当相对对偶间隙小于某一设定值时会迭代停止。2.5算法性能测试为了说明拉格朗日松弛算法的性能,进行试验测试。程序由 Python 语言编写,测试环境为 Python 3.9,求解结果的上下界间隔设定为 5%。假定在正方形二维空间随机生成 1 000 个站点候选点i I,3 000个需求点j J,候选点与需求点距离采用曼哈顿距离。参数=5,hj在区间0,1 250中随机取值,fi在区间500,2 000中随机取值。计算结果显示,算法的相对最优解差值为 0.
14、08%,运算时间为 208.8 s,相对间隙为 4.93%。从中可以发现,拉格朗日松弛算法在计算大规模问题的时候,可以在相对更短的时间内获得比较精确的结果。图 1 展示了拉格朗日松弛算法的迭代速度。1142消防科学与技术2023年 8 月第 42 卷第 8 期3天津市津南区消防站选址案例3.1研究区域概况天津市津南区位于天津市东南部,区行政辖区面积约为 387.84 km2,常住人口 92.71万。该区下辖 3个街道、8个镇。2010年以来,津南区作为承接市中心和滨海新区的黄金走廊,城市化进程不断加快,消防救援压力不断上升。合理规划消防站选址位置,合理分配消防救援资源对于减小人民生命财产损失具
15、有重要意义。3.2数据来源用 2022年 1月到 11月的天津市津南区消防救援支队警情数据进行消防站位置选址分析。警情数据和消防站选址点数据均从天津市津南区消防救援支队获得。2022 年 1 月至 11 月,津南区消防救援支队共记录救援警情 3 925 次。图 2 为天津市津南区出警处置情况图。其中,消防站到现场并实施处置的有 1 023 起,约占总数的 26%。故消防站实际参与救援共计 1 023起,排除其中地理信息异常数据 12个,有效的救援数据共计 1 011个。图 3是津南区 1 011个火灾需求点(由橙色圆圈表示)与 16 个消防站候选点(由三角形表示)的空间位置分布。其中红色三角形
16、代表天津市津南区已建消防站,总计为11个,黄色三角形代表“未建设候选点”,总计为 5个。本研究将这 16 个候选地址加以分析,综合考虑消防站建设成本和救援等待成本,确定最优消防布局。采用高德地图平台的 web 服务 API的地理编码服务和路径规划服务,获取救援发生地点和消防站拟建设地点的坐标及从消防站点到救援发生地点的行驶时间。中华人民共和国消防法 明确规定:“消防车、消防艇前往执行火灾扑救或者应急救援任务,在确保安全的前提下,不受行驶速度、行驶路线、行驶方向和指挥信号的限制,其他车辆、船舶以及行人应当让行,不得穿插超越。”因此,消防救援车辆的行驶速度稍微高于社会车辆。根据先前研究18,23,
17、本研究将把从 API上获取的社会车辆行驶时间乘以 0.8作为实际消防车行驶时间。3.3计算结果和分析在本算例中,参数被假设为 0.8。求解结果的上下界间隔设定为 0.1%。计算所花时间为 3.73 s,求解结果为总成本 568 937 万元,消防站建设成本 50 160 万元,救援等待成本 518 777万元,最优拟建设消防站选址点编号为 3、4、5、6、8、9、10、11、15。最优消防站分布图如图 4 所示。16 个消防站点候选点中,7 个站点是“不建设”站点,由黄色三角形表示;9 个站点为“建设”站点,由红色三角形表示。消防“建设”站点与火灾需求点的响应关系由红色线段表示。3.4敏感度分
18、析优化模型的结果严重依赖于几个重要参数。在敏感度分析中,其他系数仍然保持不变,通过调整目标参数取值,分析其敏感性。所有计算过程仍然使用拉格朗日松弛算法求解,并且保证上下界间隔小于 0.1%。时间/s0 40 80 120 160 2000.9%0.8%0.7%0.6%0.5%0.4%0.3%0.2%0.1%相对间隙图 1拉格朗日松弛算法迭代速度Fig.1Iteration speed of Lagrangian relaxation algorithm中途返回551到场实施处置1 023到场未实施处置2 081图 2天津市津南区消防站出警处置情况Fig.2Situation of fire b
19、rigade dispatching in Jinnan District,Tianjin未建设已建设需求点151331157489616图 3津南区消防站选址点分布图Fig.3Distribution map of fire station selection sites in Jinnan District不建设建设需求点消防站服务需求点连线113515104869图 4津南区最优消防站选址分布图Fig.4Distribution map of optimal fire stations in Jinnan District1143Fire Science and Technology,A
20、ugust 2023,Vol.42,No.8图 5 展示了等待损失成本系数 对计算结果的最优消防站数量的影响,在此过程其他参数保持不变。当参数从 0.2增加到 0.8时,最优消防站数量从 5个快速增加9 个。从 0.8 到 2.0 时,最优消防站数量从 9 个增加到 12个。当参数从 2.0增大到 3.0时,最优消防站数量保持不变。从中可以发现,随着参数增加,其对最优消防站数量的影响作用显著降低,这说明等待损失成本系数 存在明显的边际效益。城市规划设计需要考虑未来城市的发展,因此城市决策者们需要考虑在不同的等待损失成本系数下消防站的最优选址情况,以便对城市消防规划进行统筹安排。表 1展示了在不
21、同等待损失成本系数下,最优拟选址消防站选址点编号,并且与目前津南区已建消防站位置进行了比较。表 1数据显示,当=1.6时,最优拟选址建设消防站数量为 11个,与目前天津市已建消防站数量相同,但是消防站选址位置略有出入:模型选址在 1、10和 14号选址点,而不是目前天津市津南区已建设的 7、13和 16号选址点,并且这 3 个选址点在等待损失成本系数从 0.2 增加到 3.0时,一次都未被模型选择。图 6 为=1.6时的消防站选址点,其中蓝色表示非最优但是目前已建设选址点(即 7、13 和 16 号选址点)。上述图表结果说明,目前天津市津南区消防站布局仍有优化空间,建议在未来的消防规划中对上述
22、 3个消防站位置进行调整以增加消防覆盖水平。城市道路交通通行速度与时空之间存在密切关系。从时间角度来看,城市道路交通通行速度在早上和下午的高峰期会显著降低,从空间角度来看,中心区域的拥堵状况会高于周边区域。祝开心18等研究发现,在早晚高峰时段消防车 10 min 覆盖率相较于闲时会严重下降,部分地区消防覆盖率甚至会下降 50%。为了研究早晚高峰道路拥堵对消防站布局的影响,研究假设消防车到需求点的交通通行增加时间随与中心距离增加呈现指数分布EP()。图 7图 9展示了不同拥堵情况下的消防站最优布局,拥堵参数反映了交通拥堵情况,越大交通拥堵越严重。可以发现,随着交通拥堵情况越发严重,中心区域的消防
23、站逐渐增多。当=2时,消防站数量增加到 12个,增加幅度为 33%。这说明消防站最优布局对于交通拥堵情况非常敏感,在研究城市消防站布局的时候需要考虑早晚高峰等交通拥堵对消防救援效率的影响。0.2 0.6 1.0 1.4 1.8 2.2 2.6 3.013121110987654消防站数量577999101112121212121212图 5等待损失成本系数对消防站数量的影响图Fig.5Impact of waiting loss cost coefficient on the number of fire stations表 1不同等待损失成本系数计算结果Table 1Results unde
24、r different waiting loss cost coefficient等待损失成本系数0.20.40.60.811.21.41.61.822.22.42.62.83已建消防站候选点编号最优拟建设消防站选址点编号5 6 9 11 153 4 5 6 9 11 153 4 5 6 9 10 113 4 5 6 8 9 10 11 151 3 4 5 6 9 10 11 151 3 4 5 6 9 10 11 151 3 4 5 6 9 10 11 14 151 3 4 5 6 8 9 10 11 14 151 2 3 4 5 6 8 9 10 11 14 151 2 3 4 5 6 8
25、 9 10 11 14 151 2 3 4 5 6 8 9 10 11 14 151 2 3 4 5 6 8 9 10 11 14 151 2 3 4 5 6 8 9 10 11 14 151 2 3 4 5 6 8 9 10 11 14 151 2 3 4 5 6 8 9 10 11 14 153 4 5 6 7 8 9 11 13 15 16不建设非最优已建消防选址点建设需求点11351415101316968147图 6=1.6时的最优消防站选址分布图Fig.6Distribution map of optimal fire stations when=1.6不建设建设需求点113515
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 拉格朗日 松弛 框架 消防 站点 选址 优化 方法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。