交巡警服务平台的设置和调度模型.doc

2013财经大学数学建模竞赛B题交巡警服务平台的设置与调度模型参赛队员: 参赛队编号：20130032013年8月7日~8月11日交巡警服务平台的设置与调度 摘要本文针对交巡警服务平台的设置与调度等相关问题进行建立模型和研究首先，运用matlab软件对节点和相应距离组成的三列矩阵进行预处理得到邻接矩阵，基于floyd算法得到任意两点间的最短距离矩阵juli然后针对问题（一）和问题（二）,依据lingo11.0对问题进行指派优化，得到合理的结论 问题（1.1） 关于A区的交巡警平台得管辖分配，依据原则一“尽量在3分钟有交巡警到达事发地”的前提下，以各交巡警平台任务量方差最小为目标函数，建立0—1规划模型，从而得出最佳分配方案 问题（1.2） 依据木桶盛水原理，封堵A区13个路口方案的好坏取决于最晚到达指定封锁路口的交巡警到达时间的长短建立以最晚到达时间最短为目标的优化模型，建立0-1规划模型借助于lingo11.0软件编程，从而得出最佳交巡警平台调度方案 问题（1.3） 对于个别节点20个中任何一个交巡警平台无论如何在三分钟之赶达事故发生地我们增设4个交巡警平台，分别在节点28、38、61、92 。

通过这四个交巡警平台的增设使交巡警尽量在3分钟之赶到事故发生地且警务平台任务量趋于平均问题（2.1）综合全市各区实际情况，我们把案发率、各区人口、各区管辖面积作为一个相关因子，考虑各区节点到交巡警服务平台是否符合设置原则，一：“尽量在三分钟之赶到案发现场”；原则二“保持警务平衡”作为评判标准，确定各区是否设置合理对于不合理区域，需要新增平台数建立的平台尽可能少，工作量尽可能的均匀，建立合理模型问题（2.2）对P点案发三分钟后进行围堵在模型建立应该遵循围最小原则，出动警员最小为原则利用对P进行围堵利用lingo11.0软件编程和matlab软件编程从而得到最佳围堵方案关键词：floyd算法 0-1规划 多目标优化，1问题重述警察肩负着重大职能，为了更好的贯彻职能，更好的为人民服务，需要在市区的重要部位建立服务平台如何在警察资源有限的情况下，根据城市实际情况和需求设置警务平台和有效的调度警务资源是警务部面临的实际问题现在就针对某市设置交巡警服务平台的相关情况，建立数学模型分析问题如下：（一）（1.1）依据附件1和附件2中所给的该市区的网络图和数据，对各交巡警的服务平台进行合理分配，使其在所管辖的围出现突发事件时，尽量能在3分钟有交巡警（警车的时速为60km/h）到达事发地。

1.2）给出一个合理的交警服务平台的合理调度方案，在发生重大突发事件时，调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁实际中一个平台的警力最多封锁一个路口（1.3）根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区再增加2至5个平台，请确定需要增加平台的具体个数和位置二）（2.1）针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性如果有明显不合理，请给出解决方案2.2）如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案2 问题分析此题是研究交巡警的合理分配和调度的数学建模问题需要我们通过建立合理的数学模型，进行多目标优化，对交巡警进行合理的分配首先根据附件提供的数据，通过matlab进行数据预处理，利用三列矩阵通过三列转邻接矩阵函数在matlab软件中得到相邻两节点的领接距离矩阵基于floyd算法，借助于matlab软件进行编程，得到任意两点最短路径的距离矩阵juli.随后针对各个问题进行深入分析和处理得到合理解释。

针对问题（一）问题（1.1）：依据交巡警服务平台原则之一：“尽量在三分钟之赶到事故的发生地”，我们通过floyd算法，计算出任意两点之间的最短距离依据原则一，将各个节点到交巡警服务平台最近的原则，将交巡警管辖节点进行分类时间对于任何一个交巡警服务平台都无法在3分钟之赶到的节点，我们采取就近原则问题（1.2）基于预处理得到的所有节点的距离矩阵距离，用matlab提取出20个服务平台分别到13个路口的最短距离 ,用此数据组合成一个20×13新的矩阵,通过借助lingo11.0软件进行编程（value=1为表示该服务平台管辖这个节点出口，value=0，则说明该服务平台不接管该节点出口）得到最优调度结果在最短的时间能对A区13个出口进行封锁问题（1.3）依据问题（1.1）所得出结果即各服务平台所管辖的路口，为了更合理的安排和调度交巡警服务平台，我们增设4个交巡警服务平台，使得28、29、38、39、61、92这几个节点能在事故发生三分钟之有交巡警的赶到，我们通过对（1.1）各节点之间的最短距离调用，找出这六个点的之间任意两点之间的距离，在原则一的前提下将新增平台设在节点28、38、61、92.针对问题（二）问题（2.1）综合全市各区实际情况，我们把案发率、各区人口、各区管辖面积作为一个相关因子，考虑各区节点到交巡警服务平台是否符合设置原则，一：“尽量在三分钟之赶到案发现场”；原则二“保持警务平衡”作为评判标准，确定各区是否设置合理。

