选址问题及最佳巡视路线的数学模型.doc

《选址问题及最佳巡视路线的数学模型.doc》由会员分享，可在线阅读，更多相关《选址问题及最佳巡视路线的数学模型.doc（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品文档，仅供学习与交流，如有侵权请联系网站删除本科14组 许泽东，邹志翔，陈佳成选址问题及最佳巡视路线的数学模型摘 要本文解决的问题是缴费站、派出所选址和最佳巡视路线的确定。合理设置缴费站，可以为居民缴费节省大量时间和精力。派出所位置和数量的不同选择，会产生不同的建设成本和管理经费。而最佳巡视路线的确立，可以让领导在最短时间内巡视完所有社区。为解决以上问题，我们建立的三个最优化模型。针对问题一，我们先用floyd算法求出各社区间的最短路，然后用计算机枚举出所有选址方案。对每一种选址方案都会产生一个平均距离，我们以此为指标对方案进行评估。经过合理化推导，我们得出最优解（百米），且此时应该在M,

2、Q,W三社区设置煤气缴费站。针对问题二，我们在问题一求出的最短路基础上，建立了0-1线性规划模型。然后借助matlab软件求得最优解（即应该设置3个派出所），并给出了各派出所管辖范围。这样既满足了每个社区在3分钟内至少能得到一个派出所服务，也为派出所的建设管理节省了不少成本。具体结果如下表3：表3：各派出所管辖的范围派出所所管辖社区KH J K L M N P YQC D E Q R S T U VWA B C E F G I L T U W X Y针对问题三，我们主要运用了模拟退火的方法。我们先利用前面求得的最短路矩阵构建了社区网络的完全图，然后考虑到最优哈密顿圈的求解极其困难，我们连续使用

3、30次模拟退火的方法求得连接各社区的近似最优哈密顿圈。其中，我们对每次求出的哈密顿圈都进行了合理划分，产生了三个子圈，即三组巡视路线。最终得到近似最优解128，见表4。接着，我们还对哈密顿圈划分方法进行了改进，求得近似最优解125（具体结果见表5）。表4：巡视路线图（单位：百米）路线名称巡视社区线路途经社区（未巡视）总路线长度最大的总路线长度LL1W-F-G-I-P-K-H-Y-F-WF115128LL2W-F-L-M-N-J-U-V-Q-R-S-D-C-WF、C128LL3W-C-T-E-C-A-X-B-WC120关键词：最优化floyd算法 0-1线性规划模拟退火 哈密顿圈1.问题重述1.

4、1问题背景社区已是现代都市的的基础，随着城市社会经济的飞速发展，社区与人们生活的联系越来越密切，人们需要在社区解决日常生活涉及的各种利益和需要，因而人们对社区社会生活服务提出更高的要求，而政府也希望能够更好的指导和管理城市社区，社区生活服务建设以及安全保障等问题便由此而生。据某项调查显示，我国七成以上的家庭表示需要更多更好的社会化社区服务，其范围涉及食、住、行、工、学、医、娱、境、安等居民生活的各个方面。与此同时，在我国经济体制改革和城市管理体制改革不断推进的背景下，社区需要承接越来越多的政治、文化、甚至行政功能。1.2问题重述本题便是关于社区服务建设的相关问题。题目给出了如下两项条件：1.

5、某一城市社区的分布情况以及社区之间的路程（见附录二）；2. 各个社区的人口数量（见附录一）。根据已知条件，需要解决如下问题：（1） 为了方便社区居民缴纳煤气费，煤气公司现拟建三个煤气缴费站，问煤气缴费站怎样选址才能使得居民与最近煤气站之间的平均距离最小。（2） 市公安局拟在该城区建立若干个派出所，请为派出所分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有警察（警车的时速为 50km/h）到达事发地，问设置多少个派出所比较合理，位置选在哪？（3） 社区W是市政府所在地，市领导从W出发巡视，分三组巡视所有社区，为了尽快完成巡视，请问如何安排巡视路线。2.模型假设与符号说明2.1

