智慧物流中的最优配送路径规划问题

史屹琛 贾伯年

摘要    随着国家对智慧城市的大力发展，智慧物流作为智慧城市发展中的一部分，有着很大的作用，通过发展智慧物流，可以极大的提高物流效率，降低物流成本，加速产业的发展。本文针对货物在仓库之间的配送路径规划问题，对Dijkstra算法进行分析，加以改进，挑选出最优的配送路径。

【关键词】智慧物流 最优路径规划 Dijkstra算法

1 前言

智慧物流首次由IBM提出，并在2009年12月由中国物流技术协会信息中心、华夏物联网、《物流技术与应用》编辑部联合提出概念。随着信息技术快速发展，中国的智慧物流也受到了极大的影响。“智慧物流”是指通过智能硬件、物联网、大数据等智慧化技术与手段，提高物流系统分析决策和智能执行的能力，提升整个物流系统的智能化、自动化水平。

通过智慧物流，在一下几方面会带来极大的进步：

（1）降低物流成本，提高企业利润;

（2）加速物流产业的发展，成为物流业的信息技术支撑;

（3）节约消费者的购物成本，让消费者放心;

（4）可以提高社会各部门工作效率，尤其是提高政府部门工作效率。

分析物流的最优路径是发展智慧物流中极为重要的一部分，可以极大的节省配送成本，提高配送效率。

2 常用路径搜索算法

寻路问题属于组合优化的范畴，从路径搜素策略上可分为三类，第一类是局部最优化算法，但并无法获得全局最优解，例如贪心算法，第二类是全局最优化算法，以获取全局最优解为目的，主要的算法有Dijkstra算法，floyed算法等，最后一类是计算智能算法。

本文将对Dijkstra算法在物流配送中的应用进行探究。

3 Dijkstra算法

Dijkstra算法使用了BFS（广度优先搜索）解决单源最短路问题。算法的基本思路就是先将所有节点分成两组第一组用S表示为已求出的最短路径的顶点集合，第二组用U表示剩余顶点，U中的每个顶点对应着一条由源点到达该点的最短路径，起始时S中只含有一个源点，每求得一条最短路，就在U中更新相应的点对应的最短路径，按照最短路径递增的次序把U中的点加入到S中，直到确定了到目标结点的最短路，也就是所有节点都在S中，算法结束。

基本步骤如下：

（1）把起始点加入到S中，即S={v0}，起点到自己的距离为0。更新源点v到U（处源点外其他点）上的最短距离，若存在边相连则更新为最短距离，若无边相连则更新为∞

（2）从U中选择一个权值较小的点u，加入到S中。

（3）以（2）中取出的u为中间节点，更新源点到U中剩余顶点的最短路径。其调整过程如下：dist[i]表示从起始节点到顶点i的最短距离，扫描u的所有出边，若dist[j]>dist[u]+weight，則使用dist[u]+weight更新dist[j]。

（4）重复步骤（2），（3）。

4 Dijkstra算法在物流配送中的运用

假设提前已经知道每段配送路的长度和花费时间，在物流配送问题中，要用尽可能短的时间，走尽可能短的距离，到达目的地。

首先我们建立图论模型如图1所示。

其中节点表示起点，终点及中间的补给站，这里假设0号节点为起点，6号节点为重点，其余节点为补给站，每条路径有t和d两个权值，权值t表示预期要花费的时间，权值d表示道路的长度，本文将所有的道路都假定为双向道路，所以此图为无向图。

传统的Dijkstra算法只考虑路径长度，本文在考虑路程短的同时还考虑到运送花费时间，对经典的Dijkstra算法加以改进，第（2）步中从U中选择一个权值较小的点u，加入到S中，如果有多个点满足这个条件，选择花费时间最少的那条路径所连的点，这样则可是的路径规划最优。

在这个模型中，我们要从起始节点0到达终点6，为了减少成本，我们要选择最短的路径。如果是根据经典的Dijkstra算法，我们先把0这个节点加入到集合S中，再去更新源点0到达U中剩余节点的最短路径。因为d[2]

5 结语

本文基于Dijkstra算法的理论知识，针对智慧物流配送这个特定情境下的具体运用进行讨论，对如何选择最优路径进行了分析探究，利用改进的Dijkstra算法搜索出一条路径最短，成本最低的路径。

参考文献

[1]张本俊，周海娇，刘淑琴.改进Dijkstra算法在公共交通出行的研究[J].物联网技术，2018，8（11）：45-48.

[2]李元臣，刘维群.基于Dijkstra算法的网络最短路径分析[J].微计算机应用，2004（03）：295-298+362.