本科14组 许泽东，邹志翔，陈佳成

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

摘 要

本文解决的问题是缴费站、派出所选址和最佳巡视路线的确定。合理设置缴费站，可以为居民缴费节省大量时间和精力。派出所位置和数量的不同选择，会产生不同的建设成本和管理经费。而最佳巡视路线的确立，可以让领导在最短时间内巡视完所有社区。为解决以上问题，我们建立的三个最优化模型。

针对问题一，我们先用floyd算法求出各社区间的最短路，然后用计算机枚举出所有选址方案。对每一种选址方案都会产生一个平均距离S，我们以此为指标对方案进行评估。经过合理化推导，我们得出最优解S?11.712（百米），且此时应该在M,Q,W三社区设置煤气缴费站。

针对问题二，我们在问题一求出的最短路基础上，建立了0-1线性规划模型。然后借助matlab软件求得最优解X?3（即应该设置3个派出所），并给出了各派出所管辖范围。这样既满足了每个社区在3分钟内至少能得到一个派出所服务，也为派出所的建设管理节省了不少成本。具体结果如下表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 针对问题三，我们主要运用了模拟退火的方法。我们先利用前面求得的最短路矩阵构建了社区网络的完全图，然后考虑到最优哈密顿圈的求解极其困难，我们连续使用30次模拟退火的方法求得连接各社区的近似最优哈密顿圈。其中，我们对每次求出的哈密顿圈都进行了合理划分，产生了三个子圈，即三组巡视路线。最终得到近似最优解128，见表4。接着，我们还对哈密顿圈划分方法进行了改进，求得近似最优解125（具体结果见表5）。

表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 floyd算法 0-1线性规划 模拟退火 哈密顿圈

1.问题重述

1.1问题背景

社区已是现代都市的的基础，随着城市社会经济的飞速发展，社区与人们生活的联系

越来越密切，人们需要在社区解决日常生活涉及的各种利益和需要，因而人们对社区社会生活服务提出更高的要求，而政府也希望能够更好的指导和管理城市社区，社区生活服务建设以及安全保障等问题便由此而生。

据某项调查显示，我国七成以上的家庭表示需要更多更好的社会化社区服务，其范围

涉及食、住、行、工、学、医、娱、境、安等居民生活的各个方面。与此同时，在我国经济体制改革和城市管理体制改革不断推进的背景下，社区需要承接越来越多的政治、文化、甚至行政功能。

1.2问题重述

本题便是关于社区服务建设的相关问题。题目给出了如下两项条件：

1. 某一城市社区的分布情况以及社区之间的路程（见附录二）；

2. 各个社区的人口数量（见附录一）。

根据已知条件，需要解决如下问题：

（1） 为了方便社区居民缴纳煤气费，煤气公司现拟建三个煤气缴费站，问煤气缴费站怎

样选址才能使得居民与最近煤气站之间的平均距离最小。

（2） 市公安局拟在该城区建立若干个派出所，请为派出所分配管辖范围，使其在所管辖

的范围内出现突发事件时，尽量能在3分钟内有警察（警车的时速为 50km/h）到达事发地，问设置多少个派出所比较合理，位置选在哪？

（3） 社区W是市政府所在地，市领导从W出发巡视，分三组巡视所有社区，为了尽快完

成巡视，请问如何安排巡视路线。

2.模型假设与符号说明

2.1模型假设

假设1：题目所给的数据真实有效；

假设2：缴费站所在社区居民到缴费站的距离为0；

假设3：各社区人口稳定，不发生大规模迁移等情况；

假设4：社区间公路不发生变化，即不发生大规模修整或者改道情况；

假设5：公路不考虑等级差别，也不受交通情况影响；

假设6：各条公路段上汽车的行驶速度可以认为是均匀的；

假设7：巡视组保持统一行动，即不允许一个巡视组再分为若干个组；

2.2符号说明

社区编号，即将社区抽象为编号1,2，…，24的点（i,j=1,2，…， 24） Ai,Aj 为了方便运算表达，又将社区编号记为Ai,Aj 社区Ai与Aj间的最短路长度 任意选取的3个建站位置，其中?i?1,2,3.1?ki?24? i社区的人口数 Ai居民选择Akfi的缴费站缴费，其中?f?i??1,2,3.i?1,2,...,24? ?? 各社区居民到最近缴费站间的总距离 各社区居民到最近缴费站间的平均距离 Aj区派出所能否在3分钟内赶到Ai区的判断矩阵 在第i个社区设置了派出所，则xi?1，否则xi?0， 派出所的总数 三组巡视路线的路程 哈密顿圈中的分割点 由三个分割点分割哈密顿圈后形成的三段路线长度 另两个分割点到已确定的一个分割点（即市政府W）的最短距离 3. 问题分析

本题研究的是有关城市社区服务和安全保障方面的问题。已知该城市有24个社区，各社区都有一定的常住人口；各社区间通过公路连接形成一个交通网络，且各社区间的路径距离也都已知。我们先简单的分析下题目数据情况：（1）社区人口主要集中于W,Q,M,K,X,C等几个城市，这些城市的人口都在10千人以上；（2）社区形成的交通网络可看做是一个复杂的无向带权路径图，即把24个社区抽象为24个点。接着，我们需要解决三个问题：第一是要为建立三个煤气缴费站选址，第二是要为建立派出所选址以及确定派出所的数量，第三是安排巡视路线。

对于问题一：

在社区，煤气的使用率较高，煤气缴费便成为居民经常要解决的问题。因此缴费站的合理选址将有助于提升居民对社区服务的满意度。

这是一个选址问题，此问题的关键是使得居民与最近缴费站之间的平均距离最小，这