2011高教社杯全国大学生数学建模竞赛题目（请先阅读“全国大学生数学建模竞赛论文格式规范”）B题交巡警服务平台的设置与调度“有困难找警察”，是家喻户晓的一句流行语。

警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。

为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。

每个交巡警服务平台的职能和警力配备基本相同。

由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。

试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：（1）附件1中的附图1给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图，相关的数据信息见附件2。

请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。

对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。

实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。

根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。

（2）针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。

如果有明显不合理，请给出解决方案。

如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。

为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。

附件1：A区和全市六区交通网络与平台设置的示意图。

附件2：全市六区交通网络与平台设置的相关数据表（共5个工作表）。

送货路线设计问题与交警平台设置方法相同摘要最短路作为图与网络技术研究中的一个经典问题一直在工程规划、地理信息系统、通信和军事运筹学等领域有着十分广泛的应用，基于对成本与效率的考虑，可以设计一可行性方案使其耗时最少。

针对本文要解决的的问题，通过图论对问题进行转化，转化为最优Hamilton 圈问题，采用Floyd算法思想、借助矩阵、MATLAB软件和编程，再通过数据的分析、筛选和计算，从而可在图上标出送货员到各个点的最短路径，得到最优解。

问题一：将1~30 号货物送到指定地点并返回，构造最优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→0/51,总长度为m54709，总时间为h78.3问题二：基于问题一，在添加了时间限制的情况下，将时间限制条件加入到问题一求解的最优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，总长度为m54996，总时间为.379h问题三：由于考虑到送货员一次送货所能承载的最大重量和体积，我们采用将区域分块。

对送货地点的进行相关分组，继而回归到问题一的方法中，在每组中寻求最佳送货路线，得出要完成这次送货，送货员必须分三趟进行送货以及其最终路线。

关键字：耗时最少图论最优Hamilton 圈矩阵翻转 Floyd算法一问题的重述现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个地方，请设计方案使其耗时最少。

现有一快递公司，库房在图1中的O点，一送货员需将货物送至城市内多处，请设计送货方案，使所用时间最少。

该地形图的示意图见图1，各点连通信息见表3，假定送货员只能沿这些连通线路行走，而不能走其它任何路线。

各件货物的相关信息见表1，50个位置点的坐标见表2。

假定送货员最大载重50公斤，所带货物最大体积1立方米。

送货员的平均速度为24公里/小时。

假定每件货物交接花费3分钟，为简化起见，同一地点有多件货物也简单按照每件3分钟交接计算。

现在送货员要将100件货物送到50个地点。

请完成以下问题。

问题一：若将1~30号货物送到指定地点并返回。

设计最快完成路线与方式。

给出结果。

要求标出送货线路。

问题二：假定该送货员从早上8点上班开始送货，要将1~30号货物的送达时间不能超过指定时间，请设计最快完成路线与方式。

要求标出送货线路。

问题三：若不需要考虑所有货物送达时间限制(包括前30件货物)，现在要将100件货物全部送到指定地点并返回。

设计最快完成路线与方式。

要求标出送货线路，给出送完所有快件的时间。

由于受重量和体积限制，送货员可中途返回取货。

可不考虑中午休息时间。

二、问题分析快递公司的送货员需要把货物送到所有货物交接地点，最后回到出发点。

如何安排送货路线，能最快完成任务，即总的送货行程最短。

问题一，1~30号货物的总重量是48.5公斤，总体积是0.88立方米，均在送货员的最大承受范围，所以，不用考虑送货员返回取货；只要设计最快完成路线与方式，不用考虑时间，这就相当于旅游者环游世界问题，所以我们采用最优Hamilton 回路模型求解问题。

问题二， 1~30号货物仍可一次性送完，不用考虑送货员最大载重和体积。

但要考虑每件货物送达时间的要求，而每件货物对应相应的送货地点，从而转化为达到指定送货地点的时间限制，而时间的贤者可以分为几个时间段，因此采用以时间为基础的多次分区域的假设模型从而找出最优解。

问题三，要在体积和质量的双重限制下得到送货员最快完成送货的路线，1~100号货物的总重量是148公斤，总体积是2.8公斤，根据时间和体积的限制，送货员至少要往返三次送货，我们可以将区域划分为三部分，讨论问题。

三模型假设对于上述实际问题，我们给了合理的假设1.假设送货员的最大载重是50公斤，所带货物的最大体积为1立方米；2.每件货物交接花费3分钟，同一地点有多件货物也简单按照每间3分钟交接计算；3.要求到达的时间不包括此次在该点交接的时间；4.所用的距离数据到精确到米，时间精确到0.01h；5..在满足时间限制的条件下，顾客能够更早的拿到货物顾客的满意度越高；6.送货员在多次经过同一送货地点时在第一次经过交接货物效率最高；四符号说明与变量G 表示加权无向图V 无向图中的点集E 链接点集中点的所有边的集合W(e) e边的权重即现实中的距离图中任意两点见的最短距离Cij用翻转矩阵法求解的最终解果PijM 一个极大值表示图中两点不可达五模型的建立与求解5.1 问题一我们将问题就归结为求最优Hamilton 圈问题，采用矩阵翻转法来实践二边逐次修正法过程，中间需要用到Floyd算法求出任意两点只见最短距离,从而求出最优Hamilton 圈。

