消防站选址问题(附代码)（最大覆盖模型选址lingo）.docx

1、城市消防站点选址问题（附代码）第二组组员：郑舟 杜洋洋 陈建彬张强沈露陈宇银307S.L ZZv =1z 厂.<0d.jj < 50004o3 / w < 300023jZ23j 3000277；Z277j - 3(X)0求解的模型：307 307min Z = £dijZ§r=1 j=l307W. £"5j=ld.ij < 5000d.jj < 3000 z厂坊0307iz7=,同样用lingo求解得出:j=45, 75, 211, 224, 228 (即消防站应建在第45,75, 211, 224, 228 交叉路口)。

2、90008000700060005000 Y583 *15*16 *17凶 «35 «44000300020001000193祝55275459 ,16»6千倾58伯7211QSB2Q8003802 803*9046070«91 妃98<62 GV3 8962*12feO*l31空76妃81成制检0产皿7 句1 «3 -68 «4«1口尊HU16 踌768«170_JF知 蛔41史42 遍"曲8261297°05000"*28一气 30235 必7 妃5松5310000妃57它9

3、5005 <306<296607 I150004.5问题五：根据查阅的资料得到，消防车的速度最小值达到30km/h,最大速度值可达 到110km/h,如森林消防车的速度一般为30km/h，机场消防车的速度为 80110km/h，针对本题第五问，我们设置城市消防车的速度v>40W/z,以此 为最低值考虑消防车到达火警现场的时间t的影响。由物理学公式有：消防车行驶的距离s = uw,根据国家标准城市消防规划 规划，消防车从出发到火警现场的时间不超过5分钟，对于某一城市，消防站 的辖区面积一定，即可知消防车达到某一现场距离s是确定的，即得到v与t成 反比例关系，进而考虑影响速度的因

4、素：1：道路状况其中城市道路的弯折度为主要影响因素，记其为h,查阅资料，h计算公 式：道路的弯折度=辖区内任点到消防站该两点的最小实际距肉该两点的直线距离对于确定的辖区内，设可能发生火灾部位的个数为n,辖区内任一点到消防 站的最小实际距离为。= 1，2,)，直线距离为4(，= 1,2,)；=y-(i = l,2,., n)n万=上(/ = 1,2,.刀)-则该辖区平均道路的弯折度，人为道路的弯折度最终比较量)万越大，道路越弯折，平均速度亍越小，s 一定时，消防车到达火警现场的 时间越大。2：交通拥堵情况，天气情况，驾驶员驾车技术等等都会对会通过速度来影 响消防车到达火警现场的时间。5模型的分析

5、本论文针对五个问题，建立了四个模型。第一问的模型考虑了图上的所有点，而不仅仅是图上的顶点，对应现实问题, 相当于考虑了城市街道上的所有住户，而不仅仅是以往问题中的路口上的住户， 这样得到的中心点更具有现实意义。第二问所建立的多目标规划模型，考虑突发事件应急救援设施的选址决策目 标时，宜采用多目标方法，并充分体现公共服务设施的公平性和效率性。比一般 的单R标规划模型更加具有灵活性和综合性。第三问、第四问建立的都是根据消防站点责任区内最大行车距离建立的中位 点选址模型，但是此模型要求知道图中最少需要建立的消防站点数目，故先建立 了一个以最少站点数位约束目标函数的优化模型，求出需要的最少消防站点数。

6、 这两个模型算法简洁，结果稳定，具有一定可推广性。6模型的评价优点：1.模型本身不存在近似误差，计算误差由Lingo软件和计算机精度决2. 适用范围广，该模型适用于诸如医院急救站、巡逻警点等类似公共设施的 规划建设，只需将参数或约束条件做相应修改即可。3. 该模型易于推广普及，仅需一幅城市地图和相应的坐标信息，便可解决 一类中位选址问题。4. 算法简单易懂，得到的结果稳定性好缺点：1. 假设理想化，没有考虑到诸多因素如水源的影响，实际问题可能更加复杂 化。2. 只考虑了将消防站建立在交叉路口的情况，忽略了消防站可建立在路边 的情形，所以得到的模型可能不是最优的模型。7参考文献1 王正东，数学软

7、件与数学实验，北京：科学出版社，2004年邓佩，苏翔，时间约束下的运输网络最短路径研充，机电产品开发与创新, 第19卷第一期：18-20, 2006年2 韩伟一，王铮，Dijkstra算法的一个改进，运筹与管理，第十三卷第6期: 6-10, 2004 年李德宜，李明，数学建模，北京：科学出版社，2009年【5】谢金星，薛毅，优化建模与LINDO/LING0软件，北京：清华大学出版社,2005 年附录:第一问代码(lingo)model: sets:point/1. 307/:s, a;links (point, point):d;connect (point, point)/l, 2 1, 3

