缴费站选址问题

09-15

论文题目：缴费选址问题

摘要

本文根据社区的公路网络图，求解不同条件下的选址问题，及分组巡视问题。文中首先将网络图转换为赋权连通图。

对于问题一，本文首先通过赋权连通图求出社区间的邻接矩阵，通过Floyd 算法求出任意两点间的的最短距离，通过matlab 编程利用枚举法，在24个社区中任意求出三点，求出这种情况下居民与最近煤气站的平均距离，再找寻满足平均距离最小的三点，即可求解，三点为M 、Q 、W 社区。

对于问题二，首先假设派出所对某个社区的覆盖度是二元的，引入决策变量，建立了0-1整数规划模型，以确保24个社区均被覆盖，同时要满足警察局在3分钟之内赶到事发社区。考虑到派出所的成本，显然设置个数越少越好，在任意两社区的最短距离已知的情况下，则此问题转换为非线性规划问题，目标函数即为派出所个数。通过Lingo 编程，可快速求出派出所的个数为3，设置在D 、K 、W 社区。

对于问题三，为分组巡查问题，实质为多旅行商问题，首先将社区的赋权连通图简化为生成树，其中各顶点到W 点的权值最小，再以树干为基础分为三组，分组后依据分组情况画出最佳旅行商路径并在Lingo 中编程求出每组最小权值，选出最优路径如下图表一：

关键词: Floyd 算法枚举法 0-1规划非线性规划多旅行商问题

一、问题重述

某城市共有24个社区，各社区的人口（单位：千人）如下表

（注：横线上的数据表示相邻社区之间的距离，单位：百米）

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

缴费站怎样选址才能使得居民与最近煤气站之间的平均距离最小。 (2) 市公安局拟在该城区建立若干个派出所，请为派出所分配管辖范围，使其

在所管辖的范围内出现突发事件时，尽量能在3分钟内有警察（警车的时速为 50km/h）到达事发地，问设置多少个派出所比较合理，位置选在哪？ (3) 社区W 是市政府所在地，市领导从W 出发巡视，分三组巡视所有社区，

为了尽快完成巡视，请问如何安排巡视路线。

二、假设说明

假设1：各社区没有人数的迁入迁出；

假设2：同一社区的居民到同一缴费点交费；

假设3：每个派出所有足够的时间去处理管辖范围内的突发事件；假设4：每个社区只能被一个派出所管辖；

假设5：派出所接到报警后能立即出警，中间没有延误；假设6：每组从县政府同时出发，且行驶速度相同；假设7：行驶过程中汽车不会出现故障；

假设8：市领导从市政府出发巡视完后回到市政府。

三、符号说明

四、问题分析

此题研究的是在各社区人数、社区之间的距离已知的情况下，寻找合理的路径，确定缴费站、派出所的位置使结果最优。在市领导巡视路线的问题中，要求市领导从市政府出发巡视完后回到市政府，可以利用图论中的最佳旅行商回路方法来解决。

针对问题一：

本题主要求三个煤气缴费站怎样选址时使居民与最近煤气站之间平均距离最小，而居民的总人数已知，即要使所有居民到煤气站的总距离最小。假设每个社区的居民到同一个缴费站交费，则每个社区的居民到煤气站的总距离等于该社区的人数与该社区到缴费站的距离之积。只有每个社区到缴费站的总距离都最

小，才能使目标函数最优。所以先确定24个社区两两相互间的最短距离，设任意三社区x 、y 、z 为所设的三个缴费站，则每个社区到缴费站的最小总距离为该社区的人数乘以该社区到x 、y 、z 三个缴费站中的最小距离，所有居民到煤气站的总距离为24个社区到缴费站的最小总距离之和。而x 、y 、z 三个缴费站是24

个社区中任意三个地点，具体是哪三个社区不确定，有C 24种情况，所以用穷举

的方法来确定社区的位置使所有居民到煤气站的总距离最小。

针对问题二：

