缴费站选址问题.doc

论文题目：缴费选址问题摘要本文根据社区的公路网络图，求解不同条件下的选址问题，及分组巡视问题。文中首先将网络图转换为赋权连通图。对于问题一，本文首先通过赋权连通图求出社区间的邻接矩阵，通过floyd算法求出任意两点间的的最短距离，通过matlab编程利用枚举法，在24个社区中任意求出三点，求出这种情况下居民与最近煤气站的平均距离，再找寻满足平均距离最小的三点，即可求解，三点为m、q、w社区。对于问题二，首先假设派出所对某个社区的覆盖度是二元的，引入决策变量，建立了0-1整数规划模型，以确保24个社区均被覆盖，同时要满足警察局在3分钟之内赶到事发社区。考虑到派出所的成本，显然设置个数越少越好，在任意两社区的最短距离已知的情况下，则此问题转换为非线性规划问题，目标函数即为派出所个数。通过lingo编程，可快速求出派出所的个数为3，设置在d、k、w社区。对于问题三，为分组巡查问题，实质为多旅行商问题，首先将社区的赋权连通图简化为生成树，其中各顶点到w点的权值最小，再以树干为基础分为三组，分组后依据分组情况画出最佳旅行商路径并在lingo中编程求出每组最小权值，选出最优路径如下图表一：表一组号巡视路线总路程路线总长度平衡度1w-l-y-h-k-m-n-j-u-e-f-w1103405.98%2w-g-i-p-i-b-w1133w-x-a-s-d-q-r-v-t-c-w117关键词: floyd算法 枚举法 0-1规划 非线性规划 多旅行商问题一、问题重述某城市共有24个社区，各社区的人口（单位：千人）如下表编号abcdefghijkl人口10121861015487111311编号mnpqrstuvwxy人口11892214871015281813各社区的的道路连接如下图（注：横线上的数据表示相邻社区之间的距离，单位：百米）（1） 为了方便社区居民缴纳煤气费，煤气公司现拟建三个煤气缴费站，问煤气缴费站怎样选址才能使得居民与最近煤气站之间的平均距离最小。(2) 市公安局拟在该城区建立若干个派出所，请为派出所分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有警察（警车的时速为 50km/h）到达事发地，问设置多少个派出所比较合理，位置选在哪？(3) 社区w是市政府所在地，市领导从w出发巡视，分三组巡视所有社区，为了尽快完成巡视，请问如何安排巡视路线。二、假设说明假设1：各社区没有人数的迁入迁出；假设2：同一社区的居民到同一缴费点交费；假设3：每个派出所有足够的时间去处理管辖范围内的突发事件；假设4：每个社区只能被一个派出所管辖；假设5：派出所接到报警后能立即出警，中间没有延误；假设6：每组从县政府同时出发，且行驶速度相同；假设7：行驶过程中汽车不会出现故障；假设8：市领导从市政府出发巡视完后回到市政府。三、符号说明符号符号说明1-24个社区24个社区所给数据构成的距离矩阵24个社区两两之间的最短距离矩阵社区的人数所有居民到缴费站的总距离24个社区中任意3个社区社区派出所的个数分组后第k组的tsp回路路程均衡度第个加权网络图第个顶点集社区i与社区j之间的最短距离第i个分组巡视的社区个数soi(n)从点到城镇的第n种路径的权值ki访问某镇或村一次所用的时间ki从o点径直访问第点往返所用的时间ki从o点径直访问第点附加访问其它城镇所用的时间maxki从o点径直访问第点往返所用的最大时间四、问题分析此题研究的是在各社区人数、社区之间的距离已知的情况下，寻找合理的路径，确定缴费站、派出所的位置使结果最优。在市领导巡视路线的问题中，要求市领导从市政府出发巡视完后回到市政府，可以利用图论中的最佳旅行商回路方法来解决。针对问题一：本题主要求三个煤气缴费站怎样选址时使居民与最近煤气站之间平均距离最小，而居民的总人数已知，即要使所有居民到煤气站的总距离最小。假设每个社区的居民到同一个缴费站交费，则每个社区的居民到煤气站的总距离等于该社区的人数与该社区到缴费站的距离之积。只有每个社区到缴费站的总距离都最小，才能使目标函数最优。所以先确定24个社区两两相互间的最短距离，设任意三社区x、y、z为所设的三个缴费站，则每个社区到缴费站的最小总距离为该社区的人数乘以该社区到x、y、z三个缴费站中的最小距离，所有居民到煤气站的总距离为24个社区到缴费站的最小总距离之和。而x、y、z三个缴费站是24个社区中任意三个地点，具体是哪三个社区不确定，有种情况，所以用穷举的方法来确定社区的位置使所有居民到煤气站的总距离最小。针对问题二：社区发生突发事件时要有派出所出来管辖，首先假设每个社区要么被其中一个派出所完全管辖，要么被完全不管辖，即覆盖度是二元的，所以考虑到用0-1整数规划模型。当派出所所管辖的范围内出现突发事件时，尽量能在3分钟内有警察（警车的时速为 50km/h）到达事发地，即派出所距发生突发事件的地方的最大距离为25百米。而且当每个社区有突发事件发生时，都只有一个派出所到达现场处理事件。建立派出所需要投入成本和警务资源，要使派出所的个数比较合理，所以建立的派出所个数越少时成本越少，结果为最优，即目标函数为派出所的个数。既而确定派出所的位置。针对问题三：由于问题要求分三组巡视，且要尽快完成巡视，即要使巡视总路程最短且各组的巡视路线尽可能均衡。为了解决此问题，我们先画出各个点到w点的最短路径图(如图一)，此图有5个分支，为使巡视路线均衡，我们较为均匀地分为三组路线，（见附录6）,分别计算两种分法的最短巡视路线和均衡度，然后取最优。五、数据分析5.1猜想一个城市有个社区，个缴费站，则将缴费站设立在社区可使得居民与最近缴费站之间的平均距离最小。证明:假设在任意两个相邻两社区和之间的道路上设立缴费站，则居民必须经过或缴费。设：经过社区缴费的人数和其与的最小距离加权后的值为，经过社区缴费的加权值为，社区和之间的距离为，缴费站与社区的距离为。则，居民人数与其到缴费站最小距离加权后的和值为： 若=，则为定值，缴费站设立在社区和、或者两社区之间道路上的任意一点，缴费人数与其到缴费站相应最小距离加权后的和值均可达到最小。若，则当时，最小，即缴费站应设立在社区。若，则当时，最小，即缴费站应设立在社区。同理可得，城市有个社区，个缴费站时，将缴费站设立在社区，缴费居民的人数与其到相应缴费站最小距离加权后的和值最小，即居民与最近缴费站之间的平均距离最小。5.2求图中24个社区中任意两点间的距离根据图中24个社区间的距离，要求赋权图中任意两点间的最短路。采用floyd算法得出了图中任意两点间的最短距离。结果如下表一：表一：任意两点间的最短距离（百米）abcdefgstuvwxya034242833353920344241241646b340374841333754474754221844c24370119172819101817152328d28481102028398212919263439e33419200819286913192719f35331728801136141421111911g393728391911047252532152322s20541982836470293727423647t3447102161425290157343325u42471829914253715o15253325v41541719132132277150324032w24221526191115342525320822x16182334271923363333408030y4644283919112247252532223005.3以w为起点到各顶点的最短路程生成树以w为起点到各顶点的最短路程生成树如下图一：图一：到w的最短路径生成树 六、模型建立6.1模型一的建立：要使居民与最近煤气站之间平均距离最小，居民的总人数已知，即求所有居民到煤气站的总距离最小，先确定24个社区两两相互间的最短距离。 任意选三社区为缴费站，选取这24个社区到三缴费站的最小距离与该社区的人数相乘，其总和为所有居民要走的总路程；再变换三社区的位置（有种情况），取这些总路程中的最小值，最后用这个最小值除以所有人数即为目标函数。目标函数l:其中为社区的人数，为24个社区中任意3个社区，分别为社区到三社区的最短距离；6.2 模型二的建立考虑使用0-1整数规划模型，下面确定目标函数和约束条件。假设每个派出所有足够的时间去处理管辖范围内的突发事件，即当某个派出所处理一起突发事件的同时，在它所管辖的区域内不会发生其他的突发事件。设问题的决策变量为是0-1变量，即建立派出所需要投入成本和警务资源，要使派出所的个数比较合理，所以建立的派出所个数越少时成本越少，结果为最优。即目标函数:然后确定五个约束条件:一是要求任一派出所到达其所管辖的社区的时间都小于3分钟，即派出所距发生突发事件的地方的最大距离为25百米；二是当每个社区有突发事件发生时，有且只有一个派出所到达现场处理事件；三是j社区派出所的个数可以为0或1；四是j社区发生突变事件时，有派出所来参与管辖；五是保证社区j派出所个数大于等于决策变量；综上所述，问题二的最优化模型是6.3 模型三的建立因为最小生成树包含图中所有顶点，而且最小树的边权是相邻顶点之间的距离，故可考虑用最小生成树进行分块。现在对已经得到的最小生成树（如图一）进行分解，以获得三个子图使得分解结果尽量均衡。6.3.1 确定目标函数为使总巡视路线尽可能短且每组巡视路线尽可能均匀，我们确立了两个目标函数。1：分成的三组回路中每组回路对应的权值w(ck)最小令，则所以 2：均衡度a最小:我们定义为该分组的实际均衡度，显然。越小说明分组的均匀性越好。因此所以我们建立了一下目标函数：6.3.2 确定约束条件在加权网络图g中，将顶点集v划分为v1 , v2, v3,则g的三个子图为gv1, gv2, gv3,需满足一下几个条件1:顶点o包含在每个顶点集vi 中，即o vi，i=1,2,32：顶点集vi为v（g）的子集，即3：在加权图g中，g的三个子图gv1, gv2, gv3,必须形成一条回路，即由此得到问题三的最优化模型为：七、问题求解及结果分析7.1 模型一7.1.1 模型一的求解为了求解24个社区任意两社区之间的最短距离，可以采用floyd算法。floyd算法比dijkstra算法更方便有效，dijkstra算法只是求解单源点无负边最短路径，而floyd算法可以求解任意两点间的最短路径。floyd算法在matlab中运行程序见附录一。24个社区之间的最短距离见附表二d矩阵。用穷举的方法求出三个缴费站为13、16、22号，即三个缴费站建在m、q、w三个社区才能使居民与最近煤气站之间平均距离最小，平均距离为11.7118百米，源程序见附录三。各社区到缴费站的路径图如下图二：图二7.1.2模型一结果分析三个缴费站中，q收缴费站所负担的权最少，可以适当减少设施人员以节省成本。w、m缴费站负担的权均重些，所以w、m站设施人员方面需准备更充分及应急措施。7.2 模型二7.2.1 模型二的求解为了设置合理的派出所个数，尽量使派出所的个数最少，我们将派出所个数的最小值作为目标函数，确定相应的约束条件，借助lingo软件求解，得到设置3个派出所比较合理，三个派出所的序号为4、11、22即派出所建在d、k、w三个社区里。程序见附录四7.2.1模型二结果分析根据三个派出所的地点，可画出24个社区到d、k、w三个派出所的距离表格如下表二：表二：各社区到d、k、w三个派出所的距离（百米）abcdefghijkld28481102028394749375838k65634758383041114224021w242215261911153025294121mnpqrstuvwxyd4743669168212919263439k121823576466443247414919w3035443532342525320822各社区发生突发事件时由距该地区最近的派出所参与管辖，三个派出所各自管辖的社区及最短距离如下表三：表三：三个派出所各自管辖的社区及最短距离abcdefghijkld110k1124021w24221911152521mnpqrstuvwxyd91682119k12182319w253208由上表可知：24个社区到d、k、w三个派出所中的最小距离都小于25百米，符合题目要求。且l社区距k、w社区的最小距离都为21百米，即l社区发生突发事件时k、w社区都可以参与管辖。7.3 模型三7.3.1 模型三的求解首先我们对数据进行处理，表示为邻接矩阵的形式。并求出以w点为根的最小生成树，然后根据我们确定的分组原则把最小生成树大致分成三组，分组后依据分组情况画出最佳旅行商路径并在lingo中编程求出每组最小权值，得出最优路径为下表：表四组号巡视路线总路程路线总长度平衡度1w-l-y-h-k-m-n-j-u-e-f-w11035436.24%2w-g-p-i-b-a-x-w1493w-c-t-v-q-r-s-d-w95由表分析知平衡度达到36.24%，误差很大。通过对路线分析，将第二组的a,x点加到第三组，得出以下结果，如下表： 表五组号巡视路线总路程路线总长度平衡度1w-l-y-h-k-m-n-j-u-e-f-w1103405.98%2w-g-i-p-i-b-w1133w-x-a-s-d-q-r-v-t-c-w117根据以上结果，求出均衡度为比较小，说明结果合理满足要求。相应的路径图如下：图三7.3.1模型三结果分析第二组走过的社区个数最少，与其余两组相差较大，但走过的总路程与其余两组相差不大，均衡度相对较小。八、模型的评价、改进及推广8.1模型评价优点：（1）对于题目中的问题，我们借助于数学软件matlab中基于floyd算法的程序而不是dijkstra算法对模型进行求解，找出了最优化的选址方案， dijkstra算法只是求解单源点无负边最短路径，而floyd算法可以求解所有点间的最短路径，floyd算法比dijkstra算法更方便有效。（2）模型操作性强，只要给出任意图g及各边上的权值，就能够将一个复杂的图g分为若干个子图，大大的降低了解题的难度；缺点：（1）对于问题一中的模型，我们忽略了每个居民的个体差异，认为他们的选择是一致的，因为在没有统一规定或者指导的情况下，他们是可以随意到任意缴费点缴费的；而且我们规定社区的人数不变，这样不符合实际情况。（2）对于问题二中的模型，没有考虑到各个派出所工作的不均衡性。在分配结果中可以看到，部分交巡警的工作量很小而部分交巡警的工作量很大。这显然是不合理的。事实上，可以建立一个多目标规划问题，使得分配管辖范围的方案更加合理。8.2模型改进（1）在问题二中，要求尽快完成巡视，即巡视的总时间尽量最短，但求出来的结果往往不尽人意，每组完成的时间有时相距很大，我们可以让已经完成的那一组去帮助还未完成的那一组，从而可以缩短整体的巡视时间，达到近一步优化模型的目的。（2）建模时可以考虑更多的因素，让模型实用性更强，比如说，如何让巡视过程中花费最小。8.3模型推广本文所建立的模型可以推广到任何一个市区或者更广范围内的交巡警服务平台的设置和调度问题的解决中，也可以解决以满足时间紧迫性为要求的其他类似问题中，如消防站的选址问题、急救中心的选址问题、应急设施选址问题等等。在实际应用中有很强的实用性和通用性。而且问题中用到旅行商问题，该问题可以应用的范围较广，只要是寻求最佳哈密顿圈，该模型均可以作为参考。九、参考文献【1】李海涛，邓樱，matlab程序设计教程，北京：高等教育出版社，2002.【2】 田贵超，黎明，韦雪洁.旅行商问题（tsp）的几种求解方法j.计算机仿真，2006.8（8）：153-157.【3】张先迪，李正良，图论及其应用，北京：高等教育出版社，2005. 【4】谢金星，薛毅，优化建模与lingo软件，北京：清华大学出版社，2005。附录一matlab中 floyd算法 function d,path=floydz(a) %定义函数n=size(a,1); %返回矩阵a的行数d=a;path=zeros(n,n); % 设置将a矩阵赋值给d, 和将path 设为n*n的0矩阵for i=1:n %i从1到n循环 for j=1:n %j从1到n循环 if d(i,j)=inf %如果i到j的最短距离为无穷大 path(i,j)=j; %j 是i 的后继点 end endend for k=1:n %做n 次迭代, 每次迭代均更新d(i,j) 和path(i,j) for i=1:n %i从1到n循环for j=1:n %j从1到n循环if d(i,k)+d(k,j)d(i,j) d(i,j)=d(i,k)+d(k,j) ; %修改长度 path(i,j)=path(i,k) ; %修改路径 end end end end 附录二求解最短路径源代码a= 0inf24infinfinfinfinfinfinfinfinfinfinfinfinfinf20infinfinfinf16infinf0infinfinfinfinfinf28infinfinfinfinfinfinfinfinfinfinfinf2218inf24inf0119infinfinfinfinfinfinfinfinfinfinfinfinf10infinf15infinfinfinf110infinfinfinfinfinfinfinfinfinfinf9inf8infinfinfinfinfinfinfinf9inf08infinfinfinfinfinfinfinfinfinfinfinf69infinfinfinfinfinfinfinf8011infinfinfinf10infinfinfinfinfinfinf14inf11inf11infinfinfinfinf110inf10infinfinfinfinfinfinfinfinfinfinfinf15infinfinfinfinfinfinfinfinf0infinf11inf15inf19infinfinfinfinfinfinfinf8inf28infinfinfinf10inf0infinfinfinfinf19infinfinfinfinfinfinfinf25infinfinfinfinfinfinfinfinf0inf8inf6infinfinfinfinf8infinfinfinfinfinfinfinfinfinfinf11infinf0inf12inf23infinfinfinfinfinfinfinfinfinfinfinfinfinf10infinfinf8inf09infinfinfinfinfinfinfinfinfinf10infinfinfinfinfinfinf15infinf12906infinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinf6infinf60infinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinf1919inf23infinfinf0infinfinfinfinfinfinfinfinfinfinfinf9infinfinfinfinfinfinfinfinfinfinf07infinfinf10infinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinf7012infinfinfinfinfinf20infinf8infinfinfinfinfinfinfinfinfinfinfinf120infinfinfinfinfinfinfinf10inf6infinfinfinfinfinfinfinfinfinfinfinfinf0inf7infinfinfinfinfinfinf914infinfinf8infinfinfinfinfinfinfinfinf015infinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinf10infinf7150infinfinfinf2215infinf1115infinfinfinfinfinfinfinfinfinfinfinfinfinf08inf1618infinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinfinf80infinfinfinfinfinf11inf825infinf10infinfinfinfinfinfinfinfinfinfinf0 ; b,path= floydz (a); d=b最短路径运行结果：d = 0 34 24 28 33 35 39 54 49 50 65 45 54 56 68 37 32 20 34 42 41 24 16 46 34 0 37 48 41 33 37 52 28 51 63 43 52 57 47 57 64 54 47 47 54 22 18 44 24 37 0 11 9 17 28 36 38 26 47 27 36 32 55 20 27 19 10 18 17 15 23 28 28 48 11 0 20 28 39 47 49 37 58 38 47 43 66 9 16 8 21 29 19 26 34 39 33 41 9 20 0 8 19 27 29 17 38 18 27 23 46 23 30 28 6 9 13 19 27 19 35 33 17 28 8 0 11 19 21 18 30 10 19 24 38 31 38 36 14 14 21 11 19 11 39 37 28 39 19 11 0 30 10 29 41 21 30 35 29 42 49 47 25 25 32 15 23 22 54 52 36 47 27 19 30 0 33 26 11 18 15 21 19 50 57 55 33 33 40 30 38 8 49 28 38 49 29 21 10 33 0 39 42 31 40 45 19 52 59 57 35 35 42 25 33 25 50 51 26 37 17 18 29 26 39 0 24 8 12 6 45 33 40 45 23 8 23 29 37 18 65 63 47 58 38 30 41 11 42 24 0 21 12 18 23 57 64 66 44 32 47 41 49 19 45 43 27 38 18 10 21 18 31 8 21 0 9 14 37 41 48 46 24 16 31 21 29 10 54 52 36 47 27 19 30 15 40 12 12 9 0 6 34 45 52 55 33 20 35 30 38 19 56 57 32 43 23 24 35 21 45 6 18 14 6 0 40 39 46 51 29 14 29 35 43 24 68 47 55 66 46 38 29 19 19 45 23 37 34 40 0 69 76 74 52 52 59 44 52 27 37 57 20 9 23 31 42 50 52 33 57 41 45 39 69 0 7 17 17 25 10 35 43 42 32 64 27 16 30 38 49 57 59 40 64 48 52 46 76 7 0 12 24 32 17 42 48 49 20 54 19 8 28 36 47 55 57 45 66 46 55 51 74 17 12 0 29 37 27 34 36 47 34 47 10 21 6 14 25 33 35 23 44 24 33 29 52 17 24 29 0 15 7 25 33 25 42 47 18 29 9 14 25 33 35 8 32 16 20 14 52 25 32 37 15 0 15 25 33 25 41 54 17 19 13 21 32 40 42 23 47 31 35 29 59 10 17 27 7 15 0 32 40 32 24 22 15 26 19 11 15 30 25 29 41 21 30 35 44 35 42 34 25 25 32 0 8 22 16 18 23 34 27 19 23 38 33 37 49 29 38 43 52 43 48 36 33 33 40 8 0 30 46 44 28 39 19 11 22 8 25 18 19 10 19 24 27 42 49 47 25 25 32 22 30 0附录三求3个缴费站的源代码clear all;a=combntns(1:24,3); %定义a为任意三个数组成的矩阵for i=1:nchoosek(24,3) %循环的次数 b=a(i,:); %返回第i行x=b(1,1); y=b(1,2);z=b(1,3); people= 10 12 18 6 10 15 4 8 7 11 13 11 11 8 9 22 14 8 7 10 15 28 18 13; d= 0 34 24 28 33 35 39 54 49 50 65 45 54 56 68 37 32 20 34 42 41 24 16 46 34 0 37 48 41 33 37 52 28 51 63 43 52 57 47 57 64 54 47 47 54 22 18 44 24 37 0 11 9 17 28 36 38 26 47 27 36 32 55 20 27 19 10 18 17 15 23 28 28 48 11 0 20 28 39 47 49 37 58 38 47 43 66 9 16 8 21 29 19 26 34 39 33 41 9 20 0 8 19 27 29 17 38 18 27 23 46 23 30 28 6 9 13 19 27 19 35 33 17 28 8 0 11 19 21 18 30 10 19 24 38 31 38 36 14 14 21 11 19 11 39 37 28 39 19 11 0 30 10 29 41 21 30 35 29 42 49 47 25 25 32 15 23 22 54 52 36 47 27 19 30 0 33 26 11 18 15 21 19 50 57 55 33 33 40 30 38 8 49 28 38 49 29 21 10 33 0 39 42 31 40 45 19 52 59 57 35 35 42 25 33 25 50 51 26 37 17 18 29 26 39 0 24 8 12 6 45 33 40 45 23 8 23 29 37 18 65 63 47 58 38 30 41 11 42 24 0 21 12 18 23 57 64 66 44 32 47 41 49 19 45 43 27 38 18 10 21 18 31 8 21 0 9 14 37 41 48 46 24 16 31 21 29 10 54 52 36 47 27 19 30 15 40 12 12 9 0 6 34 45 52 55 33 20 35 30 38 19 56 57 32 43 23 24 35 21 45 6 18 14 6 0 40 39 46 51 29 14 29 35 43 24 68 47 55 66 46 38 29 19 19 45 23 37 34 40 0 69 76 74 52 52 59 44 52 27 37 57 20 9 23 31 42 50 52 33 57 41 45 39 69 0 7 17 17 25 10 35 43 42 32 64 27 16 30 38 49 57 59 40 64 48 5