07年B题最优公交线路问题(9)

在算法设计之初，设所有的N个蚂蚁都集中在出发站。蚂蚁A从Si 点出发，

26

按照选择策略，从和相关联的线路的集合中，选择一条线路；然后，再从这条线路的另一站点Sk开始，从和Sk相关联的路线中的集合中，选择另一路线；以此类推，直到搜索到终点Sj，于是，蚂蚁A得到一个从Si 到Sj的解。每当蚂蚁选择完一条路线后，就马上更新路线上的信息量(局部更新)，蚂蚁A搜索完后，蚂蚁B从Si出发，按照和A相同的方法，搜索出一条Si从到Sj的路径，得到一个解。直到所有的N个蚂蚁都完成搜索，得到N个解(包括重复的)。以N个解为基础，采用局部搜索算法，进行局部搜索，得到局部最优解；根据局部最优解全局计算信息增量(全局更新)；全局更新后，继续迭代直到满足停止条件，停止条件为最大迭代次数。在所求得的有局部最优解中，值最小的解为所求的全局最优解，即最短路径的距离值。用基本的蚂蚁算法求解最短路径问题的主要实现步骤如下：

1）首先确定两点之间边长的权数，其中权数表示两点之间相连的最短时间（通过地铁，汽车，步行进行比较）。

2）信息初始化。算法开始运行时，赋予每条线路上相等数量的信息量。 选择策略。位于第i个站点的蚂蚁A，按以下选择策略选择边( i，k)。

t(i,s)?q?q0?argsmax?Vi K??q?q0??h式中：Vi表示{和i相连的站点}－{蚂蚁A已访问过的站点}，即每个蚂蚁对每个节点最多只允许访问一次，对不连通的点则赋给一个足够大的惩罚值；argmax(t,s)

为在与i相关联的边的集合中，具有最大信息量的边的另一个站点；q。为给定参数，0

ui=vi-argmax t( i,s )内随机取值。

3)局部更新信息量。当蚂蚁选中边( i，k)后，更新边(i ，k)上的信息量。 t(i，j )＝?t(i，j) 0

每当蚂蚁选中一条边后，就按上式更新减少边上的信息量，从而增加蚂蚁选择其它边的概率。

4)局部搜索。当N只蚂蚁从Si到Sj搜索完后，则求得N个解。为了尽可能遍历所有解，分别在这些解的邻域中，采用局部搜索算法，求出局部最优解。

5)全局更新信息量。当所有的N只蚂蚁都得到局部最优解后，全局更新边上的信息量。

27

6)求全局最优解。到当前迭代次数为止，所建立的所有局部最优解中，值最小的解作为当前迭代次数的全局最优解。选择某条路径的次数越多，说明此路径是比较优的路径，其信息素的数值也越大，为以后选择路径提供必要的信息，运用此算法求解的时间越长，为乘客提供的信息越全面、越准确，查询也越来越智能化。 算法实现

算法实现流程如图1所示。

公交网络数据 用邻接结点算法记录公交线路上每个站点 公交站点数据 生成线路相关表 读取相关表中每条线路所经过的站点及其顺序 生成站点邻接表 用基本的蚂蚁算法计算任意两点的最短路径 得出最佳乘车方案

图1 公交网络最短路径计算步骤

7)初始化。在一个城市中如果公交车的数量、路线不变，那么从一个站到另一个站的路线基本上也不变。先将所有站点之间的路线求出，全部放在数据库中。当乘客选择乘车路线时，根据实时的信息从数据库中选择可行的路线，每条路径附带一个参数，即蚂蚁的信息素，开始时将所有路线上的信息素的值置为相同的值。

8)选择路线。如当前结点为i，当前时刻为t，则转移到点j的概率为

abab?k?U?[Rij(t)][sij(t)]/?[Rij(t)][sij(t)]pij??

其他??0上式中：U为i车的换乘车集；Rij(t)为弧( i，j)在t时间的信息素强度，代表以