社区发生突发事件时要有派出所出来管辖，首先假设每个社区要么被其中一个派出所完全管辖，要么被完全不管辖，即覆盖度是二元的，所以考虑到用0-1整数规划模型。当派出所所管辖的范围内出现突发事件时，尽量能在3分钟内有警察（警车的时速为 50km/h）到达事发地，即派出所距发生突发事件的地方的最大距离为25百米。而且当每个社区有突发事件发生时，都只有一个派出所到达现场处理事件。

建立派出所需要投入成本和警务资源，要使派出所的个数比较合理，所以建立的派出所个数越少时成本越少，结果为最优，即目标函数为派出所的个数。既而确定派出所的位置。

针对问题三：

由于问题要求分三组巡视，且要尽快完成巡视，即要使巡视总路程最短且各组的巡视路线尽可能均衡。为了解决此问题，我们先画出各个点到W 点的最短路径图(如图一) ，此图有5个分支，为使巡视路线均衡，我们较为均匀地分为三组路线，（见附录6）, 分别计算两种分法的最短巡视路线和均衡度，然后取最优。

五、数据分析

5.1猜想

一个城市有i 个社区，n 个缴费站，则将缴费站设立在社区可使得居民与最近缴费站之间的平均距离最小。证明:

假设在任意两个相邻两社区

R i 和R j 之间的道路上设立缴费站，则居民必

R j R R R i 须经过或缴费。设：经过社区i 缴费的人数和其与i 的最小距离加权

后的值为

D ij

f i ，经过社区R j 缴费的加权值为f j ，社区R i 和R j 之间的距离为

，缴费站与社区i 的距离为x 。

则，居民人数与其到缴费站最小距离加权后的和值为：

f =f i x +f （=(f i -f j ) x +f j D ij j D ij -x ）

R j R f j f i i f 若=，则为定值，缴费站设立在社区和、或者两社区之间道路上的任意一点，缴费人数与其到缴费站相应最小距离加权后的和值均可达到最小。

R f j f f i x =0若>，则当时，最小，即缴费站应设立在社区i 。

R f

若f i

同理可得，城市有i 个社区，n 个缴费站时，将缴费站设立在社区，缴费居民的人数与其到相应缴费站最小距离加权后的和值最小，即居民与最近缴费站之间的平均距离最小。

5.2求图中24个社区中任意两点间的距离

根据图中24个社区间的距离，要求赋权图中任意两点间的最短路。采用Floyd 算法得出了图中任意两点间的最短距离。结果如下表一：

5.3以W 为起点到各顶点的最短路程生成树

以W 为起点到各顶点的最短路程生成树如下图一：

图一：到W 的最短路径生成树

六、模型建立

6.1模型一的建立：

要使居民与最近煤气站之间平均距离最小，居民的总人数已知，即求所有居民到煤气站的总距离最小，先确定24个社区两两相互间的最短距离。

任意选三社区为缴费站，选取这24个社区到三缴费站的最小距离与该社区

的人数相乘，其总和为所有居民要走的总路程；再变换三社区的位置（有C 24种

情况），取这些总路程中的最小值，最后用这个最小值除以所有人数即为目标函数。

目标函数L:

min =

∑R ⋅min (d

i i =1

,d iy , d iz )

∑R

i =1

其中R i 为i 社区的人数，x 、y 、z 为24个社区中任意3个社区，d ix ,d iy , d iz 分别为i 社区到x 、y 、z 三社区的最短距离；

6.2 模型二的建立

考虑使用0-1整数规划模型，下面确定目标函数和约束条件。假设每个派出所有足够的时间去处理管辖范围内的突发事件，即当某个派出所处理一起突发事件的同时，在它所管辖的区域内不会发生其他的突发事件。

设问题的决策变量为

x ij

是0-1变量，即

⎧1，当i 社区有突发事件时，由j 社区派出所管辖x ij =⎨

⎩0，当i 社区有突发事件时，不由j 社区派出所管辖

(i =1,2, ,24; j =1,2, ,24)

建立派出所需要投入成本和警务资源，要使派出所的个数比较合理，所以建立的派出所个数越少时成本越少，结果为最优。

