给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线.以各城镇为图G的顶点，两城镇间的直通铁路为图G相应两顶点间的边，得图G.对G的每一边e，赋以一个实数w（e）为直通铁路的长度，称为e的权，得到赋权图G.G的子图的权是指子图的各边的权和.问题就是求赋权图G中指定的两个顶点u0，v0间的具最小权的轨.这条轨叫做u0，v0间的最短路，它的权叫做u0，v0间的距离，亦记作u0，v0.
求最短路已有成熟的算法：迪克斯特拉（Dijkstra）算法，其基本思想是按距u0从近到远为顺序，依次求得u0到G的各顶点的最短路和距离，直至v0（或直至G的所有顶点），算法结束.为避免重复并保留每一步的计算信息，采用了标号算法.下面是该算法.
（1）令l（u0）=0，对v≠u0，令l（v）=∞，S0={u0}，i=0.
（2）对每个v∈i（i=V-Si），用min u∈Si{l（v），l（u）+w（uv）}代替l（v）.计算min v∈i{l（v）}，把达到这个最小值的一个顶点记为ui+1，令Si+1=Si∪{ui+1}.
（3）若i=|V|-1，停止；若i＜|V|-1，用i+1代替i，转（ii）.
例9-1 城市购票问题
某公司在六个城市c1，c2，…，c6中有分公司，从ci到cj的直接航程票价记在下述矩阵的（i，j）位置上（∞表示无直接航路）.请帮助该公司设计一张城市c1到其他城市间的票价最便宜的路线图.
【解题思路】
用矩阵an×n（n为顶点个数）存放各边权的邻接矩阵，行向量pb，index1，index2，d分别用来存放P标号信息、标号顶点顺序、标号顶点索引、最短通路的值.
其中，分量
；index2（i）存放始点到第i点最短通路中第i顶点前一顶点的序号；d（i）存放由始点到第i点最短通路的值.
求第一个城市到其他城市的最短路径的Matlab程序如下：
clear；
clc；
M=10000；
a（1，：）=［0，50，M，40，25，10］；
a（2，：）=［zeros（1，2），15，20，M，25］；
a（3，：）=［zeros（1，3），10，20，M］；
a（4，：）=［zeros（1，4），10，25］；
a（5，：）=［zeros（1，5），55］；
a（6，：）=zeros（1，6）；
a=a+a′；
pb（1∶length（a））=0；pb（1）=1；index1=1；index2=ones（1，length（a））；
d（1∶length（a））=M；d（1）=0；temp=1；
while sum（pb）＜length（a）
tb=find（pb==0）；
d（tb）=min（d（tb），d（temp）+a（temp，tb））；
tmpb=find（d（tb）==min（d（tb）））；
temp=tb（tmpb（1））；
pb（temp）=1；
index1=［index1，temp］；
index=index1（find（d（index1）==d（temp）-a（temp，index1）））；
if length（index）＞=2
index=index（1）；
end
index2（temp）=index；
end
d，index1，index2.
计算赋权图中各对顶点之间最短路径，显然可以调用Dijkstra算法.具体方法是：每次以不同的顶点作为起点，用Dijkstra算法求出从该起点到其余顶点的最短路径，反复执行n次这样的操作，就可得到从每一个顶点到其他顶点的最短路径.这种算法的时间复杂度为O（n3）.第二种解决这一问题的方法是由Floyd提出的算法，称之为Floyd算法.
假设图G权的邻接矩阵为
来存放各边长度，其中：aii=0；aij=∞，i，j之间没有边，在程序中以各边都不可能达到的充分大的数代替；aij=wij，wij是边的长度.Floyd 算法的基本思想是：递推产生一个矩阵序列A0，A1，…，Ak，…，An，其中Ak（i，j）表示从顶点vi到顶点vj的路径上所经过的顶点序号不大于k的最短路径长度.
计算时用迭代公式：Ak（i，j）=min（Ak-1（i，j），Ak-1（i，k）+Ak-1（k，j））.
例9-2 乘公交，看奥运——CUMCM2007
人民翘首企盼的第29届奥运会2008年8月在北京举行，当时有大量观众到现场观看奥运比赛，其中大部分人乘坐公共交通工具（简称公交，包括公汽、地铁等）出行.这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题.针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统.
为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求.请你们解决如下问题：
1.仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法.并根据附录数据，利用你们的模型与算法，求出以下6对起始站→终点站之间的最佳路线（要有清晰的评价说明）.
（1）S3359→S1828 （2）S1557→S0481 （3）S0971→S0485
（4）S0008→S0073 （5）S0148→S0485 （6）S0087→S3676
2.同时考虑公汽与地铁线路，解决以上问题.
3.假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型.
【附录1】 基本参数设定：
相邻公汽站平均行驶时间（包括停站时间）：3 min
相邻地铁站平均行驶时间（包括停站时间）：2.5 min
公汽换乘公汽平均耗时：5 min（其中步行时间2 min）
地铁换乘地铁平均耗时：4 min（其中步行时间2 min）
地铁换乘公汽平均耗时：7 min（其中步行时间4 min）
公汽换乘地铁平均耗时：6 min（其中步行时间4 min）
公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：0～20站：1元；21～40站：2元；40站以上：3元.
地铁票价：3元（无论地铁线路间是否换乘）.
注：以上参数均为简化问题而作的假设，未必与实际数据完全吻合.
【附录2】 公交线路及相关信息（见数据文件B2007data.rar）.
附件可以通过官方网站下载http：//mcm.edu.cn.
【解题思路】
考虑到问题的假设与要求，以最短的行车时间和最低的乘车费用作为最佳的路线和方案.题目第1问要求根据附录数据，仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法，并求出6对起始站至终点站之间的最佳路线.实质上就是求两站之间最佳路线.由于题给数量较多，逐条路线去求最佳路线的问题是不可能的，所以决定用Dijkstra算法求出最佳的路线.题目第2问要求在第1问的基础上同时考虑公汽与地铁线路的问题，并求出第1问所要解决的问题，实际上是将地铁看成一辆新增加的公交车，并同时考虑新增加的公交车站的问题.题目第3个问要求在假设知道所有站点之间步行时间的情况下，给出任意两站点之间线路选择问题的数学模型.
为了解决这类最优路线问题，采用网络理论模型来求解.在所求的起始站到终点站最佳问题中，仅仅考虑乘公共汽车的情况，也涉及许多情况.如直接乘直达车，不经任何中转站，换乘K辆车等.
设所研究的问题共有n个公共汽车站点，并且有m辆车，为了解决问题的方便，假设有
.
当车行驶至第j站时，又作如下假设：
.在仅考虑公交路线的情况下，可以得到任意两站之间的最优乘车时间值.
即所求的最优时间为行驶时间和换乘时间之和.所求的最优时间要受到如下的7个条件约束：
以上是公交车行驶的时间和换乘时间的和.其中，
是从第i站点到第j站点m辆车所经过的总站点数，
是转车次数.
表示出发站应满足的条件，即乘客必须乘某一车次前往某一站.
表示目的站应满足的条件，即乘客必须乘某一车次经某一站到达目的站.
表示在第j站作为中间站点时，若有车次经过则式子左边的值为0，若此站作为终点站则式子左边的值为1，即有进无出去的情况.
，j=1，2，…，n-1表示第i站作为中间站点时，若有车次经过则式子左边的值为0，若此站作为起点站则式子左边的值为1，即车辆有出无进的情况.
，j=2，3，4，…，n-1表示车辆与某站点的关系，若某车辆既不进也不出某站点，此式子左右两边都为0，若车辆既从此站点进去同时也从此站点出来，则此式子左右两边都为1.
分为以下几种情况：假如车辆没有经过某站点，此时
的值为0，同时
的值也为0，中间的式子为0；假如车辆经过了某站点且没有转车，此时
的值为1，同时
的值也为1，中间的式子为0；假如车辆经过了某站点且有转车的情况，对于转车前的车，此时
的值为1，同时
的值也为0，中间式子为1；对于转车后的车有
的值为0，同时
的值也为1，中间式子为-1.
上述目标函数是基于时间最短而得出的最佳路线，所以此项指标作为评价一条路径的最重要的指标.但是同时人们也会考虑到乘车的花费，所以在选择公交车时会对路径和花费进行综合考虑，既要求到达目的地的时间最短且花费最小.下面针对这种情况给出了模型及其方案，并相应得出最短时间和最少花费.
第二个目标函数是求最小花费，其中
表示某一辆车从第i站点到第j站点中间所经过的站点数，P（l）表示票价函数，其函数式子为：
问题2中要求考虑乘客可以乘坐地铁交通工具，因此我们依据问题一中的模型，考虑如下因素：
乘客选择的交通工具为公交或地铁，此时相应地有变量：
乘客可由公交车转乘地铁，此时相应地有变量及约束条件：
乘客可由地铁转乘公交车，此时相应地有变量及约束条件：
乘客可由地铁转乘地铁，此时相应地有变量：
乘客在公交站可不换公交车，或可转乘公交车，或可转乘地铁，但三种选择不可同时进行，因此相应的有约束条件，
乘客在D12及D18地铁站可不换地铁线，或可换乘公交车，或可换乘地铁线，但三种选择不可同时进行，因此相应的有约束条件：
综合以上因素，建立如下的双目标规划模型：
问题3中要求考虑乘客可以采用步行方式，因此依据问题2中的模型，考虑如下因素：
乘客选择的交通工具为公交或地铁或步行，此时相应地有变量：
乘客可由公交车转为步行方式；乘客可由地铁转为步行方式；乘客在公交站可不换公交车，或可转乘公交车，或可转乘地铁，或转为步行方式，但四种选择不可同时进行；乘客在D12及D18地铁站可不换地铁线，或可换乘公交车，或可换乘地铁线，或改为步行方式，但四种选择不可同时进行.
综合以上因素，建立如下的双目标规划模型：
决定用Dijkstra算法来解决这类最短路问题，通过Lingo软件实现.经过编程得到问题一的解决方案，下面是在仅至考虑公共汽车之间的换乘问题，给替乘车者提供最优路线的方案，如表9-1至表9-6所示.
表9-1 仅考虑公汽线路时的S3359→S1828最佳路线
表9-2 仅考虑公汽线路时的S1577→S0481最佳路线
表9-3 仅考虑公汽线路时S0971→S0485的最佳路线
表9-4 仅考虑公汽线路时S0008→S0073的最佳路线
表9-5 仅考虑公汽线路时S0148→S0485的最佳路线
表9-6 仅考虑公汽线路时S0087→S3676
以上6个公交车路线是根据网络模型所得出的结论，在起始站到终点站之间有很多不同的乘车路线，但可以看出所求的6条路线都是要经历一个或两个中转站才能到达终点站，与其他的路线相比，它们耗费的时间短，且路费也低，所以该模型很好地解决了最短行程的问题.
在第1问的基础上，又需要重新考虑公共汽车和地铁的换乘问题，以及地铁和地铁的换乘问题，在利用软件进行的编程过程中，又得到以下的结论，如表9-7至表9-12所示.
表9-7 同时考虑公汽与地铁线路时S3359→S1828的最佳路线
表9-8 同时考虑公汽与地铁线路时 S1577→S0481的最优路线
表9-9 同时考虑公汽与地铁线路时S0971→S0485 的最优路线
表9-10 同时考虑公汽与地铁线路时 S0008→S0073的最优路线
表9-11 同时考虑公汽与地铁线路时S0148→S0485的最优路线
表9-12 同时考虑公汽与地铁线路时S0087→S3676的最优路线
从以上的6条线路问题，可以得出前三个公交车路线都只有涉及公交车之间的换乘，而不涉及地铁与公交车之间以及地铁与地铁之间的换乘，费用相对较低.当涉及地铁与公交车换乘时，所经历的中转站较多，超过两个，且费用相对其他较高一些，但中间站都是地铁站时，所用的时间短，路线也短.
例9-3 交巡警服务平台的设置与调度——CUMCM2011
“有困难找警察”，是家喻户晓的一句流行语.警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能.为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台.每个交巡警服务平台的职能和警力配备基本相同.由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题.试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：
附件1中的附图给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图，相关的数据信息见附件2.请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60 km/h）到达事发地.对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁.实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案.根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置.
针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性.如果有明显不合理，请给出解决方案.
如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑.为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案.
【附件1】 附图
图9-2 城市、区警力配置、路口设置示意图
注：图中实线表示市区道路；灰色线表示连接两个区之间的道路；实圆点“•”表示交叉路口的节点，没有实圆点的交叉线为道路立体相交；星号“*”表示出入城区的路口节点；圆圈“○”表示现有交巡警服务平台的设置点；圆圈加星号“○*”表示在出入城区的路口处设置了交巡警服务平台.
【附件2】 全市六区交通网路和平台设置的数据表.
可以通过官方网站下载http：//mcm.edu.cn.
【解题思路】
问题1是以城区A为研究对象，主要是处理城区A在出现突发事件时，交巡警服务平台警力资源的调度问题，共3小问：考虑如何划分各交巡警服务平台管辖范围，可以根据就近原则，将每个路口节点归类到与其距离最近的平台，确保平台接警后能快速到达现场，解决突发事件.另外，平台的警力要尽量能在3分钟内到达事发地.我们首先以每个交巡警服务平台为圆心，3分钟能行进的路程为半径画圆，去覆盖路口节点，结果发现有6个路口节点未被覆盖.平台和交通要道路口的位置是确定的，为了能在出现突发事件时实现快速封锁13条交通要道，采用二分图匹配，确保每个出入城区的路口都有一个平台的警力.各个平台的工作量不均衡和有些地方出警时间过长的状况，是因为各个平台管辖范围内发案率大小不一，因此可以调整各个平台的管辖范围大小，使各个管辖范围内的发案率大致均衡.
问题2是以全市为研究对象，考虑6个城区，共2个小问：平台的工作量不均衡主要体现在其管辖范围内的发案率，而有些地方出警时间过长是因为3 min之内平台无法到达某些路口节点.依据就近原则确定各个平台的管辖范围，然后分析该市现有交巡警服务平台的设置方案的合理性.当犯罪分子逃离时，平台在3分钟之后接到报警.由于交巡警受到时间和时速的限制，只能动态地确定犯罪分子的逃离范围，同时根据路况，不断动态地围堵犯罪分子，确定围堵方案.
中心城区A的92个路口节点分别标记为Ai，i=1，…，92.其中A1～A20是20个交通服务平台，其余72个是一般的路口节点.建立路口节点Ai之间的邻接距离矩阵DA=（d0ij）92×92，继而运用Floyd算法计算出任意两点之间的最短距离矩阵D=（dij）92×92.
题目要求是给20个交通服务平台分配管辖范围，因而只需取最短距离矩阵D中的一部分，即只需要72个一般路口节点到20个交通服务平台之间的距离D0.
对于交巡警服务平台管辖范围的分配，我们是从路口节点，路口节点之间的道路这两方面来考虑，我们运用就近原则的思想建立数学模型：
对于路口节点的分配：G1i={Aj|dji≤djk，j=21～92，k≠i}，i=1～20；其中Gi为Ai所管辖的路口节点集.
对于道路的划分，也就是对相邻两路口节点之间的道路进行划分.之所以这样分，是因为假如突发事件发生在道路上，而非路口时，可以优先考虑最近的交巡警服务平台，从而可以快速处理问题：G2i={满足性质φ的边集}.性质φ如下：
其中Xjk是边AjAk上的一个分割点，使其到交通服务平台Ai和Ap的最短距离相等，即
；因此平台Ai的管辖范围Gi=G1i∪G2i.
通过VC编程实现如何分配每个交巡警服务平台的管辖范围，再对其管辖范围内的发案率进行了统计，并记录到表9-13中.
表9-13 20个交巡警服务平台标号
通过对表9-13中数据的分析，发现：5、6、7号节点为相邻的3个交巡警服务平台，并且6号节点发案率比较低，而5和7号节点发案率相对来说比较高；1、19号节点为相邻的2个交巡警服务平台，并且19号节点发案率低，而1号节点发案率相对来说比较高.
因而决定，在6、19号交巡警服务平台的警力能在3分钟之内到达案发地的前提下：适当扩大6号交巡警服务平台的管辖范围，这样就能分别减轻5、7号交巡警服务平台的工作量；类似地，同样适当扩大19号交巡警服务平台，减轻1号交巡警服务平台的工作量.
进而做到每个交巡警服务平台工作量的相对平衡.可以把47、58、59号路口节点分配给6号交巡警服务平台管辖，把76号路口节点分配给19号交巡警服务平台.再通过Matlab编程实现，得到每个交巡警服务平台管辖的发案率、路口节点及其管辖的道路段.表9-14为优化后的20个交巡警服务平台标号.
表9-14 优化后的20个交巡警服务平台标号
显然，相对于表9-13来说，表9-14每个平台的发案率相对均衡，因而发案率的方差较小.表9-15给出了优化后每个交巡警服务平台所管辖的路口节点.
表9-15 优化后每个交巡警服务平台管辖的路口节点
由于道路段管辖的划分难以直观地叙述，因而通过图形的形式进行描述，其中道路直线与短斜杠的交叉点即为分割点所在之处.为了比较清晰地描绘管辖范围，图9-3只给出城区A右下角部分.
图9-3 优化后每个交巡警服务平台管辖范围分布
图中，11、26、27处的节点都用正方形表示，且归为一类；12、25处的节点都用“*”表示，且归为一类；13、21、22、23、24处的节点都用左三角形表示，且归为一类.
clc
clear
C=zeros（92，92）；
E=［ ］；%输入街道的两端路口标号
for i=1∶143；
if E（i，1）＜=92 ＆＆ E（i，2）＜=92；
C（E（i，1），E（i，2））=1；
end
end
for i=1∶92
C（i，i）=1；
end
D=ones（92，92）*inf；
for i=1∶92；
D（i，i）=0；
end
X=［ ］；%输入网络中路口的坐标
for i=1∶92；
for j=1∶92；
if C（i，j）==1；
D（i，j）=sqrt（（X（i，1）-X（j，1））^2+（X（i，2）-X（j，2））^2）；
end
end
end
for i=1∶92；
for j=1∶92；
if D（i，j）==inf；
D（i，j）=D（j，i）；
end
end
end
for l=1∶90；
for i=1∶92；
for j=1∶92
for k=1∶92
if D（i，k）+D（k，j）＜=D（i，j）
D（i，j）=D（i，k）+D（k，j）；
end
end
end
end
end
Z=［ ］；%交巡警平台的网络坐标
M=zeros（20，92）；
for i=1∶20；
k=1；
for j=1∶92；
if D（i，j）/10＜=3；
M（i，k）=j；
k=k+1；
end
end
end
for i=1∶19
for j=1∶92；
if M（i，j）～=0 ＆＆ M（i，j）～=i；
for k=i+1∶20；
l=1；
while（M（i，j）～=0 ＆＆ l＜=92）
if M（i，j）==M（k，l）＆＆ length（find（M（i，：）～=0））＞=length（find（M（k，：）～=0））
M（i，j）=0；
end
l=l+1；
end
end
end
end
end
for i=1∶20；
for j=1∶92；
if M（i，j）＜i
M（i，j）=0；
end
end
end
for i=1∶20；
M（i，：）=sort（M（i，：））；
end
for i=1∶20
L=M（i，：）；
M（i，：）=L（end：-1∶1）；
end.
假定一个平台的警力只能封锁住一个路口，并且一个路口只需一个平台的警力.对于重大突发事件，调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封.这可以理解为20个交巡警服务平台的警力要以最快的速度到达出入城区A的路口（即附件中提到的A12，A14，A16，A21，A22，A23，A24，A28，A29，A30，A38，A48，A62），即每个出入城区A的路口都需一个交巡警服务平台来封锁，因而这是一个匹配问题，建立如下模型：
在赋权二分图N=（V1，V2，E，W）中V1={R1，…，R13}，V2={A1，…，A20}，E是边集，W是E中所有边的权值矩阵.我们的目标是在最短的时间内使得每个出入城区的路口都能由一个互不相同的交巡警服务平台的警力来封锁.也就是V1中每个点都能与V2中互不相同的点进行相连，并且使得一个可行的匹配边集M在这一条件下中选择边的距离的最大值最小.
分别定义权值矩阵W和邻接矩阵I如下：
其中
是节点Ri与节点Aj之间的最短距离.
目标函数：min =T.
其中v=60 km/h=1 km/min .
距离可以通过公式t=s/v折算到时间，通过Lingo 编程实现，得出具体的信息如表9-16所示.
表9-17 指定交巡警服务平台需封锁的要道、警力行警路线及行警时间
通过上表的分析，可知最快全封锁时间T=8.0155 min.因此调度13个平台的警力对13条交通要道进行全封锁最快只需8.0155 min.
sets：
jc/1..20/：a；
lk/1..13/：b；
fa（jc，lk）：p，t；
endsets
data：
p=；！20个交巡警平台到13个路口的最短距离
enddata
min=@max（fa∶p*t）；
@for（jc（i）：@sum（lk（j）：t（i，j））＜=1）；
@for（lk（j）：@sum（jc（i）：t（i，j））=1）；
@for（fa：@bin（t））.
对上述匹配问题进行进一步的讨论，发现二分图最大匹配未必唯一，而匈牙利算法求解只是所有完备匹配中的任意一种，还不具有最优性.根据对问题的进一步分析，在满足最快全封锁时间为T的要求下，使得所有交巡警服务平台封锁住其对应的路口的总距离和最小，我们根据Kuhn-Munkras算法建立如下二分图最小权匹配模型.
在赋权网络N=（V1，V2，E，W）中求权值总和最小的匹配，其中
其中dij是Ri与Aj之间的最短距离，v=60 km/h=1 km/min，T=8.0155 min 是通过上述二分图最佳匹配模型得到的最快全封锁时间.建立整数线性规划模型如下：
通过给每个顶点一个标号（叫做顶标）来把求最小权匹配的问题转化为求完备匹配的问题.设顶点i的顶标为Xi，顶点j的顶标为Yj，顶点Xi与Yj之间的边权为wij.在算法执行过程中的任一时刻，对于任一条边（i，j），Xi+Yj≥wij始终成立.
模型求解步骤如下：对于每一个顶标初始化一个可行值；用匈牙利算法寻找完备匹配；若未找到完备匹配则修改可行顶标的值；重复上面两个步骤直到找到相等子图的完备匹配.
通过VC编程实现，可以确定如何调度每个交巡警服务平台去封锁相应的出入城区路口，具体结果如表9-17所示.
表9-17 指定交巡警服务平台需封锁的要道、警力行警路线及路程长度
为了更加形象化地表示交巡警服务平台如何对相应的出入城区路口进行封锁，通过图形来对平台行警路线的进行描述，详见图9-4.
图9-4 每个交巡警服务平台的警力行警路线图
现有交巡警服务平台的工作量不均衡主要体现在其管辖范围内发案率的高低，而有些地方出警时间过长是因为3分钟之内交巡警服务平台无法到达的路口节点.为使每个交巡警服务平台的工作量和出警时间的差异性达到最小，可以考虑每个平台管辖范围内的发案率，计算发案率的方差，要使其方差达到最小.因而建立如下模型：
其中N表示交巡警服务平台总数；表示N交巡警服务平台管辖范围内的平均发案率；ai表示第i个交巡警服务平台管辖范围内的发案率，
表示节点Aj的发案率，dji表示节点j到平台i之间的最短距离.
在每增加n（n=N-20）个交巡警服务平台后，通过枚举法的思想，讨论n个平台所有可能放置的情况.取出任意一种情况，首先就近原则的方法先对这N个平台进行管辖范围的划分，再统计出N个平台管辖范围内的发案率，计算发案率的方差，并算出N个平台分别到其管辖范围内最长距离处所需的时间，所有这些时间的最大值记作TNmax.
设置一个时间指标TN0，对上述所有可能的情况进行筛选，即：若TN0＞TNmax，则保留所有情况，找出其中发案率方差最小的方案；若TN0≤TNmax，则删除那些平台到其管辖范围内最长距离处所需时间大于TN0的方案，再找出其中发案率方差最小的方案；
通过VC 编程进行计算机模拟，在不同的时间指标TN0下，增加不同的平台个数，找出了相应的发案率方差最小的那些方案，并给出了新增加的平台所放的具体位置，绘制成表9-18.
表9-18 不同时间指标、不同平台个数下的最优方案
注：其中Ⅰ列表示增加的平台个数；Ⅱ列表示所有平台到其管辖范围内最长距离处所需时间的最大值，单位：min；Ⅲ列表示所有平台发案率的方差；Ⅳ列表示新增加的平台所应放置的位置.
从以上模型和表9-19中可以看出增加2～5个交巡警服务平台都有较多个方案.
表9-19 具体的方案设置情况
从上表中可以发现，当时间限定相同时，增设点数不同最佳方案也会有所调整；当增设点数相同、时间不同时，最佳方案也会有所调整.具体方案根据当地政府增设交巡警服务平台的预算.
考虑到A、B、C、D、E、F各区的面积和人口数，作如下分析：已知人口密度ρi=Pi/Si，Pi表示区域i的总人数，Si表示区域i的面积，i取A、B、C、D、E、F，可以求得各区相关信息如表9-20所示.
表9-20 各区相关信息
C区的犯罪率和交巡警处理的案件量都很大，特别是交巡警处理案件量远远大于其他区域，所以可以在微调方案的基础上在该区适当添加交巡警服务平台；在A，B，F的局部区域的犯罪率比较高，所以可以适当增强交巡警的监管力度.
首先交巡警服务平台应该遵循以下三点的原则：警情主导警务原则，根据管区道路交通流量、拥堵状况、治安复杂情况、发案量高低，科学确定平台管辖区域；快速出警原则，城区接警后确保快速到达现场；方便与安全原则，按照醒目、规范，方便群众和确保安全的原则，科学设置平台.
平台设置在遵循上述三大原则的基础上，应当结合辖区地域特征、人口分布、交通状况、治安状况和未来城市发展规划等实际情况，在充分考虑现有警力和财力并确保安全的条件下，科学确定平台的数量和具体位置.
建立两个目标函数（管辖范围按就近原则划分）：使全市交巡警服务平台管辖范围内发案率的方差达到最小.
其中
表示N个交巡警服务平台管辖范围内的平均发案率；ai表示第i个交巡警服务平台管辖范围内的发案率，
表示节点Aj的发案率，dji表示节点j到平台i之间的最短距离.
每个交巡警服务平台都有到其管辖范围内最远的距离，目标是使所有交巡警服务平台的这些最远距离的平均值达到最小.设交巡警服务平台Mi到其管辖范围内最远距离长度为Si.
对于其现有交巡警服务平台的设置，其发案率的方差为Var0，所有最远距离的平均值为Aver _S0.
先给出可挪动的定义：80个交巡警服务平台至少有一个可以移动，则平台可挪动.根据枚举的思想，我们先对80个平台进行是否可挪动的判断.若不可挪动，则终止，得到结果；否则，继续取出任意一个交巡警服务平台，将其微调，即把该平台移到其相邻的路口节点，从而得到全市交巡警服务平台一个新的设置，再计算其发案率的方差Vart和所有最远距离的平均值Aver _St.通过与最初的Var0和Aver _S0进行比较，判断该点的移动是否有效.以下两种情况时，该点的移动有效，Aver _S0的值改为Vart，Aver _S0的值改为Aver _St；其余则无效，Var0，Aver _S0值不变.
不断微调，直至Var0和Aver_S0值不再减小.具体的流程如图9-5所示.
图9-5 优化调度方案的流程
通过VC编程实现，求得最初发案率的方差为Var0=20.3481，所有最远距离的平均值为Aver_S0=3.7690；微调后结果如表9-21所示.
表9-21 微调后平台调度情况
根据表中所示微调后，得到全市发案率的方差为Vart=12.4054，所有最远距离的平均值为Aver_St=3.2092.方差减少了7.9427，平均最远距离减少0.5598，整个城市的平均发案率和最长出警时间都更加平衡了.
该市地点P（第32个节点）处发生重大刑事案件，案发3分钟后接到报警，需要调度全市交巡警服务平台警力资源对嫌疑犯进行围堵.我们认为对嫌疑犯进行围堵的包围圈越小即为最佳方案，这样不但需要调度的警力资源比较小，而且还能以最快速度包围嫌疑犯.
作出如下定义：设集合Z为被围堵的节点，初试状态Z={P}；设集合O是Z中的边界节点集合；dist（Mi，Mj）表示路口节点Mi到Mj之间的最短距离；v表示警车速度，u表示嫌疑犯逃跑速度；判断一个路口节点Qi能被围堵的指标是：
若O中节点oi不能被围堵，则需要将与节点oi直接相连的节点放入集合Z中；建立集合O的节点与全市80个平台之间的邻接矩阵I：
根据以上分析建立如下数学模型：
目标函数：min ={Z中节点个数}.
首先对集合Z中每个节点进行判断，根据我们定义中的围堵指标，判断是否所有的节点都能被围堵：若能被围堵，则重新建立集合Z的节点与全市80个平台之间的邻接矩阵I，再调用问题一中的匈牙利算法来进行匹配，集合Z中的每个节点都必须有一个平台来进行围堵.再对匹配进行判断，判断其是否为完备匹配.若是完备匹配，则说明只需调度平台去围堵集合Z的路口节点，就能围堵成功，这是一个可行的方案；否则对未被匹配的节点中的一个进行扩展，也就是更新了集合Z，再重新对集合Z进行判断；若不能被围堵，则扩展集合Z中不能被围堵的节点，再重新对集合Z进行判断.具体流程如图9-6所示.
图9-6 最小包围圈模型的算法流程图
由于问题中并未给出嫌疑犯的逃窜速度，所以在编程过程中我们假定警车速度v与嫌疑犯逃窜速度u都等于60 km/h.继而通过VC 编程实现，得到围堵边界路口节点集合Z={3，4，5，6，10，16，40，41，55，60，168，232，240，244，246，248，370，561}，即围堵边界节点个数是18，而且在这些边界节点所围成的包围圈内（包括边界上）有49个路口节点，最快形成围堵的时间是12.65741 min，如表9-22所示.
表9-22 指定交巡警服务平台需围堵的路口、行警路径及封锁时间
为了更加直观体现出包围圈，给出图9-7示意.
图9-7 包围圈示意图
由于警车的速度和犯罪嫌疑人逃跑速度是不确定的，当警车速度有所变化或者嫌疑人逃跑速度有所变化或者两者都变化时，现有的围堵方案都会有相应的变化，围堵时间和围堵成功时所围堵的路口点数都会改变，所以我们给出了速度区间，为了更直观的讨论，设u，v 的速度分别设置为30～120 km/h，绘制表9-23.
表9-23 警车和罪犯在不同速度下的包围路口节点数
当仅警车的速度固定时，围堵成功时围堵节点的个数随着犯罪嫌疑人逃离速度的增加而增加，反之亦然；当仅犯罪嫌疑人逃离速度固定时，围堵成功时围堵节点的个数随着警车速度的增加而增加，反之亦然；当警车速度和犯罪嫌疑人的速度有变化时，要看各自速度的增量，如果犯罪嫌疑人速度的增量大，则成功围堵时围堵节点数会增加，反之亦然.
据此利用Matlab做出三维分析图来进一步验证以上结论，如图9-8所示.
图9-8 灵敏度分析图
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
