内容发布更新时间 : 2024/5/22 11:45:00星期一 下面是文章的全部内容请认真阅读。
图3
为使得每个社区都能在3分钟内至少得到一个派出所的服务，我们确立了如下约束条件
?axi?124iji?1.?j?1,2,3,...,24?，
5.1.2确定目标函数
该模型是为了解决派出所设置问题。派出所越多，建设成本、管理经费及工资陈本就越大；派出所越少，就不易满足居民需求。为了合理设置派出所，我们确立了评价指标X。即在满足约束的条件下，求解派出所数量的最小值。
minX??xi，
i?1245.1.3综上所述，我们得到问题二的0-1线性规划模型
其中，
5.2模型二的求解
rT我们通过matlab软件解得：x??0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0?。此时最优解为
X?3，即设置3个派出所比较合理，派出所的位置编号分别为11,16,22，即在K,Q,M三个社
区设立派出所。（编程运行结果见附录三）
各派出所管辖的范围如下表3：
表3：各派出所管辖的范围
派出所 所管辖社区 K H J K L M N P Y Q C D E Q R S T U V W A B C E F G I L T U W X Y 5.3模型二的结果分析
通过检验，该方案具有很好的可行性；即（1）派出所在所管辖的范围内，警察能在3分钟内到达所有社区；（2）派出所数量为3个，已是尽可能少，无论去掉其中哪个，都不能满足（1）的条件；（3）位置分布合理，所管辖区域完全覆盖整个城市，又因W为政府所在，故派出所管辖范围有重叠的区域应由派出所W负责主要管辖。
6. 问题三的解答
6.1模型三的建立
该问是关于寻求最佳路线问题，要求分三组从市政府W出发能够尽快巡视完所有社区并回到市政府W。这属于一类图上的点的行遍性问题，即哈密尔顿和旅行商问题，也就是要用若干条闭链覆盖图上所有的顶点，并使某些指标达到最优。
6.1.1确立目标函数
设三组巡视路线的路程分别为L1,L2,L3。路程越短，耗时越少，完成巡视的最短时间受到这三组巡视路线中最长路线的制约，故我们确立了目标函数为min?max?L1,L2,L3?? 6.1.2确定约束条件
首先我们对社区网络图按最短路重新赋权构造完全图，目的是为了用模拟退火法进行求解。设某次模拟退火求出的近似最优哈密尔顿圈以A22（或记v1?22）即市政府W为起点,依次经过节点AvAv...Av1224。用三个分割点把哈密尔顿圈划分为三段
Av1Av2...Avi,Avi?1Avi?2...Avj,Avj?1...Av1,记其长度分别为C1,C2,C3；由常识可知，欲使巡视时间尽
可能短，则应该把Av作为一个分割点（即市政府W或A22），在再另外23个点中取两个点
1Avi,Avj与Av连接刚好形成三个哈密顿回路AvAv...AvAv,AvAv...AvAv,AvAv...Av，他们的
112i11i?1j11j?11权值分别为L1?C1?dviv1，L2?C2?dviv1?dvjv1，L3?C3?dvjv1。如下图一：
图一
通过以上我们得出哈密尔顿圈被分割的三段长度为：
由确定三个分割点后形成的新的哈密尔顿圈为：
即他们的权值分别为：
6.1.3综上所述，我们确立了问题三的优化模型
6.2模型三的求解
定初始温度为120，结束温度为0.001，温度下降速率为0.95，重复模拟退火算法30
次，分别求出近似最优哈密尔顿圈。其中，我们对每次求出的哈密顿圈都进行了合理划分，产生了三个子圈，即三组巡视路线。最后得到近似最优解128。该问题的解题模型思想对计算机编程求解的依赖度比较大，因此我们也需要借助源程序来表达我们的解题思路，具体源程序请看附录。经过使用计算机matlab软件编程求出最终结果如下表4：
表4：巡视路线图（单位：百米）
路线名称 巡视社区线路 途经社区（未巡视） F F、C C 总路线长度 115 128 120 最大总路线的长度 LL1 LL2 LL3 W-F-G-I-P-K-H-Y-F-W W-F-L-M-N-J-U-V-Q-R-S-D-C-W W-C-T-E-C-A-X-B-W 128 6.3模型三的结果分析与改进
在目标函数分析中已说明，由社区网络重新赋权形成的完全图中一定存在连接各节点的最短闭路径，这个最优解一般难以求出，所以我们只能用模拟退火法经过多次运算求出一个接近最优的哈密尔顿圈。
因此我们再在这里分析对比，按图一的思想得出近似最优解128。但考虑图二，Avi,Avj虽然被重复行走，但他们却能起到“搭桥”的作用，极可能得到更省时的巡视路线。经过计算的近似最优解125，这与我们的想法是一致的，这也是模型的一种拓展改进方法。
下图一、二是关于分割哈密尔顿圈生成的三个子圈。
图一的三个回路为：
……?Av???A???Av1v1i??………图一：?Av1???Avi?1???Avj???Av1
?……A???A???Av1?vvj?1?1图二的三个回路为：
……?Av???A???Av1v1i??………图二：?Av1???Avi???Avj???Av1
?……A???A???Av1?vj?v1图一 图二
模型改进后的路线结果如下表5：（即按照图二的所示方法算出的结果）
表5：按照图二进行模型改进后的巡视路线表
路线名称 LL1 LL2 LL3 巡视社区线路 途经社区（未巡视） F、J F、H Q 总路线长度 125 122 122 最大总路线的长度 W-G-F-L-J-U-J-N-M-K-H-Y-F-W W-F-Y-H-P-I-B-X-W W-X-A-S-D-Q-R-Q-V-T-E-C-W 125 5.模型的评价、改进与推广
5.1模型的评价
优点：
（1）对于问题一，我们较好地利用了计算机的强大功能，枚举出所有情况，得出了满足题意的最优解，有效缩短了居民与最近缴费站的平均距离。
（2）问题二是交巡警服务平台管辖范围的合理分配研究，对数据进行深入的分析，运用0-1规划模型，妥善地分配了各个派出所的管辖范围。既节约了成本，又满足了居民需求。