刘臣宇 孙伟奇 李卫灵

摘  要：运输路线的选择主要是选择起点到终点的最短路线，路线的选择直接影响到运输成本。最短路线的度量可能是时间最短、距离最短或费用最少等。正确地选择运输路线是运输工作人员的一项重要工作。直送式配送运输是众多运输路线选择问题中的一种，该问题的解法也比较多，但应用Dijkstra标号法来解决复杂的直送式配送运输问题有其独特的优势。

关键词：Dijkstra标号法;直送式配送;方法应用

中图分类号：U116.2    文献标识码：A

Abstract： The choice of transportation route is mainly to choose the shortest route from the start point to the end point. The choice of route directly affects the transportation cost. The measurement of the shortest route may be the shortest time， the shortest distance， or the least cost. Choosing the transportation route correctly is an important task for transportation staff. Direct delivery transportation is one of many transportation route selection problems， and there are many solutions to this problem. However， applying Dijkstra labeling method to solve complex direct delivery transportation problems has its unique advantages.

Key words： Dijkstra labeling method; direct delivery; method application

直送式配送运输是指由一个供应点对一个收货点的专门送货，其货物配送路线的优化就是选择最短的配送路线，以节约时间、费用，提高配送效率。所以直送式配送运输问题，主要是寻找物流网络的最短路问题。对于分离的单个始发点和终点的网络运输路线选择问题，可以有多种解决方法，Dijkstra标号法在解决直送式配送运输问题中具有独特的优势，该方法不仅能够快速找到配送的最短路线，而且还有利于编程计算，最终得到最短距离。

1  Dijkstra标号法

Dijkstra标号法适用于每条弧的赋权数c都大于或等于零的情况，Dijkstra标号法也称为双标号法。所谓双标号法，也就是对图中的点v赋予两个标号l，k，第一个标号l表示从起点v到v的最短路的长度，第二个标号k表示在v至v的最短路上

v前面一个邻点的下标，从而找到起点v到终点v的最短路径及v与v的距离。

对于一个赋权图（其赋权根据具体问题的要求可以是路程的长度，成本的花费等）中指定的两个点v和v找到一条从v到v的路，使得这条路上所有弧的权数总和最小，这条路被称之为v到v的最短路，这条路上所有弧的权数之和被称之为从v到v的距离。……