建模 选址 巡视 图论

第1页共25页选址问题摘要本文以图论模型为基础，通过图1中各社区道路连接情况，我们构造出一个无向图G＝（V（G），E（G）），然后分别对多源最短路问题、多目标优化问题、多旅行商问题进行了讨论研究。针对问题一：我们利用“图论的最短路径”思想，建立了一个多源最短路模型，首先用Floyd-Warshall算法计算出社区间最短路径，然后运用matlab软件，得出其与社区人数加权后的值的矩阵，最后利用穷举法，确定了使居民与最近煤气站之间平均距离最小的3个缴费站的位置，最终结果如下：缴费点该缴费点覆盖的社区号M社区号MHJKLNPUYQ社区号QDRSTVW社区号WABCEFGIX针对问题二：我们运用优先等级法，以成本性、效率性、公平性、均衡性五个方面为目标函数，并以三分钟到达为约束建立了多目标最优化模型。我们首先假设建立3个派出所，使用序贯式算法进行求解，并通过优化得出最终结果。最后验证建立2个派出所的情况，得出无法满足条件，最终结果如下：派出所管辖人口出勤距离该派出所管辖的社区K841664HJKLMNPYQ821870DQRSTUVW1221892ABCEFGIWX针对问题三：我们了一个多旅行商问题模型，利用图论的思想，建立了最小生成树，并进行求解。我们以巡视总路程最短为首要目标，并尽量使三个巡视小组行走路程均衡，通过多次优化，得出如下结果：路线路程总路程平均路程W-B-X-A-C-T-E-F-W114365121.7W-G-I-P-K-M-H-Y-F-W127W-C-D-S-R-Q-V-U-J-N-J—F-W124本文最后对所建模型的优缺点进行了分析，并进行了改进和推广。关键词：图论多源最短路多目标规划多旅行商问题第2页共25页1．问题重述1.1问题背景煤气公司计划对某城市24个社区中的缴费站设置、派出所分配管辖范围以及市领导巡视路线问题进行设计。下表1是24个社区的人口数，单位为千人。下图1是此城市内各社区之间主要道路的连通示意图，连接社区之间的弧上标出了它们之间的距离，单位为百米。表1各社区的居民数编号ABCDEFGHIJKL人口10121861015487111311编号MNPQRSTUVWXY人口11892214871015281813各社区的的道路连接如下图：图1：城市各社区道路连接情况VCDGUFEIQSRATWXBJYLHNKMP101587971410611128920241615182211661223810118111510251519928810911819（注：横线上的数据表示相邻社区之间的距离，单位：百米）1.2需解决的问题为了方便社区居民缴纳煤气费，煤气公司现拟建三个煤气缴费站，问煤气缴费站怎样选址才能使得居民与最近缴费站之间的平均距离最小。(2)市公安局拟在该城区建立若干个派出所，请为派出所分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有警察（警车的时速为50km/h）到达事发地，问设置多少个派出所比较合理，位置选在哪？(3)社区W是市政府所在地，市领导从W出发巡视，分三组巡视所有社区，为了尽快完成巡视，请问如何安排巡视路线。第3页共25页2．模型的假设与符号说明2.1模型假设假设1：假设各社区之间以直线路程计算，不考虑路程与时间的关系。假设2：假设三个缴费点之间无特定联系。假设3：假设每个社区的居民只能到最邻近的其中一个缴费点缴费。假设4：假设每次突发事件发生时，警员都从派出所出发，且警力资源充足。假设5：假设出行警察及警车时刻待命（从接到报警电话到上车时间忽略不计）。假设6：假设每个小组的汽车行驶速度完全一样，且汽车在路上的速度总是一定，不会出现抛锚等现象。假设7：假设巡视当中，在每个社区每户居民的停留时间一定，不会出现特殊情况而延误时间。建设8：假设分组后，各小组只能走自己区内的路，不能走其他小组的路，除公共路外。2.2符号说明i社区标号；iP社区i的居民数（单位：千人）；ijD社区i和j间可行的最短距离（单位：百米）；,,abc所选缴费站的社区标号；,,iaibicDDD社区i和,,abc缴费站间可行的最短距离（单位：百米）；k派出所标号；ikD社区i带其管辖派出所k的可行最短距离（单位：百米）；N建设派出所的数量；C建设单个派出所的综合成本；P社区总人口数；kP派出所k辖区内的总人口数；人数对出警的影响系数（该地区的犯罪率等）；V警车的出警时速（单位：/kmh）；mDm巡视小组的巡视路径长（单位：百米）；mGm巡视小组的巡视路线构成的图；第4页共25页3．问题分析此题研究的是多源最短路问题、多目标优化问题及多旅游商问题，均可建立图论模型进行分析。通过图1各社区道路连接情况，我们可以构造出一个无向图G＝（V（G），E（G）），并求出各社区间最短路矩阵。针对问题一：本题的目标是从24个社区内，选出三个煤气缴费站,建立缴费站网络，实现居民与最近的缴费站之间平均距离最小。为了方便社区居民缴纳煤气费，题目要求使得居民与最近煤气站之间的平均距离最小，我们将平均距离这个指标转化为各社区居民人数与该社区到其缴费站的最小距离加权后的累积和。缴费站的位置可以是任意的，我们将通过分析，证明建在社区内比建在相邻社区间的道路上更优。通过计算各社区间的最短路径，然后利用社区居民数目以及道路信息，采用合适方法搜索缴费点，再确定各缴费点管辖区域，直到求得最优解。本问题重点是要解决如何选择缴费点和如何划分缴费区域，即建立合理的最优缴费点搜索和区域划分模型。针对问题二：本题的要求是在24个社区内建立若干派出所，并为派出所分配管辖范围，使其在所管辖的范围内出现突发事件时，能在3分钟内有警察到达事发地。我们首先要保证这个要求，然后考虑成本问题，即派出所数量越少越好；其次考虑效率性，使所建派出出勤总路程最小；在考虑公平性，均衡派出所出勤时间；最后均衡每个派出所管辖的区域人数。根据问题一，假设至少建立三个派出所，通过计算各社区间的最短路径以及与人数加权后的距离值，建立多目标规划模型[3]，采用序贯式算法[3]对其求解，从而确定派出所位置以及区域分配。本问题的重点是要解出建立三个派出所的位置及管辖区域，最后还要证明建立两个派出所不可取。针对问题三：本题的要求是安排三组人巡视24个社区，为了尽快完成巡视，不但要求总路程最短，而且要求三组之间尽可能均衡，显然，路程最短与均衡是不一致的。一般情况下，路程最短不会均衡；极端情况下，一组巡视全部社区，另外两组不动，路程最短但最不均衡。反之，均衡的也不会是最短，如三组中只要有一组尚未完成巡视，则另外两组再转个圈子，等待同时回到市政府，这样达到了尽量均衡，但显然增加了无效路程，路程不会最短。由以上分析知，均衡不是主要矛盾，首先应求最短，然后要求尽量均衡。而巡视时间的长短由路程最长的巡视小组所用的时间决定，欲使总行走时间最短，应使行程最大的巡视组巡视时间尽量小。为此，我们设置目标函数，使三个巡视组的总行程最小，并使三个小组中路程最长者的路程最小，即尽量达到均衡。第5页共25页4．数据分析通过图1各个社区道路连接情况，我们构造出一个无向图G＝（V（G），E（G）），并使用Floyd-Warshall算法计算出社区间最短路径矩阵，其缩略表格2如下，具体表格见附录一：表2社区间最短路径矩阵abcdef…tuvwxya03424283335…344241241646b34037484133…474754221844c2437011917…101817152328d28481102028…212919263439e334192008…6913192719f3533172880…141421111911……………………………………t34471021614…0157253325u42471829914…15015253325v415417191321…7150324032w242215261911…2525320822x161823342719…3333408030y464428391911…25253222300关于问题一，我们根据表2中的数据计算出了各社区之间的距离与社区人数加权后的值，缩略表格3如下，具体见附录三。表3各社区之间的距离与人数加权后的值abcdef…tuvwxya0340240280330350…340420410240160460b4080444576492396…564564648264216528c4326660198162306…180324306270414504d168288660120168…126174114156204234e33041090200080…6090130190270190……………………………………s16043215264224288…232296216272288376t238329701474298…010549175231175u42047018029090140…1500150250330250v615810255285195315…1052250480600480w672616420728532308…7007008960224616x288324414612486342…5945947201440540y598572364507247143…3253254162863900第6页共25页通过图一的信息，将各社区间的连通情况做成表4，数字部分为从一个社区到另一社区的连通条数，NO表示不连通。缩略表格4如下，具体见附录三。表4各社区间的连通情况abcdef…tuvwxya0NO24NONONO…NONONONO16NObNO0NONONONO…NONONO2218NOc24NO0119NO…10NONO15NONOdNONO110NONO…NONONONONONOeNONO9NO08…69NONONONO……………………………………tNONO10NO6NO…0NO7NONONOuNONONONO914…NO015NONONOvNONONONONONO…7150NONONOwNO2215NONO11…NONONO08NOx1618NONONONO…NONONO80NOyNONONONONO11…NONONONONO0关于问题二：我们将表2中的数据做如下处理：将两社区间的最短距离其中大于25（单位：百米）的数据排除掉不作考虑，然后根据表4的连通关系再次将两社区间的最短距离大于25的舍掉，最后再从中选择符合约束条件的点。关于问题三：我们用Matlab软件画出以W为根的最小生成树(程序见附录)，如下图2所示：图2以W为根的最小生成树第7页共25页从图2中我们可以看出，从树根W出发的共有五个干枝。各干枝分别为（括号内为两点之间的距离）：干枝一：W(22)B干枝二：W(8)X(16)A干枝三：W(15)G(10)I(19)P干枝四：W(15)C(11)D(8)SD(9)Q(7)R干枝五：W(11)7)VF(8)E(6)T(F(14)UL(8)J(6)NL(9)MF(10)(11)KF(11)Y(8)H5．问题一的解答5.1证明结论假设一个城市有i个社区，n个缴费站，则将缴费站设立在社区可使得居民与最近缴费站之间的平均距离最小。证明假设在任意两个相邻两社区iC和jC之间的道路上设立缴费站，则居民必须经过iC或jC缴费。设：经过社区iC缴费的人数和其与iC的最小距离加权后的值为1f，经过社区jC缴费的加权值为2f，社区iC和jC之间的距离为d，缴费站与社区iC的距离为x。则，居民人数与其到缴费站最小距离加权后的和值为：12()ffxfdx122()ffxfd若=12ff，则f为定值，缴费站设立在社区iC和jC、或者两社区之间道路上的任意一点，缴费人数与其到缴费站相应最小距离加权后的和值均可达到最小。若12ff，则当=0x时，f最小，即缴费站应设立在社区iC。若12ff，则当=dx时，f最小，即缴费站应设立在社区jC。同理可得，城市有i个社区，n个缴费站时，将缴费站设立在社区，缴费居民的人数