丁浩　苌道方

摘要： 针对目前快递车辆运输成本问题，研究了如何利用Dijkstra算法来迅速寻找出快递车辆配送派件过程中的最短路，并与解决该类问题常用的遗传算法，蚁群算法和A*算法进行了比较分析。证明了Dijkstra算法可以准确迅速地寻找出快递配送车辆派件过程中的最短路，从而有效的帮助快递公司降低运输成本。

Abstract： Express transportation cost is very important. This article studies how to use Dijkstra algorithm to quickly find the shortest path when distributing， and makes comparative analysis by the genetic algorithm， ant colony algorithm and A* algorithm. It is proved that Dijkstra algorithm can accurately and quickly find out the shortest path when distributing， so as to effectively help the courier company to reduce transportation costs.

关键词： 最短路问题；快递配送车辆；Dijkstra算法

Key words： the shortest path；express distribution vehicle；Dijkstra algorithm

中图分类号：TP301.6 文献标识码：A 文章编号：1006-4311（2014）03-0015-04

0 引言

由于全球经济的迅猛发展、现代科学技术的不断更新，物流行业作为国民经济中的重要产业，正在全球范围内快速发展[1]。传统的货物运输产业中慢慢发展生成了一个新的分支——快递服务产业。同时随着油价上涨等一系列问题，运输成本在物流活动中所占的比重也在不断上升，通过合理的方法规划车辆行驶路径，降低运输成本也成为国内各个快递企业效益提升的关键因素。

针对物流车辆行驶路径最短路问题，国内外诸多学者对此进行了深入研究。乐阳等从网络结构的拓扑表示以及Dijkstra算法中快速搜索技术的实现入手，提出了一种Dijkstra最短路径算法的高效率实现方法[2]。王海晓研究了Dijkstra算法在求解物流大件运输最短路径中的应用，证明了Dijkstra算法在求解物流大件运输最短路问题的准确性[3]。黄睿分析了如何利用Dijkstra算法对物流活动进行优化，并求得了相关物流活动的优化解[4]。潘开灵等阐述了Dijkstra算法的基本思路以及求解运输最短路径的具体步骤，并通过Dijkstra算法找出了运输中的最短路径，最终减少了运输距离，降低了物流成本[5]。……