基于Floyd算法的城市配送最快路径选择

唐克生，钱 民，段丽梅，王 滨

（昆明冶金高等专科学校，云南 昆明 650033）

基于Floyd算法的城市配送最快路径选择

唐克生，钱 民，段丽梅，王 滨

（昆明冶金高等专科学校，云南 昆明 650033）

提出了一种基于车辆通行时间大数据选择最快路径的方法，充分考虑道路拥堵和交叉路口红绿灯等待时间的因素，用通行时间代替距离，采用改进的Floyd算法来发现最快的配送路径，研究发现该方法可以提高城市配送的效率，降低时间成本，具有较高的应用价值。

大数据；城市配送；最快路径；时间成本；Floyd算法

1 引言

目前“最后一公里”的城市配送的效率问题已成为影响物流业发展的一个重要因素。配送路径的选择对配送的效率和成本起着关键的作用。过去，我们会选择一条最短路径作为配送路径，最短路径算法主要有Dijkstra广度搜索算法、Floyd算法、A*启发式算法以及在搜索节点时加入蚁群算法和遗传算法以提高搜索的效率[1]。现在，随着城市交通拥堵的加剧，人们意识到最短路径并不等于最快路径，基于对配送效率和时间成本的考虑，倾向于在配送时选择一条最快路径。类似的研究成果主要有对交通拥堵可能发生进行提前预测[2]、建立考虑天气状况、道路容量等动量的动态交通网络对出行道路进行规划和中途调整[3]、引入道路拥堵因子的基于动态规划法的配送路径动态选择[4]、基于交通信号的路口延迟和时间最短路径(TLBSP)的计算模型实现交通信号控制下各车最短时间路径的计算[5]、基于CapeCod方法计算最短时间路径的最优出发时间[6]等。

Dijkstra广度搜索算法，是一种贪心算法，能够搜索出一条单源最短路径，即在图中求出给定节点到其它任一节点的最短路径。其计算复杂度为o(n2)。Floyd算法，能够搜索出图上的所有节点对的最短路径。其计算复杂度为o(n3)，可以一次求解无向图和有向图。

本文提出了一种基于道路通行时间大数据来选择最快配送路径的方法，即通过记录自有配送车辆在配送过程中所经过的每条道路的通行时间，区分通行时段、天气条件、交通信号路口数量等影响通行时间的因素，以道路的通行时间代替距离，使用Floyd算法计算完成一趟配送任务的最快路径，即得出一条从配送中心到一次配送任务的多个客户且返回配送中心的最快路径。

2 影响道路通行时间的因素

2.1 天气条件

一些特殊的天气条件会直接影响到道路的通行速度，比如能直接导致能见度降低的大雾和沙尘天气，导致路面湿滑的雨雪天气。在城市道路的通行实例中，由于特殊天气条件导致道路通行速度降低而发生拥堵的情况较为常见。

2.2 通行时段

机动车辆的通行速度直接和该时段的交通流量直接相关。比如高峰时段，由于交通流量增大，道路宽度等条件不足以容纳，往往造成通行缓慢，直至发生拥堵；正常时段，交通流量没有达到拥堵所需的量，则会道路通畅，不易发生拥堵。

2.3 交通路口数量

机动车行驶到路口需要降低速度通过，且由于交通信号灯等待延误时间，常导致车辆的通行时间直接增加。由于交通信号灯的红绿灯显示是动态变化的，不能提前预测，也不能加以控制，故每个路口的等待时间取值红灯等待时间的一半较为合适。如果红灯等待时间为1min，则路口延误时间取30s，具体的取值可以视不同的城市而有所不同。

本文中，天气条件、通行时段对通行的影响可以通过该种条件下通行时间的长短得到反映，交通路口的等待时间则单独标记。

3 最快路径选择

随着城市拥堵的加剧，城市配送时选择一条最短路径已经不具有现实意义，为了提高效率和降低配送的时间成本，往往需要选择一条最快路径来进行配送。

显然，不同的通行时段，同一条道路需要不同的时间，比如周末与工作日，高峰时段与正常时段所需时间都会不同。当然，不同城市的高峰时段和正常时段会有不同，需要根据具体的车辆通行时间大数据统计得来。接下来，我们给出选择最快配送路径的具体步骤。

步骤1 车辆通行大数据统计。物流公司的配送客户通常是确定的，在配送时可选择的路径通常是有限的。在自有配送车辆上安装GPS，按是否工作日、是否高峰时段、是否雨雪等特殊天气来统计和记录所经过的每一条通行路段的时间，通常以1个月为统计数据区间，所得数据作为下个月决策的依据。

步骤2 数据处理。某路段某一时段的通行时间取该时段统计数据的平均值作为其时间权值。画出交通网络图，其中，道路的通行时间标注在相应线段上，无向边表示双向通行时间无差异，单向边表示单向通行，双向边表示同一条道路该时刻双向通行时间不相同。节点标注交叉路口等待时间，通常取红灯等待时间的一半，不考虑左转、直行、右转的区别。

步骤3 采用改进的Floyd算法来计算交通网络图中所有节点对之间的最短通行时间路径。Floyd算法是一种基于迭代思想的动态规划算法，本文中增加了交叉路口的等待时间，算法也相应地做出了改进。算法的主要部分如下：

声明并初始化时间代价矩阵T(0)[i][j]，路口等待时间数组W[i]

其中，G.vnum()为节点数函数，T[i][j].time为节点Vi与节点Vj之间的时间代价，T[i][j].pre存储节点Vi与节点Vj之间的前驱节点（跳节点）。

步骤4 使用全排列递归算法，计算一次配送所经过的各个客户的各种可能路径的通行时间，通过比较得出其中一条最短时间路径，算出最短时间，并给出本次配送的途经节点顺序，便于本次调度安排。全排列算法已经非常成熟，在这里不再赘述。

