Dijkstra算法在物流配送运输中的最短路径优化研究

友情文档

龙源期刊网 http://www.doc.oiuq.com/doc/610db867ee06eff9aff8071e.html

Dijkstra算法在物流配送运输中的最短路径优化研究

作者：阮洁钟宝荣

来源：《计算机光盘软件与应用》2013年第15期

摘要：传统的Dijkstra算法一般用于计算一个源节点到所有其他节点的最小代价路径，它能够适应网络拓扑的变化，因而可以应用在物流中的配送线路规划上。原始的Dijkstra算法在实现时不仅占用大量计算机内存，而且执行效率也不高。针对这一问题，本文基于传统的Dijkstra算法，对其数据存储和算法思路进行了优化。最终通过实验证明优化后的Dijkstra比原始的Dijkstra算法在执行效率上有了较大的提高。

关键词：Dijkstra算法；最短路径；物流配送；优化算法

中图分类号：TP301.6

物流业的发展已成为国民经济的一个新的增长点，科学合理的物流业是经济可持续发展的重要部分，其发展程度已经成为衡量一个国家现代化程度和综合国力的重要标志之一，被喻为促进经济增长的“第三利润源泉”。在物流配送活动中，主要是把一批货物从配送中心运送到一个或多个非固定客户的接货处。通常配送中心与客户之间有多条运输路线可以选择。如果配送中心不进行运输路线的合理规划，往往会出现不合理的运输现象，如迂回运输、重复运输等。不合理运输会造成运输成本上升。因此确定合理的配送路线，从而使运输成本降低的同时又使服务水平得到改善是物流配送管理工作的一项重要内容。

本论文是笔者在湖北某软件公司实习期间，参与的一个物资综合管理系统，其中有一个模块是关于车辆调配和物流运输的，然后在此基础上实现基于Dijkstra算法并对其进行优化的物流配送最短路径选择算法。通过实验发现，不仅节约了物流成本，而且提高了运输的效率。

1 Dijkstra算法介绍

1.1 Dijkstra算法思想及步骤

Dijkstra算法用于计算一个源节点到所有其他节点的最短代价路径，它是按路径长度递增的次序来产生最短路径的算法。该算法的输入包含一个有权重的有向图G以及G中的一个顶点s，用V表示G中所有顶点的集合，S表示已求得最短路径的值顶点，w（u，v）表示从顶点u到顶点v的权重（设定权重均为非负值），（u，v）表示从顶点u到顶点v有路径相连，d（v）表示从顶点s到顶点v的最小权重。步骤如下：