28

前信息；sij(t)为欲转车时向j转车的方便程度，代表实时信息；a为以前信息的重要性(a≥0)；b为当前信息的重要性(b≥0)。

9)每次选择完后要根据选择情况确定信息素的值，Rij(new)=??Rij(old)+?Rij 式中：?为信息素的持久性，0≤?

本文应用蚂蚁算法对公交网络中最短路径问题进行求解，把该算法中的蚂蚁对路径的选择模拟为乘客行为，使算法更符合实际，能够更有效率地，更加快速，更能简化复杂度。

七、模型的优缺点评价

模型的优点

（1） Floyd算法可以算出任意两个点之间的最短距离，并不针对题目所问的路

线，其结果具有普遍性，可以用数据库的技术辅助，每次查询只需提取相关的数据，而无需重新进行运算。

（2） 相比搜索算法随着迭代次数增加其算法的复杂程度成几何程度增加，

Floyd算法每一次迭代，算法的复杂度并没有增加，面对多次迭代的情况，Floyd算法是一种相对高效的算法。 （3） 在处理地铁站与汽车站关系的时候，把地铁站看作汽车站之间内部的特殊

“通路”，从而减少了转乘的节点，简化了算法和运算复杂度。 模型的缺点

（1） 在建立规划模型时，为了简化模型，弱化了复杂的约束条件。

（2） Floyd算法在处理简单迭代的情况时，明显比搜索算法复杂，对于简单的转车情况下，运算速度较低。

八、模型的推广与改进

（1）此模型及算法适用于任何与最短路有关的问题当中，可推广到网络中最大流量和最大费用流问题的解决中，可以应用到邮递业，快递公司的运输问题。 (2)此模型还可用于公交公司设立新站点和更改站点的一种评判标准，应该要在大众普遍选择的路线上增加新的班次和线路。 （3）模型的改进：

由于我们之前的算法中矩阵中存在大量的??，浪费了大量的时间和空间，现将算法做如下改进：(1)将目标结点作为已到达结点， 标志为已到达结点。同时扫描它的关联结点，即该结点的相关弧段的另一端结点。将这些关联结点加入已搜索结点表中，并将目标结点作为这些已搜索

结点的上一结点。(2)从已搜索结点表中，找出累积权值最小的结点作为已到达结点，标志为已到达结点。该点的关联结点中如果已存在于已搜索结点表中，则

29

这个已搜索结点的累计权值=min(已搜索结点的累计权值，这个已到达结点的累计权值+已搜索结点到这个已到达结点的权值)。如果该值被修改，则这个已搜索结点的上一结点也应作相应修改，改为当前的已到达结点。判断该已到达结点是否为起始结点，若是，则执行第(6)步，否则执行第(3)步。3)判断有没有未搜索结点，如果有继续第(4)步，否则执行第(6)步。(4)扫描刚刚标志为已到达结点的结点的关联结点，这些关联结点不包括在已搜索节点表中已经存在的结点。将这些关联结点放入已搜索结点表中，并将这个已到达结点作为这些关联结点的上一结点；已搜索结点的累计权值=已到达结点的累计权值+已搜索结点到已到达结点的权值。(5)重复执行第(2)步至第(4)步。(6)在所有的已到达结点中，从起始结点到目标结点进行追踪，找出最短路径。

由于时间限制，本算法没有实现。

九、参考文献：

[1] 费浦生等，《数学建模与其基础知识详解》，武汉：武汉大学出版社，2007年 [2] 高为民，基于蚂蚁算法的公交网络最短路径问题研究，《交通与计算机》 ，25卷 总134期：94页至103页 ，2007年1期

[3] 刘光明，蔡先华等，一种城市公交查询的算法及其应用，《交通运输工程与信息学报》，第3卷 第2期：87页至91页，2005年6月 [4] 张永梅等，城市公交查询系统的研究与设计，《计算机应用》，第25卷第2期：422页至425页，2005年2月

30