基于Bellman―Ford算法的最优交通路径选取建模

摘要：在现代社会，城市交通是一个城市运行的基础，随着社会的进步和经济的发展，交通越来越发达，给人们的生活带来极大的便利，但是与此同时交通拥堵、交通安全等问题为人们的出行笼罩上了一片阴影。针对以上问题，最优交通路径选取模型的建立是根本解决途径。通过对城市公交路径选择问题的分析，在Bellman-Ford算法的基础上，根据乘客的不同需求建立不同的最优路径选择模型，并同时以算例验证模型和算法的合理性和实用性。

关键词：Bellman-Ford算法；最优交通路径；路径选择；模型；

中图分类号：R179.32 文献标识码：A 文章编号：1009-3044（2018）09-0192-02

改革开放后，我国经济得到了大力发展，科技水平也在不断增长，带动了城市交通的兴起，各大城市相继建立了四通八达的交通网络[1]。图1为2011～2015年某一线城市交通线路增长情况，由图1可知在这5年间，交通线路增长了30%以上。公交线路的增加一方面为人们的出行带来了便利，另一方面也给人们带来了交通拥堵、交通费用、出行时间等方面的困扰，使得人们不得不面临多条线路的选择问题。根据不同出行者的要求，建立一种最优交通路径选取模型是根本解决之道。现阶段，应用最广的最优交通路径选取模型是在Dijkstra算法基础上建立起来，但随着交通线路的不断增加，交通问题的不断加重，该模型已经开始流露出“疲态”，已无法解决交通网络中的实时导航、通勤、调度等时刻变化的交通流量情况[2]。在此情况下，本文考虑出行者的换乘次数、出行时间、出行费用等因素，在Bellman-Ford算法的帮助下建立最优交通路径选取模型。

1 Bellman-Ford算法

1.1算法流程

第一，初始化，即把所有顶点的最优距离估计值都进行[d=v←+∞，ds←0]处理（出除源点外）[3]。

第二，分布式迭代求解，即对边集E中的每条边进行多次松弛操作，让顶点集中各个小顶点v的最优距离估计值与最优距离[运行v-1次]相接近[4]。

第三，检验负权回路，即分析边集E每条边的两个端点是否收敛。如果顶点都收敛了，算法则是正确的，并把这段距离进行保存，说明是最优的距离；如果没有，则说明算法是错误的，这段距离不是最优距离[5]。

1.2动态最优路径算法

从出行者的实际角度出发，把subgoals method思想与Bellman-Ford算法相结合，设计一个动态最优路径算法。该算法可以把考察源点与待选点之间，以及待选点与目标点之间的路况变化情况，利用下一个点到目标点之间的最优距离作为选择启发步。在所有起始点到待选点实际花费时间与待选点到目标点的评估时间之和中选择最小的一个，则对应的待选点为当前点，继续考虑下一步的起始节点，直到选到目标点为止[6]。根据以上描述，算出的最终结果就是交通最优路径。

2交通最优路径选取模型

2.1出行总距离最短的最优路径选择模型

该模型是整个交通体系中最重要的一个模型，它可以最大限度节约出行者的时间。其模型建立步骤如下：

第一步，建立车辆各站点之间的距离矩阵，把各站点作为矩阵中的各个小顶点，然后根据车辆的行驶方向，把有往返车辆的站点用边连接起来，只有单程车辆经过的站点用弧连接起来，通过以上的边和弧连接构成一个车辆站点邻接关系图，并利用上Bellman-Ford算法进行计算，求出两个站点之间的最短距离，以此建立这条路径的最短距离矩阵[7]。

第二步，在步骤一的基础上，构建总的各车辆站点直达时的距离矩阵，然后利用[Λ：aΛb=mina，b]进行合成处理，得到距离矩阵[B=B1ΛB2Λ…ΛBn]。

第三步，利用Bellman-Ford算法对从步骤2中得到的矩阵B进行计算处理。处理完毕后，得到各车辆站点之间的最短直达距离，辅助出行者选取出出行总距离最短的最优路径。

2.2出行总费用最少的最优路径选择模型

出行费用也是制约出行者出行的主要因素，因此在满足出行者要求的基础下，建立出行费用最少的最优路径选取模型是十分重要的[8]。其模型建立步骤如下：

第一步，车辆行驶的距离越长，收费越高，因此就可以直接通过车辆路径直达距离矩阵建立直达费用矩阵A。

第二步，把步骤一中的直达费用矩阵利用Bellman-Ford进行合成处理，得到总的直达费用矩阵B。