即目标函数:

min =∑P j

j =1

然后确定五个约束条件:

一是要求任一派出所到达其所管辖的社区的时间都小于3分钟，即派出所距发生突发事件的地方的最大距离为25百米；

二是当每个社区有突发事件发生时，有且只有一个派出所到达现场处理事

j =1

∑d

⋅x ij ≤25(i , j =1,2⋅⋅⋅24)

件；

∑x =1(i =1,2⋅⋅⋅24)

ij j=1

三是j 社区派出所的个数可以为0或1；

⎧0⎪

P j =⎨ j 社区派出所的个数为0或1

⎪1⎩

四是j 社区发生突变事件时，有派出所来参与管辖；

⎧1，当i 社区有突发事件时，由j 社区派出所管辖x ij =⎨

⎩0，当i 社区有突发事件时，不由j 社区派出所管辖

五是保证社区j 派出所个数大于等于决策变量；

P j ≥x ij (i , j =1,2⋅⋅⋅24)

综上所述，问题二的最优化模型是

min =∑P j

j =1

⎧24

⎪∑d ij ⋅x ij ≤25(i , j =1,2⋅⋅⋅24) ⎪j =1⎪24

⎪∑x ij =1(i =1,2⋅⋅⋅24) ⎪j=1⎪⎧0⎪⎪⎪

s. t ⎨P j =⎨ j 社区派出所的个数为0或1 ⎪⎪1

⎩⎪⎪⎧1，当i 社区有突发事件时，由j 社区派出所管辖⎪x ij =⎨⎪⎩0，当i 社区有突发事件时，不由j 社区派出所管辖⎪

⎪P j ≥x ij (i , j =1,2⋅⋅⋅24) ⎪⎩

6.3 模型三的建立

因为最小生成树包含图中所有顶点，而且最小树的边权是相邻顶点之间的距离，故可考虑用最小生成树进行分块。现在对已经得到的最小生成树（如图一）进行分解，以获得三个子图使得分解结果尽量均衡。 6.3.1 确定目标函数

为使总巡视路线尽可能短且每组巡视路线尽可能均匀，我们确立了两个目标函数。

1：分成的三组回路中每组回路对应的权值w(Ck)最小

N N

⎧1, 城镇i 与城镇j 之间联通x ij =⎨w (c k ) =∑∑w ij c ij

i =1j =1⎩0, 城镇i 与城镇j 之间不联通，则令

所以 2：均衡度a 最小:

∑w (c ) =min

a =

我们定义

max w (c i ) -w (c j )

max w (c i )

为该分组的实际均衡度，显然0≤a ≤1。a

越小说明分组的均匀性越好。因此

min a =

max w (c i ) -w (c j )

max w (c i )

所以我们建立了一下目标函数：

⎧3

⎪∑w (c i ) =min ⎪1⎨

⎪min a =max w (c i ) -w (c j ) ⎪max w (c i ) ⎩

6.3.2 确定约束条件

在加权网络图G 中，将顶点集V 划分为V 1 , V2, V3, 则G 的三个子图为G[V1], G[V2], G[V3],需满足一下几个条件

1:顶点O 包含在每个顶点集V i 中，即O ∈V i ，i=1,2,3

2：顶点集V i 为V （G ）的子集，即

=V (G )

3：在加权图G 中，G 的三个子图G[V1], G[V2], G[V3],必须形成一条回路，即

⎧p

⎪∑x ij =1, j ∈N ; ⎪i =1⎨p

⎪x =1, i ∈N ∑ij ⎪j =1⎩

由此得到问题三的最优化模型为：

⎧3

⎪∑w (c i ) =min ⎪1⎨

⎪min a =max w (c i ) -w (c j ) ⎪max w (c i ) ⎩

⎧O ∈V i ，i =1, 2,3

⎪3

⎪ V =V (G ) ⎪1i ⎪s . t ⎨p

⎪∑x ij =1, j ∈N ⎪i =1⎪p

⎪∑x ij =1, i ∈N ⎩j =1