算法过程为：用矩阵A描述出图，)iA表述i点到j点的距离，将不能直(j,达的点的距离赋一个很大的数，先用Floyd算法求出任意两点见最短距离，得到矩阵B，再用矩阵翻转法求出最优Hamilton 圈。

基本概念：（1）令)G=为一个加权无向图，其中{}V,(E,2,1=为顶点集合，,3vvnvvV,E为边集合。

图G 中每一条边e 都对应一个实数)(e w ，则称)(e w 为改变的权。

若任意两点均有边相连，称G 为完备图。

（2）距离矩阵：对无向图G ，其距离矩阵n n a A ij ⨯=)(，其中ji ij a a =为i ，j两点间的距离。

（3）Hamilton 图：设),(E V G =是连通无向图，经过G 的每个顶点正好一次的圈，称为G 的一条Hamilton 图，简称H 圈；含H 圈得图称为哈米尔顿图或H 图。

（4）最佳H 圈：在加权图),(E V G =中，权最小的Hamilton 圈称为最佳 （5）矩阵翻转：在一个矩阵中，对它的第i 行（列）到第j 行（列）翻转是以第i 行（列）和j 行（列的）中心位置为转轴，旋转180度，这样，第i 行（列）和第j 行（列）的位置互换，第1+i 行（列）和第1-j 行（列）位置互换，……二边逐次修正法的算法过程如下：（1）任取初始H 圈: 1210,,,,,v v v v v v C n j i =；（2）对所有j i ,，nj i <<+<11，若),(),(),(),(1111+++++<+j j i i j i j i v v w v v w v v w v v w 则在CO 中删去边),(1+i i v v 和),(1+j j v v 而加入边),(j i v v 和),(11++j i v v ，形成新的H 圈C ，即111121,,,,,,,,,v v v v v v v v v C n j i j j i ++-=；（3）对C重复步骤（2），直到条件不满足为止，最终得到的C 即为所求． Floyd 算法的基本思想：主要用于计算所有节点对之间的最短路,其基本是从代表任意两个节点i v 到j v 经过一次经转的所有可能路径，经过比较后选出最短路，代替)0(D中对应的路径，迭代出距离矩阵)1(D , )1(D 中各元素表示通过一次迭代后网络中任意两点间最短路，也即网络中任意两点之间直接到达或只经过一个中间点时的最短路。

在此基础上依次计算)()1()3()2(,,,k k D D D D - ，其中对应的元素表示任意两点间不经过中间点或最多允许经过12-k 个中间点时的最短路。

当)()1(k k D D =-时，表明得到的带权邻接矩阵)(k D 反映了所有顶点对之间的最短距离信息，称为最短距离矩阵。

（程序见附表）5.1.1 模型的建立此题共有50个目标点，加上出发点原点O共51个点，要求将货物送往目标点，且用的时间最短，则必须知道目标点和原点O的距离（令O点为第51个点），及各个点之间的坐标距离ijd。

此图并不是每个点都相连，有些点不能直接到达，所以要先列出此题的权矩阵ijc，然后求出它们之间的最短距离ij p和最短路径ij q则模型规划如下：∑∑---+-=51151122)()(i jjiyiijyyxxd，∑∑---+-=51151122)()(i jjiyiijyyxxp，51,,1=i；51,,1=j利用MATLAB软件进行计算，编程结果得：ijd取值情况如下表所示：1 2 3 4 …48 49 50 511 0 7740.2 1916.3 5452.7 …16603 14854 14871 7959.72 7740.2 0 5825 2292.6 …14331 17770 16159 122653 1916.3 5825 0 3536.4 …15670 15212 14774 8537.94 5452.7 2292.6 3536.4 0 …14493 16475 15266 104995 6583.6 1252.9 4669.4 1161.4 …13993 16758 15310 110846 1294.3 8679.2 2940.1 6391 …16289 13806 14043 6876.87 1968.2 8750.7 3242.5 6492.8 …15566 12973 13200 6049.1∶∶∶∶∶…∶∶∶∶46 15588 13968 14780 13901 …1494.1 9268.5 5739.6 1068847 14125 15339 13988 14445 …6857.9 3888.1 822.34 7095.848 16603 14331 15670 14493 …0 10694 7138.9 1209449 14854 17770 15212 16475 …10694 0 3568.8 6933.950 14871 16159 14774 15266 …7138.9 3568.8 0 7680.951 7959.7 12265 8537.9 10499 …12094 6933.9 7680.9 0ijc得取值情况如下表：12345 (4748495051)10M1916.3M M…M M M M M2M0M2292.61252.9…M M M M M31916.3M03536.4M…M M M M M4M2292.63536.40M…M M M M M5M1252.9M M0…M M M M M﹕﹕﹕﹕﹕﹕﹕﹕﹕﹕﹕﹕47M M M M M…0M M M M48M M M M M…M0M M M49M M M M M…M M03568.8M50M M M M M…M M3568.80M51M M M M M…M M M M0此表中的M表示相应两点不能直接到达，数值表示两点间可以直接到达的距离值，0表示自身到自身的距离利用Floyd算法求得ijp，ij p取值情况如下表所示1 2 3 4 5 …47 48 49 50 511 0 7745.3 1916.3 5452.7 8998.3 …16277 18761 20306 16989 100682 7745.3 0 5829.1 2292.6 1252.9 …22427 18002 26325 22757 162963 1916.3 5829.1 0 3536.4 7082 …16676 17856 20705 17388 104674 5452.7 2292.6 3536.4 0 3545.6 …20212 20295 24242 20924 140045 8998.3 1252.9 7082 3545.6 0 …21174 16749 25073 21504 16563 ﹕﹕﹕﹕﹕﹕﹕﹕﹕﹕﹕﹕47 16277 22427 16676 20212 21174 …0 11253 8943.5 5374.7 9215.848 18761 18002 17856 20295 16749 …11253 0 10708 7139.6 1580649 20306 26325 20705 24242 25073 …8943.5 10708 0 3568.8 1172250 16989 22757 17388 20924 21504 …5374.7 7139.6 3568.8 0 9928.151 10068 16296 10467 14004 16563 …9215.8 15806 11722 9928.1 05.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 的距离最短即可。