6、模型假设假设1：题目所给的数据真实有效；假设2：缴费站所在社区居民到缴费站的距离为0；假设3：各社区人口稳定，不发生大规模迁移等情况；假设4：社区间公路不发生变化，即不发生大规模修整或者改道情况；假设5：公路不考虑等级差别，也不受交通情况影响；假设6：各条公路段上汽车的行驶速度可以认为是均匀的；假设7：巡视组保持统一行动，即不允许一个巡视组再分为若干个组；2.2符号说明社区编号，即将社区抽象为编号1,2，24的点（=1,2，24）,为了方便运算表达，又将社区编号记为,社区与间的最短路长度任意选取的3个建站位置，其中社区的人口数居民选择的缴费站缴费，其中各社区居民到最近缴费站间的总距离各社区居民

7、到最近缴费站间的平均距离区派出所能否在3分钟内赶到区的判断矩阵在第个社区设置了派出所，则，否则，派出所的总数三组巡视路线的路程哈密顿圈中的分割点由三个分割点分割哈密顿圈后形成的三段路线长度另两个分割点到已确定的一个分割点（即市政府W）的最短距离3. 问题分析本题研究的是有关城市社区服务和安全保障方面的问题。已知该城市有24个社区，各社区都有一定的常住人口；各社区间通过公路连接形成一个交通网络，且各社区间的路径距离也都已知。我们先简单的分析下题目数据情况：（1）社区人口主要集中于W,Q,M,K,X,C等几个城市，这些城市的人口都在10千人以上；（2）社区形成的交通网络可看做是一个复杂的无向带权路

8、径图，即把24个社区抽象为24个点。接着，我们需要解决三个问题：第一是要为建立三个煤气缴费站选址，第二是要为建立派出所选址以及确定派出所的数量，第三是安排巡视路线。对于问题一：在社区，煤气的使用率较高，煤气缴费便成为居民经常要解决的问题。因此缴费站的合理选址将有助于提升居民对社区服务的满意度。这是一个选址问题，此问题的关键是使得居民与最近缴费站之间的平均距离最小，这就涉及到了社区到缴费站之间的距离以及社区人口两个相关量，并且实际生活中，缴费站的设置一般是在人口较集中的社区。我们的做法是：首先确立目标是取得平均距离最小，再用floyd算法求出各社区间的最短路径；其次任意选出了3个社区作为建站位置

9、，并通过matlab软件计算，枚举出所有可能的选址方案。然后在所有的选址方案中，由居民去选择距离其最近的缴费站缴费，所以对于每一种选址方案，都会产生一个由居民的选择所确定的总距离；接着我们再通过matlab软件计算对每一种方案进行评价筛选，直至筛选出最小的；最后，因为平均距离为总距离和总人口的比值，所以也同时取得最小值，此时便得出了最优解。对于问题二：城市社区的安全保障问题是社区居民最关心的问题之一，派出所则是居民安全保障的坚强后盾。社区安全保障也是城市社区建设中不可少的项目之一。此题也是一个选址问题，另外还要求确定派出所的数量。在选址方面要求派出所在其所管辖的范围内出现突发事件时，尽量能在3

10、分钟内有警察到达事发地；在数量上，合理性应为在满足前面的条件下派出所数量尽量少。我们的做法是：首先对24个社区按编号顺序构造一个矩阵。我们设有若干个派出所，若派出所能在3分钟内赶到社区（即，单位：百米），则，否则。若在第个社区设置了派出所，则，否则，。运用floyd算法求出各社区间的最短路径；并通过matlab软件编程循环求解得出矩阵；并通过matlab软件编程循环求出了所以的，并筛选出最小的，即。对于问题三：找出社区巡视的最佳路径方便政府及时的了解社区居民的日常生活情况，并能够及时的满足社区居民对社区服务的需求，以此该模型的建立对于市政府和社区人们都有极大的好处。已知巡视人员分三组由市政府出