七、问题求解及结果分析

7.1 模型一

7.1.1 模型一的求解

为了求解24个社区任意两社区之间的最短距离，可以采用floyd 算法。floyd 算法比Dijkstra 算法更方便有效，Dijkstra 算法只是求解单源点无负边最短路径，而floyd 算法可以求解任意两点间的最短路径。floyd 算法在matlab 中运行程序见附录一。24个社区之间的最短距离见附表二D 矩阵。

用穷举的方法求出三个缴费站为13、16、22号，即三个缴费站建在M 、Q 、W 三个社区才能使居民与最近煤气站之间平均距离最小，平均距离为11.7118百米，源程序见附录三。

各社区到缴费站的路径图如下图二：

图二

7.1.2模型一结果分析

三个缴费站中，Q 收缴费站所负担的权最少，可以适当减少设施人员以节省成本。W 、M 缴费站负担的权均重些，所以W 、M 站设施人员方面需准备更充分及应急措施。 7.2 模型二

7.2.1 模型二的求解

为了设置合理的派出所个数，尽量使派出所的个数最少，我们将派出所个数的最小值作为目标函数，确定相应的约束条件，借助Lingo 软件求解，得到设置3个派出所比较合理，三个派出所的序号为4、11、22即派出所建在D 、K 、W 三个社区里。程序见附录四 7.2.1模型二结果分析

根据三个派出所的地点，可画出24个社区到D 、K 、W 三个派出所的距离表格如下表二：

各社区发生突发事件时由距该地区最近的派出所参与管辖，三个派出所各自管辖的社区及最短距离如下表三：

米，符合题目要求。且L 社区距K 、W 社区的最小距离都为21百米，即L 社区发生突发事件时K 、W 社区都可以参与管辖。

7.3 模型三

7.3.1 模型三的求解

首先我们对数据进行处理，表示为邻接矩阵的形式。并求出以W 点为根的最小生成树，然后根据我们确定的分组原则把最小生成树大致分成三组，分组后依据分组情况画出最佳旅行商路径并在Lingo 中编程求出每组最小权值，得出最优路径为下表：

A,X 点加到第三组，得出以下结果，如下表：

根据以上结果，求出均衡度为

a =

max(c k ) -min(c k ) 117-110

==5.98%

max(c k ) 117

比较小，说明结果合理满足要求。

相应的路径图如下：

图三

7.3.1模型三结果分析

第二组走过的社区个数最少，与其余两组相差较大，但走过的总路程与其余两组相差不大，均衡度相对较小。

八、模型的评价、改进及推广

8.1模型评价优点：

（1）对于题目中的问题，我们借助于数学软件MatlAB 中基于Floyd 算法的程序而不是Dijkstra 算法对模型进行求解，找出了最优化的选址方案， Dijkstra 算法只是求解单源点无负边最短路径，而floyd 算法可以求解所有点间的最短路径，floyd 算法比Dijkstra 算法更方便有效。

（2）模型操作性强，只要给出任意图G 及各边上的权值，就能够将一个复杂的图G 分为若干个子图，大大的降低了解题的难度；缺点：

（1）对于问题一中的模型，我们忽略了每个居民的个体差异，认为他们的选择是一致的，因为在没有统一规定或者指导的情况下，他们是可以随意到任意缴费点缴费的；而且我们规定社区的人数不变，这样不符合实际情况。

（2）对于问题二中的模型，没有考虑到各个派出所工作的不均衡性。在分配结果中可以看到，部分交巡警的工作量很小而部分交巡警的工作量很大。这显然是不合理的。事实上，可以建立一个多目标规划问题，使得分配管辖范围的方案更加合理。

8.2模型改进

（1）在问题二中，要求尽快完成巡视，即巡视的总时间尽量最短，但求出来的结果往往不尽人意，每组完成的时间有时相距很大，我们可以让已经完成的那一组去帮助还未完成的那一组，从而可以缩短整体的巡视时间，达到近一步优化模型的目的。

（2）建模时可以考虑更多的因素，让模型实用性更强，比如说，如何让巡视过程中花费最小。

