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

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

[关键词]大数据；城市配送；最快路径；时间成本；Floyd算法

1引言

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

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

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

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

2.1天气条件

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

2.2通行时段

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

2.3交通路口数量

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

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

3最快路径选择

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