对于不合理区域，需要新增平台数建立的平台尽可能少，工作量尽可能的均匀，建立合理模型问题（2.2）对P点案发三分钟后进行围堵在模型建立应该遵循围最小原则，出动警员最小为原则对P进行围堵案发三分钟后，警员开始出动，可以计算出警员出动时，嫌犯的最大活动围，然后根据对嫌犯可能所在的区域计算在他跑出路口之前将路口封锁最短时间3模型假设与符号的说明3.1模型的假设为方便问题的求解与说明，我们对该模型做出如下前提假设：（1） 、所有的道路至少都可以双向通车，即车辆是可以相向形式2） 、车速不受任何外界因素影响，保持恒定3） 、事故发生和接到服务平台接受信息的时延忽略不计4） 、所有警车行动路线都选择最短路线5） 、事故发生，嫌疑犯选择逃跑路线是随机的3.2符号说明三列矩阵：sanlie邻接矩阵:linjie 最短距离矩阵juli为 第i个节点到第j个节点的最短距离； X 0-1 整数规划矩阵；4模型的求解 首先对数据进行处理，每条路线的节点建立三列矩阵sanlie，运用matlab编程编写函数threetolinjie得到邻接矩阵linjie,采用floyd算法得到任意两点之间的最短距离，作为路线的权重juli。

其基本算法步骤为：（1） 、输入三列矩阵sanlie（2）、计算邻接矩阵（threetolinjie） linjie （3）、 计算任意两点之间的最短距离juli 数据详见附录1通过floyd算法计算出来的任意两点之间的最短距离为后面解题基础 4．1.1要对交巡警服务平台进行合理分配建立数学模型 依据我们的数据预处理得到邻接矩阵，我们用matlab分别提取出A区20个服务平台到92个节点的距离矩阵mzyqJL，建立以交巡警额速度恒定的情况下，服从原则一“尽量在三分钟之赶到事故发生地”下模型，通过函数zhaoshu依据最短距离分配原则，将各个节点分配到服务平台图纸上1mm为现实中100米，∴警车速度为60km/h在图纸上为10mm/d通过floyd算法计算出任意两点之间的距离矩阵juli中利用matlab提取92个点分别到20个警务平台的距离矩阵，利用zhaoshu函数将各个节点进行管辖划分，其中（ 1≤ i≤92 , 1≤ j≤20 ）建立目标函数：划分为第j个警务平台管辖。

S.t 最后求的划分结果如下：平台序号管辖的节点案发率总和平台11、67、68、69、71、73、74、75、76、7810.3平台22、40、43、44、70、728.3平台33、54、55、65、665.6平台44、57、60、62、63、646.6平台55、49、50、51、52、53、56、58、599.7平台66、2.5平台77、30、32、47、489平台88、33、465平台99、31、34、35、458.2平台1010、1.6平台1111、26、274.6平台1212、254平台1313、21、22、23、248.5平台1414、2.5平台1515、2.1平台1616、36、373.8平台1717、41、425.3平台1818、80、81、82、836.1平台1919、77、793.4平台2020、84、85、86、87、88、89、90、9110.7对辖区进行优化：对于在三分钟，警务人员无法到达的节点，我们按距离最近进行划分最后得到划分结果如下：平台序号管辖的节点案发率总和平台11、67、68、69、71、73、74、75、76、7810.3平台22、40、43、44、70、72、399.7平台33、54、55、65、665.6平台44、57、60、62、63、646.6平台55、49、50、51、52、53、56、58、599.7平台66、2.5平台77、30、32、47、48、619.6平台88、33、465平台99、31、34、35、458.2平台1010、1.6平台1111、26、274.6平台1212、254平台1313、21、22、23、248.5平台1414、2.5平台1515、28、294.8平台1616、36、37、385平台1717、41、425.3平台1818、80、81、82、836.1平台1919、77、793.4平台2020、84、85、86、87、88、89、90、91、9211.5对辖区再优化：为保持警务量均衡，在此采用lingo11.0 辖区节点按照在原则一下使得平均警务量方差最小为原则，保持警务量平衡进行优化:S.t 优化的结果：平台序号管辖节点案发率总和平台11、67、71、73、74、756.4平台22、3、39、42、727.9平台343、44、54、55、65、68、767.4平台44、57、60、62、63、64、667.4平台55、49、53、58、596.7平台66、50,51、52、565.5平台79、30、32、48、617.7平台834、35、47、465.9平台97、16、33、37。