《全国大学生数学建模大赛交巡警服务平台的设置和调度》由会员分享，可在线阅读，更多相关《全国大学生数学建模大赛交巡警服务平台的设置和调度（12页珍藏版）》请在金锄头文库上搜索。
1、交巡警服务平台的设置和调度摘 要 本文针对交巡警服务平台的设置和调度问题，通过题目给出的全市交通信息，采用弗洛伊德算法思想、借助矩阵、MATBLE和LINGO软件，求出最短距离矩阵和最短路径矩阵，再过数据的分析、筛选和计算，将目标函数进行优化。 针对A区问题一：根据最短路径原则，利用弗洛伊德算法计算A区92个路口任意两个之间的最短路径距离。首先，根据距离最短原则建立数学模型，即根据最短路径进行分配；其次，对模型进行优化，对模型增加各平台的工作量，即为平台到节点的距离和该节点的案发频率的乘积。为使达到相对工作量均衡（大于10的即为不公平），将其大于10的进行调整。针对A区问题二：将问题转化为求所
2、有方案中到达指定A区出入口路径最长的交巡警平台的最小值问题，建立目标规划模型，即对13个出入A区的节点实现最短时间封锁，同时一个交巡警服务平台只能封锁一个出入路口。运用LINGO程序，进行求解，最优解为。针对A区问题三：对于该问题主要总结上面两小问，在满足各交巡警服务平台到达各管辖节点最长时间小于三分钟且工作量相对均衡下，求交巡警服务平台增加数的最小值。建立在符合相应约束条件求最小值的线性规划问题，求得最优解为新增四个交巡警服务平台。关 键 词Floyd算法 整体规划 优化决策 问 题 重 述为了有效地贯彻实施警察刑事执法、治安管理、交通管理、服务群众的职能，需要在市区的一些交通要道和重要部位
3、设置交巡警服务平台，且各职能和警力配备基本相同。警务资源是有限的，问题在于根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源。1.中心城区A要解决的问题（1）根据题目给出的各附表，为各交巡警服务平台分配管辖范围，使其在所管辖的有突发事件尽量能在三分钟内到达。（2）调度全区20个交巡警服务平台的警力资源，对进出该区的13条范围内出现突发事件时，要道实现快速全封锁。设计该区交巡警服务平台警力合理的调度方案。（3）根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，确定增加平台的具体个数和位置。2.主城六区要解决的问题
4、（1）对全市按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案的合理性。对不合理处给出改进方案。（2）在该市P点处发生重大刑事案件，为了抓捕三分钟前逃跑的犯罪嫌疑人，给出调度全市交巡警服务平台警力资源的最佳围堵方案。解 题 思 路本题主要是交巡警服务平台的设置与调度问题，根据城市的实际情况需要合理的分配各平台的管辖范围与警务资源、设置交巡警服务平台。共有两个大问题，可分为五个小问题： 1.问题关键在于求得各交巡警服务平台的分配管辖范围，在一定条件下各交巡警平台的功能最大。该问题为连通最短路问题。首先在A区中根据弗洛伊德算法求出的各节点到20个交巡警服务平台的最短路径，大
5、约确定各交巡警服务平台的范围；其次考虑案发率和距离计算工作量，设定标准：工作量不能超过10，如果超过10则要再进行调整。2.该问题的研究意义为设计调度方案能够最快的实现全市区封锁，是如何调度。将问题转化为求所有方案中到达指定A区出入口路径最长的交巡警平台的最小值问题，即优化模型。运用LINGO软件，即可求得最优解。3.在全部满足在出现紧急情况时巡交警能在三分钟以内到达，同时工作量相对平衡的条件下，尽可能少的增加交巡警服务平台，以节省不必要的开支。将问题归结为最优化问题，运用线性规划的方法进行求解。4.问 题 假 设1. 道路均为双向，不存在单行道。2. 在道路上发生的案发率为零，只考虑节点处的
6、案发率。3. 假设交巡警具有先进的通讯设备，不考虑信息传递的时间。4. 假设交巡警具有先进的卫星定位设备，发生突发事件时均能准确确定事发地点。5. 交巡警到事发现场道路畅通，且以最短路径到达。6. 假设巡交警处理突发事件的时间忽略不计。符 号 说 明 路口i到路口j的距离,，注：当i路口和j路口不直接相通，=，计算中取为= ,路口之间的最短路径距离； 路口是否为交巡警服务平台服务 注： 路口是否设巡交警服务平台注: 路口的案发率 警车的时速为模 型 建 立 与 求 解1.1.1 模型建立与求解1.根据节点到服务平台的距离最短的原则，利用弗洛伊德算法求的A区92个路口任意两个之间的最短路径距离。
7、对各节点到交巡警服务平台的路径距离进行筛选，其分配结果如表一。表一：管辖范围安排表交巡警服务平台节点交巡警服务平台节点167、68、69、71、73、74、75、76、781126、27239、40、43、44、70、721225354、55、65、661321、22、23、24457、60、62、63、641414549、50、51、52、53、56、58、591528、29661636、37、38730、32、47、48、611741、42833、461880、81、82、83931、34、35、451977、7910102084、85、86、87、88、89、90、91、922.根据路口
8、到交巡警服务平台的距离最短的分配原则，利用Floyd算法，其目标函数即为求所有交巡警服务平台的路程的最小值。 交巡警服务平台所管辖的范围和工作量如表二。表二：管辖范围安排表交巡警服务平台节点工作量交巡警服务平台节点工作量167、68、69、70、71、73、74、75、76、789.40491126、272.3946239、40、727.608512252.8622344、54、55、65、667.1281321、22、23、248.8833457、60、62、63、646.134214140549、50、51、52、53、56、58、598.72551528、2914.158661.3688
9、1636、37、384.868730、32、47、48、619.30411741、42、435.6137833、462.27481880、81、82、83、84、897.3322931、34、35、456.27051977、791.1457101002085、86、87、88、90、91、927.7372所用程序详见附录中程序一、二、三1.1.2 模型建立与计算求解要实现A区快速全封锁所用时间最短，即为最后一交警平台到达指定出入路口节点所用时间最短，因为交警速度一定，即可转化为求最后一组交巡警到达指定出入A区的路口节点最长路径的最小值问题。可建立如下模型：目标函数为： 为出入A区的13各路口节
10、点的标号； 为20个交巡警服务平台的标号；用Lingo软件实现求目标函数的最优解，Lingo程序见附录程序四。求得出最优解：分析得出的结果：取中的，表示号交巡警服务台围堵路口。取得结果如下：；于是得出合理的调度方案为：表三：平台A10A16A2A14A12A11A13A15A7A9A19A5A20路口121416212223242829303848621.1.3 模型建立与求解尽可能少的增加交巡警服务平台，实现满足在出现紧急情况时巡交警能在三分钟以内到达，同时工作量相对平衡，将问题转化为最优化问题求解，即增加的交巡警服务平台的数目最少。设目标函数为： 利用程序五求的最优解：即需新增加四个交巡警
11、平台，分析Lingo的结果，的值即为交巡警平台的路口号，可得出新增设的交巡警平台为：29号，38号，61号，92号。 1.1.4模型建立与求解对于全市各区设置平台的合理性的评价，其原则为实现满足在出现紧急情况时巡交警能在三分钟以内到达，同时工作量相对平衡。现设为新增加交巡警服务平台的个数，将交巡警服务平台的增设方案进行优化，即将问题转化为最优化问题求解。目标函数为： 为求得最优的交巡警服务平台总个数，设计了Lingo程序，求得结果为：程序详见附录中程序六。分析程序运行结果，可得新增平台号见表四：表四：各区新增设平台的路口号A区29,38,61，92B区104,153C区184,201,204,
12、208,210,216，238，240,249,250,263,269,288,312,315D区329,332,333,338,344,362,369,371E区387，389，390，392，393，408，419，420，421，446，454，458，472，474F区491，509，514，533，539，541，558，560，569，574，575，578，5821.1.5 模型建立与求解 在最短的时间内实现全市快速全封锁，即为最后一交警平台到达指定出入路口节点所用时间最短，因为交警速度一定，即可转化为求最后一组交巡警到达指定出入A区的路口节点最长路径的最小值问题。 模型优化和改
13、进可以用老师给的1.在计算各交巡警服务平台的工作量时，其自身节点处的突发事件和处理每一个突发事件的发生都占用的时间都应是工作量函数的因变量。假设交巡警处理每件突发事件的平均时间为5分钟，即工作量为路上时间和处理突发事件的时间之和。路上时间的系数为，处理突发事件的时间的系数为。建立数学模型为：（）2.在模型假设中考虑所有的道路为双行道，在模型的推广中应该考虑道路的单行线问题，即只能交巡警只能按特定的方向到达案发现场。参 考 文 献1数学模型编写组.数学模型.广州：华南理工大学出版社，2003.2数学建模案例精选 朱道元等编著 北京：科学出版社，20033曾建军、李世航等，MATLAB语言与数学建模.安徽：安徽大学出版社， 2005。4消防灭火救援最优路径算法研究，http:/ 5警车配置及巡逻问题的研究，http:/ 录程序一：计算直接相连的两节点间的直线距离for i=1:582 for j=1:582 if (i=j) d(i,j)=0; else d(i,j)=1e10; end endendfor i=1:928d(bian(i,1),bian(i,2)=sqrt(xy(bian(i,1),