11、发进行巡视，而且要求在尽可能短的时间内巡视完所有社区并回到市政府。这属于一类图上的点的行遍性问题，即哈密尔顿和旅行商问题。我们的做法：设三组巡视路线的路程分别为，求出这三组巡视路线中最长的一条，即得到目标函数；接着由floyd算法计算出社区网络的最短路径矩阵，并以此构造连接各社区的一个完全图；运用模拟退火的方法求出连接各节点的一个近似最优的哈密尔顿圈。并设哈密尔顿圈以（或记）即市政府W为起点，依次经过节点。用三个分割点把哈密尔顿圈划分为三段，把作为一个分割点（即市政府W或），在再另外23个点中取两个点与连接刚好形成三个哈密顿回路，采用模拟退火法，最后求出满足目标函数的最佳分割，并取得三个回路。

12、4. 问题一的解答针对问题一，我们建立了模型一4.1模型一的准备针对题目要求，我们对题目数据进行了简单的处理。首先为了便于说明，我们把编号为A,B,C,，X，Y的24个社区抽象为编号1，2,3，24的24个点，为方便运算表达并记为如表1；其次，我们将各社区的的道路连接图用电子表格进行存储以便于数据的分析（见附录）。表1：各社区的人口（单位：千人）社区ABCDEFGHIJKL编号123456789101112人口10121861015487111311社区MNPQRSTUVWXY编号131415161718192021222324人口118922148710152818134.2模型一的建立由题

13、可知，此问题的关键是使得居民与最近缴费站之间的平均距离最小，这就涉及到了社区到缴费站之间的距离以及社区人口两个相关量，即社区缴费站的选址必需考虑这两个相关量。4.2.1确立约束条件为了便于说明，我们把24个社区抽象为24个点，并记为。与间的最短距离为，显然，为0。首先我们通过构造24个社区网络的带权邻接矩阵，再用floyd算法求出各社区间的最短路径；在已知任意社区间的最短路径的条件下，任意选出了3个社区作为建站位置，并通过matlab软件计算，枚举出所有可能的选址方案。设各社区人口数为，各社区到最近缴费站间的总距离为；由常识易知，在所有的选址方案中居民会优先选择距离最近的缴费站缴费，所以对于每

14、一种选址方案，都会产生一个由居民的选择所确定的总距离；设社区的居民做出的选择为，即居民选择的缴费站缴费。则：4.2.2确立目标函数本题的目标是满足居民与煤气站的平均距离最小，为此我们确立了如下目标函数：4.2.3综上所述，我们得到问题一的优化模型4.3模型一的求解由于问题的数据分析求解较为复杂，数据量大，所以我们选择使用matlab软件编程来求解。我们再通过matlab软件计算对每一种方案进行评价筛选，直至筛选出最小的（也同时取得最小值），此时的缴费站设置即为最优解。此时，最小平均距离=11.712百米，煤气缴费站应设在13,16,22号社区，即在M,Q,W号社区；各社区居民应选择的最近煤气缴

15、费站编号如表2：表2：各居民应选择的最近煤气缴费站缴费站社区MH J K L M N P U YQD Q R S T VWA B C E F G I W X4.4模型一的结果分析通过表2，首先从收费站区域分布情况，我们可初步判断出缴费站区域位置分布具有一定合理性；其次从人口角度，M,Q,W人口均超过10千人，Q和W更分别多达22和28千人。因为人口也是影响选址的重要因素之一，缴费站的选址通常位于人口较多的社区，这符合实际生活；最后从模型的角度，我们运用计算机枚举了所有的选址方案，并从居民的角度考虑，让居民从这所有的方案中去选择离自己最近的缴费站进行缴费，我们由居民的选择来确定，再通过计算机对每

16、一种方案进行评价和筛选，最后得出最终目标函数，由此确定了最终的选址方案。所以该模型可靠性更强。5. 问题二的解答针对问题二，我们建立了模型二5.1模型二建立本题的关键在于合理的设置派出所的数目与位置。其合理在于（1）在其所管辖的范围内出现突发事件时，尽量能在3分钟内有警察（警车的时速为 50km/h）到达事发地；（2）各个派出所管辖范围的并集必须覆盖整个社区，即派出所位置的合理性；（3）派出所的管辖范围允许有交集，但应规定其中一个为主要管辖。此时，当突发事件发生时，派出所可以根据实际情况进行选派哪个派出所出警处理。这样有效的避免了诸如道路损坏、交通阻塞或者派出所人手不足等问题；（4）派出所的数

