1. 引言
水是生命之源,是城市发展的基础。近些年来,随着我国经济的迅猛发展,城市化进程和人口迅速扩张,城市用水量也日益剧增,城市供水面临的问题越来越突出,严重限制了城市的进一步发展。而管道是运输水源的重要途径,所以说对管道的铺设进行优化设计显得刻不容缓。管道铺设问题的优化其根本目的在于能够最大限度的缩小管道的铺设长度,其实也就是我们常说的最短路径问题。目前,国内外的专家学者对最短路线问题已经有了很多的研究。比如,王俊珺、夏华丽( [1] )选择Dijkstra算法作为核心算法;并且针对原始Dijkstra算法的不足,分别对原始Dijkstra算法的数据存储方式、执行效率和数据结构提出了优化方法;施益昌、郑贤斌等( [2] )应用Floyd算法,借助于MATLAB程序设计语言对动态规划中最短路径进行了有效的设计;赵娟、王建新( [3] )运用动态规划方法的基本思想求解最短路径问题;张水舰、刘学军等( [4] )定义了动态随机最短路径,给出了动态随机最短路径优化数学模型,提出了一种动态随机最短路径遗传算法;王树西、吴政学( [5] )通过对Dijkstra算法进行改进,解决了Dijkstra算法退出机制对不联通的有向图是无效的,会陷入死循环等问题;王荣、江东、韩惠( [6] )将Floyd与Dijkstra算法结合,优化后的算法在很大程度上减少了运算次数和时间,提高了算法的时间及空间复杂度,算法效率较高。本文主要基于Dijkstra算法的思想并作出了改进,Dijkstra算法是保证源点到各个顶点之间的路程最短,而改进后的算法是在保证经过所有顶点的前提下,使得总的路线最短,这样就提出了管道铺设最短路线的优化设计方案,给出了算法步骤,并编制出了MATLAB程序。
2. 优化设计数学模型
假设有一个自来水厂为周边的城市进行供水,自来水厂净化的水足够多,完全可以供应周边城市,那我们如何进行管道的铺设可以将自来水厂生产的自来水供应给周边的城市又保证所铺设的管道路线最短呢?下面我们给出两种思路的管道铺设优化方案。
2.1. 单条线路的管道铺设方案(附录1)
假设自来水厂的位置是固定的,它要供给给周边n个城市的自来水,并且我们已知任何一个城市之间的距离以及任何一个城市和自来水厂的距离。因为我们建造的是单条线路的管道,即管道由自来水厂出发经过所有的城市,最终到达最后一个城市,所以我们先固定自来水厂找到和自来水厂距离最近的城市,然后再以该城市为起点找到和它距离最近的城市,进行迭代,每次都选取最近的距离,最终所形成的路线也是最短的。
例如,在图1所示中,1表示自来水厂,2~6表示自来水厂要供给自来水的五个城市,采用单条线路进行管道铺设,每段路线长度如图1所示,问如何才能使得铺设管道的总路线最短?
通过计算得知,从自来水厂开始铺设管道先到达3号城市,由3号城市再铺到5号城市,再到2号城市,再由2号城市到4号城市,最后铺到6号城市结束。即:1→3→5→2→4→6。图中红线部分即为
Figure 1. Single line pipe laying diagram
图1. 单条线路管道铺设图
管道铺设的分布图(长度单位为km),总长度为11.3 km。
下面我们通过矩阵的形式进行解释:
第一步,构造自来水厂与各个城市之间的距离以及各个城市之间的距离,设
为自来水厂和第j个城市之间的距离,
表示为第i个城市与第j个城市之间的距离,这样就可以建立一个
的矩阵A。
其中,在矩阵A中当
时,
表示的为自身之间的距离,为避免对数据准确性造成影响,故设为无穷大数。
第二步,比较矩阵A的第一列,得出第一列的最小值,设为
,其含义为自来水厂与第k个城市之间的距离最短。
第三步,以第k个城市为起点,找与第k个城市距离最短的城市。我们需要先找到矩阵A的第
行,因为第
行表示的是第k个城市与其他城市之间的距离。所以我们比较第
行中各个元素的大小,可得第
行中最小的元素为
,其含义为第k个城市与第m个城市之间距离最短。输出城市m后,将元素
所在的列上所有的元素都变为无穷大值,得到矩阵B。
第四步,以城市m为起点,找到与城市m距离最近的城市。先找到矩阵B的第
行,比较
行中所有元素的大小,得出
为最小值。按照第三步的做法将p输出,并将
所在列的所有元素变为无穷大值,得到矩阵C。
第五步,每次都按照第三步的方法依次进行迭代,每次输出一个值,直到最后输出完所有值,进行完n次迭代,根据依次输出的值就可以知道从自来水厂经过各个城市的最短单条线路的顺序。
本题是基于迭代思想并且运用矩阵给出的算最短路径的方法,该方法简单易懂,过程相对简单,不过对于计算机要求较高,运算起来较为麻烦,对前期数据要求较为具体,但是也从迭代的方面提出了最短路径的算法。
2.2. 树状的管道铺设方案(附录2)
我们下面运用Dijkstra算法的思想对上述问题进行进一步的优化求解,在我们的日常生活中自来水厂给周围城市进行供水一般来说不会采用单线路的管道运水方案,因为这样来说不能够做到铺设管道总路线最短,现在一般都采用树状形式的管道输水路线,这样既可以做到铺设管道总路线最短,又可以保证使用的管材最省。通过Dijkstra算法求解管道铺设总路线最短的主要思想是每次找到离源点最近的一个点,然后将该点看做源点再寻找离它最近点,通过层层迭代,最终就可以找到铺设管道的最短路线。
例如,在图2所示中,1表示自来水厂,2~6表示自来水厂要供给自来水的五个城市,现在采用树状的管道铺设方案对管道进行铺设,每段路线长度如图1所示,问如何才能使得铺设管道的总路线最短?
同样是上面的问题,如果我们采用树状的管道铺设方案,其管道铺设方案如下图所示。
下面我们具体的进行解释:
第一步,我们先将源点到各个城市之间的距离和各个城市之间的距离用矩阵的形式表示出来。用0表示自来水厂,
表示n个城市,
表示自来水厂到n个城市之间的距离,
表示第i个城市到第j个城市之间的距离,
表示n个城市到自来水厂的距离,则表示上述距离的矩阵A可表示为:
其中矩阵A中
时表示的是自身之间的距离,为避免对数据准确性造成影响,故设为无穷大数。
第二步,先对矩阵第一行自来水厂与各个城市之间的距离大小进行比较,假设自来水厂和城市k之间的距离最小,即
是第一行所有元素中最小的。先输出k值,然后将矩阵中的
和第
行的元素
都用无穷大值替换,得到矩阵B。
第三步,比较第1行和第
行中所有的元素求出最小值,下面假设几种不同的情况:
① 若
是其中的最小值,那么表示从自来水厂直接到城市m距离最小;
② 若
是其中的最小值,那么表示从第k个城市到第p个城市之间距离最小,我们就可以从城市k直接铺设管道到达城市p,这样就会减少管道铺设的总线路,达到最节约管材。
第四步,先假设第三步中的②成立,然后将
以及矩阵B中第
行元素
变为无穷大值,得到新的矩阵C,按照上述的方法再比较矩阵C中的第1行、第
行和第
行中的所有元素得出最小的元素,下面对最小的元素进行分情况讨论:
① 若
是最小的元素,即从自来水厂直接铺设管道到城市q会使得总路线最短;
② 若
是最小的元素,即从城市k铺设管道到城市w会使得总路线最短;
③ 若
是最小的元素,即从城市p铺设管道到城市r会使得总路线最短。
第五步,根据上述的做法进行层层迭代,就可以求出铺设管道到所有城市总路线最短的方案。
该方法较为贴合实际,对现实的生活中管道铺设方案有较为重要的指导意义,本算法是基于Dijkstra算法,在此基础上进行的进一步的改进,Dijkstra算法研究的是源点到各个顶点之间的路程最短,而我们这个算法是在保证经过所有顶点的前提下,使得总的路线最短,这样就可以达到铺设管道所用管材最省,节约社会资源。
3. 数值算例
有一个自来水厂要给周围的5个城市供水,自来水厂和5个城市依次用1~6个数字进行表示,自来水厂和5个城市的分布图如图1所示,自来水厂到各个城市之间的距离以及5个城市之间的距离如表1,求在经过所有城市的前提下,从自来水厂如何铺设管道?
求解思路:首先,用矩阵形式表示自来水厂和5个城市以及5个城市之间的距离,然后比较第一行中元素的大小,根据第一行元素的位置,找到下一个元素的位置,将两个元素都变为无穷大值,再比较两行的元素的大小得出最小值,再逐次往下计算。具体求解过程:
Step1:用矩阵形式表示自来水厂和各个城市之间的距离以及5个城市之间的距离:
Step2:先比较第一行元素的大小值,经过比较得出第一行中最小值为
,再将矩阵A中的
和
都用无穷大值替换,得到矩阵B:
即先从自来水厂出发铺设管道到第3个城市。
Step3:比较矩阵中的第一行和第三行的元素,得最小值
,再将矩阵B的
和
用无穷大值替换,得到矩阵C:
即从自来水厂铺设管道到第3个城市,再从第3个城市铺设管道到达第5个城市
Step4:比较矩阵中的第一行、第三行和第五行元素,得最小值是
,再将矩阵C中的
和
用无穷大值替换,得到矩阵D:
即从自来水厂铺设管道到第3个城市,再从第3个城市铺设管道到达第5个城市,再由第3个城市铺设管道到第4个城市
Step5:依次进行下去,就可以得到管道铺设方案为从自来水厂铺设管道到第3个城市,再从第3个城市铺设管道到达第5个城市,再由第3个城市铺设管道到第4个城市,由第3个城市铺设管道到第2个城市,再由第4个城市铺设管道到第6个城市,总长为
,分布图如图3所示。
如果采用单条线路铺设方案,需要铺设的管道长度为
,而采用树状管道铺设方案只需要铺设
,与单条线路管道铺设方案相比在管道铺设长度上减少了15%,所以说树状管道铺设方案对于缩短管道铺设长度具有重要的意义。
附录
附录1 单条线路的管道铺设方案MATLAB程序
function [U,V,d]=lcxz(A,b)
B=A;
U=zeros(1,n);
V=ones(1,n);
R=b*ones(1,n);
L=b*ones(m,1);
a=A(1,:);
B(1,:)=R;
B(:,1)=L;
t=1;
U(1,2)=u;
V(1,2)=v;
for i=2:n-1
s=v;
f=B(v,:);
t=i+t;
U(1,i+1)=u;
V(1,i+1)=v;
B(s,:)=R;
B(:,s)=L;
i=i+1;
end
U;
V;
d=sum(U);
附录2树状的管道铺设方案
function [U,V,d]=ndjtsl(A,b)
C=inf*ones(n);
B=A;
U=zeros(1,n);
V=ones(1,n);
rep=b;
a=B(1,:);
B(1,v)=rep;
B(v,1)=rep;
U(1,2)=u;
V(1,2)=v;
f=B(1,:);
for i=3:n
r=v;
F=[f;B(v,:)];
rv=v;
U(1,i)=u;
x=v;
s=V(x);
y=rv(v);
v=y;
V(1,i)=y;
B(r,y)=rep;
B(y,r)=rep;
B(s,y)=rep;
B(y,s)=rep;
f=[f;B(r,:)];
f(x,y)=rep;
i=i+1;
end
d=sum(U);