多级水站间的自来水管道铺设问题

The Problem of Water Pipeline Laying in Multi-Stage Water Stations

摘要: 在村村通自来水工程实施过程中，某区需建1个中心供水站、12个一级供水站、168个二级供水站。中心供水站A与一级供水站及一级供水站之间使用I型管道连接，一级供水站与二级供水站及二级供水站间用II型管道连接。本文主要针对各级供水站间的管道铺设问题，从保证供水质量以及设备维护方便角度出发，以最小化规定型号管道长度为目标，综合分析了供水质量及维修便利程度、水站分布、多级水站相互关系等方面因素，运用LINGO和C++等编程语言进行求解，最后制定出不同条件要求情况下的各级供水管道最优化模型，并进行了适当的科学性分析。

Abstract: In the process of implementing the water supply project to every village, one central water supply station, 12 first-level water supply stations and 168 second-level water supply stations are needed to be built in one district. Center water stop water stop A and level and the level of water stop use between the I type pipe connection, between primary water stop and secondary water stop and secondary water stop using II type pipe connection. This paper is aimed at all levels of the plumbing problem between water stop, from easy to ensure the quality of water supply and equipment maintenance perspective, to minimize regulation model pipe length as the goal, comprehensive analysis of the quality of water supply and maintenance convenience, water station distribution, the relationship between multistage water stations, using LINGO to solve and C++ programming language, finally worked out a different cases of the requirements of all levels of the water supply pipeline optimization model, and make the properly scientific analysis.

1. 问题重述

1.1. 问题背景

在村村通自来水工程实施下，拟建立1个中心供水站，12个一级供水站，168个二级供水站。考虑供水质量与设备维护等角度，需要建立合适的数学模型，求出最优路径。

1.2. 题目重述与理解

某地区需要建设一个中心供水站，12个一级供水站和168个二级供水站。由于供水站间管道铺设技术问题限制，中心供水站只能和一级供水站连接(铺设I型管道)，不能和二级供水站直接相连。一级供水站之间可以连接(铺设I型管道)，且与二级供水站相连(铺设II型管道)。二级供水站之间可以连接(铺设II型管道)。管道铺设均从节点出发，至节点终止，管道长度看作节点间直线距离。

根据上述条件，我们需要研究以下问题：

1. 对于给出的中心、一级、二级水站坐标、管道连接方式等信息，问自来水管道应该如何铺设才能使管道的总里程最少？要求以图形给出铺设方案，并给出I型管道和II型管道总里程数。

2. 由于二型管道供应不足，考虑升级2个二级水站为一级水站解决此问题，问选择哪两个二级水站才能使二型管道总里程数最少？与问题一相比，二型管道总里程减少多少？

3. 在问题一基础上，由于受功率影响，从一级供水站出发铺设的管道只能供水40公里，为解决此问题，考虑升级二级供水站，问最少升级多少个二级供水站，可保证正常运行？铺设管道总里程为多少？

2. 问题分析

该问题属于优化问题，主要的任务是：在已知的水站位置、管道连接方式等限制条件下，建立不同的距离优化模型，从而科学合理地安排出多级水站之间的连接方式。问题属于最小树问题，即对于确定水站信息给出路程最短的水站连接方式。

2.1. 问题一的分析

问题一的要求是在保证供水质量以及设备维护方便的前提下，建立以水站连接管道距离最小为目标的最优化模型，进而求出此情况下的管道连接方式。通过分析问题，我们考虑并解决了题目中水站位置及管道连接方式限制下的距离最短化问题。出于对供水质量及保障维修便利度因素的考虑，我们采用区域中心供水制，将更多的二级供水站划分到距离最近的一级水站区域，将168个二级水站按区域归属于12个一级水站区域。在本题中，我们先运用图论最优树模型，将一级供水系统简化为含权值的树状图形。根据给出的坐标信息，我们求得第一级系统中任意两点之间的最短距离，给出距离矩阵。然后应用同样的方法，对12个区域分别进行距离矩阵计算。最后，我们对水站添加节点约束条件，引入决策变量，形成最优规划模型目标函数，采用Lingo求解得出最短水管道的距离和连接方式。

