路线规划软件中Dijkstra算法实现的时基动态权重外文翻译资料

 2022-12-23 14:58:34

英语原文共 4 页，剩余内容已隐藏，支付完成后下载完整资料

路线规划软件中Dijkstra算法实现的时基动态权重

Lukman Rosyidi, Hening Pram Pradityo, Dedi Gunawan, Riri Fitri

Sari电气工程部

Universitas Indonesia

Depok, 印度尼西亚

lukman.rosyidi@ui.ac.id, dedi.gunawan31@ui.ac.id, hening.pram@ui.ac.id, riri@ui.ac.id

摘要-本文回顾了Dijkstra算法在寻找路径规划最短路径时的实现。常规最短路径算法不考虑路网的时基动态交通状况，即交通密度的每小时变化。Dijkstra算法的时基动态权重根据道路网络的交通状况的实际情况计算最有效的时间和最小的燃料消耗。交通状况描述了基于时间通过道路所需的时间，该时间在工作日和周末也不同。仿真表明，与常见的最短距离计算和交通避免计算相比。Dijkstra算法的时基动态权重的实现可以提供更好的成本效率。

关键词-路径规划，最短路径，时基基础动态流量，dijkstra算法。

  1. 介绍

在印度尼西亚的大城市，探险业务发展迅速。该业务将依靠远程运输车队管理来提取和交付。印尼大都市具有以下交通特征：

  • 地面运输高度依赖交通；
  • 由于城市运动，天气和特殊条件，交通根据时间变得非常动态；
  • 每条道路都有自己的交通状况，两个方向有有。

德波市是印度尼西亚的大都市之一。Depok市的每条道路每一个小时都可能有不同的交通状况。每条路也有两种不同的交通方式。早上，前往雅加达（北部）的道路道路上的交通都很拥堵。相反，前往茂物（南部）的道路上就不堵。与此同时，在下午，交通状况与早晨情况相反。这些交通状况仅发生在工作日，但是在周末或瞻礼日会有所不同。

本文回顾了优先方法的实施，以便将规划线路定位到目标客户的地理位置，以获得最少的行车路线和最低的燃料消耗。我们建议使用Dijkstra算法将最短路径算法应用于软件以获得最佳结果。

图1显示了Depok City的主要道路网络。我们的程序将仅依赖于图中的网络实现。

图1.德波市主干道网络

Dijkstra算法是一种经典的最短路径算法，并已在许多系统中作为理论基础采用。它通常用于计算从第一个节点到所有其他节点的最小成本路径。Dijkstra算法的原理由EWDDijkstra于1995年提出[1]。

A.Dijkstra算法简介[2]

考虑一个由ngt;1个节点{1,2,...,n}组成的最短路径问题和表示节点之间直接链路长度的矩阵D，因此D[i,j]表示将node_i连接到node_j的直接链路的长度。这意味着任何节点对之间最多只有一个直接链接。

Dijkstra算法假定如下：

minus;infin; lt; D[i, j] le; infin;, forall;i, j isin; C := {1, . . . , n}

with D[i, i] = infin;, forall;i isin; C

解释D[i,j]=infin;用作指示没有从node_i到node_j的直接链接。定义以下内容非常有用：

A[j] :={i isin; C : D[j, i] lt; infin;} , j isin; C (1)

B[j] :={i isin; C : D[i, j) lt; infin;} , j isin; C (2)

该算法是迭代过程，其重复尝试改进{f[j]}的（精确）值的初始（上）近似{F[J]}。对于j=2，...，n，F[1]=0并且F[J]=infin;。每次迭代中，处理一个新节点：其F[j]值用于更新其尚未处理的直接后继者的F[j]值。记录U保留在尚未处理的道路组中，因此最初的U=C={1,...,n}。终止时，F[n]的值等于f[n]。细节如下。

初始化:

j = 1; F[1] = 0; F[i] = infin;, i isin; {2 . . . , n}; U = C

迭代:

While (j ne; n and F[j] lt; infin;) Do:

更新 U : U = U{j}

更新 F : F(i) = min{F[i], F[j] D[j, i]}, i isin; A[j] cap; U Update j : j = argmin{F[i] : iisin;U}

_

如果由于 F(j) = infin;而发生终止,则 F(n) = f(n) = infin;

无论终止时是否j=n。

B.原始Dijkstra算法

最初的Dijkstra最短路径算法仅使用网络上节点之间的距离进行计算。如图2所示，该算法仅需要距离数据。它简单易行，易于计算。但是，它不能应用于依赖流量的网络。图3显示了仅依赖于距离而不管交通状况的网络示例。

图2.原始Dijkstra算法的框图

图3. 原始Dijkstra算法的网络示例

C.改进的系数Dijkstra算法[3]

对于依赖于流量的网络，最短路径算法不能通过距离确定，但将在很大程度上取决于流量。已经对Dijsktra算法进行一些增强，例如对高，中和低流量的不同距离实施修改的系数因子。该算法适应所有时间下的交通状况。但是，这仍然不能应用于动态交通网络。下面的图4显示了作为Dijkstra算法输入的距离的修正系数因子。图5显示了道路网络中修改的系数距离。

图4.修正系数Dijkstra算法的框图

图5. 修改系数Dijkstra算法的网络示例

1.Dijkstra算法的时基动态权重

