Dijkstra標(biāo)號法在直送式配送運(yùn)輸問題中的應(yīng)用

劉臣宇 孫偉奇 李衛(wèi)靈

摘? 要：運(yùn)輸路線的選擇主要是選擇起點(diǎn)到終點(diǎn)的最短路線，路線的選擇直接影響到運(yùn)輸成本。最短路線的度量可能是時間最短、距離最短或費(fèi)用最少等。正確地選擇運(yùn)輸路線是運(yùn)輸工作人員的一項(xiàng)重要工作。直送式配送運(yùn)輸是眾多運(yùn)輸路線選擇問題中的一種，該問題的解法也比較多，但應(yīng)用Dijkstra標(biāo)號法來解決復(fù)雜的直送式配送運(yùn)輸問題有其獨(dú)特的優(yōu)勢。

關(guān)鍵詞：Dijkstra標(biāo)號法;直送式配送;方法應(yīng)用

中圖分類號：U116.2? ? 文獻(xiàn)標(biāo)識碼：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

直送式配送運(yùn)輸是指由一個供應(yīng)點(diǎn)對一個收貨點(diǎn)的專門送貨，其貨物配送路線的優(yōu)化就是選擇最短的配送路線，以節(jié)約時間、費(fèi)用，提高配送效率。所以直送式配送運(yùn)輸問題，主要是尋找物流網(wǎng)絡(luò)的最短路問題。對于分離的單個始發(fā)點(diǎn)和終點(diǎn)的網(wǎng)絡(luò)運(yùn)輸路線選擇問題，可以有多種解決方法，Dijkstra標(biāo)號法在解決直送式配送運(yùn)輸問題中具有獨(dú)特的優(yōu)勢，該方法不僅能夠快速找到配送的最短路線，而且還有利于編程計(jì)算，最終得到最短距離。

1? Dijkstra標(biāo)號法

Dijkstra標(biāo)號法適用于每條弧的賦權(quán)數(shù)c都大于或等于零的情況，Dijkstra標(biāo)號法也稱為雙標(biāo)號法。所謂雙標(biāo)號法，也就是對圖中的點(diǎn)v賦予兩個標(biāo)號l，k，第一個標(biāo)號l表示從起點(diǎn)v到v的最短路的長度，第二個標(biāo)號k表示在v至v的最短路上

v前面一個鄰點(diǎn)的下標(biāo)，從而找到起點(diǎn)v到終點(diǎn)v的最短路徑及v與v的距離。

對于一個賦權(quán)圖（其賦權(quán)根據(jù)具體問題的要求可以是路程的長度，成本的花費(fèi)等）中指定的兩個點(diǎn)v和v找到一條從v到v的路，使得這條路上所有弧的權(quán)數(shù)總和最小，這條路被稱之為v到v的最短路，這條路上所有弧的權(quán)數(shù)之和被稱之為從v到v的距離。如何找到v到v的最短路，可以應(yīng)用Dijkstra標(biāo)號法。

Dijkstra標(biāo)號法求最短路徑的算法程序如下：

（1）給起點(diǎn)以標(biāo)號0，s表示從v到v的距離為0，v為起點(diǎn)。

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

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

如果上述弧的集合不是空集，則轉(zhuǎn)下一步。

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

s=l+c

在所有的s中，找到其值為最小的弧，不妨設(shè)此弧為V，V，則給此弧的終點(diǎn)以雙標(biāo)號scd，c，返回步驟2。

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

2? 方法應(yīng)用

圖1為一運(yùn)輸網(wǎng)絡(luò)，弧線旁的數(shù)字為運(yùn)輸距離（單位：千米），試求V到V間的最短路徑及其距離。

解：

（1）給起點(diǎn)V標(biāo)以0，s，表示從V到V的距離為0，V為起點(diǎn)。

（2）這時已標(biāo)定點(diǎn)的集合I=V，未標(biāo)定點(diǎn)的集合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的終點(diǎn)V標(biāo)以22，1，表示從V到V的距離為22，并且V到V的最短路徑中V的前一個點(diǎn)是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的終點(diǎn)V標(biāo)以31，1，表示從V到V的距離為31，并且V到V的最短路徑中V的前一個點(diǎn)是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的終點(diǎn)V標(biāo)以42，1，表示從V到V的距離為42，并且V到V的最短路徑中V的前一個點(diǎn)是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的終點(diǎn)V標(biāo)以56，1，表示從V到V的距離為56，并且V到V的最短路徑中V的前一個點(diǎn)是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的終點(diǎn)V標(biāo)以74，4和74，3，表示從V到V的距離為74，并且V到V的最短路徑中V的前一個點(diǎn)是V和V。

（7）這時I=V，V，V，V，V，V，J=Φ，弧集合v，v|v∈I， v∈J=Φ，計(jì)算結(jié)束。

到此根據(jù)終點(diǎn)V的標(biāo)號可知，從V到V的最短距離是74，最短路徑中V的前一個點(diǎn)是V或V，V和V的前一個點(diǎn)是V，即此最短路徑為V→VV→V。

3? 結(jié)? 論

在Dijkstra算法中，網(wǎng)絡(luò)中的每個結(jié)點(diǎn)都要進(jìn)行標(biāo)號，標(biāo)號的目的是找出每一點(diǎn)到后面各點(diǎn)的距離和路徑，通過比較得到最短路徑和最短距離，以此類推，直至終點(diǎn)，因此該算法實(shí)際上求出了從起點(diǎn)到網(wǎng)絡(luò)中各點(diǎn)的最短路徑和最短距離。在實(shí)際應(yīng)用中，從起點(diǎn)到終點(diǎn)可能存在多條相同的路徑，這時可以根據(jù)實(shí)際情況任選其中一條路徑。

參考文獻(xiàn)：

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

[2] 韓伯棠. 管理運(yùn)籌學(xué)[M]. 2版. 北京：高等教育出版社，2005.