公园道路最短路径问题

公园道路最短路径问题

摘要

针对问题一：我们建立了基于floyd 算法的综合评价模型。我们根据题目所给的的信息，主要通过任意两点边线距离是否可用进行第一步筛选，选出个直连路径。根据题目所提供的原则，我们选取了路长和利用效率相结合的权值，并且构建了一种满足题目要求的路径，长度为472.5m

针对问题二：我们建立了一种基于蚁群算法的数学模型来求解。把主要路径进行分类，然后以入口为单位综合评价了各个点对点间路径使用频率的情况。 通过建立约束函数选择初步出要选用的路径，在根据所选择的路径，通过最佳路径算法求出修路过程中的路程及由其产生的一系列影响。列出路线综合筛选方程，比较选择出，即为我们所需要的最优旅游路线。

针对问题三：与问题二对比后发现问题三可以直接对问题二结果修正后得到。考察湖泊对参照问题二的影响，在蚁群算法的基础上建立综合比较方程，全面的评估了湖泊对路径的影响。对相关路径修正后得出结果。

关键词： 图论 floyd 算法 最佳路径 蚁群算法

一、问题背景

随着近些年，国家经济的发展，教育投入的增加，以及高校的进一步扩招，许多大学都陆陆续续建起了新校区或者是分校，校园建筑正是许多老师和学生共同关注的。一方面，校园建筑要注重美观，注重校园特色；另一方面，处于经济上的考虑，建筑成本也是不可忽视的一个重要因素。现有一所大学，正是如此，他们计划建一个矩形公园，公园计划有若干出口，现在处于成本的考虑，要去设计道路让任意两个入口相连，使得总长度最小，且两个入口之间的最短道路不大于两点连线的1.4倍。先就此问题作如下几个方面的探讨:

主要问题：

主要设计对象可假设为如图所示的矩形公园，其相关数据为：长200米，宽100米，1至8各入口的坐标分别为：

P1(20,0),P2(50,0),P3(160,0),P4(200,50),

P5(120,100),P6(35,100),P7(10,100),P8(0,25).

示意图见图1，其中图2即是一种满足要求的设计，但不是最优的。

现在完成以下问题：

