选址问题及最佳巡视路线的数学模型(1)

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

2、气缴费站。针对问题二，我们在问题一求出的最短路基础上，建立了 0-1线性规划模型。然后 借助matlab软件求得最优解X 3 （即应该设置3个派出所），并给出了各派出所管辖 范围。这样既满足了每个社区在3分钟内至少能得到一个派出所服务，也为派出所的建 设管理节省了不少成本。具体结果如下表 3:表3:各派出所管辖的范围派出所所管辖社区KH J K L M N P YQC D E Q R S T U VW 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.

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

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

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

7、数A居民选择Akfi的缴费站缴费，其中 f i 1,2,3.i 1,2,24各社区居民到最近缴费站间的总距离各社区居民到最近缴费站间的平均距离Aj区派出所能否在3分钟内赶到Ai区的判断矩阵在第i个社区设置了派出所，则Xi1,否则Xi 0,派出所的总数三组巡视路线的路程哈密顿圈中的分割点由三个分割点分割哈密顿圈后形成的三段路线长度另两个分割点到已确定的一个分割点（即市政府 W的最短跑离3 .问题分析本题研究的是有关城市社区服务和安全保障方面的问题。已知该城市有24个社区，各社区都有一定的常住人口；各社区间通过公路连接形成一个交通网络，且各社区间的 路径距离也都已知。我们先简单的分析下题目数据情况

8、：（1）社区人口主要集中于W,Q,M,K,X,C等几个城市，这些城市的人口都在10千人以上；（2）社区形成的交通网络 可看做是一个复杂的无向带权路径图，即把 24个社区抽象为24个点。接着，我们需要 解决三个问题：第一是要为建立三个煤气缴费站选址，第二是要为建立派出所选址以及 确定派出所的数量，第三是安排巡视路线。对于问题一：在社区，煤气的使用率较高，煤气缴费便成为居民经常要解决的问题。因此缴费站 的合理选址将有助于提升居民对社区服务的满意度。这是一个选址问题，此问题的关键是使得居民与最近缴费站之间的平均距离最小， 这就涉及到了社区到缴费站之间的距离以及社区人口两个相关量，并且实际生活中，缴

9、费站的设置一般是在人口较集中的社区。我们的做法是：首先确立目标是取得平均距离最小minS,再用floyd算法求出各社区间的最短路径dj；其次任意选出了 3个社区作为建站位置，并通过 matlab软件计 算，枚举出所有可能的选址方案。然后在所有的选址方案中，由居民去选择距离其最近 的缴费站缴费，所以对于每一种选址方案，都会产生一个由居民的选择所确定的总距离 S ;接着我们再通过matlab软件计算对每一种方案进行评价筛选，直至筛选出最小的S ; 最后，因为平均距离为总距离和总人口的比值，所以 S也同时取得最小值，此时便得出 了最优解。对于问题二：城市社区的安全保障问题是社区居民最关心的问题之一，

10、派出所则是居民安全保障 的坚强后盾。社区安全保障也是城市社区建设中不可少的项目之一。此题也是一个选址 问题，另外还要求确定派出所的数量。在选址方面要求派出所在其所管辖的范围内出现 突发事件时，尽量能在3分钟内有警察到达事发地；在数量上，合理性应为在满足前面的条件下派出所数量尽量少r我们的做法是：首先对24个社区按编号顺序构造一个矩阵a24 24。我们设有若干个派 出所，若派出所j能在3分钟内赶到社区i （即dj 500 60 3,单位：百米），则列1, 否则aj 0。若在第i个社区设置了派出所，则Xi 1,否则Xi 0, （i,j 1,2,3, - ,24） 0 运用floyd算法求出各社区间

11、的最短路径dj ；并通过matlab软件编程循环求解得出矩阵； 并通过matlab软件编程循环求出了所以的Xi,并筛选出最小的为，即minX。对于问题三：找出社区巡视的最佳路径方便政府及时的了解社区居民的日常生活情况，并能够及 时的满足社区居民对社区服务的需求，以此该模型的建立对于市政府和社区人们都有极 大的好处。已知巡视人员分三组由市政府出发进行巡视，而且要求在尽可能短的时间内巡视完所有社区并回到市政府。这属于一类图上的点的行遍性问题，即哈密尔顿和旅行商问题。我们的做法：设三组巡视路线的路程分别为 LL2,L3,求出这三组巡视路线中最长的一条，即得到目标函数min max Li,L2,L3