上述方法不适用于动态流量依赖网络。我们提出了一种基于时间函数的动态流量因子，它被用于Dijkstra算法的计算。这成为将算法用于增强实际的商业条件，特别是对于像Depok这样的印度尼西亚大城市的交通依赖网络。下面的图6显示了在Dijkstra算法计算中作为输入的时基流量分布数据。

图6.时基动态权重Dijkstra算法的框图

为了实现基于时间的动态流量因子，将需要节点之间的每条道路的流量分布图，其描述了通过道路以及通过道路所需的时间。流量配置文件可以定义为时间功能：

T[i,j](t) which start at t=0 (00:00) to t=tmax (23:59)

交通状况也会随着工作日、周末、节假日等发生相应的变化，工作日交通拥挤，周末和节假日交通则比较通畅。每条道路也可以有两个交通配置文件，因为在相反的交通方向上有两种方式可以在其流量配置文件上，两者会不同。下面的图7显示了流量剖析图的示例。

图7. 时基动态权重Dijkstra算法的流量图

Dijsktra算法计算将包括定义的时间的特定流量数据权重，其从流量简档数据的时间函数查找。下面的图8显示了每条道路（双向）在不同时间段的交通量。

图8. 时基动态权重Dijkstra算法的网络示例

以分钟为单位的时间函数从0：00到23：59展开，算法如下：

_

初始化:

j = 1; F[1] = 0; F[i] = infin;, i isin; {2 . . . , n}; U = C; t isin; {0 . . . , 1339}

迭代:

While (j ne; n and F[j] lt; infin;) Do:

更新 U : U = U{j} Update D[j,i](t)

更新F : F(i) = min{F[i], F[j] D[j, i](t)}, i isin; A[j] cap; U Update j : j = argmin{F[i] : iisin;U}

计算可以通过使用关系数据库管理系统（RDBMS）的计算机程序来完成，尤其是为特定时间映射网络中每条道路的流量分布图来完成。

2.实施和测试

为了实现Dijkstra算法的时基动态权重，使用Visual Studio作为开发工具，编程制作了软件应用程序。该软件专为远征公司设计，是为车队管理制定线路的线路规划软件工具。首先，管理员应该为每条道路提供不同情况下的全天数据，有工作日的，也要有周末和节假日的。用户可以输入每日取货/交货活动活动的目标位置来使用该软件，以获得最有效的取货/交货路线。

下面的图9显示了该软件的用例图。图10显示了该软件的主要流程图。

图9.用于时基动态权重Dijkstra算法软件的用例图

图10. 时基动态权重Dijkstra算法软件的主流程图

图11. 网络中每个巷道的流量剖面输入的GUI

该软件提供图形用户界面（GUI)，使软件易于使用。图11中图形用户界面显示了网络中每个道路的流量剖面输入。可以通过手机不同时区中每个道路的平均旅行时间数据来提供交通概况的数据。

图12.目标位置输入和路径计算的GUI

图12显示首先输入目标位置，出发的时间输入，系统就会规划出最优路线，以地图的形式显示在界面上。用户可以从界面得到最优的驾车路线，并且得知根据此路线达到目的地所需要的时间，帮助用户减少不必要的时间浪费，提高行车效率。

表1.计算结果比较

共同路线

最短距离

交通规避

时基

Djikstra

路线

Tole Iskandar,

Raya Bogor,

Tole Iskandar,

Raya Bogor,

Margonda123,

Juanda,

Dewi Sartika,

KelapaDua,

Lenteng,

Margonda1,

Nusantara,

Lenteng

Srengseng

Lenteng,

Moch Kahfi

Agung,

Srengseng

Srengseng

时间

99 分钟

79 分钟

77分钟

72 分钟

汽油

1.485升

1.185升

1.155 升

1.08 升

成本

Rp12,622.5

Rp10,072.5

Rp9,817.5

Rp9,180

Eff.

0%

20%

22%

27%

表1所示算法的结果是在工作日从Tole Iskandar到Moch Kahfi的路线计划案例，开始的时间为上午8：00，为了进行比较，还提供了常规路线计算，最短距离计算和交通避免计算的数据。

根据上述情况，预测利用Dijkstra算法的时基动态权重得出的路线计划所花的时间是最少的，燃料消耗和成本也是最少的。它比普通路线效率高27%,并且比最短距离计算（效率20%）和交通避免计算（效率22%）规划的线路更好。

3.结论

Dijkstra算法结果的时基动态权重将有助于路线规划活动，以获得较其他方式更短的时间，降低燃烧消耗和成本，特别是对于大城市的交通网络。交通状况的权重来自流量分布数据，动态影响所花费的时间的计算。与最短距离计算和交通避免计算相比，Dijkstra算法的时基动态权重提供了更好的方案，降低成本提高了效率。

承认

作者LR感谢Sekolah Terpadu Nurul Fikri(STT NF)支持撰写本文。

引用

  1. Dijkstra E.W. “与图有关的两个问题”, in Numeris

    剩余内容已隐藏，支付完成后下载完整资料

    资料编号：[20829]，资料为PDF文档或Word文档，PDF文档可免费转换为Word

原文和译文剩余内容已隐藏，您需要先支付 30元 才能查看原文和译文全部内容！立即支付

以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。

您可能感兴趣的文章