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

《选址问题及最佳巡视路线的数学模型》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

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

3、的方法求得连接各社区的近似最优哈密顿圈。其中，我们对每次求出的哈密顿圈都进行了合理划分，产生了三个子圈，即三组巡视路线。最终得到近似最优解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线性规划模拟

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

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

6、地，市领导从W出发巡视，分三组巡视所有社区，为了尽快完成巡视，请问如何安排巡视路线。2.模型假设与符号说明2.1模型假设假设1：题目所给的数据真实有效；假设2：缴费站所在社区居民到缴费站的距离为0；假设3：各社区人口稳定，不发生大规模迁移等情况；假设4：社区间公路不发生变化，即不发生大规模修整或者改道情况；假设5：公路不考虑等级差别，也不受交通情况影响；假设6：各条公路段上汽车的行驶速度可以认为是均匀的；假设7：巡视组保持统一行动，即不允许一个巡视组再分为若干个组；2.2符号说明社区编号，即将社区抽象为编号1,2，…，24的点（=1,2，…，24）

7、17,为了方便运算表达，又将社区编号记为,社区与间的最短路长度任意选取的3个建站位置，其中社区的人口数居民选择的缴费站缴费，其中各社区居民到最近缴费站间的总距离各社区居民到最近缴费站间的平均距离区派出所能否在3分钟内赶到区的判断矩阵在第个社区设置了派出所，则，否则，派出所的总数三组巡视路线的路程哈密顿圈中的分割点由三个分割点分割哈密顿圈后形成的三段路线长度另两个分割点到已确定的一个分割点（即市政府W）的最短距离1.问题分析本题研究的是有关城市社区服务和安全保障方面的问题。已知该城市有24个社区，各社区都有一定的常住人口；各社区间通过公路连接形成一个

8、交通网络，且各社区间的路径距离也都已知。我们先简单的分析下题目数据情况：（1）社区人口主要集中于W,Q,M,K,X,C等几