2.2. 问题二的分析

问题二的要求是在所有二级供水站中选择两个二级供水站升级成为一级供水站，在新一级水站分布情况下建立二级管道铺设距离最短的最优化模型，以达到减少二型管道铺设长度的目的。出于最大限度保障供水质量以及提高维修便利度的要求，我们引入边缘供水站概念，即管道连接中距离线路内一级供水站最远的二级供水站集合。然后通过分析二级供水站升级后对原供水网络带来的影响得出此时必然存在部分二级水站的多源输入情况。我们通过对于新一级水站分布情况下二级水站做出限制，通过分别计算各区域边缘点对II级水管减少带来的影响进行排序比较，得出此最优化模型下二级水站升级的最优选取方案。

2.3. 问题三的分析

问题三的要求是对不满足一级供水站连接支路不超过40公里条件的区域，将二级供水站升级为一级供水站，升级水站数目要求尽量少，同时此配置下总里程数最小。在问题一的基础上，我们首先筛选出不符合条件的区域为V4和V7区域，对此区域选择升级二级水站，考虑到管道里程铺设，我们对A、V4、V7三点使用距离最小值模型，求出最适合升级的二级供水站。二级水站升级为一级水站后我们对涉及到的所有二级水站使用距离矩阵进行区域的重新划分。由问题一的图论最优树模型，求得最后新的管道铺设线路。

3. 模型假设

(1) 同级供水站间功能没有明显差别，可看作完全一样。

(2) 为保障供水质量及维修便利度，我们认为距离更高级供水站越近的低级水站具有很好的供水质量且更容易维修。

(3) 同级管道实现的运输功能没有明显差异，可看作一样。

(4) 管道本身不存在损坏等问题。

(5) 中心供水站供水能力足够强且水资源储备充足。

(6) 划分区域之间无干扰，划分区域时以到区域中心直线距离长短来暂代路径进行划分。

(7) 供水站升级时只有供水能力相关性质发生改变。

4. 符号说明

5. 模型建立与求解

5.1. 问题一的模型与求解

由于中心供水站只能与一级供水站连接，我们将中心供水站与一级供水站整体看作第一级供水系统，系统内使用I型管道进行连接。一级供水站与二级水站整体看作第二级供水系统。

我们将题目所给地图简化为赋权图G，设T是赋权图G的一棵生成树，称T中全部边上的权数之和为生成树的权，记为 $w\left(T\right)$ ，即 $w\left(T\right)={\displaystyle \sum w\left(e\right)}$ 。如果生成树T^*的权 $w\left(T^{*}\right)$ 是G的所有生成树的权最小者，则称T^*是G的最优树，即 $w\left(T^{*}\right)={\displaystyle \sum \min \left\{w\left(T\right)\right\}}$ 。

基于已知的中心水站及一级水站位置坐标信息，我们计算求得包括中心水站在内的13个点间的距离矩阵。

接下来，我们对于水站节点给出限制条件，形成最优规划模型求解一级供水系统的最短管道连接方式。

设无向图共有n个节点，其赋权图的邻接矩阵为 $d_{n\ast n}$ 。 $d_{ij}$ 表示节点i到j的距离。D为对称矩阵。令 $D_{ii}=0$ 。

现求根节点1到各节点生成的最优树，要求各线路上的权值和最小 [1]。

引入决策变量：

$x_{ij}=\{\begin{array}{l}1节点i与j连通\\ 0节点i与j不连通\end{array}$

我们的目标函数为：

$\min Z={\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{d}_{ij}{x}_{ij}}}$

约束条件：

1) 对起始点1至少有一条路出去，故有： ${\displaystyle {\sum }_{j=2}^n{x}_{ij}}\ge 1$

2) 对其余各节点，恰有一条路进入，有： ${\displaystyle {\sum }_{\begin{array}{l}k=1\\ k\ne i\end{array}}^n{x}_{ki}}=1,i=2,\cdots ,n$

3) 所有节点间连线不出现圈，引入变量u，有：

$u_i-u_j-n{x}_{ij}\le n-1,i,j=1,2,\cdots ,n$

总体规划模型为：

