基于集成物流网络的路径优化问题探究

陈 缨,陈向宜,王雪辉

（国网四川省电力公司电力科学研究院,四川成都,610072）

基于集成物流网络的路径优化问题探究

陈 缨,陈向宜,王雪辉

（国网四川省电力公司电力科学研究院,四川成都,610072）

由于物流集成网络能够规划物流作业流程，整合物流资源，从而提高物流运作效率，发挥物流规模化优势，因此，本文在集成物流网络的背景下，探讨路径优化问题，在传统的Dijkstra算法基础上，采用了完全二叉树对Dijkstra算法进行改进，并以烟草商业企业为例说明集成物流网络的特点与优势，验证算法的有效性。研究结果表明：改进后的Dijkstra算法能够降低时间复杂度，提高运行效率，为企业大规模的集成物流网络分析应用提供了一种的有效的方法。

集成物流网络；Dijkstra算法；路径优化；烟草商业企业

0 引言

随着全球经济的发展以及竞争的加剧，物流作为第三利润源泉越来越受到企业的重视。企业通过利用现代物流和信息技术，建立了完整的物流网络，使其不断的向集成化、自动化、信息化发展。路径优化是物流网络规划的关键问题，本文以集成物流网络为背景，结合Dijkstra算法，旨在探究Dijkstra算法在物流网络的应用，实现路径优化，降低物流成本。同时，为了提高Dijkstra算法的运行速度和效率，本文将对Dijkstra算法进行改进，并进行数值仿真分析以验证算法的有效性。

1 问题的描述与Dijkstra算法

随着我国物流产业的发展，物流配送中心建设逐步完善，这为集成物流网络的发展奠基了基础，集成物流网络强调的是物流仓储、配送的集成性，应用“系统集成”的思维，从物流网络运作整体要素角度，对当前的物流网路进行合理规划，保证货物的及时配送，及时满足顾客的需求，降低物流成本。其中，路径优化是物流网络的关键问题，合理的路径安排不仅可以节约物流总成本，还可以减少物流配送过程中的不确定性，降低物流风险，保障物流服务的效率。

集成物流网络的优化问题主要是解决起点到终点的最短路

2 改进的Dijkstra算法

由于传统的Dijkstra算法需要遍历每个网络节点，降低了运行效率，鉴于此，本文采用完全二叉树原理对Dijkstra算法进行了改进。完全二叉树是效率较高的数据结构，经常应用于堆排序，而采用完全二叉树对Dijkstra算法进行改进时，为了维护节点集合的数据结构，需要通过建立优先级队列，并且队列数组中每一个节点各自都有一个相应的关键字。其相应的步骤为：

（2）最短路径的选取：对优先级队列进行调整，调用SelectBT选择节点，找到出发到的最小路径。

（5）算法终止。

从遍历节点数目而言，Dijkstra算法则是遍历了所以的节点，运行时间是，而改进的Dijkstra算法只需要遍历完全二叉树的节点即可，每次调整都是将新节点加到完全二叉树的最后一层，运行时间是，说明采用改进的Dijkstra算法要比传统的Dijkstra算法执行效率更高，大大节约了计算时间。另一方面，还可以对完全二叉树进行改进，通过建立索引等方式提高完全二叉树的查找能力，快速定位网络节点，缩短时间，进一步优化算法。

3 集成物流网络路径优化问题的Dijkstra算法实现

为了说明集成物流网络路径优化的Dijkstra算法实现问题，本文以烟草商业企业的物流网络为例。从整体上看，我国烟草商业企业的物流网络大多是按照行政区域划分，由总公司将卷烟中转到各分公司，再由各分公司负责配送到当地的零售户手中，这种层级式的物流配送造成了物流组织结构臃肿，物流资源运行效率低下，不利于实现规模化效益。因此，烟草商业企业在烟草专卖制度下，对物流进行整合，降低物流网络层次，形成集成物流网络，即在一定区域内建立几个规模较大的配送中心，打破原有的行政区域划分，由一个配送中心负责多个行政区域的卷烟配送。具体来说，由卷烟工业公司将卷烟送往几个大的配送中心；接着，配送中心按照客户的需求将卷烟直接配送至零售户，或者是配送到中转站；最后，中转站再负责相关零售户的配送。

由于整合之后增加了物流配送中心的网点数目，假设其中一个配送中心需要配送的网点数较多，为54个，分布情况如图1所示。其中，节点20是配送中心，即起点，其余节点是零售户或是中转站，各个节点之间的距离如表1所示，、表示节点，表示距离。现该配送中心需要向中转站和零售户配送卷烟，需要计算配送中心到各节点的最短路径，以安排车辆运输，以发挥配送的时效性，缩短物流配送时间。计算过程如下。

Study on Path Optimization Based on the Integrated Logistics Network

Chen Ying,Chen Xiangyi,Wang Xuehui
(State Grid Electric Power Company Electric Power Research Institute of Sichuan Province,Sichuan Chengdu,610072)

Because the integrated logistics network can standard operating processes and integrate logistics resources in order to improve the efficiency of logistics operation and develop scale superiority of logistics,this paper discusses the path optimization problem under the background of the integrated logistics network,and on the basis of traditional Dijkstra algorithm,it adopts complete binary tree to improve the Dijkstra algorithm.Meanwhile,this paper takes the tobacco commercial enterprise as an example to indicate the characteristics and advantages of the integrated logistics network and verify the validity of the improved Dijkstra algorithm. The results show that the improved Dijkstra algorithm can reduce the time complexity and improve operational efficiency,which provides an effective method for companies to analyze large-scale integrated logistics network.

integrated logistics network;Dijkstra algorithm;path optimization;tobacco commercial enterprise

图1 物流集成网络图