8、5 2, 5 2, 21 3, 6 3, 4 3,13 4, 5 4, 15 5, 16 6, 8 6, 18 7, 10 7, 11 7, 27 8, 11 8, 22 9, 12 9, 14 10, 12 10, 30 11,20 12, 26 13, 18 13, 23 14,32 14,33 15, 16 15,25 16, 17 17, 2418, 2919, 2019,2820, 3421,24 21,3721,45 22,2822,29 22,50 23,25 23,2923, 42 24, 2524, 4925, 4426,3026, 3327,30 27,3127,57 28

9、,3429,51 30,60 31,34 31,5332, 33 32, 36 33, 38 34, 54 35, 40 36, 38 36, 43 37, 39 38, 46 39,40 39, 77 40, 79 41,42 41, 47 42, 52 43, 4643, 6744, 4744,4844, 8445,49 45,8146,62 47,5248,49 48,61 49,63 50,5150, 56 51, 5251, 8352, 8853,5553, 5754,55 54,5654,87 55,6456,91 57,58 57,68 58,5958, 65 59, 6059,

10、 6560, 6260,6960, 8261,63 61,7862,66 64,7265,69 65,70 66,67 66,7167, 92 68, 7069, 7469, 9370,7571,7372,75 73,8974,76 75,9076,98 77,79 77,81 78,8478, 85 79, 237 80, 93 80, 96 80, 100 81, 86 82, 89 82,93 83,88 83, 91 83, 108 84, 88 84, 116 85,86 85, 122 86, 137 87,90 87,91 87, 106 88, 115 89, 95 90, 9

11、8 90, 99 91, 107 92,94 92, 11193, 100 94, 97 94, 109 95, 97 95, 102 96, 98 96,104 97, 102 98, 101 99, 101 99, 105 100, 132101, 103101,110102, 113103, 104103,112104,124105, 106106, 107106,118106,120107, 108107,114108, 117109, 111109,113110,112110,118ill,128112,121113,131114,117114,140115,116115, 1171

12、15,138116,123117, 139118,119118,125118,134119, 121119,127120,126121, 129122,123123,141124, 129124,135125,127125, 143126, 146127,133128, 130128,157129,133130,131130,158131,132131, 167132,135132, 160133, 142134, 144136,137136,148138,139138,141139,147139, 149140, 145140,146140,152141,148141,215142, 143

13、143,144143,156144,146144, 153145, 147145,150146,152147, 154149,151149,154149,169150,152150,154151, 166152,155153,163153,201154, 171155, 171156,162156, 183157, 158157,193158, 167159,160159,174160,161160, 178161, 162162,179163, 164164, 172165,169165, 173166,173167,211168,170168, 192169, 192169,194171,

14、185171,172172,184174, 180174,186175,179175,182175, 188176, 177176,180176,187177,178177,199178, 181178,191179,189181, 182181, 190182, 200183,196184,214185,194186, 187186, 198187,195188,189189,205190, 191190, 204191,208193,211193, 255194,210194,213194,214194, 238195, 198195, 199196, 206196,209197,2031

15、97,215198,211198,218199,208200,204200, 209200,219201,206201,207202,207202,214202,216203,210203, 220204,208205,209205, 254206, 243207,222208,212209, 221210, 225211,260212, 234213,223214,216215,226215, 228216,222216,224217,218217, 232218,231219,221219,233228,251235,236241,242247,258255, 260262, 267272