12、;接着由floyd算法计算出社区网络的最短 路径矩阵，并以此构造连接各社区的一个完全图；运用模拟退火的方法求出连接各节点 的一个近似最优的哈密尔顿圈。并设哈密尔顿圈以A22 （或记Vi 22）即市政府W为起点，依次经过节点A1A2Av24。用三个分割点把哈密尔顿圈划分为三段，把 A%作为一个 分割点（即市政府 W或A22）,在再另外23个点中取两个点Av ,A%与A%连接刚好形成三 个哈密顿回路，采用模拟退火法，最后求出满足目标函数 min max L,L2,L3的最佳分 割，并取得三个回路。4 .问题一的解答针对问题一，我们建立了模型一模型一的准备针对题目要求，我们对题目数据进行了简单的处理

13、。首先为了便于说明，我们把编号为A,B,C,，X, Y的24个社区抽象为编号1, 2,3,，24的24个点，为方便运 算表达并记为A. i 1,2,3,.,24如表1；其次，我们将各社区的的道路连接图用电子表 格进行存储以便于数据的分析（见附录）。表1:各社区的人口（单位：千人）社区ABCDEFGHIJKL编号123456789101112人口10121861015487111311社区MNpQRSTUVWXY编号131415161718192021222324人口11r 892214871015281813 模型一的建立由题可知，此问题的关键是使得居民与最近缴费站之间的平均距离最小，这就涉及

14、 到了社区到缴费站之间的距离以及社区人口两个相关量，即社区缴费站的选址必需考虑这两个相关量。4.2.1 确立约束条件为了便于说明，我们把24个社区抽象为24个点，并记为A. i 1,2,3,.,24 0 a与Aj间的最短距离为dj. 1 i, j 24 ,显然dj d/，d为0。首先我们通过构造24个社 区网络的带权邻接矩阵，再用floyd算法求出各社区间的最短路径dj；在已知任意社区 间的最短路径dj的条件下，任意选出了 3个社区Aki. i 1,2,3.1 k 24作为建站位置， 并通过matlab软件计算，枚举出所有可能的选址方案。设各社区人口数为p. i 1,2,3,.,24 ,各社区

15、到最近缴费站间的总距离为 S;由常识 易知，在所有的选址方案中居民会优先选择距离最近的缴费站缴费，所以对于每一种选 址方案，都会产生一个由居民的选择所确定的总距离S;设社区A的居民做出的选择为fi.fi 1,2,3.i 1,2,.,24，即A居民选择 i的 缴费站缴费。则：4.2.2 确立目标函数本题的目标是满足居民与煤气站的平均距离最小，为此我们确立了如下目标函数：4.2.3 综上所述，我们得到问题一的优化模型 模型一的求解由于问题的数据分析求解较为复杂，数据量大，所以我们选择使用matlab软件编程来求解。我们再通过matlab软件计算对每一种方案进行评价筛选，直至筛选出最小的S（S也同时

16、取得最小值）,此时的缴费站设置即为最优解。此时，最小平均距离 minS = 百米，煤气缴费站应设在13,16,22号社区，即在M,Q,W号社区；各社区居民应选择的 最近煤气缴费站编号如表2:表2:各居民应选择的最近煤气缴费站缴费站社区Mm J K L M N P U YQId q r s t vWA B C E F G I W X模型一的结果分析通过表2,首先从收费站区域分布情况，我们可初步判断出缴费站区域位置分布具有一定合理性；其次从人口角度，M,Q,W人口均超过10千人，Q和W更分别多达22和28千人。因为人口也是影响选址的重要因素之一，缴费站的选址通常位于人口较多的社区，这符合实际生活；

17、最后从模型的角度，我们运用计算机枚举了所有的选址方案，并从居民的角度考虑，让居民从这所有的方案中去选择离自己最近的缴费站进行缴费，我 们由居民的选择来确定S,再通过计算机对每一种方案进行评价和筛选，最后得出最终目标函数min S,由此确定了最终的选址方案。所以该模型可靠性更强。5.问题二的解答针对问题二，我们建立了模型二模型二建立本题的关键在于合理的设置派出所的数目与位置。其合理在于（1）在其所管辖的范围内出现突发事件时，尽量能在3分钟内有警察（警车的时速为50km/h）到达事发地；（2）各个派出所管辖范围的并集必须覆盖整个社区，即派出所位置的合理性；（3）派出所的管辖范围允许有交集，但应规定

18、其中一个为主要管辖。此时，当突发事件发生时， 派出所可以根据实际情况进行选派哪个派出所出警处理。这样有效的避免了诸如道路损坏、交通阻塞或者派出所人手不足等问题；（4）派出所的数量在满足社区安全保障和 服务需求的情况下其数量应尽量减少，以减少建设成本和管理经费。5.1.1 确定约束条件r我们先分别在各社区虚设一个派出所，构造判断矩阵a24 24 ,并做如下约定：若社区Aj的派出所能在3分钟内赶到社区Ai （即dij 500 60 3,单位：百米），则a。 1,r否则aj 0o然后构造解向量x,并约定：若在社区A设置了派出所，则x 1,否则,、一 .一 ,一、 rX 0（i, j 1,2,3, ,