4 算法仿真

Floyd算法是一种用于计算所有节点对的最短路径的常用算法。在这里采用通行时间来代替距离，且在算法中增加了交叉路口等待时间，用来计算城市配送中的最快路径。我们来看一个具体的例子。

例：图1表示了一个城市交通的网络图，V1，V2，V3，V4，V5，V6分别表示6个交通节点，其中的数字表示路口等待时间，相连接的边表示交通节点间的道路，权重表示通行时间，单位为分钟。其中，双向边表示两节点间的通行时间不同，单向边表示单向通行，无向边表示双向通行的时间无差异。现实中，配送中心通常设在城市边缘，其双向通行时间会随着出入城车辆数量的动态变化而有所不同，在图中我们使用双向边来表示。假定配送中心位于V1处，现在需要完成一项配送任务，此次配送的两个客户分别位于V5、V6，我们该如何选择最快配送路线，最快时间是多少？

图1 城市配送网络示意图

步骤1 根据Floyd算法，得出初始时间代价矩阵T0(i,j)（见表1）、前驱节点矩阵P0(i,j)（见表2）、路口等待时间数组W[i]={0.5,0.5,0.5,0.5,0.5,0.5}。

表1 时间代价矩阵T0(i,j)

表2 前驱节点矩阵P0(i,j)

值得注意的是，时间代价矩阵是不对称的，标明了有些路段双向通行时间不相同，符号“∞”表示不可达。

步骤2 通过计算经过中间跳点V1来更新时间代价矩阵为T1(i,j)（见表3）、前驱节点矩阵P1(i,j)（见表4）。更新原则：

例如：在T0(I,j)里，V2→V3的时间权重为∞，经更新后为 20.5，通过判断 T[2][3].time＞T[2][1].time+T[1][3].time+W[1]，即∞＞10+10+0.5，故将 T[2][3].time更新为20.5，同时在前驱节点矩阵中V2→V3的前驱节点标记为1，即此时V2→V3需途经V1中转。

表3 时间代价矩阵T1(i,j)

表4 前驱节点矩阵P1(i,j)

步骤3继续更新时间代价矩阵和至T6(i,j)（见表5）和P6(i,j)（见表6），即分别计算经过V2，V3，V4，V5，V6中转的最快时间，从任一节点至任一节点。

表5 时间代价矩阵T6(i,j)

表6 前驱节点矩阵P6(i,j)

例如：V1→V6,最快时间为 38min，路径为 V1→V3→V4→V6，总时间为10+0.5+15+0.5+12，表示经过了两个路口，等待时间为0.5+0.5。

步骤4 本次配送需要从配送中心V1出发一次送完两个客户V5、V6，然后返回配送中心V1，计算出最短时间和最快路径。使用成熟的全排列递归算法，进行比较后得出最短时间。例如：按照全排列规则，需要计算和比较以下的路径：V1V5V6V1、V1V6V5V1，它们所用的时间分别为83.5min、81min，由此可知，最短时间为81min，其路径V1V6V5V1，它的具体路径为V1→V3→V4→V6→V5→V4→V2→V1。值得注意的是，在该路径中，节点V4经过了两次，这是根据实际情况而选定的。

至此，我们得出了此次配送的最短时间和最快路径。

5 结束语

本文选择Floyd算法来计算最快路径，是因为该算法能够满足两种情形：配送时，一次配送任务通常需要满足不止一个客户，也即一次计算可以得出一条包含往返的最快路径；城市中通常会出现单行道路和通行时间不对称道路。但是，Floyd算法的时间复杂度比其他算法复杂，我们可以将一条较长的道路作为一条通行路段来看，而不必按照交叉路口所分割的路段数量来计算，这与实际的配送情形是一致的，也即正常情况下，在确定了配送客户后，我们可供选择的路径是有限的。

[1]赵青,朱乐天.基于ArcGIS的最短路径算法在城市交通中的应用[J].航空计算技术,2014,(2):14-17.

[2]钱民,唐克生.基于定性动态概率网络的交通状态预测及改进[J].云南大学学报(自然科学版),2012,(2):165-168.

[3]杨浩雄,王丹,张敬蕤.基于蚁群算法的拥堵交通最短路径研究[J].计算机仿真,2015,(32):186-191.

[4]赵慧娟,汤兵勇,张云.基于动态规划法的物流配送路径的随机选择[J].计算机应用与软件,2013,(30):110-112.

[5]李晓东,王东,曾凡智,陈俊健.城市交通时间最短路径计算模型及应用仿真[J].计算机仿真,2014,(31):172-175.

[6]E Kanoulas,Du Yang,Xia Tian,Zhang Donghui.Finding Fastest Paths on A Road Network with Speed Patterns[A].Proceedings of the 22nd International Conference on Data Engineering[C].2006．

Selection of Fastest Route in Urban Distribution Based on Floyd Algorithm

Tang Kesheng,Qian Min,Duan Limei,Wang Bin
(Kunming Metallurgy College,Kunming 650033,China)

In this paper,we proposed a method for the selection of the fastest route based on the big data on vehicle travelling time,then having fully considered road congestion and the waiting time at crossroads and traffic lights,substituted distance with travelling time and at the end,used the improved Floyd algorithm to identify the fastest distribution route.

big data;urban distribution;fastest route;time cost;Floyd algorithm

F224.0;F252.14

A

1005-152X(2017)09-0101-04

10.3969/j.issn.1005-152X.2017.09.023

2017-08-03

云南省教育厅项目（2015Y550）；昆明冶金高等专科学校项目（2016xjsk06）

唐克生（1974－），男，云南华宁人，讲师，工学硕士，主要研究方向：物流工程技术、智能数据处理。