第17讲 应急设施的优化选址问题
问题（AMCM-86B题）里奥兰翘镇迄今还没有自己的应急设施。1986年该镇得到了建立两个应急设施的拨款，每个设施都把救护站、消防队和警察所合在一起。图17-1指出了1985年每个长方形街区发生应急事件的次数。在北边的L形状的区域是一个障碍，而在南边的长方形区域是一个有浅水池塘的公园。应急车辆驶过一条南北向的街道平均要花15秒，而通过一条东西向的街道平均花20秒。你的任务是确定这两个应急设施的位置，使得总响应时间最少。
图17-1 1985年里奥兰翘每个长方街区应急事件的数目
（I）假定需求集中在每个街区的中心，而应急设施位于街角处。
（II）假定需求是沿包围每个街区的街道上平均分布的，而应急设施可位于街道的任何地方。
§1 若干假设
1、图17-1所标出的1985年每个长方形街区应急事件的次数具有典型代表性，能够反映该街区应急事件出现的概率的大小。
2、应急车辆的响应时间只考虑在街道上行驶时间，其他因纱（如转弯时间等）可以忽略不计。
3、两个应急设施的功能完全相同。在应急事件出现时，只要从离事件发生地点最近的应急设施派出应急车辆即可。
4、执行任何一次应急任务的车辆都从某一个应急设施出发，完成任务后回到原设施。不出现从一个应急事件点直接到另一事件点的情况。（这是因为，每一个地点发生事件的概率都很小，两个地点同时发生事故的概率就更是小得可以忽略不计）。
§2 假定（I）下的模
在假定（I）下，应急需求集中在每个街区中心。我们可以进一步假定应急车辆只要到达该街区四个街角中最近的一个，就认为到达了该街区，可以开始工作了。按假定（I），每个应急设施选在街角处，可能的位置只有6×11=66个。两个应急设施的位置的可能的组合至多只有66×65/2=2145个。这个数目对计算机来说并不大，可用计算机进行穷举，对每种组合一一算出所对应的总响应时间，依次比较得出最小的响应时间及对应的选址方案。具体算法是：
建立直角坐标系，以该镇的西北角为原点，从北到南为X-轴正方向，从西到东为Y-轴正方向，在南北、东西方向上分别以一个街区的长作为单位长，则街角的坐标(X,Y)是满足条件0?X?10,0?Y?5的整数。而每个街区中心的坐标具有形式
(i?0.5,j?0.5)，其中i,j是满足条件：0?i?9,0?j?4的整数。如果不考虑障碍和水
塘的影响，同应急车辆从设在(X,Y)点的应急设施到以(i?0.5,j?0.5)为中心的街区的行驶时间等于
t(X,Y,i,j)?15(X?i?0.5?0.5)?20(Y?j?0.5?0.5)
?15(X?(i?0.5)?20Y?(j?0.5)?17.5) 秒
记p(i,j)为以(i?0.5,j?0.5)为中心的街区的事故发生频率（即在图上该街区所标的数字）。如果应急设施设在(X1,Y1),(X2,Y2)这两点，总不妨设X1?X2，则该设置方案的总响应时间为
T(X1,Y1,X2,Y2)
???p(i,j)min{t(X1,Y1,i,j),t(X2,Y2,i,j)}
i?0j?094让X1取遍0—10，X2取遍X1?10，Y1,Y2分别独立地取遍0—4。依次对四数组
(X1,Y1,X2,Y2)的每一个值算出对应的总响应时间的最小值及对应的四数组。
以上算法不难用计算机编程实现。由于数组的个数不算多（只有两千多个），计算机可很快得出答案。答案是：
两个应急设施分别设在点（2，3），（6，3）时最优。
这是在不考虑L形障碍区域和水塘的影响的假定下得出的最优解，但从这两个点到
任何街区都可避开L形障碍区域和水塘，故它们也就是原题所需的最优选址。
§2 假定（II）下的模型
在假定（II）下，由于允许应急设施设在街道上任何位置，这就有无穷多种可能位置，不能直接用计算机穷举。不过，我们可证明：应急设施仍应设在街角处，才能使总响应时间最少。
对已选定的两个应急设施的位置A和B，我们先来看总响应时间怎样计算。首先，我们将街道上所有的点的集合划分成两个责任区VA,VB，分别由A,B进行救助：街道上的点P如果由A点去救助比由B点去救助的路程更近，就将P划进A的责任区VA，反之就划进VB，为叙述方便，我们将每个长方形街区的四条边中的每一条称为一条“街道”，街道的一段称为“街段”。每条街道中属于VA的点与属于VB的点各组成一个街段，分别称为A的或B的“责任段”。一条街道最多被分成两个责任段（也有可能整条街道属于同一个责任区，因而本身就是一个责任段），责任地段只有有限多条，对每个应急设施，我们分别算出它的每个责任段的总响应时间，将这些总响应时间求和就得到这个设施的责任区的总响应时间。将两个责任区各自的总响应时间相加就得到这一选址方案的总响应时间。
下面需要知道：任一设施A到它的一个责任段EF的总响应时间怎样计算。按假定（II），街区出现事故的频率平均分布在它周围的四条街道上，每条街段的事故发生频率与它的长度成正比。将应急车辆每秒钟行驶的路程作为长度单位，则当街区事故频率为
p、街段的长度为t时，这一街段的事故频率为p?t/70,70是街区的周长，即车辆绕街
区行驶一周需70秒。在大多数情况下，一条街段同时与两个街区相邻，两个街区的事故它都有份，它的事故频率应为(p?q)?t/70,p、q分别是两个街区的事故的总频率（即原题图上标出的数）。当然可以用积分的方法。即插入分点将责任段EF分成许多微小街段?i，对每一小段?i按其长度计算出它的事故发生频率pi?kdsi，其中dsi是?i的长度，
k是与i无关（但与EF的选取有关）的常数。取应急车辆人A到?i中任意一点的行驶时
间Ti作为A到?i的时间，则微小街段?i的响应时间近似地等于Tidsi。对这些微小的响应时间求和即得到EF的总响应时间的近似值。让每个dsi?0，求和变成求积分即可。但在这里，问题比较简单，可以不用积分。事实上，由于EF的每一小段的事故发生频