全国数学建模论文

1交巡警服务平台的设置与调度摘要本文以某市城区为对象，着重研究了交巡警服务平台的设置与调度问题。针对该市中心城区A，首先利用K-Means聚类分析方法，结合最短路算法，按照尽可能3分钟到达的原则，对A区中20个交巡警服务平台的管辖范围进行分配，使得93.5%的交通路口在发生突发事件时能在3分钟内有交巡警到达；其次，当A区有重大突发事件出现时，为调度A区中20个平台的警力资源快速封锁进出该区的13条交通要道，建立0-1规划指派模型，给出了最佳调度方案，可在8.02分钟内实现对A区的封锁；然后，考虑到由于各路口的案发率和城区道路的长短的不同，而造成A区中现有平台管辖范围分配的不均衡，我们定义了各平台中点的负荷因子和平台加权工作量，利用A区中各平台加权工作量的标准差分析20个平台的均衡性，并建立优化模型用确定在该区增加平台的最佳个数为3个，并分别设置在标号为39,48和90的路口。利用对A区的分析方法，对城区B,C,D,E,F的均衡性分别进行了量化分析，指出其中现有平台设置的不合理之处，类似于A区建立优化模型通过新增平台和移动现有平台位置增强平台设置与辖区分配的合理性，给出了具体的调度方案；另外，采用模拟退火算法，对全市各节点做全局分析，给出了平台数目为80的情况下比较均衡的设置方案，使得覆盖率提升到80.01%，比现在的设置方案提高了11%。最后，针对重大刑事案件犯罪嫌疑人目标的动态性，采用“分支决策”方法通过分析其可能逃跑路径，建模计算其最大逃跑路径，结合对A区中13个路口的封锁思想，建立快速围堵流程，并计算给出最佳围堵方案，在假设嫌疑犯的逃跑速度下，可在8.79分钟内实现围堵。关键词：K-Means聚类；0-1规划指派模型；加权工作量；模拟退火；分支决策2一、问题重述为了使警察更有效地贯彻实施刑事执法、治安管理、交通管理、服务群众四大职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：问题一、根据给出的该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图及相关的数据信息，为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。问题二、针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案的合理性。如果有明显不合理，请给出解决方案。如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。二、问题分析与假设问题一要求，首先对该市中心城区A各交巡警服务平台（简称平台）的管辖范围进行合理划分，然后给出重大案件发生时，快速全封锁13条交通要道的调度方案，最后为改善现有分配方案中工作量不均衡等问题，合理增设2至5个交巡警服务平台。由给出的该市中心城区A的交通网络和现有的20个平台的设置情况，已知警车的时速为60km/h时，为使各平台在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警到达事发地。只要合理分配各平台的管辖范围，使得到其管辖范围内最远节点的距离小于3km即可。首先以A区的20个平台为初始类中心，对A区的所有92个节点进行K-Means聚类分析。为保证聚类分析的最终类中心几乎不偏离20个服务平台，可选择迭代次数为1。至此，将每个类的类成员划分到对应平台进行管辖，得到粗略的管辖范围划分。由于聚类分析过程中采用的距离为两点间的欧式距离，而实际中，有些节点并不能由平台按欧式距离直接到达（简称直达），对于这种特殊情况，需要进一步讨论。然后，计算出各连通节点之间的距离，对于不能直达的特殊节点，计算它与离其最近的平台的距离，来判断该节点所归属的平台。最后，计算出平台的覆盖率，即能在3分钟内有交巡警到达的节点在所有节点中所占的比例。在有重大突发事件时，可以把A区看成一个无向连接网络，用C++编程求出20个平台与13条交通要道节点的最小距离矩阵。实现快速全封锁，就是指寻找调度方案，使得13个交通要道都被封锁的时间最短，该最短时间就是封锁13个交通要道中用时最长的要道所需的时间，因此把求解快速全封锁13条交通要道的调度问题转化为0-1规划问题，建立0-1规划指派模型进行求解，即可得到最优调度方案。3在只考虑当出现突发事件时，尽量能在3分钟内有交巡警到达事发地这一因素划分管辖范围时，会出现各平台工作量不平衡的现象。由于各个节点的发案率不同，所以以发案率为权重计算出各个节点的加权工作量，对20个平台的加权工作量进行排序，对于加权工作量明显高于其他平台的平台，采用在其附近增加新平台的方法来降低其工作量。为确定增设平台的位置，在加权工作量较高的平台附近确定出增设平台所在的区域范围，然后在这个区域范围内利用优化选址模型确定出增设平台的最终位置。由于增加平台数量，会导致人力、物力的增加，所以分别讨论了增加2、3、4、5个平台情况下，不平衡现状的改善程度。标准差表示变量的波动程度，所以可以用加权工作量的标准差来衡量A区所有平台工作量的均衡性，标准差越小意味着各个平台的工作量越均衡。计算出各个平台的加权工作量，通过计算每种方案加权工作量的标准差来判断对均衡性的改善程度，进而选出最优方案。问题二要求，对全市的现有平台设置方案的合理性进行分析，若有明显不合理，并给出解决方案。对于该问题，一方面，在尽量不改动现有平台的情况下，按照分析A区合理性的方法，分别对其他5个区以及两个区的交界处分别进行分析，判断各自的合理性，找出设置不合理的平台，并通过增加新平台和移动不合理平台的方法对现有的设置方案进行改进。另一方面，假设全市的平台数目为80，可以通过模拟退火算法给出相对比较均衡的分配方案，与现有方案进行比较，可以比较出现有方案的不合理之处。如果该市地点P（第32个节点）处发生了重大刑事案件，由于道路稀疏的地区节点和可选择的线路较少，且两节点间的距离较长，行驶在道路稀疏的地区很容易被围堵。所以，嫌疑犯为逃脱警察的追捕，会尽可能地沿最短路径像道路密集的地方逃逸。由于在案发3分钟后才接到报警，所以犯罪嫌疑人在这3分钟内会采取隐蔽式逃跑方式，即驾车逃跑时车速不超过最大限速，若其超速，很容易被人拦截，假设这段时间其车速为50km/h，但3分钟后已经报警，嫌疑犯为了逃离警察的追捕，会用最快速度逃跑，假设他之后都能达到警车的速度，即60km/h。当警方接到报警电话时，嫌疑犯所处的可能位置是以P点为中心，3分钟路程为半径的面（由于道路不都是直的，因此不是一个规则的圆面）内。为了快速搜捕嫌疑犯，应确定围堵圈，使得嫌疑犯被包围在围堵圈内，如果包围圈过大将导致下一步搜捕时警力不足，而且搜捕效率较低，所以还要保证围堵圈尽量小。确定了围堵圈之后，就应确定到各围堵点进行围堵的平台，使得平台到达围堵点用时最短，平台的选择可借助问题一中的优化选址模型来确定。因此，便能得到用时最短的围堵方案。为将实际问题简化，对本题作如下假设：假设1.路况假设：相邻两可达结点间路线近似为直线；道路上交通状态及信号控制对警车速度无影响。假设2.警车行驶状态假设：接警时，警车初始位置为各自服务平台，其行驶不受限制，保持固定车速60km/h行驶；划分管辖范围时，在允许的时间范围内，尽量避免多次转向。假设3.区域特点假设：各区不交叉工作；各结点在一天内任意时刻发生事故的概率相同；各区人口密度分布均匀。假设4.平台假设：假设平台只能设置在节点上；假设接到报警电话时，所属服务台有警车可以出动。假设5.假设案发现场都在城市的道路上，不会出现在区域里。假设6.假设罪犯逃跑时车速分为3分钟以内和3分钟以后两种车速。故只会出现在城市道路上,不会出现在区域里4三、符号说明),(iiyx第i个点在平面坐标系中的坐标；8021,,,uuuU所有交巡警服务平台集合；58221,,,sssS所有交叉路口的节点集合；1721,,,所有出入城区的路口节点集合；92821,,,eeeE所有交通路口的路线集合；ijd交通路线上节点ji,之间的最短距离；ijt节点i到节点j的最短时间；v警车的车速；jiwu示性函数，当A区调遣交巡警服务平台iu去封锁交通要道jw时取值1，否则取0；iuD所辖范围内，平台iu到各节点的平均出警距离；D20个平台到各节点的平均出警距离；ium平台iu所辖的节点个数；js节点js的发案率；iu平台iu的加权工作量。四、模型的建立4.1问题一模型建立4.1.1分配管辖范围的模型为保证各平台在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警到达事发地，需要合理分配各平台的管辖范围，使得到其管辖范围内最远节点的距离尽可能地小于3km即可。所以，需要计算出各个平台到其管辖范围内各节点的距离，而节点可达分两种情况：从平台可以直达节点，与从平台不可以直达节点，需要经过其他一个或多个节点转到目标节点。针对两种不同的情况，分别给出计算距离的公式。1)从平台可以直接达到节点22)()(jijijisususuyyxxd2)从平台不可以直接达到节点jjkijkjissussuddmin其中，jjkissud表示平台iu经节点jks达到节点js。若jks只是一个节点，则：jjkjkijjkisssussuddd若jks代表一个节点序列),,,(21jmjjsss，则：jjmjjjijjkisssssussudddd2115式中所有可以直接连接的两点间的距离同1)中的计算方法。在分析过程中，首先借助K-Means聚类分析[1]对管辖范围作初步划分，划分管辖范围时，将20个平台的位置作为初始类中心，92个节点为样本点，以欧式距离作为测度亲疏程度的指标，将所有样本点聚成20个类。具体聚类步骤如下：（1）指定聚类数目K为将92个节点唯一地划分到20个平台的管辖范围，因此取20K。（2）确定K个初始类中心将20个平台的位置作为初始类中心，计算其余每一个节点与初始类中心的相似度，相似度用欧式距离度量。（3）根据相似性进行分类根据欧氏距离，按照距20个类中心距离最短的原则将92个节点分派到各类中心。（4）迭代次数的选择经一次分类后，形成20组样本点，此时所有平台包含在不同的类别中。如果为得到相似度更高的解，需要重新确定类中心，重复上述聚类过程。本问题中为保证最终类中心不偏离20个平台，只迭代一次，则可以初步确定平台管辖与其同在一个类的节点。该问题最终的目标为对于平台iu管辖范围内的所有节点js，有：3000jisud4.1.2设置合理的调度方案的模型根据之前的分析，把A图看成一个无向连接网络，用C++编程，利用4.1.1中计算两点间最短距离的原理求出20个平台与13条交通要道节点的最短距离矩阵，即2021,,,uuuUA中的所有平台到1321,,,中所有路口的最短距离jiwud。为实现快速全封锁，寻找使得13个交通要道都被封锁所用的时间最短的调度方案，建立以下0-1规划指派模型：jijiwuwujivdmaxmin110..131201jwuiwujijits或其中，jiwud为节点jiwu,之间的最短有效路径距离，v为警车的车速，jiwu为示性函数，当调遣平台