应急中心的选址问题

救护中心建立问题的研究摘要本文对某小镇建立两个救护中心，使应对突发事件总的响应时间最少的问题进行了分析，并建立了数学模型进行了求解。在假设(I)的前提下，即需要救护的事件集中在每个街区的中心。考虑到街区数目不是很多，本文采用穷举法进行了最优解的搜索。即先任意选取两点作为救护中心的位置，然后计算其他街区到这两个救护中心的总响应时间，总响应时间最少的旧最优的方案。同时为了考虑障碍区域和水塘，本文首先对那些设置救护中心需要穿越障碍区域和水塘的点进行了剔除，然后在利用计算机一一穷举。在假设(Ⅱ)的前提下，需要救护的事件均匀分布在街道上，在计算总响应时间时，本文把整个街道的事件发生频率集中在街道的中心位置处进行计算。同时本文证明了当救护中心仍设立在街角处时所需的总响应时间是最少的，这样仍可以按照假设(I)中的穷举方法求出救护中心设立的最优位置。关键词：穷举法；剔除；街道中心；街角问题的重述某小镇开始方案建立两个救护中心，把救护站、消防队和派出所结合在一起。图1指出每个长方形街区所发生的需要救护事件的次数，北边的L形区域是障碍，而南边的长方形区域是浅水池，救护车辆驶过一条南北向的街道平均花15秒，而救护车辆驶过一条东西向的街道平均花20秒，请确定这两个救护中心的位置，使得总响应时间最少。(1)假定需要救护的事件集中在每个街区的中心，救护中心位于街角处。(2)假定需要救护的事件沿包围每个街区的街道上均匀分布，救护中心可位于街道的任何地方。图1小镇的街区分布图二．问题分析对于假设(I)的情况，要建立救助站的位置，使总的响应时间最短。在考虑障碍区域的情况下，可以首先把那些建立救护站需要穿过障碍区域的点剔除掉，然后可以考虑穷举法利用计算机求出最正确的建立救护中心的位置。对于假设(Ⅱ)的情况，由于突发事件是均匀分布在每条街道上的，可以利用每条街道的中心点位置来作为这整条街道突发事件的频率集中点。同时可以证明：在街角处设置救护中心是所需总响应时间最短的。这样建立救护中心的位置使有限的，仍可以考虑穷举法利用计算机进行求解。三．符号说明建立两个救护中心所需最少时间的函数第(i,j)个小区到()个救护站的时间函数P街区的事故发生频率矩阵坐标中第(i,j)个区域的应急事件次数i每个街区街角的横坐标j每个街区街角的纵坐标四．模型假设1.在同一时刻各街区及街区内不会同时发生两件应急事件；2.应急事件集中在街区中心，而应急设施在街角处；3.障碍区及浅水塘区应急事件次数为零；4.应急车辆的响应时间只考虑在街道上行驶的时间，不考虑转弯的时间；5.假设应急需求沿包围每个街区的街道是均与分布的，而应急措施可以位于街道的任何地方。五．模型的建立与求解问题一的模型建立与求解在假定(I)的前提下，应急需求集中在每个街区的中心，本文进一步假定应急车辆只要到达该街区四个街角中最近的一个，就认为到达率该街区。那么有假定(I)每个应急设施选在街角处，可能的位置只有6×11=66个，两个应急设施的位置的可能组合至多只有66×65/2=2145个。考虑到这个数目不是很大，可以利用计算机进行穷举，对每种组合一一算出所对应的总响应时间，依次比拟得出最小的响应时间及其对应的选址方案，具体的算法是：建立直角坐标系，一该镇的东北角为原点，以从东到西为X轴的正方向，以从北向南为Y轴的正方向，在南北和东西方向分别以一个街区的长作为单位长，那么街角的坐标(X,Y)是满足条件的整数。而每个街区的中心的坐标具有形式，其中i，j满足的条件：的整数。如果不考虑障碍和水塘的影响那么应急车辆从设在(X,Y)点的应急到一为中心的街区的行驶时间等于:记为以为中心的街区的事故发生频率(即在图上该街区所标的数字)。用矩阵P表示，那么P为那么如果应急设施设在,这两点，那么该设置方案的总响应时间为让取遍0—4，取遍—4，分别独立地取遍0—10，依次对的每一个值计算出对应的总响应时间。通过比拟可得出所有这些总响应时间的最小值。以上计算的过程没考虑障碍区域和水塘的情况，对于考虑障碍区域和水塘的情况，见图2.只要不把救护站设在图2所标记的A、B、C、D、E等点，那么救护的路线就不会穿越障碍区域。所以在计算中可以事先把这些点剔除。同理对于水塘障碍区域见图3.只要剔除F、G点即可保证救护车的路线不会穿越水塘。图3.水塘区域按照以上计算过程利用计算机求解可得在M和N处建立救护中心，所需的最少时间为5065秒。见图4.按照以上计算过程利用计算机求解可得在M和N处建立救护中心，所需的最少时间为5065秒。即两个救护中心分别建立在(2,2)和(2,6)两点。见图4.(求解代码见附件)5.2模型二的建立与求解在假定(Ⅱ)的情况下,由于允许应急设施在街道上任何位置，这就有无穷多种可能，不能直接用计算机穷举，不过，本文可以证明:应急设施仍应设在街角处，才能使总的响应时间最短。 对已选定的两个应急设施的位置A和B。首先，本文将街道上所有的点的集合划分成两个责任区和，分别由A，B进行救助：街道上的点P如果由A点去救助比由B点去救助的时间更短，就将P划进A的责任区，反之就划进。为了表达方便，本文将每个长方形街区的死条边中的每一条称为一条“街道〞，街道的一段称为“街段〞。没挑街道中属于的点与属于的点各组成一个街段。分别成为A的或B的责任段。一条街道最多被分成两个责任段，责任段只有有限多条。对于每个应急设施，分别计算出它的每个责任段的总响应时间，将总响应时间求和就得到这个设施的责任区的总响应时间，将两个责任区各自的总响应使劲相加就得到这一选址方案的总响应时间。下面需要知道：任一设施A到它的一个责任区段EF的总响应时间怎样计算。按假定(Ⅱ),街区出现事故的频率平均分布在它周围的四条街道上，每条街段的事故发生频率与它的长度成正比。将应急车辆每秒钟行驶的路程作为长度单位，那么当街区事故频率为p，街段的长度为t是，这一街段的事故频率为p×t/70，70是街区的周长，即车辆绕街区行驶一周需70秒，在大多数情况下，一条街段同时与两个街区相邻，两个街区的事故它都有份，它的事故频率应为(p+q)×t/70,p,q分别是这两个街区的事故的总频率。事实上，由于EF的每一小段的事故发生频率只与这一小段的长度有关，换句话说:频率密度是常数，只要求出EF到A的平均行驶时间T，再乘以EF的总的事故频率就行了。当A设在街角处时，平均行驶时间也就是A到EF的中点M的行驶时间秒，这里(X,Y)，(,)分别是A，M的坐标，将乘以EF的事故频率，就得到EF的总响应时间。假设应急设施A不是设在街角处，而是设在某条街道CD的两个端点C、D之间，那么可能出现这样的情况：从A出发到EF中的某些点的最短救助路线应该向C方向行驶，而到另一些点去那么应向D方向行驶。这时，平均时间就不等于A到EF中点M的时间，而是比小。在这样的情况下EF可以分成两段EG、GF，从A到其中一段上的所有的点的最短救助路线应向C方向行驶，而到另一段上的所有的点那么应向D方向行驶。分别计算EG、GF的事故发生频率，，将这两个频率分别集中在EG、GF各自的中点，，就可分别算出EG、GF的总响应时间，再将他们相加就得到EF的总响应时间。下面证明：最短的总响应时间必可又这在街角处的应急设施A、B来实现，假定已选择两个应急设施A、B的位置使总响应时间最短，且至少有一个设施(比方A)不是设在街角处，而是设在某一条街道CD的两个端点C、D之间。本文证明：可以吧这个设施从A移到C或D，使总响应时间不增加。证明的主要想法是：将设施迁移到街角后，它到某些街段缩短了一段路程，同时到另外某些街段增加同样长的一段路程。如果路程缩短的那些街段的事故总频率大于路程增加的那些街段的事故总频率，那么总的响应时间缩短了，设施位置得到优化，说明原来的位置不是最优。设P是A的责任区内需要救助的一点。从A出发到P，有两种可能的最短救助路线AP：一种是沿AC、经由C点到P；另一种是沿AD、经由D点到P。但凡AP属于前一种情况的，这样的点P组成的集合记作；但凡AP属于后一种情况的，这样的点P组成的集合记作。这样就将A的责任区按最短救助路线出发时的两个不同方向分成了两个区域。比拟，这两个区域各自的事故总频率,的大小。如果比大，就将设施从A移到C，向靠拢；反之，当比大时，将设施由A迁到D去靠近；当=时将设施任意迁到C或D都可以。本文将证明：将设施经过这样的迁移后，总响应时间只可能减少，不可能增加。因此假设迁移前的方案最优，迁移后一定还是最优(事实上，当时，迁移后的方案一定比原来最优，说明原来的不可能最优)。不妨先假定，设施从A迁到C点为了便于比拟迁移前后的总响应时间的变化情况，本文先作下面两个假设：(1)应急设施从A搬迁到C后，两个旧的责任区，先仍分别由C和B负责救助，暂时不变。如果在这样不改变责任区的情形下都能证明总响应时间不增加，那么再进一步合理调整C、B的责任区还可能进一步缩短(至少不会增加)总响应时间。(2)搬迁后从新设施C到旧区域中的任何一点P的救助路线为：从C出发离开CD，沿原先A的旧的救助路线到P。从C到旧区域的任何一点P的救助路线为：从C出发沿CD〔经过A〕到D，再沿原先A的旧的救助路线到P。 设应急车辆从A到C的行驶时间为T。那么按(2)的行驶路线，的点到设施的路程减少了AC，行驶时间减少T，总响应时间减少；的点那么相反，路程都增加了AC，行驶时间都增加T，总响应时间增加。由于，，总响应时间减少量超过(或等于)增加量，总的响应时间是减少了(或不改变)，设施搬迁后的位置比原来更优，至少同样优。假设(2)的路线不一定是最短路线，如果再进一步选择最短路线，那么还有可能进一步缩短新设施方案的总响应时间，更加说明其优越性。假设(I)的责任区的划分不一定是合理的，可以再进行调整，将街道上的每一点划给离他最近的设施的责任区，这样又可能再减少新设施方案的总响应时间，再一次增加它的优越程度。这样就证明了新设施比就设施更优，或者同样优。因此在题目假定(Ⅱ)之下，仍可设应急设施设在街角处，于是与假定(I)的情况类似地可用计算机穷举算出答案来。对任一对候选的应急设施位置A(),B(),求出每一条街道CD的总响应时间，将所有街道的总响应时间相加就得到这一选址方案的总响应时间。进行比拟就可得出最短的总响应时间及相对的选址方案。CD的总响应时间的计算方法已在前面讲过。并且由于设施都设在街角处，只要将CD分成两个责任段CE、ED，将这两个责任段的事故频率分别集中在它们各自的中点计算就可以了。由于时间有限，本文未能利用计算机的求解，在这里只给出了本文的思想。六、模型的评价与改良在假设(I)的条件下，考虑到街区的数目不是很多，本文采用穷举法利用计算机求出了最优解，同时在考虑障碍区域和水塘的情况下，本文先对那些可能要穿越障碍区域的点进行了剔除，然后再一一穷举得出最后的结果。在假设(Ⅱ)的情况下，首先根据题意简化了最短时间的计算方法，同时又证明了在假设(Ⅱ)的条件下，救护中心的仍在街角处时所需时间最短的，大大简化问题的复杂性，便于求解。但由于时间有限，本文未能利用计算机给出最后的结果，这也是本文需要努力的地方。七、参考文献1.方磊，何健敏.应急系统优化选址的模型及其算法[J].系统工程学报，2003年2月，第18卷第1期.2.刘来福，杨淳，黄海洋.数学建模方法与分析[M].机械工业出版社，2005年6月.3.陈东彦，李冬梅，王树忠.数学建模[M]，北京，科学出版社，2007.附件：问题一得求解代码function[varargout]=aaa(varargin)X=[5,2,2,1,5,0,3,2,4,2;2,3,3,3,3,4,1,3,0,4;4,3,3,0,3,4,0,0,0,0;1,2,0,0,4,3,2,2,0,1;3,2,2,5,3,2,1,0,3,3];t=0;t1=zeros(1,8);T=zeros(6,11);fori=1:6forj=1:11T(i,j)=Inf;endendfori=1:6forj=1:11T1{i,j}=T;endendform=1:6;forn=1:11;fori=1:6;forj=1:11;fork=1:5forl=1:10t1(1)=((abs(m-k))*20+(abs(n-l))*15+(15+20)/2)*X(k,l);t1(2)=((abs(m-(k+1)))*20+(abs(n-l))*15+(15+20)/2)*X(k,l);t1(3)=((abs(m-k))*20+(abs(n-(l+1)))*15+(15+20)/2)*X(k,l);t1(4)=((abs(m-(k+1)))*20+(abs(n-(l+1)))*15+(15+20)/2)*X(k,l);t1(5)=((abs(i-k))*20+(abs(j-l))*15+(15+20)/2)*X(k,l);t1(6)=((abs(i-(k+1)))*20+(abs(j-l))*15+(15+20)/2)*X(k,l);t1(7)=((abs(i-k))*20+(abs(j-(l