缴费站设置问题0725(含代码程序)

选址问题研究摘要：本文研究的是某城市多个社区多个服务站选址及领导巡视路线的优化问题。基于该城市各社区居民数的数据表，我们首先将一些数值变量（如社区居民人数、两地距离）用符号变量的形式表示。针对问题一，我们提出了基于Floyd算法的模型，并应用Matlab软件求得所有社区的最小距离矩阵和最小路径矩阵，然后利用Lingo软件得到如下结论：合理的缴费点选址方案为M、Q、W；居民与最近煤气站之间的平均距离最优值为11.7118百米。针对问题二，我们将时间约束转化成距离约束，在此约束条件下用Lingo软件求得在该城市建立的最少派出所数为3，同时考虑到派出所个数与建造成本的关系，我们确定派出所个数为3个。再在最少派出所数的约束条件下利用Lingo软件确定各个派出所所在位置K、Q、W及其管辖区域。针对问题三，可转化为三个售货员的最佳旅行售货员问题。先用Matlab软件Prim算法编程计算得到加权网络图的最小生成树，按照一定原则将最小生成树分成三块，每一块都转化为一个最佳旅行售货员问题；同时引入均衡度的概念，在保证单个巡视路线最短距离的最大值较小及总路程最短且满足各组尽可能均衡的前提下得到最终的最优化模型。关键词：Floyd算法约束条件Prim算法最优化模型1.问题重述及分析1.1问题重述某城市共有24个社区，各社区的人口（单位：千人）如下表表1编号ABCDEFGHIJKL人口10121861015487111311编号MNPQRSTUVWXY人口11892214871015281813各社区的道路连接如下图，其中连接线表示有道路相通，连接线上数字表示两地距离（单位百米），圆圈内数字是位置序号。VCDGUFEIQSRATWXBJYLHNKMP101587971410611128920241615182211661223810118111510251519928810911819图1（注：横线上的数据表示相邻社区之间的距离，单位：百米）（1）为了方便社区居民缴纳煤气费，煤气公司现拟建三个煤气缴费站，问煤气缴费站怎样选址才能使得居民与最近煤气站之间的平均距离最小。(2)市公安局拟在该城区建立若干个派出所，请为派出所分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有警察（警车的时速为50km/h）到达事发地，问设置多少个派出所比较合理，位置选在哪？(3)社区W是市政府所在地，市领导从W出发巡视，分三组巡视所有社区，为了尽快完成巡视，请问如何安排巡视路线。1.2问题分析本问题是一个基于图论的离散选址优化问题，各个居民点、缴费点和派出所都位于网络节点上，居民点区位确定，缴费点和派出所作为被选点，各个居民点之间有连线（交通线路）相连。但所给图中很多因素是定性变量，为了用数学模型分析，必须先将这些变量进行量化，因此需要用到了虚拟变量的知识。(1)对于问题一，可以利用以下两个标准来判断缴税点的设立是否合理：第一，各个居民点的居民与最近的缴费点的平均距离的长短；第二，各个缴费点缴费的居民数量的大小。具体实现时，应先列出各个居民点之间的带权邻接矩阵，然后利用Floyd算法，得到各个点之间的最短距离矩阵和最短路径矩阵。之后，根据最短路径矩阵，利用Lingo程序求得三个缴费站点所在位置及各个居民点的居民与最近的缴费点的平均距离。(2)对于问题二，要求在相应的时间限制下，使中心选址问题达到最优需要在该城市建立的派出所站点个数。根据警车的行驶速度50km/h以及反应时间限制3分钟，得出派出所所在站点与相应区域内的点的最大距离应小于d50*3/602.5km/h25（）＝（百米）,运用中位点问题模型，采用参数规划的约束法，可以很好的解决该问题。(3)对于问题三，要求分三组（路）巡视，得到总路程最短且各组尽可能均衡的巡视路线，可转化为三个售货员的最佳旅行售货员问题。先用Matlab软件编程计算得到加权网络图的最小生成树，按每块近似有相等总路程的标准将最小生成树分成三块，每一块都转化为一个最佳旅行售货员问题。再确定总路程最短且满足各组尽可能均衡的路线的目标函数，最后对目标函数适当改进，得到最终的双目标最优化模型。2.模型的假设为了便于建立模型，考虑了一些实际情况，做出了以下假设，假设系统满足如下一些条件：对于模型一（1）各社区人口基本保持不变，且区域内所有居民都须缴费；（2）每个社区的居民只能到离该社区最近的缴费点缴费；（3）假设同一居住点的所有居民都选择相同的缴费点缴费；对于模型二（5）假设警车在到达事故发生点的途中没有障碍，即不考虑路况和其他情况的影响，警车按照其行驶速度匀速行驶直至到达事故发生点；（6）假设每个社区的突发情况只有离该社区最近的派出所来解决；（7）假设不考虑派出所的反应时间，接到报警的瞬间，派出所即派人前往；对于模型三（8）假设模型三中各组在巡视过程中，路途通畅，无任何延误时间；（9）各组行驶车速都相同，并且匀速行驶；3.符号的说明12,24(,...,)Xxxx：24个居民点组成的24维向量（ix表示第i个居民点的编号）12,24(,...,)：24个居民点的居民数量组成的24维向量（iw表示编号为i的居民点的居民数量）ijd：居民点i到缴费点j的距离jj10iijixxXxx，点的居民到缴费点缴费，点的居民不到缴费点缴费1C0iijixx，点建立缴费点，点不建立缴费点S：居民总人数4.模型的建立、求解及结果分析通过阅读题目和相关资料，我们发现该类选址问题属于图论和运筹学的范畴，查阅相关文献及资料我们分别建立了以下三个模型。4.1模型一4.1.1模型的建立设12,24(,...,)Xxxx为24个居民点，居民点ix有居民iw人，由道路相连的居民点ix和jx的距离为(,)ijddij，现在选择3个居民点建立缴费点，使得居民到最近的缴费点的平均路程最小。这里的平均路程是指每一个居民点ix中的居民iw人与他们到最近的缴费点之间的距离的乘积之和除以所有居民点的总人数，即：1/iniijixXiwdw由于居民总数1niir为定值，则只需考虑iiijxXwd。此题从目标函数来看是求平均距离的最小值，即min()iiijxXwd目标函数：111min(,)/nmniijijiijifZYwdXw约束条件：2412412424113(1)1,24(2),24,24(3)..iiijjijjiijijCXiXCijstwXS241(4)0,24(5),01(6)iijiiijwXiCX都是（，）变量其中，式(1)为服务中心个数的约束条件；式(2)为同一个点的居民会到同一个缴费点缴费的约束条件；式(3)表示如果不在jx建立缴费点，其他点的居民就不会到jx缴费，即当时0jC时，所有的0ijX；式(4)为每个缴费点服务人数小于居民总人数的约束条件；式(5)为每个缴费点的服务人数都大于零的约束条件。由题意假设1224{,,}Xxxx为24个居民点，相应的居民量为10,12,18,6,10,15,4,8,7,11,13,11,11,8,9,22,14,8,7,10,15,28,18,13W4.1.2模型的求解第一步：给出任意两个居民点之间的直线距离（由图1可知），如果这两个居民点之间没有直接的路，则把这两个居民点之间的距离记为，再将这些距离写成矩阵的形式，记为a，其中矩阵a中的元素ija表示居民点ix和jx之间的距离（矩阵见附录）。第二步：在Matlab软件中用Floyd算法算出每两个居民点之间的最短距离矩阵D和最短路径矩阵PATH。其中ijD表示从点ix到点jx沿图1中所示连接线所走的最短距离，ijPATH表示从点jx到点ix沿图1中所示连接线所经过的第一个点（比如，要寻找从13x到1x的路径。根据PATH矩阵，如果(13,1)10PATH，(12,1)22PATH，(3,1)1PATH，则说明从13x到1x经过10x，从12x到1x经过22x，3x到1x直接相连；如果(3,4)4PATH，说明4x与3x直接相连；(17,1)1PATH，说明17x与1x直接相连。）第三步：把距离矩阵D代入建立的规划模型中，该模型建立的方程是以所有居民所走的总路程的平均距离最短为最优，由11.0Lingo穷举法计算得到结果如下：选择M，Q,W居民点为缴费点，此时所有社区居民所走的最短平均路程为11.7118百米。将数据整理如下表：表2模型一数据分析缴费点ixMQW到缴费点ix的居民点J、K、M、N、P、U、L、Y、HD、Q、R、S、V、TA、B、C、E、F、G、I、W、X到缴费点jx的总人数9472122居民总数288（千人）平均每位居民所走路程11.7118百米注：本文所涉及人数单位均为千人，距离单位均为百米。各个居民点居民的具体缴费去向如下图所示：VCDGUFEIQSRATWXBJYLHNKMP101587971410611128920241615182211661223810118111510251519928810911819图2图示说明：同一颜色圈内的居民到同一点缴费，其中带黑框的圈为缴费点数据分析：从上图和上表可以看出，在本模型中，很大一批人选择去W缴费点去缴费，为了更清晰的对比3个缴费点的缴费人数，我们利用Matlab绘制三维饼状图如下：W缴费点42.36%Q缴费点25.00%M缴费点32.64%图3到各个缴费点的居民数量饼状图4.1.3模型的结果分析由计算结果及表2、图2和图3可知，去3个缴费点人数虽然有一定的差距，即去W缴费点的人数占了42.36%，而去Q缴费点的人数只有25.00%，相差17.36%，人数分配不够均衡，但总体看来，该模型能够较好地符合实际情况，区域和人数分配基本合理。我们可以通过设置营业厅的大小及办理窗口个数来弥补此模型存在的不足，对于人数压力比较大的区域及缴费点，我们可以多设置一定数量的办理窗口来应对较大的缴费办理客流量；而对于人数压力相对较小的区域及缴费点，我们可以设置相对较少的窗口以免造成资源的浪费。每个社区都到距离最近的缴费点缴费，由最短路径矩阵我们可以知道各社区居民缴费所走路径，如U社区的居民想要到M点缴费，所走路线应为：U－J－N－M，A社区居民到W点缴费所走路径应为A-X-W,而不是A-C-W。这样，所有居民到缴费站点的平均距离才会达到最短。4.2模型二4.2.1模型的建立在已知警车运行速度的前提下，我们将时间约束转换成最远距离约束，即最远行车距离为25百米。利用模型一得到的最短路径矩阵，根据这一最远距离约束，结合Lingo软件程序，可以知道至少需要建设多少个派出所才能覆盖整个城市的24个居民点。模型如下：目标函数：min241ijcC约束条件：2411(1)..0(2)25(3)ijjijjijijxstxcdx模型说明：约束（1）使p中心问题得到最优，城市内每个点仅被一个派出所覆盖；约束（2）在jx点建立派出所后它