8.3模型推广

本文所建立的模型可以推广到任何一个市区或者更广范围内的交巡警服务平台的设置和调度问题的解决中，也可以解决以满足时间紧迫性为要求的其他类似问题中，如消防站的选址问题、急救中心的选址问题、应急设施选址问题等等。在实际应用中有很强的实用性和通用性。

而且问题中用到旅行商问题，该问题可以应用的范围较广，只要是寻求最佳哈密顿圈，该模型均可以作为参考。

九、参考文献

【1】李海涛，邓樱，MATLAB 程序设计教程，北京：高等教育出版社，2002. 【2】田贵超，黎明，韦雪洁. 旅行商问题（TSP ）的几种求解方法[J].计算机仿真，2006.8（8）：153-157.

【3】张先迪，李正良，图论及其应用，北京：高等教育出版社，2005.

【4】谢金星，薛毅，优化建模与lingo 软件，北京：清华大学出版社，2005。

附录一

Matlab 中 floyd算法

function [d,path]=floydz(a) %定义函数 n=size(a,1);

%返回矩阵a 的行数

% 设置将a 矩阵赋值给d, 和将Path 设为N*N的0矩阵

for i=1:n %i从1到n 循环 for j=1:n %j从1到n 循环

if d(i,j)~=inf %如果i 到j 的最短距离为无穷大 path(i,j)=j; %j 是i 的后继点 end end end

for k=1:n %做n 次迭代, 每次迭代均更新d(i,j) 和path(i,j) for i=1:n %i从1到n 循环

for j=1:n %j从1到n 循环

if d(i,k)+d(k,j)

d(i,j)=d(i,k)+d(k,j) ; %修改长度 path(i,j)=path(i,k) ; %修改路径 end end end end

d=a;path=zeros(n,n);

附录二

求解最短路径源代码 a=[

0 inf 24 inf inf inf inf inf inf inf inf inf inf inf inf inf inf 20 inf

inf inf inf 16 inf

inf 0 inf inf inf inf inf inf 28 inf inf inf inf inf inf inf inf inf inf

inf inf 22 18 inf

24 inf 0 11 9 inf inf inf inf inf inf inf inf inf inf inf inf inf 10

inf inf 15 inf inf

inf inf 11 0 inf inf inf inf inf inf inf inf inf inf inf 9 inf 8 inf

inf inf inf inf inf

inf inf 9 inf 0 8 inf inf inf inf inf inf inf inf inf inf inf inf 6 9

inf inf inf inf

inf inf inf inf 8 0 11 inf inf inf inf 10 inf inf inf inf inf inf inf 14

inf 11 inf 11

inf inf inf inf inf 11 0 inf 10 inf inf inf inf inf inf inf inf inf inf

inf inf 15 inf inf

inf inf inf inf inf inf inf 0 inf inf 11 inf 15 inf 19 inf inf inf inf

inf inf inf inf 8

inf 28 inf inf inf inf 10 inf 0 inf inf inf inf inf 19 inf inf inf inf

inf inf inf inf 25

inf inf inf inf inf inf inf inf inf 0 inf 8 inf 6 inf inf inf inf inf 8

inf inf inf inf

inf inf inf inf inf inf inf 11 inf inf 0 inf 12 inf 23 inf inf inf inf

inf inf inf inf inf

inf inf inf inf inf 10 inf inf inf 8 inf 0 9 inf inf inf inf inf inf

inf inf inf inf 10

inf inf inf inf inf inf inf 15 inf inf 12 9 0 6 inf inf inf inf inf

inf inf inf inf inf

inf inf inf inf inf inf inf inf inf 6 inf inf 6 0 inf inf inf inf inf

inf inf inf inf inf

inf inf inf inf inf inf inf 19 19 inf 23 inf inf inf 0 inf inf inf inf

inf inf inf inf inf

inf inf inf 9 inf inf inf inf inf inf inf inf inf inf inf 0 7 inf inf

inf 10 inf inf inf

inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 7 0 12 inf

inf inf inf inf inf

20 inf inf 8 inf inf inf inf inf inf inf inf inf inf inf inf 12 0 inf

inf inf inf inf inf

inf inf 10 inf 6 inf inf inf inf inf inf inf inf inf inf inf inf inf 0

inf 7 inf inf inf

inf inf inf inf 9 14 inf inf inf 8 inf inf inf inf inf inf inf inf inf 0

15 inf inf inf

inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf 10 inf inf 7 15

0 inf inf inf

inf 22 15 inf inf 11 15 inf inf inf inf inf inf inf inf inf inf inf inf

inf inf 0 8 inf

16 18 inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf inf

inf inf 8 0 inf

inf inf inf inf inf 11 inf 8 25 inf inf 10 inf inf inf inf inf inf inf

inf inf inf inf 0] ;