19、24）。接着利用在问题一中求出各社区间的最短路矩阵定下a：图3为使得每个社区都能在3分钟内至少得到一个派出所的服务，我们确立了如下约束条件24ajX 1. j 1,2,3，,24 , i 15.1.2 确定目标函数该模型是为了解决派出所设置问题。派出所越多，建设成本、管理经费及工资陈本 就越大；派出所越少，就不易满足居民需求。为了合理设置派出所，我们确立了评价指 标X 0即在满足约束的条件下，求解派出所数量的最小值。24 min X Xi , i 15.1.3 综上所述，我们得到问题二的0-1线性规划模型其中，模型二的求解- rt，我们通过matlab软件解得：x 0 0 0 0 0 0 0

20、0 0 0 1 0 0 0 0 1 0此附显优S就0 0X 3,即设置3个派出所比较合理，派出所的位置编号分别为 11,16,22 ,即在K,Q,ME 个社区设立派出所。（编程运行结果见附录三）各派出所管辖的范围如下表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模型二的结果分析通过检验，该方案具有很好的可行性；即（1）派出所在所管辖的范围内，警察能 在3分钟内到达所有社区；（2）派出所数量为3个，已是尽可能少，无论去掉其中哪 个，都不能满足（1）的条件；（3）位置分布合理，所

21、管辖区域完全覆盖整个城市，又 因W为政府所在，故派出所管辖范围有重叠的区域应由派出所 W负责主要管辖。6.问题三的解答模型三的建立该问是关于寻求最佳路线问题，要求分三组从市政府W出发能够尽快巡视完所有社区并回到市政府 W这属于一类图上的点的行遍性问题，即哈密尔顿和旅行商问题，也 就是要用若干条闭链覆盖图上所有的顶点，并使某些指标达到最优。6.1.1 确立目标函数设三组巡视路线的路程分别为LhL2,L3。路程越短，耗时越少，完成巡视的最短时间受到这三组巡视路线中最长路线的制约，故我们确立了目标函数为min max L1,L2.L36.1.2 确定约束条件首先我们对社区网络图按最短路重新赋权构造完

22、全图，目的是为了用模拟退火法进行求解。设某次模拟退火求出的近似最优哈密尔顿圈以A22 （或记522）即市政府W为起点，依次经过节点Av1 Av2Av24。用三个分割点把哈密尔顿圈划分为三段AA.AiAA?Avj,Avj1Av1 ,记其长度分别为C1C2C3；由常识可知，欲使巡视时间尽可能短，则应该把Av1作为一个分割点（即市政府 W或A22）,在再另外23个点中取两个点A ,Avj与4连接刚好形成三个哈密顿回路 A% A2.Ai AAA 1A A人人1A ,他们的权值分别为L1 C1 dv3 L2 C2 d. de，L3 C3 d.-。如下图一：图一通过以上我们得出哈密尔顿圈被分割的三段长度为

23、：由确定三个分割点后形成的新的哈密尔顿圈为：即他们的权值分别为：6.1.3 综上所述，我们确立了问题三的优化模型模型三的求解定初始温度为120,结束温度为，温度下降速率为，重复模拟退火算法 30次，分别 求出近似最优哈密尔顿圈。其中，我们对每次求出的哈密顿圈都进行了合理划分，产生了三个子圈，即三组巡视路线。最后得到近似最优解128。该问题的解题模型思想对计算机编程求解的依赖度比较大，因此我们也需要借助源程序来表达我们的解题思路，具 体源程序请看附录。经过使用计算机 matlab软件编程求出最终结果如下表4：表4：巡视路线图（单位：百米）路线名称巡视社区线路途经社区 （未巡视）总路线 长度最大总

24、路线的 长度LLiW-F-G-I-P-K-H-Y-F-WFii5i28LL2W-F-L-M-N-J-U-V-Q-R-S-D-C-WF、Ci28LL3W-C-T-E-C-A-X-B-WCi20模型三的结果分析与改进在目标函数分析中已说明，由社区网络重新赋权形成的完全图中一定存在连接各节 点的最短闭路径，这个最优解一般难以求出，所以我们只能用模拟退火法经过多次运算 求出一个接近最优的哈密尔顿圈。因此我们再在这里分析对比，按图一的思想得出近似最优解128。但考虑图二，Ai ,Avj虽然被重复行走，但他们却能起到“搭桥”的作用，极可能得到更省时的巡视路 线。经过计算的近似最优解125,这与我们的想法是