问题一：假定公园内确定要使用4个道路交叉点为：A(50,75)，B(40,40)，C(120,40)，D(115,70）。问如何设计道路可使公园内道路的总路程最短。建立模型并给出算法。画出道路设计，计算新修路的总路程。

问题二：现在公园内可以任意修建道路，如何在满足条件下使总路程最少。建立模型并给出算法。给出道路交叉点的坐标，画出道路设计，计算新修路的总路程。 问题三：若公园内有一条矩形的湖，新修的道路不能通过，但可以到达湖四周的边，示意图见图3。重复完成问题二 的任务。

其中矩形的湖为R1(140,70),R2(140,45),R3=(165,45),R4=(165,70)。 注：以上问题中都要求公园内新修的道路与四周的连接只能与8个路口相通，而不能连到四周的其它点。

图 1 公园及入口示意图

图 2 一种可能的道路设计图

二·问题分析

统观问题后，我们发现问题均为最短路径问题。且问题一、问题三均建立在问题二基础上针对各问题我们决定先解决问题二，个问题对应方法如下：

针对问题一：我们建立了基于floyd 算法的综合评价模型。首先针对所有数据进行整理，考虑到在满足题目要求下总路程尽可能短，且边线不计入总路程，故尽可能运用边线距离可使计算简化，列表将所有十二个点两两直线距离、边线距离列表求出整理筛选出48个直连路径。随后，将数据代入建立基于floyd 算法的综合评价模型。得到最短路径。

针对问题二：属最短路径问题，最优路径问题。建立蚁群算法模型。蚁群算法是求解交通路网中两点间的最短路径，是智能系统中一个重要的功能, 能够更为准确快速地找到最优解, 我们尝试采用带有方向引导信息的蚁群算法来实现该功能. 实验结果表明, 该方法能较为准确地找到交通路网中两点间最短路径的最优解。

针对问题三：与传统蚁群问题相近，我们依旧采用蚁群算法。在蚁群算法的基础上建立综合比较方程，全面的评估了湖泊对路径的影响。对相关路径修正后得出结果。

三、模型假设

1:假设目标公园是一个平面

2：公园内地理环境全部相同

3：每个拐角处都为一个点

4：公园内每处的景色都一样，即没有特定的区域

5：每一条道路赋给一定量的权值，总的结果优化为路径权值的权值

四、符号系统

公园入口 P1~P8(简记为阿拉伯数字1~8 )

道路交叉点 A~B (简记为阿拉伯数字9~12)

两点连接路径 X--Y

蚁群算法中的符号系统

N 表示网络中的节点数;

M 是蚁群中蚂蚁的数

Q 为常量;

T 表示循环次数

α 和β 为两个参数, 分别反映了蚂蚁在运动过程中所积累的信息 和启发信息在蚂蚁选择路径中的相对重要性.

五、模型建立

路径的权值优化系统

对于每条线路的考察有3个方面

1）这条线路的长度

2）这条线路的利用率

3）这条线路的可替换性

我们主要通过这3个方面的比较，选取合适的路径来进行建模，得到最短的路径。

问题一：公园内确定要使用4个道路交叉点为：A(50,75)，B(40,40)，C(120,40)，D(115,70）。

1.1准备阶段

基础数据处理与整理

我们将1~12点任意两点间直线距离、边线距离计算整理，逐步筛选48个必选通路：见附表（1）（2）

1.2基于floyd 算法的最短路线问题

（1）floyd 算法建立

实际上，问题一可以看成是在给定的加权图中，求最短路径的问题。

Floyd 算法的基本思路是：从图的带权邻接矩阵A=[a(i,j)]n×n 开始，递归地进行n 次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地

公式由D(1)构造出D(2)；……；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i 行j 列元素便是i 号顶点到j 号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path 来记录两点间的最短路径。

递推公式为：

D(0)=A；

D(1)=[dij(1)]n×n ，其中dij(1)=min{dij(0),di1(0)+d1j(0)}；

D(2)=[dij(2)] n×n ，其中dij(2)=min{dij(1),di2(1)+d2j(1)}；

……

D(n)=[ dij(n)] n×n ，其中dij(n)=min{dij(n-1),di, n-1 (n-1)+d n-1,j(n-1)}；

采用循环迭代可以简便求出上述矩阵序列，具体算法如下：

D(i,j):dij(k)；

Path(i,j)：对应于d(i,j)(k)的路径上i 的后继点，最终的取值为i 到j 的最短路径上i 的后继点。

输入带权邻接矩阵A=[a(i,j)]n×n

1） 赋初值

对所有i,j,d(i,j)=a(i,j)；当a(i,j)=无穷大时，path(i,j)=0，否则path(i,j)=j；k=1。

2） 更新d(i,j)，path(i,j)

对所有i,j ，若d(i,k)+d(k,j)>=d(i,j)，则转3）；否则d(i,j)=d(i,k)+d(k,j)，path(i,j)=path(i,k)，k=k+1，继续执行3）。

3） 重复2）直到k=n+1。

MATLAB 源程序见附源程序（1）

（2）数据的数值化处理

a=[

000 030 inf inf inf inf inf 032 inf 044 inf inf

030 000 110 inf inf inf inf inf inf 041 inf inf

inf 110 000 090 inf inf inf inf inf inf 056 inf

inf inf 090 000 032 inf inf inf inf inf 081 087

inf inf inf 032 000 inf inf inf inf inf inf 030

inf inf inf inf inf 000 025 083 030 inf inf inf

inf inf inf inf inf 025 000 085 047 inf inf inf

032 inf inf inf inf 083 085 000 070 042 inf inf

inf inf inf inf inf 030 047 070 000 036 inf 065

044 041 inf inf inf inf inf 042 036 000 080 inf

inf inf 056 081 inf inf inf inf inf 080 000 030

inf inf inf 087 030 inf inf inf 065 inf 030 000

];

注：a 矩阵是所用点之间的间距和可连接性分析

通过MATLAB 的数据处理我们得到了以下结果

ans =

【 0 30 140 204 175 110 117 32 80 44 124 145

30 0 110 174 172 107 124 62 77 41 121 142

140 110 0 64 96 181 198 172 151 136 56 86

204 174 64 0 32 157 174 197 127 161 81 62

175 172 96 32 0 125 142 165 95 131 60 30

110 107 181 157 125 0 25 83 30 66 125 95

117 124 198 174 142 25 0 85 47 83 142 112

32 62 172 197 165 83 85 0 70 42 122 135

80 77 151 127 95 30 47 70 0 36 95 65

44 41 136 161 131 66 83 42 36 0 80 101

124 121 56 81 60 125 142 122 95 80 0 30

145 142 86 62 30 95 112 135 65 101 30 0】

对于以上结果的分析我们可以得到一个较为合适的结果

即连接以上的点

（P1,P8）（P2,P10）（P3,P11）（P3,P4）（P4,P12）（P5,P12）（P9,P12）(P6,P9) 在对以上结果进行优化分析

最后在代入数据进行验证，得到最后的结果

原图路线：

（5）结果分析

通过对各项数值比对后我们确定新修道路设计如图

新修总路程为：470.2m

对所建立模型的可行性分析：

本模型中，通过附表我们可以得到每个入口之间都可以满足1.4倍的要求

问题二：现在公园内可以任意修建道路，如何在满足条件下使总路程最少。

2.1准备阶段

选取1~8点对点数据处理结果整理

表三

8个必选直连通路（初选）

2.2模型建立

（1）适合交通路网中蚁群算法模型

蚁群算法是求解交通路网中两点间的最短路径是智能交通系统中一个重要的功能, 能够更为准确快速地找到最优解, 我们尝试采用带有方向引导信息的蚁群算法来实现该功能，

我们在应用蚁群算法对中问题二最短路径的求解的研究中, 发现对于求解众多组合优化问题具有较好求解最优解能力的蚁群算法, 即传统蚁群算法, 用在求两点间的最短路径问题上容易出现如下问题:

(1)两点间出现半循环路径或根本就搜索失败, 即由于在众多组合优化问题中没有方向性的限制, 不利于收敛速度 的提高或者造成整个搜索的失败; 信息素更新模块中, 当第 k 只蚂蚁完成一条搜索路径时, 在其经过的边上按照局部更新规则对信息素浓度进行更新 , 即局部更新模块。

(2)容易陷入局部最优解, 即当搜索循环到一定次数后, 由 于局部最优解产生的信息素浓度的增加, 造成了所有搜索都趋于一个解, 即出现近似遗传算法中的早熟现象，针对以上问题, 我们采用了适合交通路网中两点间最短路径的蚁群算法模型.

根据图论中的相关知识, 整个公园和道路被抽象成为带权网络无向图G=( V, E , W) , 其中 V 为网络顶点的有穷非空集合, E 为 V 中顶点之间边的有穷集, W 为 E 上个边权值的有穷集. 基 于 图 G=( V, E , W) 的 蚁 群 算 法

的 组 成 模 型 如 图所 示 群系

通过这种方法我们得到了以下的结果，并且对结果进行了可行性分析和优化，得到了最终的优化结果，

最终我们通过MATLAB 计算得到结果如下所示

但是以上的结果通过验证，我们发现有些入口不能够满足最短路径为直线距离1.4倍的要求，于是我们就对以上的路径进行了修正，主要的修正方法如下 通过CAD 画圆，初步排除掉一些点，将1.4倍近似为1.41倍，通过画圆和椭圆的方法得到最佳值主要是通过调整道路的交叉口的位置来达到所需要的值。 （3）结果分析

通过对各项数值比对后我们确定新修道路设计如图

最后的结果为：新修总路程为：364.6m

新的道路交叉的坐标分别是：（45.29 92.81）和（182.7 49.32）

每个入口之间的最短距离见附表

出入口1--51--61--82--52--6最短路径197135.5232.02167.98105.48允许最大值197.99141.5744.82170.89141.57出入口2--73--43--53--63--7最短路径130.4871.59

134.84219.84244.84通过上表我们可以看出，我们所建的模型是符合标准的

问题三：若公园内有一条矩形的湖，新修的道路不能通过，但可以到达湖四周的边，示意图见图3。重复完成问题二 的任务。其中矩形的湖为：R1(140,70),R2(140,45),R3=(165,45),R4=(165,70)。

问题3是在问题2的基础上来的，我们依旧选用了问题2中的蚁群算法模型通过在增加路障的方式来表示湖的位置

相比于问题二，我们发现仅需要增加P11点即可达到所需要的结果

新修总路程：372.41m

新的道路交叉的坐标分别是：（45.29 92.81），（182.7 49.32） （165 70）

六、模型分析

本模型较好地解决了题目中的问题。相对于传统模型，我们认为有如下 优点：

通常计算2点间最短路径采用Dijkstra 算法，Dijkstra 算法则用于计算一个节点到其他所有节点的最短路径。Dijkstra 算法是已经证明的能得出最短路径的最优解，但它的效率是一个很大的问题。对于具有n 个节点的一个图，计算一个节点到图中其余节点最短路径的算法时间复杂度为O(n2)。Floyd 算法则用于同时计算出所有节点之间的最短路径。能够大大的简化计算量。同时蚁群算法是一种人工智能的算法，能够拟合出合适的值，得到最适合我们的结果。 缺点：

本模型是基于多种假设多建立的，和实际情况还有一些差距，模型中没有考虑到不同的区域人流量有所不同等问题

七、模型推广

生活中，经常会遇到一些路径最短，最优，费用最低等问题。如：旅游路线选取，公交路线安排，以及铺设铁路，电话线等。我相信我们的模型也可以轻松解决这一类问题。

另外，由于软件使用种类繁多，可以更全面，更准确的反应现实中容易被忽略的损失现象，供使用者更好更及时发现并改进。

八、结论

对于公园内道路设计问题，我们建立了一套独立的搜索体系（粗选-量化-判断-精选）。我们比较成功的解决了公园内道路设计问题，给出了三个问题各自最有优解决方案。

对于模型本身，我们认为有如下优缺点： 优点：

（1）适用范围广，我们的模型适用于多种最短路径类问题。将最短路径，最优路径，蚁群问题集中解决。

（2）在解决过程中我们的模型，首先是对一类问题重基础问题的解决（如问题二）其次层层加深，可解决一定程度内较为复杂的最短路径问题。

（3）解决问题时，我们的模型第一时间将基础数据处理完成，为后续工作极大节省时间。

（4）在处理最问题二时，对讨论三点间取对短路径交点时结合Auto CAD 等专业绘图软件，较为直观的展现实际模型，大大节省不必要的计算次数，有启迪作用，希望后续研究建模者加以改进。

九、参考文献

1 基于遗传算法的机器人路径规划 2 蚁群算法最短路径

3 MATLAB 遗传算法工具箱及应用

4 基于模糊数学和Dijkstra 算法的地质公园地质科普旅游线路设计 5 基于模糊数学和Dijkstra 算法的地质公园地质科普旅游线路设计 6 图论算法理论、实现及应用 7 遗传算法及其MATLAB 实现

建模过程中用到的数据处理表格 表一：

48个必选直连通路（初选）

表二：

数据处理部分

表3

建模过程中所使用的源程序 附：源程序（1）floyd 的MATLAB 实现 function [d,path]=floyd(a,sp,ep) % floyd - 最短路问题 %

% Syntax: [d,path]=floyd(a,sp,ep) %

% Inputs:

% a - 距离矩阵是指i 到j 之间的距离 可以是有向的 % sp - 起点的标号 % ep - 终点的标号 %

% Outputs:

% d - 最短路的距离 % path - 最短路的路径 n=size(a,1); D=a;

path=zeros(n,n);

for i=1:n

for j=1:n if D(i,j)~=inf

path(i,j)=j; %j是i 的后续点

end

end

end

for k=1:n

for i=1:n

for j=1:n

if D(i,j)>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

p=[sp];

mp=sp;

for k=1:n

if mp~=ep

d=path(mp,ep);

p=[p,d];

mp=d;

end

end

d=D(sp,ep)

path=p

Floyd （A ）

附:源程序，基于MATLAB 的蚁群算法最小路径问题的程序设计

clear all

close all

clc

%初始化蚁群

m=31;%蚁群中蚂蚁的数量，当m 接近或等于节点个数n 时，本算法可以在最少的迭代次数内找到最优解

C=[20 0;50 0;160 0;200 50;120 100;35 100;10 100;0 25;

];%节点的坐标矩阵

Nc_max=200;%最大循环次数，即算法迭代的次数，亦即蚂蚁出动的拨数（每拨蚂蚁的数量当然都是m ）

alpha=1;%蚂蚁在运动过程中所积累信息（即信息素）在蚂蚁选择路径时的相对重要程度，alpha 过大时，算法迭代到一定代数后将出现停滞现象

beta=5;%启发式因子在蚂蚁选择路径时的相对重要程度

rho=0.5;%0

Q=100;%蚂蚁释放的信息素量，对本算法的性能影响不大

%变量初始化

n=size(C,1);%表示TSP 问题的规模，亦即节点的数量

D=ones(n,n);%表示节点完全地图的赋权邻接矩阵，记录节点之间的距离 for i=1:n

for j=1:n

if i

D(i,j)=sqrt((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2); end

D(j,i)=D(i,j);

end

end

eta=1./D;%启发式因子，这里设为节点之间距离的倒数

pheromone=ones(n,n);%信息素矩阵, 这里假设任何两个节点之间路径上的初始信息素都为1

tabu_list=zeros(m,n);%禁忌表，记录蚂蚁已经走过的节点，蚂蚁在本次循环中不能再经过这些节点。当本次循环结束后，禁忌表被用来计算蚂蚁当前所建立的解决方案，即经过的路径和路径的长度

Nc=0;%循环次数计数器

routh_best=zeros(Nc_max,n);%各次循环的最短路径

length_best=ones(Nc_max,1);%各次循环最短路径的长度

length_average=ones(Nc_max,1);%各次循环所有路径的平均长度

while Nc

%将m 只蚂蚁放在n 个节点上

rand_position=[];

for i=1:ceil(m/n)

rand_position=[rand_position,randperm(n)];

end

tabu_list(:,1)=(rand_position(1:m))';%将蚂蚁放在节点上之后的禁忌表，第i 行表示第i 只蚂蚁，第i 行第一列元素表示第i 只蚂蚁所在的初始节点 %m只蚂蚁按概率函数选择下一座节点，在本次循环中完成各自的周游 for j=2:n

for i=1:m

city_visited=tabu_list(i,1:(j-1));%已访问的节点

city_remained=zeros(1,(n-j+1));%待访问的节点

probability=city_remained;%待访问节点的访问概率

cr=1;

for k=1:n%for循环用于求待访问的节点。比如如果节点个数是5，而已访问的节点city_visited=[2 4],则经过此for 循环后city_remanied=[1 3 5]

if length(find(city_visited==k))==0

city_remained(cr)=k;

cr=cr+1;

end

end

%状态转移规则**************************************** q0=0.5;

if rand>q0

for k=1:length(city_remained)

probability(k)=(pheromone(city_visited(end),city_remained(k)))^alpha*(eta(city_visited(end),city_remained(k)))^beta;

position=find(probability==max(probability)); to_visit=city_remained(position(1));

end

else

for k=1:length(city_remained)

probability(k)=(pheromone(city_visited(end),city_remained(k)))^alpha*(eta(city_visited(end),city_remained(k)))^beta;

end

probability=probability/sum(probability);

pcum=cumsum(probability);

select=find(pcum>=rand);

to_visit=city_remained(select(1));

end

tabu_list(i,j)=to_visit;

%**************************************************************

end

end

if Nc>0

tabu_list(1,:)=routh_best(Nc,:);%将上一代的最优路径（最优解）保留下来，保证上一代中的最适应个体的信息不会丢失

end

%记录本次循环的最佳路线

total_length=zeros(m,1);%m只蚂蚁在本次循环中分别所走过的路径长度 for i=1:m

r=tabu_list(i,:);%取出第i 只蚂蚁在本次循环中所走的路径 for j=1:(n-1)

total_length(i)=total_length(i)+D(r(j),r(j+1));%第i 只蚂蚁本次循环中从起点节点到终点节点所走过的路径长度

end

total_length(i)=total_length(i)+D(r(1),r(n));%最终得到第i 只蚂蚁在本次循环中所走过的路径长度

end

length_best(Nc+1)=min(total_length);%把m 只蚂蚁在本次循环中所走路径长度的最小值作为本次循环中最短路径的长度

position=find(total_length==length_best(Nc+1));%找到最短路径的位置，即最短路径是第几只蚂蚁或哪几只蚂蚁走出来的

routh_best(Nc+1,:)=tabu_list(position(1),:);%把第一个走出最短路径的蚂蚁在本次循环中所走的路径作为本次循环中的最优路径

length_average(Nc+1)=mean(total_length);%计算本次循环中m 只蚂蚁所走路径的平均长度

Nc=Nc+1

%更新信息素

delta_pheromone=zeros(n,n);

for i=1:m

for j=1:(n-1)

delta_pheromone(tabu_list(i,j),tabu_list(i,j+1))=delta_pheromone(tabu_list(i,j),tabu_list(i,j+1))+Q/total_length(i);%total_length(i)为第i 只蚂蚁在本次循环中所走过的路径长度（蚁周系统区别于蚁密系统和蚁量系统的地方）

end

delta_pheromone(tabu_list(i,n),tabu_list(i,1))=delta_pheromone(tabu_list(i,n),tabu_list(i,1))+Q/total_length(i);%至此把第i 只蚂蚁在本次循环中在所有路径上释放的信息素已经累加上去

end%至此把m 只蚂蚁在本次循环中在所有路径上释放的信息素已经累加上去

pheromone=(1-rho).*pheromone+delta_pheromone;%本次循环后所有路径上的信息素

%禁忌表清零，准备下一次循环，蚂蚁在下一次循环中又可以自由地进行选择

tabu_list=zeros(m,n);

end

%输出结果，绘制图形

position=find(length_best==min(length_best));

shortest_path=routh_best(position(1),:)

shortest_length=length_best(position(1))

%绘制最短路径

figure(1)

set(gcf,'Name','Ant Colony Optimization——Figure of

shortest_path','Color','r')

N=length(shortest_path);

scatter(C(:,1),C(:,2),50,'filled');

hold on

plot([C(shortest_path(1),1),C(shortest_path(N),1)],[C(shortest_path(1),2),C(shortest_path(N),2)])

set(gca,'Color','g')

hold on

for i=2:N

plot([C(shortest_path(i-1),1),C(shortest_path(i),1)],[C(shortest_path(i-1),2),C(shortest_path(i),2)])

hold on

end

%绘制每次循环最短路径长度和平均路径长度

figure(2)

set(gcf,'Name','Ant Colony Optimization——Figure of length_best and length_average','Color','r')

plot(length_best,'r')

set(gca,'Color','g')

hold on

plot(length_average,'k')

公园道路最短路径问题

摘要

针对问题一：我们建立了基于floyd 算法的综合评价模型。我们根据题目所给的的信息，主要通过任意两点边线距离是否可用进行第一步筛选，选出个直连路径。根据题目所提供的原则，我们选取了路长和利用效率相结合的权值，并且构建了一种满足题目要求的路径，长度为472.5m

针对问题二：我们建立了一种基于蚁群算法的数学模型来求解。把主要路径进行分类，然后以入口为单位综合评价了各个点对点间路径使用频率的情况。 通过建立约束函数选择初步出要选用的路径，在根据所选择的路径，通过最佳路径算法求出修路过程中的路程及由其产生的一系列影响。列出路线综合筛选方程，比较选择出，即为我们所需要的最优旅游路线。

针对问题三：与问题二对比后发现问题三可以直接对问题二结果修正后得到。考察湖泊对参照问题二的影响，在蚁群算法的基础上建立综合比较方程，全面的评估了湖泊对路径的影响。对相关路径修正后得出结果。

关键词： 图论 floyd 算法 最佳路径 蚁群算法

一、问题背景

随着近些年，国家经济的发展，教育投入的增加，以及高校的进一步扩招，许多大学都陆陆续续建起了新校区或者是分校，校园建筑正是许多老师和学生共同关注的。一方面，校园建筑要注重美观，注重校园特色；另一方面，处于经济上的考虑，建筑成本也是不可忽视的一个重要因素。现有一所大学，正是如此，他们计划建一个矩形公园，公园计划有若干出口，现在处于成本的考虑，要去设计道路让任意两个入口相连，使得总长度最小，且两个入口之间的最短道路不大于两点连线的1.4倍。先就此问题作如下几个方面的探讨:

主要问题：

主要设计对象可假设为如图所示的矩形公园，其相关数据为：长200米，宽100米，1至8各入口的坐标分别为：

P1(20,0),P2(50,0),P3(160,0),P4(200,50),

P5(120,100),P6(35,100),P7(10,100),P8(0,25).

示意图见图1，其中图2即是一种满足要求的设计，但不是最优的。

现在完成以下问题：

问题一：假定公园内确定要使用4个道路交叉点为：A(50,75)，B(40,40)，C(120,40)，D(115,70）。问如何设计道路可使公园内道路的总路程最短。建立模型并给出算法。画出道路设计，计算新修路的总路程。

问题二：现在公园内可以任意修建道路，如何在满足条件下使总路程最少。建立模型并给出算法。给出道路交叉点的坐标，画出道路设计，计算新修路的总路程。 问题三：若公园内有一条矩形的湖，新修的道路不能通过，但可以到达湖四周的边，示意图见图3。重复完成问题二 的任务。

其中矩形的湖为R1(140,70),R2(140,45),R3=(165,45),R4=(165,70)。 注：以上问题中都要求公园内新修的道路与四周的连接只能与8个路口相通，而不能连到四周的其它点。

图 1 公园及入口示意图

图 2 一种可能的道路设计图

二·问题分析

统观问题后，我们发现问题均为最短路径问题。且问题一、问题三均建立在问题二基础上针对各问题我们决定先解决问题二，个问题对应方法如下：

针对问题一：我们建立了基于floyd 算法的综合评价模型。首先针对所有数据进行整理，考虑到在满足题目要求下总路程尽可能短，且边线不计入总路程，故尽可能运用边线距离可使计算简化，列表将所有十二个点两两直线距离、边线距离列表求出整理筛选出48个直连路径。随后，将数据代入建立基于floyd 算法的综合评价模型。得到最短路径。

针对问题二：属最短路径问题，最优路径问题。建立蚁群算法模型。蚁群算法是求解交通路网中两点间的最短路径，是智能系统中一个重要的功能, 能够更为准确快速地找到最优解, 我们尝试采用带有方向引导信息的蚁群算法来实现该功能. 实验结果表明, 该方法能较为准确地找到交通路网中两点间最短路径的最优解。

针对问题三：与传统蚁群问题相近，我们依旧采用蚁群算法。在蚁群算法的基础上建立综合比较方程，全面的评估了湖泊对路径的影响。对相关路径修正后得出结果。

三、模型假设

1:假设目标公园是一个平面

2：公园内地理环境全部相同

3：每个拐角处都为一个点

4：公园内每处的景色都一样，即没有特定的区域

5：每一条道路赋给一定量的权值，总的结果优化为路径权值的权值

四、符号系统

公园入口 P1~P8(简记为阿拉伯数字1~8 )

道路交叉点 A~B (简记为阿拉伯数字9~12)

两点连接路径 X--Y

蚁群算法中的符号系统

N 表示网络中的节点数;

M 是蚁群中蚂蚁的数

Q 为常量;

T 表示循环次数

α 和β 为两个参数, 分别反映了蚂蚁在运动过程中所积累的信息 和启发信息在蚂蚁选择路径中的相对重要性.

五、模型建立

路径的权值优化系统

对于每条线路的考察有3个方面

1）这条线路的长度

2）这条线路的利用率

3）这条线路的可替换性

我们主要通过这3个方面的比较，选取合适的路径来进行建模，得到最短的路径。

问题一：公园内确定要使用4个道路交叉点为：A(50,75)，B(40,40)，C(120,40)，D(115,70）。

1.1准备阶段

基础数据处理与整理

我们将1~12点任意两点间直线距离、边线距离计算整理，逐步筛选48个必选通路：见附表（1）（2）

1.2基于floyd 算法的最短路线问题

（1）floyd 算法建立

实际上，问题一可以看成是在给定的加权图中，求最短路径的问题。

Floyd 算法的基本思路是：从图的带权邻接矩阵A=[a(i,j)]n×n 开始，递归地进行n 次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地

公式由D(1)构造出D(2)；……；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i 行j 列元素便是i 号顶点到j 号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path 来记录两点间的最短路径。

递推公式为：

D(0)=A；

D(1)=[dij(1)]n×n ，其中dij(1)=min{dij(0),di1(0)+d1j(0)}；

D(2)=[dij(2)] n×n ，其中dij(2)=min{dij(1),di2(1)+d2j(1)}；

……

D(n)=[ dij(n)] n×n ，其中dij(n)=min{dij(n-1),di, n-1 (n-1)+d n-1,j(n-1)}；

采用循环迭代可以简便求出上述矩阵序列，具体算法如下：

D(i,j):dij(k)；

Path(i,j)：对应于d(i,j)(k)的路径上i 的后继点，最终的取值为i 到j 的最短路径上i 的后继点。

输入带权邻接矩阵A=[a(i,j)]n×n

1） 赋初值

对所有i,j,d(i,j)=a(i,j)；当a(i,j)=无穷大时，path(i,j)=0，否则path(i,j)=j；k=1。

2） 更新d(i,j)，path(i,j)

对所有i,j ，若d(i,k)+d(k,j)>=d(i,j)，则转3）；否则d(i,j)=d(i,k)+d(k,j)，path(i,j)=path(i,k)，k=k+1，继续执行3）。

3） 重复2）直到k=n+1。

MATLAB 源程序见附源程序（1）

（2）数据的数值化处理

a=[

000 030 inf inf inf inf inf 032 inf 044 inf inf

030 000 110 inf inf inf inf inf inf 041 inf inf

inf 110 000 090 inf inf inf inf inf inf 056 inf

inf inf 090 000 032 inf inf inf inf inf 081 087

inf inf inf 032 000 inf inf inf inf inf inf 030

inf inf inf inf inf 000 025 083 030 inf inf inf

inf inf inf inf inf 025 000 085 047 inf inf inf

032 inf inf inf inf 083 085 000 070 042 inf inf

inf inf inf inf inf 030 047 070 000 036 inf 065

044 041 inf inf inf inf inf 042 036 000 080 inf

inf inf 056 081 inf inf inf inf inf 080 000 030

inf inf inf 087 030 inf inf inf 065 inf 030 000

];

注：a 矩阵是所用点之间的间距和可连接性分析

通过MATLAB 的数据处理我们得到了以下结果

ans =

【 0 30 140 204 175 110 117 32 80 44 124 145

30 0 110 174 172 107 124 62 77 41 121 142

140 110 0 64 96 181 198 172 151 136 56 86

204 174 64 0 32 157 174 197 127 161 81 62

175 172 96 32 0 125 142 165 95 131 60 30

110 107 181 157 125 0 25 83 30 66 125 95

117 124 198 174 142 25 0 85 47 83 142 112

32 62 172 197 165 83 85 0 70 42 122 135

80 77 151 127 95 30 47 70 0 36 95 65

44 41 136 161 131 66 83 42 36 0 80 101

124 121 56 81 60 125 142 122 95 80 0 30

145 142 86 62 30 95 112 135 65 101 30 0】

对于以上结果的分析我们可以得到一个较为合适的结果

即连接以上的点

（P1,P8）（P2,P10）（P3,P11）（P3,P4）（P4,P12）（P5,P12）（P9,P12）(P6,P9) 在对以上结果进行优化分析

最后在代入数据进行验证，得到最后的结果

原图路线：

（5）结果分析

通过对各项数值比对后我们确定新修道路设计如图

新修总路程为：470.2m

对所建立模型的可行性分析：

本模型中，通过附表我们可以得到每个入口之间都可以满足1.4倍的要求

问题二：现在公园内可以任意修建道路，如何在满足条件下使总路程最少。

2.1准备阶段

选取1~8点对点数据处理结果整理

表三

8个必选直连通路（初选）

2.2模型建立

（1）适合交通路网中蚁群算法模型

蚁群算法是求解交通路网中两点间的最短路径是智能交通系统中一个重要的功能, 能够更为准确快速地找到最优解, 我们尝试采用带有方向引导信息的蚁群算法来实现该功能，

我们在应用蚁群算法对中问题二最短路径的求解的研究中, 发现对于求解众多组合优化问题具有较好求解最优解能力的蚁群算法, 即传统蚁群算法, 用在求两点间的最短路径问题上容易出现如下问题:

(1)两点间出现半循环路径或根本就搜索失败, 即由于在众多组合优化问题中没有方向性的限制, 不利于收敛速度 的提高或者造成整个搜索的失败; 信息素更新模块中, 当第 k 只蚂蚁完成一条搜索路径时, 在其经过的边上按照局部更新规则对信息素浓度进行更新 , 即局部更新模块。

(2)容易陷入局部最优解, 即当搜索循环到一定次数后, 由 于局部最优解产生的信息素浓度的增加, 造成了所有搜索都趋于一个解, 即出现近似遗传算法中的早熟现象，针对以上问题, 我们采用了适合交通路网中两点间最短路径的蚁群算法模型.

根据图论中的相关知识, 整个公园和道路被抽象成为带权网络无向图G=( V, E , W) , 其中 V 为网络顶点的有穷非空集合, E 为 V 中顶点之间边的有穷集, W 为 E 上个边权值的有穷集. 基 于 图 G=( V, E , W) 的 蚁 群 算 法

的 组 成 模 型 如 图所 示 群系

通过这种方法我们得到了以下的结果，并且对结果进行了可行性分析和优化，得到了最终的优化结果，

最终我们通过MATLAB 计算得到结果如下所示

但是以上的结果通过验证，我们发现有些入口不能够满足最短路径为直线距离1.4倍的要求，于是我们就对以上的路径进行了修正，主要的修正方法如下 通过CAD 画圆，初步排除掉一些点，将1.4倍近似为1.41倍，通过画圆和椭圆的方法得到最佳值主要是通过调整道路的交叉口的位置来达到所需要的值。 （3）结果分析

通过对各项数值比对后我们确定新修道路设计如图

最后的结果为：新修总路程为：364.6m

新的道路交叉的坐标分别是：（45.29 92.81）和（182.7 49.32）

每个入口之间的最短距离见附表

出入口1--51--61--82--52--6最短路径197135.5232.02167.98105.48允许最大值197.99141.5744.82170.89141.57出入口2--73--43--53--63--7最短路径130.4871.59

134.84219.84244.84通过上表我们可以看出，我们所建的模型是符合标准的

问题三：若公园内有一条矩形的湖，新修的道路不能通过，但可以到达湖四周的边，示意图见图3。重复完成问题二 的任务。其中矩形的湖为：R1(140,70),R2(140,45),R3=(165,45),R4=(165,70)。

问题3是在问题2的基础上来的，我们依旧选用了问题2中的蚁群算法模型通过在增加路障的方式来表示湖的位置

相比于问题二，我们发现仅需要增加P11点即可达到所需要的结果

新修总路程：372.41m

新的道路交叉的坐标分别是：（45.29 92.81），（182.7 49.32） （165 70）

六、模型分析

本模型较好地解决了题目中的问题。相对于传统模型，我们认为有如下 优点：

通常计算2点间最短路径采用Dijkstra 算法，Dijkstra 算法则用于计算一个节点到其他所有节点的最短路径。Dijkstra 算法是已经证明的能得出最短路径的最优解，但它的效率是一个很大的问题。对于具有n 个节点的一个图，计算一个节点到图中其余节点最短路径的算法时间复杂度为O(n2)。Floyd 算法则用于同时计算出所有节点之间的最短路径。能够大大的简化计算量。同时蚁群算法是一种人工智能的算法，能够拟合出合适的值，得到最适合我们的结果。 缺点：

本模型是基于多种假设多建立的，和实际情况还有一些差距，模型中没有考虑到不同的区域人流量有所不同等问题

七、模型推广

生活中，经常会遇到一些路径最短，最优，费用最低等问题。如：旅游路线选取，公交路线安排，以及铺设铁路，电话线等。我相信我们的模型也可以轻松解决这一类问题。

另外，由于软件使用种类繁多，可以更全面，更准确的反应现实中容易被忽略的损失现象，供使用者更好更及时发现并改进。

八、结论

对于公园内道路设计问题，我们建立了一套独立的搜索体系（粗选-量化-判断-精选）。我们比较成功的解决了公园内道路设计问题，给出了三个问题各自最有优解决方案。

对于模型本身，我们认为有如下优缺点： 优点：

（1）适用范围广，我们的模型适用于多种最短路径类问题。将最短路径，最优路径，蚁群问题集中解决。

（2）在解决过程中我们的模型，首先是对一类问题重基础问题的解决（如问题二）其次层层加深，可解决一定程度内较为复杂的最短路径问题。

（3）解决问题时，我们的模型第一时间将基础数据处理完成，为后续工作极大节省时间。

（4）在处理最问题二时，对讨论三点间取对短路径交点时结合Auto CAD 等专业绘图软件，较为直观的展现实际模型，大大节省不必要的计算次数，有启迪作用，希望后续研究建模者加以改进。

九、参考文献

1 基于遗传算法的机器人路径规划 2 蚁群算法最短路径

3 MATLAB 遗传算法工具箱及应用

4 基于模糊数学和Dijkstra 算法的地质公园地质科普旅游线路设计 5 基于模糊数学和Dijkstra 算法的地质公园地质科普旅游线路设计 6 图论算法理论、实现及应用 7 遗传算法及其MATLAB 实现

建模过程中用到的数据处理表格 表一：

48个必选直连通路（初选）

表二：

数据处理部分

表3

建模过程中所使用的源程序 附：源程序（1）floyd 的MATLAB 实现 function [d,path]=floyd(a,sp,ep) % floyd - 最短路问题 %

% Syntax: [d,path]=floyd(a,sp,ep) %

% Inputs:

% a - 距离矩阵是指i 到j 之间的距离 可以是有向的 % sp - 起点的标号 % ep - 终点的标号 %

% Outputs:

% d - 最短路的距离 % path - 最短路的路径 n=size(a,1); D=a;

path=zeros(n,n);

for i=1:n

for j=1:n if D(i,j)~=inf

path(i,j)=j; %j是i 的后续点

end

end

end

for k=1:n

for i=1:n

for j=1:n

if D(i,j)>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

p=[sp];

mp=sp;

for k=1:n

if mp~=ep

d=path(mp,ep);

p=[p,d];

mp=d;

end

end

d=D(sp,ep)

path=p

Floyd （A ）

附:源程序，基于MATLAB 的蚁群算法最小路径问题的程序设计

clear all

close all

clc

%初始化蚁群

m=31;%蚁群中蚂蚁的数量，当m 接近或等于节点个数n 时，本算法可以在最少的迭代次数内找到最优解

C=[20 0;50 0;160 0;200 50;120 100;35 100;10 100;0 25;

];%节点的坐标矩阵

Nc_max=200;%最大循环次数，即算法迭代的次数，亦即蚂蚁出动的拨数（每拨蚂蚁的数量当然都是m ）

alpha=1;%蚂蚁在运动过程中所积累信息（即信息素）在蚂蚁选择路径时的相对重要程度，alpha 过大时，算法迭代到一定代数后将出现停滞现象

beta=5;%启发式因子在蚂蚁选择路径时的相对重要程度

rho=0.5;%0

Q=100;%蚂蚁释放的信息素量，对本算法的性能影响不大

%变量初始化

n=size(C,1);%表示TSP 问题的规模，亦即节点的数量

D=ones(n,n);%表示节点完全地图的赋权邻接矩阵，记录节点之间的距离 for i=1:n

for j=1:n

if i

D(i,j)=sqrt((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2); end

D(j,i)=D(i,j);

end

end

eta=1./D;%启发式因子，这里设为节点之间距离的倒数

pheromone=ones(n,n);%信息素矩阵, 这里假设任何两个节点之间路径上的初始信息素都为1

tabu_list=zeros(m,n);%禁忌表，记录蚂蚁已经走过的节点，蚂蚁在本次循环中不能再经过这些节点。当本次循环结束后，禁忌表被用来计算蚂蚁当前所建立的解决方案，即经过的路径和路径的长度

Nc=0;%循环次数计数器

routh_best=zeros(Nc_max,n);%各次循环的最短路径

length_best=ones(Nc_max,1);%各次循环最短路径的长度

length_average=ones(Nc_max,1);%各次循环所有路径的平均长度

while Nc

%将m 只蚂蚁放在n 个节点上

rand_position=[];

for i=1:ceil(m/n)

rand_position=[rand_position,randperm(n)];

end

tabu_list(:,1)=(rand_position(1:m))';%将蚂蚁放在节点上之后的禁忌表，第i 行表示第i 只蚂蚁，第i 行第一列元素表示第i 只蚂蚁所在的初始节点 %m只蚂蚁按概率函数选择下一座节点，在本次循环中完成各自的周游 for j=2:n

for i=1:m

city_visited=tabu_list(i,1:(j-1));%已访问的节点

city_remained=zeros(1,(n-j+1));%待访问的节点

probability=city_remained;%待访问节点的访问概率

cr=1;

for k=1:n%for循环用于求待访问的节点。比如如果节点个数是5，而已访问的节点city_visited=[2 4],则经过此for 循环后city_remanied=[1 3 5]

if length(find(city_visited==k))==0

city_remained(cr)=k;

cr=cr+1;

end

end

%状态转移规则**************************************** q0=0.5;

if rand>q0

for k=1:length(city_remained)

probability(k)=(pheromone(city_visited(end),city_remained(k)))^alpha*(eta(city_visited(end),city_remained(k)))^beta;

position=find(probability==max(probability)); to_visit=city_remained(position(1));

end

else

for k=1:length(city_remained)

probability(k)=(pheromone(city_visited(end),city_remained(k)))^alpha*(eta(city_visited(end),city_remained(k)))^beta;

end

probability=probability/sum(probability);

pcum=cumsum(probability);

select=find(pcum>=rand);

to_visit=city_remained(select(1));

end

tabu_list(i,j)=to_visit;

%**************************************************************

end

end

if Nc>0

tabu_list(1,:)=routh_best(Nc,:);%将上一代的最优路径（最优解）保留下来，保证上一代中的最适应个体的信息不会丢失

end

%记录本次循环的最佳路线

total_length=zeros(m,1);%m只蚂蚁在本次循环中分别所走过的路径长度 for i=1:m

r=tabu_list(i,:);%取出第i 只蚂蚁在本次循环中所走的路径 for j=1:(n-1)

total_length(i)=total_length(i)+D(r(j),r(j+1));%第i 只蚂蚁本次循环中从起点节点到终点节点所走过的路径长度

end

total_length(i)=total_length(i)+D(r(1),r(n));%最终得到第i 只蚂蚁在本次循环中所走过的路径长度

end

length_best(Nc+1)=min(total_length);%把m 只蚂蚁在本次循环中所走路径长度的最小值作为本次循环中最短路径的长度

position=find(total_length==length_best(Nc+1));%找到最短路径的位置，即最短路径是第几只蚂蚁或哪几只蚂蚁走出来的

routh_best(Nc+1,:)=tabu_list(position(1),:);%把第一个走出最短路径的蚂蚁在本次循环中所走的路径作为本次循环中的最优路径

length_average(Nc+1)=mean(total_length);%计算本次循环中m 只蚂蚁所走路径的平均长度

Nc=Nc+1

%更新信息素

delta_pheromone=zeros(n,n);

for i=1:m

for j=1:(n-1)

delta_pheromone(tabu_list(i,j),tabu_list(i,j+1))=delta_pheromone(tabu_list(i,j),tabu_list(i,j+1))+Q/total_length(i);%total_length(i)为第i 只蚂蚁在本次循环中所走过的路径长度（蚁周系统区别于蚁密系统和蚁量系统的地方）

end

delta_pheromone(tabu_list(i,n),tabu_list(i,1))=delta_pheromone(tabu_list(i,n),tabu_list(i,1))+Q/total_length(i);%至此把第i 只蚂蚁在本次循环中在所有路径上释放的信息素已经累加上去

end%至此把m 只蚂蚁在本次循环中在所有路径上释放的信息素已经累加上去

pheromone=(1-rho).*pheromone+delta_pheromone;%本次循环后所有路径上的信息素

%禁忌表清零，准备下一次循环，蚂蚁在下一次循环中又可以自由地进行选择

tabu_list=zeros(m,n);

end

%输出结果，绘制图形

position=find(length_best==min(length_best));

shortest_path=routh_best(position(1),:)

shortest_length=length_best(position(1))

%绘制最短路径

figure(1)

set(gcf,'Name','Ant Colony Optimization——Figure of

shortest_path','Color','r')

N=length(shortest_path);

scatter(C(:,1),C(:,2),50,'filled');

hold on

plot([C(shortest_path(1),1),C(shortest_path(N),1)],[C(shortest_path(1),2),C(shortest_path(N),2)])

set(gca,'Color','g')

hold on

for i=2:N

plot([C(shortest_path(i-1),1),C(shortest_path(i),1)],[C(shortest_path(i-1),2),C(shortest_path(i),2)])

hold on

end

%绘制每次循环最短路径长度和平均路径长度

figure(2)

set(gcf,'Name','Ant Colony Optimization——Figure of length_best and length_average','Color','r')

plot(length_best,'r')

set(gca,'Color','g')

hold on

plot(length_average,'k')