《交警服务平台.docx》由会员分享，可在线阅读，更多相关《交警服务平台.docx（19页珍藏版）》请在三一办公上搜索。
1、2011高教社杯全国大学生数学建模竞赛题目（请先阅读“全国大学生数学建模竞赛论文格式规范”）B题交巡警服务平台的设置与调度“有困难找警察，是家喻户晓的一句流行语。警察肩负着刑事执法、治安 管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在 市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职 能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需 求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部 门面临的一个实际课题。试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问 题：（1）附件1中的附图1给出了该
2、市中心城区A的交通网络和现有的20个交 巡警服务平台的设置情况示意图，相关的数据信息见附件2。请为各交巡警服务 平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内 有交巡警（警车的时速为60km/h）到达事发地。对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进 出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个 路口，请给出该区交巡警服务平台警力合理的调度方案。根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际 情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。（2）针对全市（主城六区A，B，C，D，
3、E，F）的具体情况，按照设置交 巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见 附件）的合理性。如果有明显不合理，请给出解决方案。如果该市地点P （第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡 警服务平台警力资源的最佳围堵方案。附件1： A区和全市六区交通网络与平台设置的示意图。附件2：全市六区交通网络与平台设置的相关数据表（共5个工作表）。送货路线设计问题与交警平台设置方法相同最短路作为图与网络技术研究中的一个经典问题一直在工程规划、地理信息 系统、通信和军事运筹学等领域有着十分广泛的应用，基
4、于对成本与效率的考虑， 可以设计一可行性方案使其耗时最少。针对本文要解决的的问题，通过图论对问题进行转化，转化为最优Hamilton 圈问题，采用Floyd算法思想、借助矩阵、MATLAB软件和编程，再通过数据的 分析、筛选和计算，从而可在图上标出送货员到各个点的最短路径，得到最优解。问题一：将130号货物送到指定地点并返回，构造最优Hamilton圈，采 用矩阵翻转法来实现二边逐次修正法过程，Floyd算法，进而求出最优Hamilton 圈。得到最终路线为：0/51-26-21-17-14-16-23-32-38-36-43-42 -49-45-40-34-39-27-31-24-13-18
5、-0/51,总长度为54709 m，总时间 为 3.78h问题二：基于问题一，在添加了时间限制的情况下，将时间限制条件加入到 问题一求解的最优Hamilton圈方法中去，得到在有时间限制的情况下的最佳线 路，得到最终路线：0/51-18-13-24-31-34-40-45-42-49-43-38-32 -23-16-14-17-21-36-39-27-26-0/51，总长度为 54996 m，总时间为 3.79 h问题三：由于考虑到送货员一次送货所能承载的最大重量和体积，我们采用 将区域分块。对送货地点的进行相关分组，继而回归到问题一的方法中，在每组 中寻求最佳送货路线，得出要完成这次送货，送
6、货员必须分三趟进行送货以及其 最终路线。关键字：耗时最少 图论 最优Hamilton圈 矩阵翻转Floyd算法一问题的重述现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业 也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个地方，请设计方案使其耗时最少。现有一快递公司，库房在图1中的O点，一送货员需将货物送至城市内多处， 请设计送货方案，使所用时间最少。该地形图的示意图见图1，各点连通信息见 表3,假定送货员只能沿这些连通线路行走，而不能走其它任何路线。各件货物 的相关信息见表1， 50个位置点的坐标见表2。假定送货员最大载重50公斤，所带货物最大体积
7、1立方米。送货员的平均 速度为24公里/小时。假定每件货物交接花费3分钟，为简化起见，同一地点有 多件货物也简单按照每件3分钟交接计算。现在送货员要将100件货物送到50个地点。请完成以下问题。问题一：若将130号货物送到指定地点并返回。设计最快完成路线与方式。 给出结果。要求标出送货线路。问题二：假定该送货员从早上8点上班开始送货，要将130号货物的送达 时间不能超过指定时间，请设计最快完成路线与方式。要求标出送货线路。问题三：若不需要考虑所有货物送达时间限制（包括前30件货物），现在要 将100件货物全部送到指定地点并返回。设计最快完成路线与方式。要求标出送 货线路，给出送完所有快件的时间
8、。由于受重量和体积限制，送货员可中途返回 取货。可不考虑中午休息时间。二、问题分析快递公司的送货员需要把货物送到所有货物交接地点，最后回到出发点。如 何安排送货路线，能最快完成任务，即总的送货行程最短。问题一，130号货物的总重量是48.5公斤，总体积是0.88立方米，均在 送货员的最大承受范围，所以，不用考虑送货员返回取货；只要设计最快完成路 线与方式，不用考虑时间，这就相当于旅游者环游世界问题，所以我们采用最优 Hamilton回路模型求解问题。问题二，130号货物仍可一次性送完，不用考虑送货员最大载重和体积。 但要考虑每件货物送达时间的要求，而每件货物对应相应的送货地点，从而转化 为达到
9、指定送货地点的时间限制，而时间的贤者可以分为几个时间段，因此采用 以时间为基础的多次分区域的假设模型从而找出最优解。问题三，要在体积和质量的双重限制下得到送货员最快完成送货的路线， 1100号货物的总重量是148公斤，总体积是2.8公斤，根据时间和体积的限制，送货员至少要往返三次送货，我们可以将区域划分为三部分，讨论问题。三模型假设对于上述实际问题，我们给了合理的假设1. 假设送货员的最大载重是50公斤，所带货物的最大体积为1立方米；2. 每件货物交接花费3分钟，同一地点有多件货物也简单按照每间3分钟交接计算；3. 要求到达的时间不包括此次在该点交接的时间；4. 所用的距离数据到精确到米，时间
10、精确到0.01h；5.在满足时间限制的条件下，顾客能够更早的拿到货物顾客的满意度越高；6.送货员在多次经过同一送货地点时在第一次经过交接货物效率最高；四符号说明与变量G表示加权无向图V无向图中的点集E链接点集中点的所有边的集合W(e)e边的权重即现实中的距离Cij图中任意两点见的最短距离Pij用翻转矩阵法求解的最终解果M个极大值表示图中两点小可达五模型的建立与求解5.1问题一我们将问题就归结为求最优Hamilton圈问题，采用矩阵翻转法来实践二边 逐次修正法过程，中间需要用到Floyd算法求出任意两点只见最短距离,从而求 出最优Hamilton圈。算法过程为：用矩阵A描述出图，如表述z点到j点
11、的距离，将不能直 达的点的距离赋一个很大的数，先用Floyd算法求出任意两点见最短距离，得到 矩阵b，再用矩阵翻转法求出最优Hamilton圈。基本概念：（1）令G =申,E）为一个加权无向图，其中V =晶,v 2, v 3,助为顶点集合，E为边集合。图G中每一条边e都对应一个实数w（e），则称w（e）为改变的权。若 任意两点均有边相连，称G为完备图。（2）距离矩阵：对无向图G，其距离矩阵4 =（知）n次n，其中a. = a为i， j两点间的距离。（3）Hamilton图：设g = （V,E）是连通无向图，经过g的每个顶点正好一 次的圈，称为g的一条Hamilton图，简称H圈；含H圈得图称为
12、哈米尔顿图或 H图。（4）最佳H圈：在加权图G = （V,E）中，权最小的Hamilton圈称为最佳（5）矩阵翻转：在一个矩阵中，对它的第i行（列）到第j行（列）翻转是以第i行（列）和j行（列的）中心位置为转轴，旋转180度，这样，第i行（列）和第j行（列）的位置互换，第i + 1行（列）和第j - 1行（列）位置互换， 二边逐次修正法的算法过程如下：（1）任取初始 H 圈：c = y , y ,. y ,，y ；（ 2）对所有 i, j， 012ijn 1若 w(y , y ) + w(y , y ) w(y , y ) + w(y , y )则在 CO 中删去i ji+1 j+1i i+1
13、j j+1边（y , y ）和（y , y ）而加入边（y , y ）和（y , y ），形成新的H圈c，即 i i + 1j j +1i ji +1 j +1C = y , y ,. y , y , y ，y , y ，y , y ；（3）对C重复步骤（2），直到条件不 1 2i j j-1i +1 j +1n 1满足为止，最终得到的c即为所求.Floyd算法的基本思想：主要用于计算所有节点对之间的最短路,其基本是从代表任意两个节点匕到勺经过一次经转的所有可能路径，经过比较后选出最短路，代替D （0）中对应的 路径，迭代出距离矩阵D，D中各元素表示通过一次迭代后网络中任意两 点间最短路，也即
14、网络中任意两点之间直接到达或只经过一个中间点时的最短 路。在此基础上依次计算D （2）, D （3）,. D （S1）, D （k），其中对应的元素表示任意两点间不经过中间点或最多允许经过2k - 1个中间点时的最短路。当D （k-1） = D （k）时，表明得到的带权邻接矩阵D （k）反映了所有顶点对之间的最短距离信息，称为最短 距离矩阵。（程序见附表）5.1.1模型的建立此题共有50个目标点，加上出发点原点O共51个点，要求将货物送往目标 点，且用的时间最短，则必须知道目标点和原点O的距离（令O点为第51个点）， 及各个点之间的坐标距离。此图并不是每个点都相连，有些点不能直接到达， 所以要
15、先列出此题的权矩阵七，然后求出它们之间的最短距离匕和最短路径. 则模型规划如下：p = YY、( x - x )2 + (y - y )2， ji yi jZVT-乙、.：( x - x )2 + (y -ij i yiI j-1i = 1,. ,51 ； j = 1,. ,51利用MATLAB软件进行计算，编程结果得: d取值情况如下表所示：1234 48495051107740.21916.35452.7 1660314854148717959.727740.2058252292.6 1433117770161591226531916.3582503536.4 15670152121477
16、48537.945452.72292.63536.40 1449316475152661049956583.61252.94669.41161.4 1399316758153101108461294.38679.22940.16391 1628913806140436876.871968.28750.73242.56492.8 1556612973132006049.1: :4615588139681478013901 1494.19268.55739.6106884714125153391398814445 6857.93888.1822.347095.8481660314331156701
17、4493 0106947138.9120944914854177701521216475 1069403568.86933.95014871161591477415266 7138.93568.807680.9517959.7122658537.910499 120946933.97680.90C得取值情况如下表: ij12345474849505110M1916.3MMMMMMM2M0M2292.61252.9MMMMM31916.3M03536.4MMMMMM4M2292.63536.40MMMMMM5M1252.9MM0MMMMM:47MMMMM0MMMM48MMMMMM0MMM49MM
18、MMMMM03568.8M50MMMMMMM3568.80M51MMMMMMMMM0此表中的M表示相应两点不能直接到达，数值表示两点间可以直接到达的距离值，0表示自身到自身的距离利用Floyd算法求得p , p取值情况如下表所示12345 4748495051107745.31916.35452.78998.3 162771876120306169891006827745.305829.12292.61252.9 224271800226325227571629631916.35829.103536.47082 166761785620705173881046745452.72292.6353
19、6.403545.6 202122029524242209241400458998.31252.970823545.60 2117416749250732150416563:471627722427166762021221174 0112538943.55374.79215.8481876118002178562029516749 112530107087139.615806492030626325207052424225073 8943.51070803568.811722501698922757173882092421504 5374.77139.63568.809928.15110068
20、16296104671400416563 9215.815806117229928.105.1.2模型的求解由于前30个货物要到达的节点分别为，13，14，16，17，18, 21，23, 24, 26，27，31，32，34，36，38，39，40，42，43，45，49，且送货员不需要返回 0点重新取货，故只需要满足从0点出发遍历图中的21个点回到0的距离最 短即可。取任意几个初始圈，再利用翻转矩阵法对p进行处理，得到各自的最佳H 圈，由于初始圈的选取不同，所的的最佳H圈也不同，从中选取总路程最近的作 为最佳Hamilton圈。编 号总路线 长度（米）送货路线I547090/51一26一2
21、1一17一14一16一23一32一38一36一43一42一49一45一40一34 一39一27一31一24一13一18一0/51 （最佳 H 圈）II549960/51一18一13一24一31一34一40一45一42一49一43一38一32一23一16一14一17一21一36一39一27一260/51III557730/51一21一17一14一16一23一32一36一38一43一42一49一45一40一34一31一39一27一18一13一24一26一0/51IV579140/51一18一13一24一31一34一40一45一49一42一43一38一36一27一39一26一14一16一23一32一
22、17一21一0/51结果: 得到选择总路线长度最短的送货路线，即第I条送货路线，如图5.1.2所示O/51一26一21一17一14一16一23一32一38一36一43一42一49一45一40一34一39一27一31一24一13一18一 O/51图 5.1.2送货总长度： min X 1000 f (v ) = 54709 m送货总时间：T = 3.78 h5.2问题二对问题二的分析可知，相对于问题一，问题二加上了时间的限制，但货物重量和体积不变。在解决问题一时，采用矩阵翻转法对初始矩阵进行修正，结果也为一个对称轴为零，上 方即为距离，所以我们可以在对矩阵进行修正时加上时间限制。得到如下结果：获
23、得符合题意的最快完成路线，如图5.2所示O/51一18一13一24一31一34一40一45一42一49一43一38一32一23一16一14一17一21一36一39一27一26一 O/51图5.2送货总长度：min 1000 f (v ) = 54996 m送货总时间：T = 3.79h5.3问题三5.3.1模型的建立与求解由题目附录中给定的各货物号信息表，1100号货物总重量148公斤、总体 积2.8立方米。考虑到送货员最大载重和体积，送货员可分三次送完所有货物。此问题包含两个方面：第一、对送货地点的分组；第二、在每组中求最佳送 货路线。我们只能去寻求一种较合理的划分准则使得各组总路线长度加起
24、来比较理 想。选出三个点，使这三个点中两两之间的最短路长度是50个送货点所有的三点组中最大的，这三个点是各组的基点。通俗地说，就是找到图中“分的最开” 的三个点作为基点。对于其他任意点，依次算出它与三个基点的最短路长度，离 哪个基点近，它就被分到哪一组。根据以上算法，用MATLAB编程我们得到了一个初始分组并算得它的货物重 量总和、货物体积总和，如下表所示：编号包含的送货点货物重量总和（kg ）货物体积总和（m 3）第一组2,5,11,12,13,15,19,20,22,24,25,26,28,29,30,31,33,41,44,46,4855.041.0622第二组1,3,4,6,7,8,9
25、,10,14,16,17,18,2129.120.5688第三组23,27,32,34,35,36,37,38,39,40,42,43,45,47,49,5063.841.169可以看出要对初始分组的两组并不满足题意，所以我们对其进行调整，使得每组货物重量总和 50 kg、货物体积总和 1m 3调整后每组送货点，货物重量总和、货物体积总和如下表所示:编号包含的送货点货物重量总和（kg ）货物体积总和（m 3）第一组11,12,13,15,19,20,22,24,25,26,28,29,30,33,41,44,46,4849.90.9112第二组1,2,3,4,5,6,7,8,9,10,14,1
26、6,17,18,21,23,32,3548.380.985第三组27,31,34,36,37,38,39,40,42,43,45,47,49,5049.720.9038调整后的每组货物重量总和均 50 kg、货物体积总和均 1 m 3,满足题意，则利用问题一中的算法，可以得出每组的送货时间，最优送货路线及总路线长度， 如下表所示：编号送货时间（h ）总路线长 度（m）送货路线第一 组3.69477360/512624192541444846332830 f 292022151211 130/51 （图 5.31）第二 组3.7952743O/51 18825431671091416 32352
27、31721O/51 （图 5.32）第三 组3.4742421O/512739363843424950454037 473431O/51 （图 5.33）图 5.31图 5.32图 5.33结果：第一组路线为送货总长度：0/51262419 一 2541 一 44 一 48 46 一 33 一 28 一 30 一 29 一 20 一 22 一 15 一 12 一 11 一 13 一 O/51送货总长度： 47736 m第二组路线为：0/51 1882543167109141632 一 35 一 23 一 17 一 21 一 O/51送货总长度： 52743 m第三组路线为：0/51273936
28、384342495045403747 3431O/51送货总长度： 42421 m送货总线路长度： 47736 + 52743 + 42421 = 142900 m送货总时间： T = T + T + T = 10.95 h为了检验该结果，我们还计算了把50个送货点只分一组，在不考虑送货员最大载重和体积的情况下，送货员的最短路线长度为：119762 m。但分组变多时，由于路线的重复，总路线会增加，本结果增加了 23000 m，这是可以容忍的。六模型的评价与推广6.1模型的评价在解决图中任意两点间最短距离时间我们采用了 Floyd算法，精确性很高， 但执行效率低，求解最佳Hamilton圈时所用
29、的方法只是一个近似的解决方法， 但得到的结果与精确解很接近，对现实问题的处理还是可以满足要求的。在解决 问题三时，我们考虑到了限制因素重量和总路程最短的要求，进行分区域计算， 是符合实际的。6.2模型的推广1、在解决问题二时，题中没有要求回到起点，但我们可以利用最小生成树 这一理论求出整体的最短距离并且还能保持连通性。2、在计算图中任意两点最短距离时，除了运用Floyd算法外，还可以调用 Dijkstr算法进行计算。七参考文献【1】刘向东，数学模型与数学建模，北京师范大学出版社，1998【2】贾秋玲、袁冬丽、栾云凤，基于matlab的系统仿真、分析及设计，西北工业大学出版 社.2006【3】龚
30、劬，图论与网络最优化，重庆大学出版社，1998【4】姜启源，谢金星，叶俊，数学模型，高等教育出版社，2003【5】姜启源、谢金星、叶俊，数学模型，北京：高等教育出版社，2003【6】胡红亮、赵芳玲、辛小龙，数学建模与竞赛辅导，西安：西北大学出版社，2010【7】任善强、雷鸣，数学模型，重庆：重庆大学出版社，1998八、附录各节点间距离程序：A=1 9185 500;2 1445,560;3 7270,570;4 3735,670;5 2620,995;6 10080,1435;7 10025,2280;8 7160,2525;9 13845,268010 11935,3050;11 7850,
31、3545;12 6585,4185;13 7630,5200;14 13405,5325;15 2125,5975;16 15365,7045;17 14165,738518 8825,8075;19 5855,8165;20 780,8355;21 12770,8560;22 2200,8835;23 14765,9055;24 7790,9330;25 4435,952526 10860,9635;27 10385,10500;28 565,9765;29 2580,9865;30 1565,9955;31 9395,10100;32 14835,10365;33 1250,1090034
32、 7280,11065;35 15305,11375;36 12390,11415;37 6410,11510;38 13915,11610;399510,12050;40 8345,1230041 4930,13650;42 13265,14145;43 14180,14215;44 3030,15060;45 10915,14235;46 2330,14500;47 7735,1455048 885,14880;49 11575,15160;50 8010,15325;C=1,1,3;2,1,8;3,2,20;4,2,4;5,3,8;6,3,4;7,4,2;8,5,15;9,5,2;10,
33、6,1;11,7,18;12,7,1;13,8,12;14,9,14;15 ,9,10;16,10,18;17,10,7;18,11,12;19,12,13;20,12,25;21,12,15;22,13,18;23,13,19;24,13,11;25,14,18; 26,14,16;27,14,1728,14,21;29,15,22;30,15,25;31,16,23;32,17,23;33,18,31;34,19,24;35,20,22;36,21,26;37,21,36;38,2 1,17;39,22,3040,23,17;41,24,31;42,25,41;43,25,19;44,25
34、,29;45,27,31;46,28,33;47,29,22;48,30,28;49,30,41;50,3 1,26;51,31,3452,32,35;53,32,23;54,33,46;55,33,28;56,34,40;57,35,38;58,36,45;59,36,27;60,37,40;61,38,36;62,39,27;63,40,3464,40,45;65,41,44;66,41,37;67,41,46;68,42,43;69,42,49;70,43,38;71,44,48;72,44,50;73,45,50;74,45,42;75,46,4876,47,40;77,48,44;7
35、8,49,50;79,49,42;80,50,40;for i=1:80d(i)=sqrt(A(C(i,2),2)-A(C(i,3) ,2)A2+(A(C(i,3),3)-A(C(i,2) ,3)人2)endFloyd算法求每对地点之间最短路径距离：functionD,R=floyd(a)n=size(a,1);D=afor i=1:nfor j=1:nR(i,j)=j;endendRfor k=1:nfor i=1:nfor j=1:nif D(i,k)+D(k,j)D(i,j)D(i,j)=D(i,k)+D(k,j);R(i,j)=R(i,k);endendendkDRend求最佳H圈M文
36、件functiona,b,s=h(e)%e为按照初始H圈点的顺序组成的含点序边框的距离矩阵 n=size(e);%求出距离矩阵的维数.for i=2:n-2;%有一个顺序的外框，所以循环从2开始到n - 2.for j=i+1:n-2;if e(i,j)+e(i+1,j+1)m m=s-(p-q); z1=i;z2=j;z3=k;endendendendz1,z2,z3 %这三个点是各组的基点p=1;m=1;n=1;u=1;for i=1:50if i=51,keyboard;endif (D(i,z1)D(i,z2)&(D(i,z3)D(i,z2) Z1(p)=i;p=p+1;elseif (D(i,z2)D(i,z1)&(D(i,z3)D(i,z1) Z2(m)=i;m=m+1;elseif (D(i,z2)D(i,z3)&(D(i,z1)D(i,z3) Z3(n)=i;n=n+1;endendZ1,Z2,Z3 %对送货地点的分组的初始分组
