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

    智慧物流中的最优配送路径规划问题    史屹琛 贾伯年Summary    随着国家对智慧城市的大力发展，智慧物流作为智慧城市发展中的一部分，有着很大的作用，通过发展智慧物流，可以极大的提高物流效率，降低物流成本，加速产业的发展本文针对货物在仓库之间的配送路径规划问题，对Dijkstra算法进行分析，加以改进，挑选出最优的配送路径Key】智慧物流 最优路径规划 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]