[b,path]= floydz (a); d=b

最短路径运行结果： d =

0 34 24 28 33 35 39 54 49 50 65 45 54 56 68 37 32 20 34 42 41 24 16 46

34 0 37 48 41 33 37 52 28 51 63 43 52 57 47 57 64 54 47 47 54 22 18 44

24 37 0 11 9 17 28 36 38 26 47 27 36 32 55 20 27 19 10 18 17 15 23 28

28 48 11 0 20 28 39 47 49 37 58

33 41 9 20 0 8 19 27 29 17 38 18 27 23 46 23 30 28 6 9 13 19 27 19

35 33 17 28 8 0 11 19 21 18 30 10 19 24 38 31 38 36 14 14 21 11 19 11

39 37 28 39 19 11 0 30 10 29 41 21 30 22

54 18 15 8

49 31 40 25

50 8 12 18

65 21 12 19

45 0 9 10

54 9 0 19

56 14 6 24

68 37 34 27

37 41 45 42

32 48 52 49

20 46 55 47

35 29 52 36 21 19 28 38 45 19 51 26 6 45 63 47 18 23 43 27 14 37 52 36 6 34 57 32 0 40 47 55 40 0 57 20 39 69 64 27 46 76 54 19 51 74 42 49 47 47 27 19 50 57 55 49 29 21 52 59 57 37 17 18 33 40 45 58 38 30 57 64 66 38 18 10 41 48 46 47 27 19 45 52 55 43 23 24 39 46 51 66 46 38 69 76 74 9 23 31 0 7 17 16 30 38 7 0 12 8 28 36 17 12 0 25 25 30 0 33 33 10 33 35 35 29 26 23 8 41 11 44 32 21 18 24 16 30 15 33 20 35 21 29 14 29 19 52 52 42 50 17 25 49 57 24 32 47 55 29 37 32 15 33 26 40 30 0 39 42 25 39 0 23 29 42 24 47 41 31 8 31 21 40 12 35 30 45 6 29 35 19 45 59 44 52 33 10 35 59 40 17 42 57 45 27 34 23 11 38 42 33 24 37 0 49 21 29 12 38 18 43 23 52 57 43 64 48 66 36

24 33 29 52 17 24 29 0 15 7 25 33 25

42 47 18 29 9 14 25 33 35 8 32 16 20 14 52 25 32 37 15 0 15 25 33 25

41 54 17 19 13 21 32 40 42 23 47 31 35 29 59 10 17 27 7 15 0 32 40 32

24 22 15 26 19 11 15 30 25 29 41 21 30 35 44 35 42 34 25 25 32 0 8 22

16 18 23 34 27 19 23 38 33 37 49 29 38 43 52 43 48 36 33 33 40 8 0 30

46 44 28 39 19 11 22 8 25 18 19 10 19 24 27 42 49 47 25 25 32 22 30 0

附录三

求3个缴费站的源代码 clear all ;

A=combntns(1:24,3); %定义A 为任意三个数组成的矩阵 for i=1:nchoosek(24,3) %循环的次数

B=A(i,:); %返回第i 行 x=B(1,1); y=B(1,2); z=B(1,3);

