应急服务设施选址问题的模型及算法.pdf

万方数据

一类应急服务设施选址问题的模型及算法张玉芬1，齐红然2，刘世普3数学的实践与认识MATHEM引言2基本概念与假设条件在城市规划建设中，经常需要考虑一些设施诸如医疗救护中心、消防中心、110报警中心等的优化选址问题，以便一旦该城市中某地出现需要服务的紧急事件后，有相应的服务中心能在规定的时间内到达现场进行服务．在应急规定中，一般都对时间有特殊的要求，如公安部标准(GNJl—82)规定：城镇消防站的布局，应以消防队从接警起15分钟到达责任区最远点为一般原则．为了保证应急的时间要求与经济性要求，应急服务点选址设计必须合理布局优化配置[1-3]．选址问题最早是由Hakim提出[4]，在救护车和消防站等应急设施的设置等许多领域得到广泛应用．多应急服务点的选址问题属于P—Center问题，主要研究如何设置P个设施点，使之既满足一定服务对象又使设施点与服务对象之间距离最大值最小化的问题[1]．本文从城市应急服务点选址问题出发，提出了限定期条件下最少应急服务点的选址模型，并以改进的遗传算法对选址模型的求解进行了设计．2．1基本概念定义1给定图G一(y，E)，对G中的每一条边(让，口，)，相应的有一个数哟，，称这样的图为赋权图，咄，称为边[矾，口，]上的权．如果把应急点看作赋权图中的顶点，连接它们的道路看成赋权图中的边，则整个应急系统可看成一个网络图G．定义2设F={y。，yz，⋯，‰)为应急地点集，E={e。，e：，⋯，e。)为网络图中k条边的集合，bi为边Pi的长度，边ei的两端点为％和％(假设户<g)，即有e；一(％，Vq)．则对于边e。上的任意一点&(到点z，，的距离为五)到顶点q的最短距离为：第39卷第14期ATICSINPRACTICEANDTHEORY2009年7月(1．河北大学数学与计算机学院，河北保定071002)(3．华北电力大学(保定)数理学院，河北保定071003)摘要：在分析城市应急服务设施选址问题基础上，建立了限定期条件下应急服务设施选址问题的数学模型，提出了一种基于遗传算法的应急服务设施选址模型的有效算法，并通过算例分析验证了该方法的有效关键词：应急服务设施；选址；模型；遗传算法1V01．39No．14(2．保定职业技术学院，河北保定071002)性．收稿日期：2009—02—11
万方数据

z=∑Y』限定期条件下应急服务设施选址问题的数学模型【0，≥：Y，≥1，V4应急服务设施选址模型的优化算法设计定义3设对每个应急地点存在最大标准时间A，当应急地点砖到可能的应急服务设施点si的行车时间t，，在该标准时间A之内(即tiJ≤A)时，则可能的应急服务设施点已覆盖应急地点址，或称为应急地点I／i被应急服务设施点为覆盖．2．2假设条件为了建立城市中限定期条件下多个应急服务点的选址优化模型，作如下假设：1)应急服务点的位置可以设在城市道路的任何位置．不考虑由于地理位置、周围环境及成本等问题所造成的影响．2)在每条道路上最多建立一个应急服务点，可能的应急服务设施点s，建在边e，上．3)应急服务点的容量是无能力限制的．即只要是在应急服务点的服务范围内，应急点的需求总是可以满足的．4)假设图中的距离均为时间距离，边e，上可能的应急服务设施点q到应急地点秽，的距离为．75，．设应急地点集为F={确，屹，⋯，‰}，砖(i一1，2，⋯，m)为应急地点；S一{s。，s。，⋯，晶)为可能的应急服务设施点集，sj(歹一1，2，⋯，雅)为可能的应急服务设施点，t打表示从应急服务设施点屯到达应急地点址的最短时间．现在计划在城市中建立若干应急服务设施点，要求当任何应急地点发生事故时，距离其最近的应急服务设施点到达该应急点的时间不超过规定期限A．阉如何确定该城市应急服务设施点的地址，使需要建立的应急服务设施点的数目最小?3．2应急服务设施选址问题的数学模型设二元值决策变量Yj为：f1，当可能的应急设施点s，被选中时当可能的应急设施点s，未选中时记所有能覆盖应急地点M的可能应急设施点的集合为Ni=(．fId(sj，砖)≤A)，则能覆盖所有应急地点所需的最少设施数及其位置可由下列模型决定：其中，目标函数(1)是设置的应急服务设施数最小，约束(2)保证每个应急地点至少被一个服务设施点覆盖，约束(3)限制决策变量YJ为。一1变量．上述模型是一个NP难题，采用传统算法难以解决．由于遗传算法具有高度并行、随机、数学的实践与认识d(si，∥，)=min{d(vp，口J)+b(s。，ZJp)，d(v口，口J)+6(&，口口)=min{d(砂p，口，)+五，d(v口，秒f)+bi—zi)33．1问题描述i∈A={1，2，⋯，m)Yj∈{0，1}，V“min(1)(2)Y，∈S(3)38s．tyyESJ∈N，
万方数据

只：掣，f(妻％)～，∑f(