$\begin{array}{l}\min Z={\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{d}_{ij}{x}_{ij}}}\\ \text{s}\text{.t}\text{.}\{\begin{array}{l}{\displaystyle \underset{j=2}{\overset{n}{\sum }}{x}_{ij}}\ge 1\\ {\displaystyle \underset{\begin{array}{l}k=1\\ k\ne i\end{array}}{\overset{n}{\sum }}{x}_{ki}}=1,i=2,\cdots ,n\\ u_i-u_j-n{x}_{ij}\le n-1,i,j=1,2,\cdots ,n\\ x_{ij}=0或1\end{array}\end{array}$

5.1.1. 一级供水系统的最短管道连接模型

对于一级供水系统(由中心供水站与12个一级供水站组成)， $n=13$ ，选取中心供水站为1号水站。

总体规划模型为：

$\begin{array}{l}\min Z={\displaystyle \underset{i=1}{\overset{13}{\sum }}{\displaystyle \underset{j=1}{\overset{13}{\sum }}{d}_{ij}{x}_{ij}}}\\ \text{s}\text{.t}\text{.}\{\begin{array}{l}{\displaystyle \underset{j=2}{\overset{13}{\sum }}{x}_{ij}}\ge 1\\ {\displaystyle \underset{\begin{array}{l}k=1\\ k\ne i\end{array}}{\overset{13}{\sum }}{x}_{ki}}=1,i=2,\cdots ,13\\ u_i-u_j-n{x}_{ij}\le 13,i,j=1,2,\cdots ,13\\ x_{ij}=0或1\end{array}\end{array}$

得到距离矩阵 $D_1$ ，以图1方式给出。

Figure 1. Distance matrix between water stations

图1. 水站间距离矩阵

5.1.2. 一级供水系统的最短管道连接问题求解

将上述中已得到的数据输入LINGO软件中，可直接得出一级供水系统的连接方式，如图2 (0对于A中心水站)。

Figure 2. Connection mode of primary water supply system

图2. 一级供水系统的连接方式

对应水站位置连接结果如图3。图中，横坐标为水站位置相对原点水平投影，纵坐标为水站位置相对原点竖直方向投影。下文水站连接图同理。

Figure 3. Location connection results of water stations

图3. 水站位置连接结果

此时一级管道连接最短距离为： $\min Z={\displaystyle {\sum }_{i=1}^{13}{\displaystyle {\sum }_{j=1}^{13}{d}_{ij}{x}_{ij}}}=120.9412\text{km}$ 。

5.1.3. 各区域内二级供水系统的最短管道连接模型

考虑到供水质量及保障维修便利度因素，我们采用区域中心供水制，从每个二级供水站出发寻找距离它最近的一级供水站，选择同一一级供水站的二级水站组成一个集合，将168个二级水站按区域归属于12个一级水站区域。我们通过计算每一二级水站距离12个一级供水站的完整距离矩阵，得到分区情况。

对于每一个区域二级系统，我们进行赋权图简化，应用5.1.1中的最小树模型，将各二级区域内的一级供水站看作供水出发点，设为1号水站，得到总体规划模型为：

$\begin{array}{l}\min Z={\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{d}_{ij}{x}_{ij}}}\\ \text{s}\text{.t}\text{.}\{\begin{array}{l}{\displaystyle \underset{j=2}{\overset{n}{\sum }}{x}_{ij}}\ge 1\\ {\displaystyle \underset{\begin{array}{l}k=1\\ k\ne i\end{array}}{\overset{n}{\sum }}{x}_{ki}}=1,i=2,\cdots ,n\\ u_i-u_j-n{x}_{ij}\le n-1,i,j=1,2,\cdots ,n\\ x_{ij}=0或1\end{array}\end{array}$

5.1.4. 二级供水系统的最短管道连接问题求解

根据我们得到的分区情况，区域对应规划模型中的n值如图3。

将上述中已得到的数据输入LINGO软件中，可直接得出各区二级供水系统的连接方式，如图4~图6 (各区中区号点对应区域的一级供水站)。

Figure 4. Connection mode of water stations in zone V1~V4

图4. V1~V4区水站连接方式

Figure 5. Connection mode of water stations in V5~V8 zones

图5. V5~V8区水站连接方式

得到最终整体二级供水系统连接方式如图7。

此时二级管道连接最短距离为： $\min L=484.38409\text{km}$ 。

综合上述一级、二级供水系统连接方式求解，我们得到最终所有水站连接方式如图8。

Figure 6. Connection mode of water stations in V9~V12 zones

图6. V9~V12区水站连接方式

Figure 7. Connection mode of the overall secondary water supply system

图7. 整体二级供水系统连接方式

Figure 8. Connection mode of primary and secondary water supply systems

图8. 一级、二级供水系统连接方式

5.2. 二级水站升级的选取模型与求解

5.2.1. 二级水站升级的选取模型

根据二级水站连接方式，我们可以将二级水站进行分类。基于二级供水站有无传递水源能力，我们将二级水站分为以下两类：

$\{\begin{array}{l}只接受供水类型\left(如下图\text{9}中\text{B}点\right)\\ 作为供水中转类型\left(如下图\text{9}中\text{A}点\right)\end{array}$

Figure 9. Classification diagram of secondary water stations

图9. 二级水站分类示意图

通过决策变量 ${\displaystyle {\sum }_{\begin{array}{l}k=1\\ k\ne i\end{array}}^n{x}_{ki}}=1,i=2,\cdots ,n$ 可以看出，任何类型的二级水站都只有一个输入路线 [2]。

我们首先引入边缘点的概念：边缘点是在各二级供水系统中，到达一级供水站路线长度较长，处于各区二级供水系统边缘的二级水站。根据分析，我们可以知道边缘点具有如下特征：

(1) 距离区域一级供水站距离较远，供水质量等条件较差。

(2) 连接边缘点使用更多II型供水管道。

出于更大程度增强供水质量以及缩短II型供水管道的目的，我们认为应优先升级各区域的边缘点。

根据分析二级点升级后对于周围二级点的影响，我们发现，在一条线路中对二级点进行升级时，将

必然出现 ${\displaystyle {\sum }_{\begin{array}{l}k=1\\ k\ne i\end{array}}^n{x}_{ki}}>1,i=2,\cdots ,n$ 的情况，如图10示意。此时B升级为一级点，A存在两条输入路线。

Figure 10. Schematic diagram of connection of secondary water station after upgrade

图10. 二级水站升级后连接示意图

针对这种情况，为了满足 ${\displaystyle {\sum }_{\begin{array}{l}k=1\\ k\ne i\end{array}}^n{x}_{ki}}=1,i=2,\cdots ,n$ 的决策变量限制，我们在已知线路中减去一条输入路线。

此时升级成一级供水站的二级供水站可以使全部二级供水站满足单条道路输入并且减短了二级水站的供水距离。根据5.1中所得到的各区域内部距离矩阵，我们挑选出成为通道的二级管道距离，并进行排序。找出各区域内最长的单条二级管道并设置该条通道上的边缘点为所在区域边缘点：B1~B12。如图11所示。

12个区域内最长二级管道距离J1~J12如图12。

当以i区边缘点作为升级点时，比较 $B_{ij}\left(i=1,2,\cdots ,12;j=1,\cdots ,12\right)$ 与 $J_j\left(j\ne i\right)$ 的大小关系，当 $B_{ij}\left(i=1,2,\cdots ,12;j=1,\cdots ,12\right)>J_j\left(j\ne i\right)$ 时，不连通两个边缘点。当 $B_{ij}\left(i=1,2,\cdots ,12;j=1,\cdots ,12\right)\le J_j\left(j\ne i\right)$ 时，连通两个边缘点，此时II型管道长增加 $B_{ij}$ ，减小 $J_j$ 。

Figure 11. Area edge points B1~B12

图11. 区域边缘点B1~B12

Figure 12. Distance of the longest secondary pipeline in 12 areas J1~J12

图12. 12个区域内最长二级管道距离J1~J12

12个区域边缘点间距离矩阵如图13。

引入决策变量 $Y_{ij}$ ：

$Y_{ij}=\{\begin{array}{l}1节点B_i与B_j连通\\ 0节点B_i与B_j不连通\end{array}$

目标函数为：

$\begin{array}{l}\min T={\displaystyle \underset{i=1}{\overset{12}{\sum }}{\displaystyle \underset{j=1}{\overset{12}{\sum }}\left(B_{ij}-J_j\right)Y_{ij}}}\\ \text{s}\text{.t}\text{.}\{\begin{array}{l}{B}_{ij}>J_j,Y_{ij}=0\\ B_{ij}\le J_j,Y_{ij}=1\\ Y_{ij}=0或1\end{array}\end{array}$

Figure 13. Distance matrix between edge points of 12 regions

图13. 12个区域边缘点间距离矩阵

5.2.2. 二级水站升级的选取模型求解

将上述中已得到的 $B_{ij}$ 距离矩阵逐个输入与 $J_j$ 进行比较，可得出分别取12区域时T值，经过排序后得到最小T值为T5和T8，即选取P9 (24, 30)及P151 (40, 20)点升级为一级供水站，和的值分别为−21.2678和−24.46。B5连接B4，B9，B10，B8连接B10。升级二级水站取点情况如图14所示。图中黄色点为新升级的一级供水站。

Figure 14. Schematic diagram of newly upgraded first-level water supply station

图14. 新升级的一级供水站示意图

此时II型管道减少长度最多，相对于问题一减少45.7278 km (T5 + T8)。II级管道总里程为438.65629 km。

该情况下二级管道连接方式如图15。

Figure 15. Connection mode of secondary pipeline

图15. 二级管道连接方式

5.3. 考虑功率因素的二级水站升级模型与求解

5.3.1. 考虑功率因素的二级水站升级选取模型

在问题一的基础上，我们筛选出不符合题目要求的区域为V4、V7区，考虑将在这两个区域范围内的二级水站中的一个进行升级。新升级一个二级水站为一级水站会增加一级管道铺设里程，本着尽量少使用一级管道的原则，我们将改变中心水站与一级水站原本的连接路线。为使连接线路最短。我们将A、4、7三点连接成三角形，寻求三角形内一点到三角形三个顶点距离之和最小点，将此点设为Q。最靠近此点的二级水站被优化。这种情况下我们不考虑新升级水站对于其他区域的影响。

(1) 寻找点Q

在A、V4、V7构成的三角形(如图16)中选取距离三个顶点距离之和最小的点。

Figure 16. Triangles formed by A, V4 and V7

图16. A、V4、V7构成的三角形

对于Q点的寻找我们建立距离最小模型，设Q点坐标为(x, y)。

目标函数为：

$Z=\sqrt{{\left(x-26\right)}^2+{\left(y-31\right)}^2}+\sqrt{{\left(x-13\right)}^2+{\left(y-34\right)}^2}+\sqrt{{\left(x-25\right)}^2+{\left(y-47\right)}^2}$

令 $\frac{\partial Z}{\partial x}=\frac{\partial Z}{\partial y}=0$ ，求出x, y的值即为Q点坐标。

(2) 寻找被升级的二级水站

在Q点附近搜寻与Q点距离最小的二级水站，将此二级水站升级为一级水站。

(3) 给出新规划区域的最优连接方式

随后我们沿用解决问题一的模型，将新升级为一级水站命名为V13。对原V4区V7区包含的二级供水站重新划分区域，现区域为新V4、V7、V13区。得到每个区域内的距离矩阵，利用图论最优树模型得到新的水站铺设路线。将新规划的4、7、13区域中的一级点设置为1号水站。如5.1给出总体规划模型 [3] 为：

$\begin{array}{l}\min L={\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{d}_{ij}{x}_{ij}}}\\ \text{s}\text{.t}\text{.}\{\begin{array}{l}{\displaystyle \underset{j=2}{\overset{n}{\sum }}{x}_{ij}}\ge 1\\ {\displaystyle \underset{\begin{array}{l}k=1\\ k\ne i\end{array}}{\overset{n}{\sum }}{x}_{ki}}=1,i=2,\cdots ,n\\ u_i-u_j-n{x}_{ij}\le n-1,i,j=1,2,\cdots ,n\\ x_{ij}=0或1\end{array}\end{array}$

同时对中心供水站与一级供水站利用图论最优树模型得到新A区的铺设路线图。

$\begin{array}{l}\min Z={\displaystyle \underset{i=1}{\overset{n}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{d}_{ij}{x}_{ij}}}\\ \text{s}\text{.t}\text{.}\{\begin{array}{l}{\displaystyle \underset{j=2}{\overset{n}{\sum }}{x}_{ij}}\ge 1\\ {\displaystyle \underset{\begin{array}{l}k=1\\ k\ne i\end{array}}{\overset{n}{\sum }}{x}_{ki}}=1,i=2,\cdots ,n\\ u_i-u_j-n{x}_{ij}\le n-1,i,j=1,2,\cdots ,n\\ x_{ij}=0或1\end{array}\end{array}$

5.3.2. 升级后区域划分及铺设路线求解

(1) Q点坐标求解

通过模型建立中的最小距离模型，我们得到被升级的二级水站为P59 (24, 38)。取点情况如图17 (图中黄色点为升级点)。

(2)新V4、V7、V13区铺设线路图

根据我们得到的分区情况，区域对应规划模型中的n值如图18。

将上述中已得到的数据输入LINGO软件中，可直接得出各区二级供水系统的连接方式，如图19 (各区中区号点对应区域的一级供水站)。

由LINGO求解得 $L_4=36.11771\text{km}$ ， $L_7=50.66563\text{km}$ ， $L_{13}=22.72291\text{km}$ 。结合5.1已知结果，可得： $\min L={\displaystyle {\sum }_i^{12}{L}_{i\min }}=484.48187\text{km}$ 。

Figure 17. Upgraded secondary water stations are shown in yellow dots

图17. 被升级的二级水站如图黄色点

Figure 18. The region corresponds to the n value in the planning model

图18. 区域对应规划模型中的n值

Figure 19. Connection mode of secondary water supply system in each district

图19. 各区二级供水系统的连接方式

图形连接方式如图20。

Figure 20. Connection modes of all graphs

图20. 全部图形连接方式

(3) 新一级供水系统铺设线路图

对于一级供水系统， $n=14$ 。将上述中已得到的数据输入LINGO软件中，可直接得出新一级供水系统的连接方式，如图21 (1点对应中心供水站)。

Figure 21. Connection pattern of the new primary water supply system

图21. 新一级供水系统的连接方式

图形连接方式如图22。

整体管道连接方式如图23所示。

在这种情况下，只选取一个二级供水站进行升级。此时，每个一级供水站的分支路线长均小于40 km，所以可以确实，只需升级一个节点即可满足题目要求。这种情况下总距离长为： $L_{\min }+Z_{\min }=609.75977\text{km}$ 。

Figure 22. Connection modes of all graphs

图22. 全部图形连接方式

Figure 23. Overall pipeline connection mode

图23. 整体管道连接方式

6. 模型评价与推广

6.1. 优缺点分析

6.1.1. 优点

1. 我们的模型在最优规划的基础上，进一步灵活运用了线性规划、非线性规划、整数规划、图论最小数等具体模型；

2. 对问题的求解直观简单，计算效率高，程序较易实现；

3. 对问题进行了多方面考虑，按题目对于I、II级管道的限制要求，并综合、多方面考虑了水站的供水质量及维修便利程度等等因素并使用分区供水方式保障供水；

4. 使用的最优规划方法不仅限于题目条件，更将所运用方法向普遍情况发展，具有普遍适用性。此模型不仅可以在本问题中使用，我们还可以将其推广到其他实际问题使用。如通信网络搭建、城市乡村交通规划、都可以通过此模型得到解决。

6.1.2. 缺点

1. 采用的分区域的方法将168个二级供水站分配到12个区域。分区的进行可能一定程度上会影响最小生成树的建立；

2. 模型考虑部分实际影响因素，但与实际情况可能仍存在差异；

3. 在解决一级供水站功率问题时，忽略新一级供水站对功率充足的区域的影响。

6.2. 模型改进方向及拓展

1. 可将整个供水区域作为范围进行水管路线探索，使提升供水质量与维修便利度的方法更完善；

2. 新建立一级供水站时可更多考虑对整体供水系统管道缩短的影响。