17、量在满足社区安全保障和服务需求的情况下其数量应尽量减少，以减少建设成本和管理经费。5.1.1确定约束条件我们先分别在各社区虚设一个派出所，构造判断矩阵，并做如下约定：若社区的派出所能在3分钟内赶到社区（即，单位：百米），则，否则。然后构造解向量，并约定：若在社区设置了派出所，则，否则。接着利用在问题一中求出各社区间的最短路矩阵定下：图3为使得每个社区都能在3分钟内至少得到一个派出所的服务，我们确立了如下约束条件5.1.2确定目标函数该模型是为了解决派出所设置问题。派出所越多，建设成本、管理经费及工资陈本就越大；派出所越少，就不易满足居民需求。为了合理设置派出所，我们确立了评价指标。即在满足约束

18、的条件下，求解派出所数量的最小值。5.1.3综上所述，我们得到问题二的0-1线性规划模型其中，5.2模型二的求解我们通过matlab软件解得：。此时最优解为，即设置3个派出所比较合理，派出所的位置编号分别为11,16,22，即在K,Q,M三个社区设立派出所。（编程运行结果见附录三）各派出所管辖的范围如下表3：表3：各派出所管辖的范围派出所所管辖社区KH J K L M N P YQC D E Q R S T U VWA B C E F G I L T U W X Y5.3模型二的结果分析通过检验，该方案具有很好的可行性；即（1）派出所在所管辖的范围内，警察能在3分钟内到达所有社区；（2）派出所

19、数量为3个，已是尽可能少，无论去掉其中哪个，都不能满足（1）的条件；（3）位置分布合理，所管辖区域完全覆盖整个城市，又因W为政府所在，故派出所管辖范围有重叠的区域应由派出所W负责主要管辖。6. 问题三的解答6.1模型三的建立该问是关于寻求最佳路线问题，要求分三组从市政府W出发能够尽快巡视完所有社区并回到市政府W。这属于一类图上的点的行遍性问题，即哈密尔顿和旅行商问题，也就是要用若干条闭链覆盖图上所有的顶点，并使某些指标达到最优。6.1.1确立目标函数设三组巡视路线的路程分别为。路程越短，耗时越少，完成巡视的最短时间受到这三组巡视路线中最长路线的制约，故我们确立了目标函数为6.1.2确定约束条件

20、首先我们对社区网络图按最短路重新赋权构造完全图，目的是为了用模拟退火法进行求解。设某次模拟退火求出的近似最优哈密尔顿圈以（或记）即市政府W为起点,依次经过节点。用三个分割点把哈密尔顿圈划分为三段,记其长度分别为；由常识可知，欲使巡视时间尽可能短，则应该把作为一个分割点（即市政府W或），在再另外23个点中取两个点与连接刚好形成三个哈密顿回路，他们的权值分别为。如下图一：图一通过以上我们得出哈密尔顿圈被分割的三段长度为：由确定三个分割点后形成的新的哈密尔顿圈为：即他们的权值分别为：6.1.3综上所述，我们确立了问题三的优化模型6.2模型三的求解定初始温度为120，结束温度为0.001，温度下降速率

21、为0.95，重复模拟退火算法30次，分别求出近似最优哈密尔顿圈。其中，我们对每次求出的哈密顿圈都进行了合理划分，产生了三个子圈，即三组巡视路线。最后得到近似最优解128。该问题的解题模型思想对计算机编程求解的依赖度比较大，因此我们也需要借助源程序来表达我们的解题思路，具体源程序请看附录。经过使用计算机matlab软件编程求出最终结果如下表4：表4：巡视路线图（单位：百米）路线名称巡视社区线路途经社区（未巡视）总路线长度最大总路线的长度LL1W-F-G-I-P-K-H-Y-F-WF115128LL2W-F-L-M-N-J-U-V-Q-R-S-D-C-WF、C128LL3W-C-T-E-C-A-X