16、.304278,290287,289295, 296304.305endsetsdata:d=ole(, C:Documents and SettingsAdministrator桌面D1. xlsx',' distance*); enddatamin=dis;for (point (i) :s (i)>sum(connect (p, q): d(p, i)*b(p, q)+x(p, q)-100000*a(i);for (point (i) :s(i)>sum(connect (p, q) :d(q, i)*b(p, q)+d(p, q)*b(p, q)-x(p,

17、 q)-100000*(l-a )；for (connect (i, j) :x(i, j)<d(i, j)*b(i, j);for(connect(i, j) :2*dis>s(i)+s(j)+d(i, j);©for(point:您bin (a);for(connect:©bin(b);sum(connect (i, j) :b(i, j)=l;End220,226229,233235,237241,261249,250255,275264,271273,274279,286288, 292295, 306305,306220,227230.250236.2

18、51242,272250.252256,258265, 266274,278280, 299289, 291296, 307221,229231,232237, 257243, 249250,264256, 259265, 277275,297282, 283290, 294297, 298222,230231,259238,240243, 263251,253257,296267.281276.281282,284290,302298,300223,224232, 234238,244244.268251,305258,276268.269276, 291282, 288291,292299

19、,303224, 239232.246238, 265245.246252,269260, 270268, 279277,279283,293291,298299,304224,244233,234239,252245.256253.257261,266269,273277,280285,286292.300300.301225, 227233, 248240,241246, 247253,295261,280270,287277,285285,294293, 301301,302226,242234.247240, 266247.248254,258262,263271,284278, 27

20、9286, 290294, 303302, 303306,307/:b, x;minZ = Lm307s, 2+ xw)-10000 q(1-1)307Si Z z(4加 + 勾 f 四)T0000(1F)1=1(1-2)(1-3)第二问代码：model:sets :point/1.307/:w,u,y; links(point,point):d,z,s;endsetsdata:w=ole('C:Documentsand SettingsAdministratorxAAaeD2 . xls *, 'weight');d=0ole('C:DocumentsandS

21、ettingsAdministratorxAAaeDl. xlsx *, ' distance 1);enddatamin=sum(links(i,j):w(i)*d(i,j)*z(i,j);for(links(i,j) :bin(z (i,j);for(links(i,j):d(ir j)*z(iz j)<=s(i,j);for(point (i):Gsum(links (i,j) :z(i,j)-u (i)>=1);0for(point (i):gin (u (i);0for(point (i) :u(i)<=4);for(links(i,j) :s(iz j)-

22、5000*z (i,j)<=0);0sum(point(i) :w(i)* u(i)>=6;for(links(i,j):z(i,j)-y(j)<=0);for(point (j) :bin(y(j);sum(point(j):y(j)=5;end第三问代码：model:sets :point/1.307/:y;links(point,point):d,z;endsetsdata:d=ole('C:DocumentsandSettingsAdministratorxAAaeDl. xlsx ', ' distance ');enddatamin

23、=sum(links:d*z);sum(point:y)=2;for(point(i):sum(point(j):z(i,j)=1);for(links (i,j) :z(i,j)-y(j)<=0);0for(links:d*z<=10000);Gfor(point:Gbin(y);for(links:bin (z);end第四问代码：model:sets :point/1.307/:y;links(point,point):d,z;endsetsdata:andd=ole('C:DocumentsSettingsAdministratorxAAaeDl. xlsx *,

24、' distance *); enddatamin=sum(links:d*z);Gsum(point:y)=5;for (point(i):sum(point(j) :z (iz j)=1);0for(links(i,j):z(i,j)-y(j)<=0);for(links:d*z<=5000);for(point(j):d(103,j)*z(103,j)<=3000);Gfor(point(j):d(123,j)*z(123,j)<=3000);0for (point(j) :d(277,j)*z(277,j)<=3000);Qfor(point:Gb

25、in(y);0for(links:bin(z);end摘要随着国家现代化进程的不断推进，必须要有一个与之相适应的现代化城市应 急系统和消防布局规划.选址问题是应急系统中重要的长期决策之一，选址的好 坏直接影响到服务方式、质量以及服务成本等，从而影响到城市应急能力的有效 发挥和资源的合理配置.本文主要研究城市消防选址的决策问题，包括单目标选址模型和多目标选址 模型。其中问题一，三，四属于单目标选址问题，问题二属于多目标选址问题。 首先我们运用网络图的最短路径算法理论，给出了基于最短路径的选址问题的算 法（Floyd算法），计算出任意两点的最小路径。问题一：单一消防站选址问题，我们借用P中心模型，

26、求离消防站的点的最 大距离的最小值。先假定应急服务设施点都选在网络图的顶点处，所求的中心点 是139点，离消防站的最远距离为10296.1米。然后考虑了消防站和火灾现场在 道路上的的情况，求出了整个网络的一般绝对中心点A（7354.915, 4096364），离 消防站的最远距离为10271.18米.问题二：多消防站选址问题，我们采用了多目标决策模型，既考虑了离消防 站最远距离的最小化，又考虑了消防站离需求点的总加权最小，还考虑了超额覆 盖需求区域的总权重最大。然后用参数规划的目标约束法，把多目标转化成单目 标，求出消防站的位置。为了简化问题，仅考虑消防站和火灾现场在端点的情况。 本题中，假设

27、离消防站的最大距离为5000米，超额覆盖区域的总权重赋值为6, 求出消防站的位置分别为点24, 98, 194, 211, 253.该模型可以根据不同城市的 具体情况赋权值，求出适合不同城市的最佳消防点，易于推广。问题三：共同时间约束下的消防站数量最少问题，我们首先应用位置集合覆 盖模型，结合本题的约束条件（10分钟）算出所需消防站最少个数为2个，其 次，建立P中值模型，得出所求点为点24和143。问题四：不同时间约束下的消防站最少问题，通过集合覆盖模型，结合本题 约束条件（一般位置5分钟，重要位置3分钟），算出所需消防站最少个数为5 个，其次建立P中值模型，得出所求点为点45,点75,点21

28、1,点224,点228.问题五：分析消防车的速度对到达时间的影响，当速度改变时，考虑到经济 效益以及最优化结果，则消防站点的个数相应改变，所以时间随速度以及站点个 数的影响o根据以上分析可以得到对于实际问题得出最优的消防站的选址，解决经济 效益和满足实际的救火需求。关键词：最优选址问题P中心模型P中值模型 多目标决策模型1问题重述在城市中消防站的选址对于及时的消灭火警有着特别重要的意义。考虑某城市内一区域，为简化问题，假定所有火警现场均在下图的道路上。 该区域内三个重点部位的坐标分别为：(5112, 4806), (9126, 4266), (7434 , 1332)(见下图红点部位，蓝色部分

29、为水域)。要解决如下问题：1. 如果该城市只建一个消防站，最佳的地点应该位于什么位置，该消防站 到达城市道路上的点的最远距离是多少？2. 如果该城市建五个消防站，最佳的地点应该位于什么位置。3. 如果消防车的行驶速度60km/h,要建几个消防站才能使得该城市道路上 任何一点发生火警之后，消防车能在10分钟之内到达。4. 如果消防车的行驶速度60km/h,要建几个消防站才能使得该城市道路上 任何一点发生火警之后，消防车能在5分钟之内到达，同时要求到达重点部位的 时间不多于3分钟。5. 分析消防车的行驶速度对消防车到达火警现场的时间的影响。2问题分析2.1问题一分析在城市中建立一个消防站点，要求出

30、此消防站点的最佳位置以及该点到到达 城市道路上的点的最远距离。交通条件、自然地理条件、道路状况等因素都会影响消防站点的选址。为了 简化问题，本题我们只考虑行车距离因素的影响。消防站和火灾现场的地址可以是城市道路上的任何位置，而不仅仅是道路端 占o要使火灾损失达到最小，最重要的是消防队接到火警后能够尽快到达火灾现 场，这就要求消防站点到城市中任何火灾现场的“最远距离最小”。2.2问题二分析在多个消防站点选址问题中，宜采用多目标方法，并充分体现公共服务设施 的公平性和效率性。首先要求应急求援设施覆盖所有需求趋于，在考虑具体目标 时一是从快速反应或公平性考虑要求消防站服务需求点的最大距离为最小；二是

31、 从超额覆盖和备用设施考虑，要求消防站覆盖需求点的总权重最大；三是从消防 站的易接近性和使用效率出发，要求消防站服务需求点的总加权距离最小。2.3问题三分析第三问需要求出在相应的时间限制下，为了能使中位选址问题达到最优需要 在该城市建立的消防站点个数。根据消防车的行驶速度60km/h以及反应时间限 制10分钟，得出消防站点与相应区域内的点的最大距离应小于 d=60*100km=10km,运用中位点问题模型，采用参数规划的约束法，可以很好 的解决该问题。2.4问题四分析第四问在第三问的基础上，进一步将反应时间限制为5分钟，同时增加对重 点部位反应时间的限制3分钟，得出消防站距离相应区域内的普通部

32、位和重点部 位的最远距离分别为5km和3km。在问题三模型的基础上，增加以及改变某些约束条件，便可让问题得到解决。3模型假设和符号说明3.1模型假设（1）相邻两个交叉路口之间的道路近似认为是直线，把城市地图抽象成由 点和线组成的无向网络赋权图；（2）假设消防车在到达火灾点的途中没有障碍，即不考虑路况和其他突发 事件的影响，消防车按照其行驶速度匀速行驶直至到达火灾点；（3）不考虑灾情蔓延速度，即火灾点不会转移和增加（4）不考虑消防队的反应时间，假设接到火情的瞬间，消防队即出发救火3.2符号说明D(i,j)最短距离矩阵du点Vi到点Vj的最短距离I消防站点的集合J火灾现场的集合iielJjwJ4模

33、型的建立与求解4.1问题一：单个消防站点选址问题首先，用Floyd算法求出任意两个结点之间的最短路径；Floyd算法的基本思想如下：把图用邻接矩阵G表示出来，如果从Vi到Vj有路可达，则Gi,j=d, d表示 该路的长度；否则Gij=0o定义一个矩阵D用来记录所插入点的信息，Di,j表 示从Vi到Vj需要经过的点，初始化Di,j=jo把各个顶点插入图中，比较插点后 的距离与原来的距离，GiJ = min（GijLGi/k+GkJ）,如果Gi,j的值变小，则 Di,j=ko在G中包含有两点之间最短道路的信息，而在D中则包含了最短通路 径的信息。如果消防站点和火灾现场的地点仅仅可以发生在网络图的节

34、点上，则根据 “最远距离最小”的选址原则，我们很容易就可以得到在途中第139点设置消防站最合适，=10296.1m。但是实际情况中，更多的消防站点是建设在城市道路上。此模型中运用的符号说明:消防站点到最远距离最小s,消防站责任区内（0-1）变量，与=1则表示在彳.中建设消防站，否则反之Z.如果消防站点Vj覆盖点Vi,则z,=l,否则z,=0建立如下优化模型:min Z = Lllt307Si 2 £(dpjbpq + Xpq)-10000 a,(1-D1=1307S, - £ (dqib网+ d闯-x网)-10000 (1 - q)(1-2)2Lm 2 st- + Sj +

35、 djj(1-3)xa < 3"(1-4)以最远距离最小作为目标函数。约束条件（1-2）表示约束条件（1-3）表示约束条件（1-4）表示用Lingo求解得到：j=139, 147o （即消防站应建在139,147交又路口）900080008000700060005000400030002000100014« « -6F PH8 *134546T7-ei切避一2凶«35 祝4妃1421新句网 妍 5 朝7 M4 VM5w m f I I I 杵奴 /6潮130饱04C91尘98吓妃8司9&- 啊5867 早 59 |

36、l606f1-55-卡6070 75咤9977-«1毛3扇 7 峻伊辑 *199*115 4116 异晦7 60168-1707冬弗446241 妃 42 展磁8261 诚羿寥28-261236235 最5枪53°0500010000295605 灼06*296007150004.2问题二：多个消防站点选址问题此模型中运用的符号说明:第Vi点的权重，重点部位权值为2,其他点权值为1表示点Vi被超额覆盖的次数，即总覆盖次数-1, 为整数（0-1）变量，为=1则表示在Vj中建设消防站，否则反之Z”（0-1）变量，如果消防站点Vj覆盖点Vi,则Z. =1,否则为=0Sij消防站点

37、到图上的最大距离根据上述选tl上特点，本文提供了一个针对该问题的多目标决策模型。消防站选址的多目标决策模型表述为:in inZ = Sjj(1)max307z? = £*r=l(2)s.t.307£为=5/=1>1307»广纶2 1(4)气-yj"(5)307(6)模型说明如下：约束条件和（6）式保证设置的消防站数H为P；约束条件（5）式保证设置的应急救援设施数目不低于需求区域i要求的最»厂%少设施数qi,超出的数目（K ）即为需求区域i超覆盖的次数5；目标函数（1）式和约束条件（7）式使设置的应急救援设施服务需求区域的 加权最大距离（平

38、均意义上）L为最小（即p-中心模型），体现公平性； 如果约束条件（7）式改为则目标函数（1）式和约束条件（9）式保证设置的应急救援设施服务需求区 域的最大距离L为最小，体现对应急救援设施快速反应的要求；目标函数（2）式和约束条件（5）式使超额覆盖最大化，其主要目的是使权 重越大的需求区域有更多的应急救援设施为其服务；目标函数（3）式和约束条件（5）式使设置的应急救援设施服务需求点的加 权总距离为最小（即p-中值模型），体现效率性。上述模型为3个目标的多目标决策模型，多目标准则函数为minv】,V2,V3.本文采用参数规划的目标约束法把多目标转化成单目标，来求解上述选址决 策模型。保留决策问题中的一个目标，其余两个目标被作为约束，通常保留目标 V3,把目标VI和V2约束化，根据城市的具体情况，使V】和V2分别约束于a和 b.模型求解：对于本题，给离消防站的最大距离的最小值赋值5000m，给消防站覆盖需求 点的总权重赋值为6,写出目标函数和约束条件如下：min Z =iel jejSL > 4勺（2-1）307»厂丹21（2-2）(2-3)(2-3)s一5000z. <0(2-4)z厂为"模型说明： 约束 约束 约束 约束(2-1)(2-2)(2-3)(2-4)（2-3）表示在要建立五个消防