数学建模：交巡警平台的设置与调度

交巡警服务平台的设置与调度一、问题重述“有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：（1）附件1中的附图1给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图，相关的数据信息见附件2。请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。（2）针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。如果有明显不合理，请给出解决方案。如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。二、问题分析2.1问题一（1）问要求为A区的20个交巡警服务平台划分管辖范围，使每个路口尽量在3分钟内能够由交巡警赶到。根据实际情况，每个交巡警服务平台的资源是基本均衡且有限的。我们规定𝑥𝑖𝑗={1,路口i被平台j管辖0，路口i不被平台j管辖，则此问题可看作是一个多目标0—1规划问题。目标函数为：一：尽量多的路口能由交巡警在3分钟内赶到；二：若某路口不能由交巡警在3分钟内到达，则交巡警到达此路口的时间应尽量短；三：各交巡警平台的工作量尽量均衡。求解此模型时，首先用matlab对数据进行初步整理，然后将目标一、二作为约束条件把多目标规划转化为单目标0—1规划问题，利用lingo软件求解。（2）问中要求对进出A区的交通要道实现快速全封锁。可以将时间最小化问题转化为距离最短问题。建立以平台到封锁的交通要道中的最长距离最短为目标函数，以一个平台的警力最多封锁一条要道、每条要道必须被一个平台封锁为约束条件的规划模型。将此模型用lingo软件解出后，有多种调度方案，我们可以继续建立以封锁交通要道的总距离最短为目标函数，以解出的最长距离的最小值为约束条件的规划模型进行进一步优化，用lingo解出最终的封锁调度方案。（3）问要求增加平台，解决平台工作量不均衡和某些地方出警时间过长的问题。在（1）问中得到28,29,38,39,61,92这6个路口不能由交巡警在3分钟内到达。只要在离这6个路口距离不大于3km的路口处增加平台，就可以使得所有路口都能由交巡警在3分钟内到达，可以认为解决了出警时间过长的问题，并且可以求解出应增加的最少平台数。进而解决工作量不均衡的问题，可建立0—1变量𝑓𝑗={1,在路口j处增加平台0,不在路口j处增加平台，将平台工作量均衡度最大为目标函数，将解出的增加平台的可行数量作为约束条件建立规划模型，用lingo可求解出增加平台的具体位置。最后综合分析出应增加的平台数量和具体位置。三、基本假设与符号说明3.1基本假设1.假设每个巡警服务台的职能和警力配备基本相同；2.假设每个路口只由一个巡警服务平台进行管辖；3.假设每个巡警服务平台至少管辖一个路口；4.假设巡警都按最短路径到达各案发路口；5.假设每个路段道路畅通，可以双向行驶，没有堵车现象；6.假设犯罪案件都在路口上发生；7.假设在重大案件发生时，每个平台只有封锁一个路口的能力；8.工作量：每个巡警服务台所管辖范围内的所有路口案发率之和；9.出警时间：巡警到达案发路口所需时间；10.每个区的交巡警平台只可管辖本区内的路口，不可跨区管辖。11.假设巡警车和犯罪嫌疑人的车行驶中速度保持匀速且车速均为60km/h；12.假设巡警在接到报案后并不知道逃犯的逃跑方向；3.2符号说明1.𝑥𝑖𝑗={1,路口i被平台j管辖0，路口i不被平台j管辖；2.𝑑𝑖𝑗：路口i到j的最短距离；3.𝑈0：交巡警能够在3分钟内到达的路口集合；4.𝑉𝑖：能够在3分钟内到达路口i的交巡警平台的集合；5.𝑈1：交巡警不可在3分钟内到达的路口集合；6.𝑟𝑖：第i个路口的发案率；7.𝑟：交巡警服务平台的平均工作量；8.𝑟𝑟𝑗：平台j的工作量；9.𝑦𝑖𝑗={1,第i条交通要道由交巡警服务平台j封锁0，第i条交通要道不由交巡警服务平台j封锁；10.𝑠𝑖𝑗：第i条交通要道到平台j的最短距离；11.𝑓𝑗={1,在路口j处增加平台0,不在路口j处增加平台；12.n：增加的交巡警服务平台的个数；四、模型的建立与求解4.1问题一（1）：管辖区域的确定4.1.1模型建立此问要求在A区20个交巡警服务平台位置确定的情况下，分配管辖范围，使交巡警尽量能够在3分钟内到达事发地。本文考虑了三个分配原则即为三个目标。一：交巡警尽量能在3分钟内到达事发地。二：在不能满足3分钟内到达事发地的情况下，交巡警到达事发地的时间应尽量短。三：由于各交巡警平台的职能和警力配备基本相同，因此各交巡警平台的工作量应尽量均衡。由以上分析可知，此问为一个多目标规划问题。对于第一个目标，可以转化为交巡警能在3分钟内到达管辖路口的路口数应尽量多。建立0—1变量：𝑥𝑖𝑗={1,路口i被平台j管辖0，路口i不被平台j管辖。假设𝑑𝑖𝑗为路口i到交巡警平台j的最短距离。𝑈0为交巡警可在3分钟内到达的路口集合，即若∃j∈{1,2…20},使得𝑑𝑖𝑗≤3𝑘𝑚，则i∈𝑈0。𝑉𝑖为能够在3分钟内到达路口i的交巡警平台的集合。此目标可表示为：max𝑓1=∑∑𝑥𝑖𝑗𝑗∈𝑉𝑖𝑖𝜖𝑈0；对于第二个目标，假设𝑈1为交巡警不可再3分钟内到达的路口集合，此目标可表示为：min𝑓2=∑𝑥𝑖𝑗∗𝑑𝑖𝑗,𝑖∈𝑈120𝑗=1;对于第三个目标，本文用每个平台所管辖路口发案率的和表示平台的工作量，用工作量的变异系数来度量各平台工作量的均衡度，各平台工作量越均衡，变异系数越小。假设𝑟𝑖为第i个路口的发案率，𝑟为所有平台的平均工作量，𝑟𝑟𝑗为第j个平台的工作量，此目标可表示为：min𝑓3=√119∑(𝑟𝑟𝑗−𝑟)220𝑗=1𝑟⁄;𝑟=∑𝑟𝑖92𝑖=120;⁄满足条件为：1.每个路口由一个交巡警服务平台管辖：∑𝑥𝑖𝑗=1,𝑖=1,2…92;20𝑗=12.每个交巡警服务平台至少管辖一个路口：∑𝑥𝑖𝑗≥1,𝑗=1,2…20;92𝑖=13.每个交巡警服务平台必须管辖本路口：𝑥𝑖𝑗=1,𝑖=𝑗;𝑖,𝑗=1…20;4.1.2模型求解对于模型中的多目标规划问题，本文将之转化为单目标规划问题。首先将目标一和目标二解出，然后将这两个目标作为约束条件，以目标三作为最终的单目标用lingo软件求出最终解。1.各路口间最短距离的确定。首先用22[]()()ijsqrtijijxxyyw公式算出两两之间的距离（如果有路），得出582*582的邻接矩阵，其中矩阵中的元素表示两两之间的距离，若不存在路，则用一个较大的数代替,在matlab环境下利用floyd算法求出最短路程矩阵D，矩阵D中两两之间的距离即为𝑑𝑖𝑗。程序见附录一。Floyd算法的基本步骤如下：令𝑑𝑖𝑗是顶点𝑣𝑖到顶点𝑣𝑗的最短距离,w𝑖𝑗是顶点𝑣𝑖到𝑣𝑗的权。STEP1:输入临界矩阵W。对所有i,j,有𝑑𝑖𝑗=w𝑖𝑗,k=1。STEP2:更新𝑑𝑖𝑗。对所有i,j,若𝑑𝑖𝑘+𝑑𝑘𝑗𝑑𝑖𝑗,则令𝑑𝑖𝑗=𝑑𝑖𝑘+𝑑𝑘𝑗。STEP3:若𝑑𝑖𝑖0,则存在一条含有顶点𝑣𝑗的负回路,停止;或者k=n停止,否则转到STEP2。2.目标一和目标二的求解用MATLAB编程从上述得到的各路口的最短距离中抽出92个路口分别到20个服务平台的最短距离。筛选出𝑑𝑖𝑗≤3𝑘𝑚的点，求出交巡警可在3分钟内到达的所有路口（集合𝑈0），剩下的路口则为交巡警不可能在3分钟内到达的路口（集合𝑈1）。程序见附录二。为满足目标一，只需要满足：∑𝑥𝑖𝑗∗𝑑𝑖𝑗≤3,20𝑗=1𝑖∈𝑈0;为满足目标二，将集合𝑈1={28,29,38,39,61,92}中的路口直接分配给距离此路口最近的交巡警服务平台。结果如下：交巡警平台15162720管辖路口28、29383961923.最终方案的确定将目标一、二作为约束条件，目标三作为最终单目标，可得如下最终模型：min𝑓3=√119∑(𝑟𝑟𝑗−𝑟)220𝑗=1𝑟̅⁄𝑠.𝑡.{𝑟̅=∑𝑟𝑖92𝑖=120;⁄∑𝑥𝑖𝑗∗𝑑𝑖𝑗≤3,20𝑗=1𝑖∈𝑈0;𝑥𝑖𝑗=1,𝑖∈𝑈1,𝑗=𝑣𝑖;∑𝑥𝑖𝑗=1,𝑖=1,2…92;20𝑗=1∑𝑥𝑖𝑗≥1,𝑗=1,2…20;92𝑖=1𝑥𝑖𝑗=1,𝑖=𝑗;𝑖,𝑗=1…20;𝑥𝑖𝑗∈{0,1}其中𝑣𝑖表示交巡警不能在3分钟内赶到的路口i被平台𝑣𝑖管辖。用lingo求解得最小变异系数为1.934，,最终分配方案如下（程序见附录三）：交巡警服务平台管辖路口工作量（次）11、67、69、76、77、79、807.122、40、43、73、757.233、44、54、55、66、686.944、57、60、62、63、64、657.355、49、53、56、596.166、50、51、52、586.177、30、485.988、34、37、475.899、32、33、456.41010、29、394.41111、26、274.61212、254.01313、21、22、23、248.51414、38、614.31515、28、315.01616、35、36、466.31717、41、42、70、727.01818、74、84、85、87、887.21919、71、78、81、82、837.12020、86、89、90、91、927.34.2问题一（2）：封锁方案的确定4.2.1模型建立本问要求调度20个交巡警服务平台对A区的13条交通要道实现快速封锁，且每个平台最多封锁一个路口。实现完全封锁的时间取决于13条交通要道中被封锁最长的时间。本文将时间问题转化为距离问题。对13条要道实现最快封锁，即是将平台到13条被封锁要道中的最长距离最小化。可建立0—1规划模型。建立0—1变量：𝑦𝑖𝑗={1,第i条交通要道由第j个交巡警服务平台封锁0，第i条交通要道不由第j个交巡警服务平台封锁。假设𝑠𝑖𝑗为第i条交通要道到第j个平台的距离。其中i=1,2…13;j=1,2…20。目标函数：平台到13条被封锁要道中的最长距离最小：min𝑠=max(𝑦𝑖𝑗∗𝑠𝑖𝑗)𝑖=1,2…13;𝑗=1,2…20约束条件为：1.每条交通要道必须有一个交巡警服务平台进行封锁。∑𝑦𝑖𝑗20𝑗=1=1,𝑖=1,2…13。2.每个交巡警平台最多封锁一条交通要道。∑𝑦𝑖𝑗13𝑖=1≤1,𝑗=1,2…20。综上所述，此优化模型为：min𝑠=max1≤𝑖≤201≤𝑗≤13(𝑦𝑖𝑗∗𝑠𝑖𝑗)s.t.{∑𝑦𝑖𝑗20𝑗=1=1,𝑖=1,2…13;∑𝑦𝑖𝑗13𝑖=1≤1,𝑗=1,2…20;𝑦𝑖𝑗∈