22、-B-WC1206.3模型三的结果分析与改进在目标函数分析中已说明，由社区网络重新赋权形成的完全图中一定存在连接各节点的最短闭路径，这个最优解一般难以求出，所以我们只能用模拟退火法经过多次运算求出一个接近最优的哈密尔顿圈。因此我们再在这里分析对比，按图一的思想得出近似最优解128。但考虑图二，虽然被重复行走，但他们却能起到“搭桥”的作用，极可能得到更省时的巡视路线。经过计算的近似最优解125，这与我们的想法是一致的，这也是模型的一种拓展改进方法。下图一、二是关于分割哈密尔顿圈生成的三个子圈。图一的三个回路为：图一：图二的三个回路为：图二：图一 图二模型改进后的路线结果如下表5：（即按照图二的所

23、示方法算出的结果）表5：按照图二进行模型改进后的巡视路线表路线名称巡视社区线路途经社区（未巡视）总路线长度最大总路线的长度LL1W-G-F-L-J-U-J-N-M-K-H-Y-F-WF、J125125LL2W-F-Y-H-P-I-B-X-WF、H122LL3W-X-A-S-D-Q-R-Q-V-T-E-C-WQ1225.模型的评价、改进与推广5.1模型的评价优点：（1）对于问题一，我们较好地利用了计算机的强大功能，枚举出所有情况，得出了满足题意的最优解，有效缩短了居民与最近缴费站的平均距离。（2）问题二是交巡警服务平台管辖范围的合理分配研究，对数据进行深入的分析，运用0-1规划模型，妥善地分配了

24、各个派出所的管辖范围。既节约了成本，又满足了居民需求。（3）模拟退火法除了可以选择不同的参数外，还可以进行反复多次运行，而且每次得到的解可能都不一样，也就比其它算法有更多的选择余地和获得最优解的机会，这对实际应用而言是十分有优势的，因为真正实际问题的求解往往需要在多个方案中进行筛选，以获取最优方案。所以该模型具有很好的实用性。缺点：（1）把各社区抽象为一个点，产生了距离误差。（2）模拟退火具有随机性，只能得到近似解，而且对于节点偏多的网络，运行速度很慢。5.2模型的改进由于时间的限制，未能对模拟退火法的进行更多次的运行。因此，如果时间允许，我们可以增加运行次数，以求得更优越的方案，或者寻找更佳

25、的算法。5.3模型的推广本题的问题一和问题二的最优选址问题也可运用到其它的最优选址问题中去，比如关于消防救援工作最优路径问题、重大生产安全事故应急救援问题、公共交通最优路径问题等。问题三的多旅行商问题模型可推广到交通运输、管道铺设、路线的选择、计算机网路的拓扑设计、邮递员送信、计算机网络通信等众多领域。参考文献1费浦生，羿旭明，数学建模及其基础知识详解，武汉：武汉大学出版社，2006.2胡良剑，孙晓君，matlab数学实验，北京：高等教育出版社，2006.3屈强，陈雪波，matlab的模拟退火算法的实现，鞍山科技大学学报，2003年6月第26卷第3期。4韦芳芳,杨兰兰,柏瑞，灾情巡视路线的设计