People=[ 10 12 18 6 10 15 4 8 7 11 13 11 11 8 9 22 14 8 7 10 15 28 18 13]; d=[

0 34 24 28 33 35 39 54 49 50 65 45 54 56 68 37 32 20 34 42 41 24 16 46

34 0 37 48 41 33 37 52 28 51 63 43 52 57 47 57 64 54 47 47 54 22 18

24 37 0 11 9 17 28 36 38 26 47 27 36 32 55 20 27 19 10 18 17 15 23 28

28 48 11 0 20 28 39 47 49 37 58 38 47 43 66 9 16 8 21 29 19 26 34 39

33 41 9 20 0 8 19 27 29 17 38 18 27 23 46 23 30 28 6 9 13 19 27 19

35 33 17 28 8 0 11 19 21 18 30 10 19 24 38 31 38 36 14 14 21 11 19 11

39 37 28 39 19 11 0 30 10 29 41 21 30 35 29 42 49 47 25 25 32 15 23 22

54 52 36 47 27 19 30 0 33 26 11 18 15 21 19 50 57 55 33 33 40 30 38 8

49 28 38 49 29 21 10 33 0 39 42 31 40 45 19 52 59 57 35 35 42 25 33 25

50 51 26 37 17 18 29 26 39 0 24 8 12 6 45 33 40 45 23 8 23 29 37 18

65 63 47 58 38 30 41 11 42 24 0 21 12 18 23 57 64 66 44 32 47 41 49 19

45 43 27 38 18 10 21 18 31 8 21

54 52 36 47 27 19 30 15 40 12 12 9 0 6 34 45 52 55 33 20 35 30 38 19

56 57 32 43 23 24 35 21 45 6 18 14 6 0 40 39 46 51 29 14 29 35 43 24

68 47 55 66 46 38 29 19 19 45 23 37 34 40 0 69 76 74 52 52 59 44 52 27

37 57 20 9 23 31 42 50 52 33 57 41 45 39 69 0 7 17 17 25 10 35 43 42

32 64 27 16 30 38 49 57 59 40 64 48 52 46 76 7 0 12 24 32 17 42 48 49

20 54 19 8 28 36 47 55 57 45 66 46 55 51 74 17 12 0 29 37 27 34 36 47

34 47 10 21 6 14 25 33 35 23 44 24 33 29 52 17 24 29 0 15 7 25 33 25

42 47 18 29 9 14 25 33 35 8 32 16 20 14 52 25 32 37 15 0 15 25 33 25

41 54 17 19 13 21 32 40 42 23 47 31 35 29 59 10 17 27 7 15 0 32 40 32

21 30 35 44 35 42 34 25 25 32 0 8 22

16 18 23 34 27 19 23 38 33 37 49 29 38 43 52 43 48 36 33 33 40 8 0 30

46 44 28 39 19 11 22 8 25 18 19 10 19 24 27 42 49 47 25 25 32 22 30 0 ];

B1=d(:,x); %将其他社区到x 社区的最短距离返回给列向量B1 B2=d(:,y); %将其他社区到y 社区的最短距离返回给列向量B2 B3=d(:,z); %将其他社区到z 社区的最短距离返回给列向量B3 E=[B1 B2 B3 ];

F=sort(E,2); %将F 矩阵按行由小到大排列 Short=F(:,1); %得到24个社区到x,y,z 的最短距离 Sum(i)=People*Short; end

G=reshape(Sum,nchoosek(24,3),1); %返回各情况下解的矩阵 minS=find(G==min(G)); %将收费站的位置返回给minS L=min(G); A=combntns(1:24,3);

S=A(minS,:) %缴费站的位置

L=L/288 %人均最短平均距离（百米）

运行结果： S =

13 16 22 L =

11.7118

附录四

确定派出所个数代码

model :

sets : ! 定义集;

shequ/1..24/:p; ! 定义派出所数量;

link(shequ,shequ):d,x; ! 定义最短路程和决策变量;

endsets

data :

d= 0 34 24 28 33 35 39 54 49 50 65 45 54 56 68 37 32 20 34 42 41 24 16 46