Dijkstra標號法在直送式配送運輸問題中的應用

劉臣宇 孫偉奇 李衛靈

摘? 要：運輸路線的選擇主要是選擇起點到終點的最短路線，路線的選擇直接影響到運輸成本。最短路線的度量可能是時間最短、距離最短或費用最少等。正確地選擇運輸路線是運輸工作人員的一項重要工作。直送式配送運輸是眾多運輸路線選擇問題中的一種，該問題的解法也比較多，但應用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的距離。如何找到v到v的最短路，可以應用Dijkstra標號法。

Dijkstra標號法求最短路徑的算法程序如下：

（1）給起點以標號0，s表示從v到v的距離為0，v為起點。

（2）找出已標號點的集合I，沒有標號點的集合J以及弧的集合v，v|v∈I，v∈J，這里這個弧的集合是指所有從已標號點到未標號點的弧的集合。

（3）如果上述弧的集合是空集，則計算結束。如果v已標號l，k，則v到v的距離即為l，從而v到v的最短路徑可以從k反向追蹤到起點v而得到。如果v未標號，則可以斷定不存在從v到v的最短路。

如果上述弧的集合不是空集，則轉下一步。

（4）對上述弧的集合中的每一條弧，計算：

s=l+c

在所有的s中，找到其值為最小的弧，不妨設此弧為V，V，則給此弧的終點以雙標號scd，c，返回步驟2。

若在第4步驟中，使得sij值為最小的弧有多條，則這些弧的終點既可以任選一個標定，也可以都予以標定，若這些弧中有些弧的終點為同一點，則此點應有多個雙標號，以便最后可以找到多條最短路徑。

2? 方法應用

圖1為一運輸網絡，弧線旁的數字為運輸距離（單位：千米），試求V到V間的最短路徑及其距離。

解：

（1）給起點V標以0，s，表示從V到V的距離為0，V為起點。

（2）這時已標定點的集合I=V，未標定點的集合J=V，V，V，V，V，弧集合v，v|v∈I， v∈J={V，V， V，V， V，V， V，V， V，V}，并有：S=l+c=0+22=22，S=l+c=0+42=42，S=l+c=0

+31=31，S=l+c=0+56=56，S=l+c=0+79=79。

MinS，S，S，S，S=Min22，42，31，56，79=S=22

這樣給弧V，V的終點V標以22，1，表示從V到V的距離為22，并且V到V的最短路徑中V的前一個點是V。

（3）這時I=V，V，J=V，V，V，V，弧集合v，v|v∈I， v∈J={V，V， V，V， V，V， V，V，V，V， V，V， V，V， V，V}，并有：S=l+c=22+31=53，S=l+c=22+22=44，S=l+c=22+42=66，S=l+c=22+56=78。

MinS，S，S，S，S，S，S，S=Min42，31，56，79，53，44，66，78=S=31

這樣給弧V，V的終點V標以31，1，表示從V到V的距離為31，并且V到V的最短路徑中V的前一個點是V。

（4）這時I=V，V，V，J=V，V，V，弧集合v，v|v∈I， v∈J={V，V， V，V， V，V，V，V， V，V， V，V，V，V， V，V， V，V}，并有：S=l+c=31+23=54，S=l+c=31+32=63，S=l+c=31+43=74。

MinS，S，S，S，S，S，S，S，S=Min42，56，79，53，66，78，54，63，74=S=42

這樣給弧V，V的終點V標以42，1，表示從V到V的距離為42，并且V到V的最短路徑中V的前一個點是V。

（5）這時I=V，V，V，V，J=V，V，弧集合v，v|v∈I， v∈J={V，V， V，V， V，V， V，V，V，V， V，V，V，V， V，V}，并有：S=l+c=42+23=65，S=l+c=42+32=74。

MinS，S，S，S，S，S，S，S=Min56，79，66，78，63，74，65，74=S=56

這樣給弧V，V的終點V標以56，1，表示從V到V的距離為56，并且V到V的最短路徑中V的前一個點是V。

（6）這時I=V，V，V，V，V，J=V，弧集合v，v|v∈I， v∈J=V，V， V，V， V，V， V，V， V，V，并有：S=l5+c=56+24=80。

MinS，S，S，S，S=Min79，78，74，74，80=S=S=74

這樣給弧V，V和V，V的終點V標以74，4和74，3，表示從V到V的距離為74，并且V到V的最短路徑中V的前一個點是V和V。

（7）這時I=V，V，V，V，V，V，J=Φ，弧集合v，v|v∈I， v∈J=Φ，計算結束。

到此根據終點V的標號可知，從V到V的最短距離是74，最短路徑中V的前一個點是V或V，V和V的前一個點是V，即此最短路徑為V→VV→V。

3? 結? 論

在Dijkstra算法中，網絡中的每個結點都要進行標號，標號的目的是找出每一點到后面各點的距離和路徑，通過比較得到最短路徑和最短距離，以此類推，直至終點，因此該算法實際上求出了從起點到網絡中各點的最短路徑和最短距離。在實際應用中，從起點到終點可能存在多條相同的路徑，這時可以根據實際情況任選其中一條路徑。

參考文獻：

[1] 劉臣宇. 海軍航材籌措與供應[M]. 北京：國防工業出版社，2015.

[2] 韓伯棠. 管理運籌學[M]. 2版. 北京：高等教育出版社，2005.