26、，数学的实践与认识，1999年1月第29卷第1期。5史彦锋，齐鹤，网络多中心问题的几种算法及其应用，中国教育发展研究杂志，2007年8月第4卷第8期。附录附录一：各社区的人口（单位：千人）编号ABCDEFGHIJKL123456789101112人口10121861015487111311编号131415161718192021222324MNPQRSTUVWXY人口11892214871015281813附录二：各社区的的道路连接（注：横线上的数据表示相邻社区之间的距离，单位：百米）附录五：模拟所用的程序第一问源程序：clear;clc;%求任意社区间的最短路a=input(输入带权邻接矩阵

27、：);D,path=floyd1(a);ss=inf;%列出所有的煤气站选址方案，比较求出最优解fori=1:22for j=i+1:23for k=j+1:24 s=0;%各社区居民会选择距离最近的煤气站缴费%s为对应总距离for ii=1:24 w=min(D(ii,i),D(ii,j),D(ii,k); s=s+w*p(ii);end%逐步比较选择更小的总距离if sssss=s;i1=i;j1=j;k1=k;endendendend%循环结束求出总距离最小值ss%记录在最佳方案下各社区居民选择的煤气站编号forjj=1:24 aa,bb=min(D(jj,i1),D(jj,j1),D(

28、jj,k1);nn(jj)=(bb=1)*i1+(bb=2)*j1+(bb=3)*k1;endfprintf(最小平均距离：%dn,ss/sum(p);fprintf(煤气站位置：%d,%d,%dn,i1,j1,k1);fprintf(各社区选择的煤气站：n);num2str(nn)Floyd算法求最短路的程序：function D,path=floyd1(a)%a为带权邻接矩阵%D为最短距离矩阵%path为最短路径矩阵n=size(a,1);%n为点数%设置D，path的初值D=a;path=zeros(n,n);fori=1:nfor j=1:nif D(i,j)=inf;path(i,j

29、)=j;endendend%做n次迭代，每次迭代都更新D和pathfor k=1:nfori=1:nfor j=1:nif D(i,k)+D(k,j)D(i,j)D(i,j)=D(i,k)+D(k,j);path(i,j)=path(i,k);endendendend第二问源程序：clear;clc;%计算任意两社区间的最短路a=input(输入带权邻接矩阵：);D,path=floyd1(a);v=500/60;t=3;f=ones(1,24);A=zeros(24);b=ones(24,1);for j=1:24fori=1:24%判断派出所j能否在3分钟内赶到事发地iif D(i,j)t

30、minfor n=1:500newzhixu=zhixu; e=ceil(rand(1,2)*length);temp=newzhixu(e(1);newzhixu(e(1)=newzhixu(e(2);newzhixu(e(2)=temp;newf=juli(newzhixu,D);ifnewffzhixu=newzhixu;f=newf;elseif randexp(-(newf-f)/t)zhixu=newzhixu;f=newf;endend t=t*down;end%把本次模拟退火求出的近似最优哈密顿圈划分成三段L1,L2,L3,fval=huafen(zhixu,D);%按最大最小

31、化原则逐步筛选出更好的哈密顿圈%并记录其经最佳三分法得到的三个子哈密顿圈iffval(4)R1 LL1=L1;LL2=L2;LL3=L3;ffval=fval;endendLL1,LL2,LL3,ffval划分哈密顿圈的函数文件：function L1,L2,L3,fval=huafen(zhixu,D)%划分哈密顿圈%L1,L2,L3分别为三个子圈%fval记录三个子圈的权及其中的最大权值i=find(zhixu=22);ifi=1nzhixu(1:25-i)=zhixu(i:24);nzhixu(26-i:24)=zhixu(1:i-1);zhixu=nzhixu;endR=inf;%求哈

32、密顿圈的最佳三分法fori=2:22for j=i+1:23 zhixu1=zhixu(1:i); zhixu2=zhixu(1),zhixu(i+1:j); zhixu3=zhixu(1),zhixu(j+1:24);%第二种分割思想只需把相关语句修改如下： %for i=2:23% for j=i+1:24% zhixu1=zhixu(1:i);% zhixu2=zhixu(1),zhixu(i:j);% zhixu3=zhixu(1),zhixu(j:24); l1=juli(zhixu1,D); l2=juli(zhixu2,D); l3=juli(zhixu3,D);%按最大最小化原则逐步筛选 r=max(l1,l2,l3);if rR R=r;fval=l1,l2,l3,R; L1=zhixu1;L2=zhixu2;L3=zhixu3;endendend计算巡视路线的函数文件：functiondd=juli(zhixu,D)%计算巡视路线的权值length=size(zhixu,2);s=0;fori=2:length s=s+D(zhixu(i-1),zhixu(i);endif length=2 s=s+D(zhixu(1),zhixu(length);enddd=s;【精品文档】第 13 页