25、一致的，这也是模型的一种拓展改 进方法。下图一、二是关于分割哈密尔顿圈生成的三个子圈。图一的三个回路为：图一：AA、1AvjAi图二的三个回路为：AiAvAi图二：AiAvAvjAiAvjAvi图一图二模型改进后的路线结果如下表 5:（即按照图二的所示方法算出的结果）表5:按照图二进行模型改进后的巡视路线表路线 名称巡视社区线路途经社区 （未巡视）总路线长 度最大总路线 的长度LLiW-G-F-L-J-U-J-N-M-K-H-Y-F-WF、Ji25i25LL2W-F-Y-H-P-I-B-X-WF、Hi22LL3W-X-A-S-D-Q-R-Q-V-T-E-C-WQi225.模型的评价、改进与推广

26、模型的评价优点：(1)对于问题一，我们较好地利用了计算机的强大功能，枚举出所有情况，得出了 满足题意的最优解，有效缩短了居民与最近缴费站的平均距离。(2)问题二是交巡警服务平台管辖范围的合理分配研究，对数据进行深入的分析， 运用0-1规划模型，妥善地分配了各个派出所的管辖范围。既节约了成本，又满足了居(3)模拟退火法除了可以选择不同的参数外， 还可以进行反复多次运行，而且每次 得到的解可能都不一样，也就比其它算法有更多的选择余地和获得最优解的机会，这对 实际应用而言是十分有优势的，因为真正实际问题的求解往往需要在多个方案中进行筛 选，以获取最优方案。所以该模型具有很好的实用性。缺点：(1)把各

27、社区抽象为一个点，产生了距离误差。(2)模拟退火具有随机性，只能得到近似解，而且对于节点偏多的网络，运行速度 很慢。模型的改进由于时间的限制，未能对模拟退火法的进行更多次的运行。因此，如果时间允许， 我们可以增加运行次数，以求得更优越的方案，或者寻找更佳的算法。模型的推广本题的问题一和问题二的最优选址问题也可运用到其它的最优选址问题中去，比如 关于消防救援工作最优路径问题、重大生产安全事故应急救援问题、公共交通最优路径 问题等。问题三的多旅行商问题模型可推广到交通运输、管道铺设、路线的选择、计算 机网路的拓扑设计、邮递员送信、计算机网络通信等众多领域。参考文献1费浦生，羿旭明，数学建模及其基础

28、知识详解，武汉：武汉大学出版社，2006.2胡良剑，孙晓君，matlab数学实验，北京：高等教育出版社，2006.3屈强，陈雪波，matlab的模拟退火算法的实现，鞍山科技大学学报，2003年6月第 26卷第3期。4韦芳芳，杨兰兰，柏瑞，灾情巡视路线的设计，数学的实践与认识，1999年1月第29 卷第1期。5史彦锋，齐鹤，网络多中心问题的几种算法及其应用，中国教育发展研究杂志，2007年8月第4卷第8期。附录附录一：各社区的人口(单位：千人)编号ABCDEFGHIJKL123456789101112人口10121861015487111311编号131415161718192021222324

29、MNPQRSTUVWXY人口11892214871015281813附录二：各社区的的道路连接(注：横线上的数据表示相邻社区之间的距离，单位：百米)附录五：模拟所用的程序第一问源程序：clear;clc;%求任意社区间的最短路a=input( 输入带权邻接矩阵：);D,path=floyd1(a);ss=inf;%列出所有的煤气站选址方案，比较求出最优解for i=1:22for j=i+1:23for k=j+1:24s=0;%各社区居民会选择距离最近的煤气站缴费%的对应总距离for ii=1:24w=min(D(ii,i),D(ii,j),D(ii,k);s=s+w*p(ii);end%逐

30、步比较选择更小的总距离if sssss=s;i1=i;j1=j;k1=k;endendendend%循环结束求出总距离最小值ss%记录在最佳方案下各社区居民选择的煤气站编号for jj=1:24aa,bb=min(D(jj,i1),D(jj,j1),D(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

31、,path=floyd1(a)%必带权邻接矩阵%为最短距离矩阵%path为最短路径矩阵n=size(a,1); %讷点数%设置D， path 的初值D=a;path=zeros(n,n);for i=1:nfor j=1:nif D(i,j)=inf;path(i,j)=j;endendend%ftn次迭代，每次迭代都更新Dff口 pathfor k=1:nfor i=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:24for i=1:24%判断派出所j 能否在3分钟内赶到事发地iif D(i,j)tminfor n=1:500newzhixu=zhixu;e=ceil(rand(1,2)*length);temp=newzhixu(e(1);newzhixu(e(1