第三步，利用Bellman-Ford算法对从步骤二中得到的矩阵B进行计算处理。计算完毕后，选取出各车辆站点之间最少费用中的最优路径。

2.3出行总时间最少的最优路径选择模型

在城市交通中，上班者占据大部分，因此建立出行总时间最少的最优路径选取模型对于这部分人来说是最重要的，可以更好帮助上班族解决时间问题。其模型建立步骤如下：

第一步，建立车辆各站点之间的时间矩阵[T0=t0ijn×n]。

第二步，给出至多换乘1次就能到达的最短时间矩阵[T1=t1ijn×n，t1ij=mint0ij，t0is+t0sj+t]，其中[t]为换乘时间[9]。

第三步，给出至多换乘[k-1k≥2]次就能到达的最短时间矩阵[T2=t2ijn×n，tkij=mintk-1ij，tk-1is+t0sj+t]。当[Tk=Tk-1]时，得到任意两个站点之间的最短通行时间矩阵。

2.4出行满意度最大的最优路径选取模型

以上三种交通最优路径选取模型都是以一种考虑因素为中心的。但是在现实生活中，出行者更希望把这三种因素都纳入考虑范围内，建立最令人满意的交通最优路径选取模型，为此为同时满足出行者两个或两个以上的需求，下文建立了一个出行满意度最大的最优路径选择模型[10]。其模型建立步骤如下： 第一步，参考出行者需要，明确各考虑因素的权重，并以此将以上三种矩阵（直达距离矩阵、直达时间矩阵、直达费用矩阵）进行标准化处理，然后把处理结果加权平均，构建综合满意度矩阵A。

第二步，利用[Λ]把综合满意度矩阵合成总的直达综合满意度矩阵B。

第三步，利用Bellman-Ford算法对从步骤二中得到的矩阵B进行计算。计算完毕后，帮助出行者选取出综合满意度最大的最优乘车路径。

3具体算例

图2是某城市由6个公交站点，2条公交路线构成的公交网。

1）建立图2中两条公交路线的直达关系矩阵。

2）利用Bellman-Ford算法获得两条公交线路的最短直达距离矩阵[Bk=bkij]（其中[bkij]表示k号线i站到j站的最短距离）。

3）根据B1和B2矩阵构建总的直达距离矩阵。

4）利用Bellman-Ford算法构建两个站点之间最短路径的距离矩阵。

根据矩阵C就能知道经过站点最少的乘车路径。

4结束语

综上所述，社会主义市场经济的发展，给我国交通带来了翻天覆地的变化，方便了人们的出行，但是随着交通线路的增多，对于出行路径的选择成为一大难题。在此背景下，最优交通路径选取模型问世，帮助人们解决了这一难题。上文基于Bellman-Ford算法，根据出行者的不同需求建立了四个最优路径选取模型，该模型经过具体算例验证，证明了其合理性和实用性，对我国交通事业的发展具有重要意义。

参考文献：

[1] 王超， 高武奇. 基于AHP与Bellman-Ford算法的停车规划方法[J]. 数字技术与应用， 2017， 32（7）：142-143.

[2] 任小聪， 向红艳， 陈坚. 交通事故信息对路径选择行为的影响建模与分析[J]. 公路交通科技， 2016， 33（7）：103-107.

[3] 卫小伟. 基于改进遗传算法的多目标城市交通路径选择系统建模与仿真[J]. 计算机与数字工程， 2016， 44（1）：10-15.

[4] 徐广宁， 王印海， 曾自强. 城市路网动态转向建模与优先选择研究[J]. 交通运输系统工程与信息， 2017， 17（4）：132-137.

[5] 潘义勇， 马健霄. 基于可靠性的随机交通网络约束最优路径问题[J]. 东南大学学报（自然科学版）， 2017， 75（6）：1263-1268.

[6] 贺政纲， 邹晔， 杨晓. 报废汽车物流网络选址-路径问题建模与求解算法研究[J]. 公路交通科技， 2016， 33（3）：138-145.

[7] 汪宏晨， 张霞， 唐炉亮，等. 时段交通限行的时空动态建模与路径优化方法[J]. 长安大学学报：自然科学版， 2017， 37（5）：89-96.

[8] 李泽平， 杨旋， 鲍序. 对等W端到端多路径选择建模及算法研究[J]. 计算机应用研究， 2016， 33（4）：1191-1198.

[9] 张京敏， 牛群. 关于城市物流配送交通路径规划仿真研究[J]. 计算机仿真， 2017， 34（6）：367-371.

[10] 杨嘉华. 基于双向最短路径的大型停车场停车路径优化算法[J]. 信息技术与信息化， 2016， 53（9）：58-60.