一種基于Dijkstra 的物流配送路徑優(yōu)化算法設(shè)計(jì)

先夢(mèng)瑜

（西安航空職業(yè)技術(shù)學(xué)院，陜西西安 710089）

隨著互聯(lián)網(wǎng)購(gòu)物平臺(tái)規(guī)模的不斷擴(kuò)大，人們的購(gòu)物方式也從實(shí)體店購(gòu)物逐漸向電商購(gòu)物轉(zhuǎn)移[1]。據(jù)統(tǒng)計(jì)，在我國(guó)網(wǎng)絡(luò)銷(xiāo)售高峰期的郵政包裹處理量高達(dá)29 億件。保證數(shù)量如此巨大的包裹群在規(guī)定時(shí)間送至顧客手中，這對(duì)物流配送中心要求極高。要求電商必須對(duì)物流配送的各個(gè)步驟進(jìn)行全方位地把握，對(duì)物流中心分配速度進(jìn)行調(diào)控，對(duì)車(chē)輛以及人力進(jìn)行合理調(diào)度。而在上述運(yùn)輸流程中，物流配送路徑的選擇是決定快遞時(shí)效的關(guān)鍵因素[2]。

配送路徑的選擇本質(zhì)是數(shù)學(xué)中的運(yùn)籌學(xué)問(wèn)題，該問(wèn)題的最優(yōu)解是從一個(gè)物流節(jié)點(diǎn)到另一個(gè)物流節(jié)點(diǎn)的最短路徑，對(duì)應(yīng)的算法同時(shí)還需滿足實(shí)時(shí)性。常見(jiàn)的計(jì)算最短路徑算法有A*算法[3]、Dijkstra 算法[4]以及Floyd算法等。物流配送模型也可被看作是單源最短路徑的求解，Dijkstra 算法有較大優(yōu)勢(shì)。Dijkstra算法受到了諸多研究學(xué)者的關(guān)注，同時(shí)眾多學(xué)者對(duì)其進(jìn)行優(yōu)化以獲得更優(yōu)的性能。通常，優(yōu)化Dijkstra算法從數(shù)據(jù)結(jié)構(gòu)的方向進(jìn)行。例如文獻(xiàn)[5-6]中，提出使用堆結(jié)構(gòu)以及最短路徑樹(shù)結(jié)構(gòu)對(duì)數(shù)據(jù)進(jìn)行構(gòu)建從而提升算法性能。該文將對(duì)傳統(tǒng)Dijkstra 算法進(jìn)行改進(jìn)，進(jìn)而提升最短路徑算法性能。

1 算法設(shè)計(jì)

1.1 Dijkstra算法

Dijkstra 算法由英國(guó)人迪科斯徹在十九世紀(jì)提出。該算法通過(guò)廣度的優(yōu)先搜索[7-9]進(jìn)而對(duì)有向圖路徑之間的最短距離進(jìn)行計(jì)算。常見(jiàn)的算法舉例如圖1 所示，即使用Dijkstra 算法建立從0 節(jié)點(diǎn)到其他幾個(gè)節(jié)點(diǎn)的最短路徑樹(shù)。

算法執(zhí)行的流程為：

1）建立節(jié)點(diǎn)數(shù)據(jù)集合，命名為S和U，集合U的含義為未找到最短路徑的節(jié)點(diǎn)，節(jié)點(diǎn)數(shù)據(jù)集合表示的是所有節(jié)點(diǎn)，因此S為找到最短路徑的節(jié)點(diǎn)。那么，集合U和集合S就組成了全部的節(jié)點(diǎn)。

2）構(gòu)建數(shù)據(jù)矩陣d[i]，該數(shù)據(jù)矩陣為節(jié)點(diǎn)0 到其他節(jié)點(diǎn)最短路徑集合。之后構(gòu)建初值為零的矩陣t[i]，在未找到最短路徑時(shí)，最短路徑的尋找不會(huì)停止。

3）初始路徑尋找。首先尋找與節(jié)點(diǎn)0 相連接的路徑長(zhǎng)度，將其放入到矩陣t中。由圖1 可知，d[1]=100，d[2]=30。以此類推，尋找完所有路徑后，t[0]=1，此時(shí)節(jié)點(diǎn)0 遍歷完畢。

4）路徑距離比較。比較路徑的長(zhǎng)度值，即比較d[1]、d[2]，…，d[4]的長(zhǎng)度。由圖1 可知，d[4]的長(zhǎng)度最短，所以此時(shí)記t[4]=1，表示節(jié)點(diǎn)0 到節(jié)點(diǎn)4 的路徑值最短。之后，循環(huán)此過(guò)程直到結(jié)束。最終遍歷完成的結(jié)果如表1 所示。

表1 路徑樹(shù)遍歷結(jié)果

1.2 標(biāo)號(hào)數(shù)學(xué)模型

而將該方法抽象為數(shù)學(xué)表達(dá)，可以通過(guò)圖論的相關(guān)知識(shí)獲取。假設(shè)集合G為h階的帶權(quán)圖，其可以表示為三維集合G=。假設(shè)G中的Vi和Vj不是相鄰節(jié)點(diǎn)，則需要使G的初始頂點(diǎn)v1和vi之間的路徑達(dá)到最小值。

假設(shè)為G的初始頂點(diǎn)v1和vi最小路徑的權(quán)值，假如頂點(diǎn)集合中的vi被所標(biāo)號(hào)，即可以認(rèn)定vi值在第r個(gè)步驟獲得了標(biāo)號(hào)。

假設(shè)為初始頂點(diǎn)v1到vj的實(shí)時(shí)路徑上界，若頂點(diǎn)vj得到了標(biāo)號(hào)，即vj在第r個(gè)步驟獲得了一個(gè)臨時(shí)標(biāo)定。

假設(shè)Ur集合為第r個(gè)步驟的通過(guò)集，則Ur集合中的元素為已經(jīng)獲得標(biāo)號(hào)的頂點(diǎn)v。同理，可以設(shè)置Kr集合為第r個(gè)步驟的未通過(guò)集，則Kr集合中的元素為未獲得編號(hào)的頂點(diǎn)v。

該編號(hào)算法的計(jì)算機(jī)偽代碼為：

可以從其數(shù)學(xué)模型中看到，該算法符合其廣度性要求，算法的復(fù)雜度較高，算法要經(jīng)過(guò)所有的節(jié)點(diǎn)。因此，該算法在系統(tǒng)簡(jiǎn)單的情況下應(yīng)用價(jià)值較高。而對(duì)于路徑網(wǎng)絡(luò)復(fù)雜的情況算法完成時(shí)間過(guò)高，其應(yīng)用價(jià)值較低，故需要對(duì)算法進(jìn)行優(yōu)化。

1.3 Dijkstra多標(biāo)號(hào)并行算法

由上述分析可以看出，廣度性作為算法的特性嚴(yán)重拖慢了算法處理速度，該文使用多標(biāo)號(hào)并行的方法提升算法的處理速度。

下面對(duì)多標(biāo)號(hào)算法進(jìn)行描述，在對(duì)標(biāo)號(hào)進(jìn)行選擇時(shí)，若有多個(gè)不同的頂點(diǎn)在相同的步驟點(diǎn)數(shù)均擁有相同的最小編號(hào)時(shí)，則這些頂點(diǎn)應(yīng)同時(shí)被標(biāo)定[10]。這也說(shuō)明，使用多個(gè)頂點(diǎn)并行運(yùn)行的算法可以極大地減少運(yùn)行時(shí)間，進(jìn)而提升算法的性能。

假設(shè)r>0，加入存在圖中的頂點(diǎn)值vi屬于Ur-1集合，則有以下等式成立：

由此可見(jiàn)，頂點(diǎn)v集合中的頂點(diǎn)在第r個(gè)步驟可以被同時(shí)標(biāo)記。此時(shí)假設(shè)標(biāo)號(hào)只對(duì)vi進(jìn)行標(biāo)記，不對(duì)vj頂點(diǎn)進(jìn)行標(biāo)記。則在第r個(gè)步驟會(huì)存在vn，有以下關(guān)系：

假設(shè)在第r個(gè)步驟被修改，則有以下關(guān)系式：

因此可以看出，在某個(gè)步驟選擇vj進(jìn)行標(biāo)號(hào)并不會(huì)對(duì)后續(xù)遍歷的步驟產(chǎn)生影響。運(yùn)用該多標(biāo)號(hào)的方法，可以大幅縮減標(biāo)號(hào)的次數(shù)，進(jìn)而縮短算法運(yùn)行的時(shí)間。

并行算法的思想和計(jì)算機(jī)結(jié)構(gòu)極為契合，計(jì)算機(jī)可以使用多個(gè)處理器或處理器的多個(gè)線程協(xié)同計(jì)算。并行計(jì)算過(guò)程和串行計(jì)算過(guò)程的對(duì)比示意圖如圖2 所 示[11]。

圖2 串并行計(jì)算過(guò)程對(duì)比

在上文提到的多標(biāo)號(hào)Dijkstra 算法中，雖然多標(biāo)號(hào)可以縮短算法執(zhí)行時(shí)間，但是對(duì)于一個(gè)頂點(diǎn)而言，多標(biāo)號(hào)算法會(huì)將相鄰的兩個(gè)點(diǎn)同時(shí)選擇為臨時(shí)性的標(biāo)號(hào)，這也會(huì)增加計(jì)算量。因此在多標(biāo)號(hào)算法執(zhí)行過(guò)程中加入并行算法，這可從計(jì)算角度大幅度提升算法運(yùn)行速度。

使用并行算法需要注意多個(gè)線程造成的資源共用問(wèn)題，多個(gè)線程同時(shí)運(yùn)行可能會(huì)訪問(wèn)同一個(gè)資源，由此便會(huì)造成線程堵塞進(jìn)而影響執(zhí)行效率。因此，需要根據(jù)執(zhí)行算法的平臺(tái)對(duì)線程進(jìn)行分配。

該文多標(biāo)號(hào)并行算法的執(zhí)行流程圖如圖3所示。

圖3 該文算法流程圖

1.4 算法對(duì)比分析

算法性能對(duì)比通常從執(zhí)行準(zhǔn)確率和執(zhí)行速度進(jìn)行分析。

1）執(zhí)行速度[12-13]。傳統(tǒng)Dijkstra 算法采用串行搜索的模式對(duì)各個(gè)節(jié)點(diǎn)進(jìn)行遍歷，傳統(tǒng)方法時(shí)間復(fù)雜度為O(n2)，其中n為路徑中的頂點(diǎn)個(gè)數(shù)。多標(biāo)號(hào)的Dijkstra 算法通過(guò)修改標(biāo)號(hào)改為臨時(shí)標(biāo)號(hào)的方法降低時(shí)間復(fù)雜度，時(shí)間復(fù)雜度應(yīng)為O(h(n+lgn))。并行多標(biāo)號(hào)的Dijkstra 算法可以通過(guò)k個(gè)線程同時(shí)運(yùn)行，因此總的時(shí)間復(fù)雜度將會(huì)在多標(biāo)號(hào)法的基礎(chǔ)上減少，時(shí)間復(fù)雜度應(yīng)為O(h(n/k+lgn))。

2）由執(zhí)行準(zhǔn)確度[14]的概念可知，當(dāng)頂點(diǎn)數(shù)n較小時(shí)，傳統(tǒng)算法由于算法遍歷數(shù)較少，所以并行算法運(yùn)行準(zhǔn)確度大致相同，提升效果不明顯。而當(dāng)頂點(diǎn)數(shù)n較大時(shí)，遍歷數(shù)量較多，那么和并行算法運(yùn)行準(zhǔn)確度相差則較大。

2 實(shí)驗(yàn)設(shè)計(jì)

2.1 數(shù)據(jù)環(huán)境選擇與配置

該文所驗(yàn)證的算法類型為并行算法，因此使用多核處理器運(yùn)行算法。文中選擇的實(shí)驗(yàn)硬件平臺(tái)參數(shù)如表2 所示。

表2 數(shù)據(jù)環(huán)境配置

使用并行算法需要注意多個(gè)線程造成的資源共用問(wèn)題，多個(gè)線程同時(shí)運(yùn)行可能會(huì)訪問(wèn)同一個(gè)資源，由此就會(huì)造成線程堵塞。因此，在運(yùn)行代碼前需要對(duì)CPU 線程進(jìn)行分配。如圖4 所示，如果數(shù)組長(zhǎng)度設(shè)定為64，則此時(shí)CPU 的每個(gè)線程就會(huì)負(fù)責(zé)兩個(gè)頂點(diǎn)的遍歷工作[15]。

圖4 線程分配舉例

2.2 實(shí)驗(yàn)測(cè)試

最短路徑算法通常使用特定的公開(kāi)測(cè)試圖集進(jìn)行性能分析，圖集中的圖分為隨機(jī)圖和特定圖。測(cè)試圖由頂點(diǎn)和邊數(shù)組成，為了和其他算法性能進(jìn)行對(duì)比，該文實(shí)驗(yàn)使用7 幅隨機(jī)圖進(jìn)行測(cè)試。隨機(jī)圖通常是固定頂點(diǎn)數(shù)，使用某個(gè)概率分布或函數(shù)對(duì)邊數(shù)進(jìn)行控制。該文隨機(jī)生成的隨機(jī)圖屬性如表3所示。

文中測(cè)試分為運(yùn)行時(shí)間測(cè)試及準(zhǔn)確率測(cè)試兩個(gè)部分。首先，使用傳統(tǒng)Dijkstra 算法、多標(biāo)號(hào)Dijkstra算法以及該文算法進(jìn)行運(yùn)行時(shí)間的對(duì)比測(cè)試，測(cè)試結(jié)果如表4 所示。

表4 運(yùn)行時(shí)間測(cè)試結(jié)果

由測(cè)試結(jié)果可以看出，多標(biāo)號(hào)算法相比傳統(tǒng)算法有明顯的改進(jìn)。與傳統(tǒng)算法相比，多標(biāo)號(hào)算法在復(fù)雜圖中的運(yùn)行時(shí)間提升更為明顯。在20 000 個(gè)頂點(diǎn)時(shí)，多標(biāo)號(hào)算法運(yùn)算時(shí)間相比傳統(tǒng)Dijkstra 算法減少約0.929 s。而該文算法是對(duì)多標(biāo)號(hào)算法進(jìn)行并行化處理，該算法和多標(biāo)號(hào)算法相比又得到了進(jìn)一步的提升。當(dāng)圖頂點(diǎn)的個(gè)數(shù)增加到10 000 以上時(shí)，運(yùn)行時(shí)間會(huì)顯著縮短，且頂點(diǎn)個(gè)數(shù)越多，該文所提算法的運(yùn)行速度越快。

并行算法的另一個(gè)重要指標(biāo)是并行加速比，并行加速比指的是并行算法相對(duì)串行算法提升的倍數(shù)。并行加速比的定義式如式（4）所示：

根據(jù)式（4）可以計(jì)算出該文算法的并行加速比，總結(jié)如表5 所示。

表5 該文算法并行加速比計(jì)算結(jié)果

從算法并行加速比可以看出，當(dāng)隨機(jī)圖的頂點(diǎn)個(gè)數(shù)增加時(shí)，算法并行加速比呈現(xiàn)出增長(zhǎng)的態(tài)勢(shì)。但是可以看到圖1、圖2 以及圖3 算法并行度趨于1甚至小于1。這是因?yàn)樵诙嗑€程工作時(shí)，如果數(shù)據(jù)量較小，多線程算法效能無(wú)法達(dá)到最大，所以在小數(shù)據(jù)集上多線程算法優(yōu)勢(shì)不明顯。但當(dāng)圖中頂點(diǎn)達(dá)到9 000 個(gè)時(shí)，算法并行加速比可以達(dá)到1.60，此時(shí)多線程并行計(jì)算的優(yōu)勢(shì)便可以體現(xiàn)出來(lái)。

由上文實(shí)驗(yàn)測(cè)試結(jié)果可以看出，該文設(shè)計(jì)的多線程并行Dijkstra 算法相比傳統(tǒng)的Dijkstra 算法有較大的提升。而根據(jù)當(dāng)前物流處理數(shù)據(jù)維度高、數(shù)據(jù)量大的特點(diǎn)使用并行算法更為合適，因此具有較高的工程應(yīng)用價(jià)值。

3 結(jié)束語(yǔ)

傳統(tǒng)的Dijkstra 路徑求解算法無(wú)法處理當(dāng)前海量的包裹配送路徑最短問(wèn)題，該文對(duì)Dijkstra 算法進(jìn)行改進(jìn)，在遍歷過(guò)程中使用了多標(biāo)號(hào)的方法提升求解速度，同時(shí)使用并行計(jì)算的方法對(duì)求解過(guò)程實(shí)現(xiàn)了加速。實(shí)驗(yàn)結(jié)果表明，在數(shù)據(jù)量較大的情況下，該文算法的綜合性能較為理想，運(yùn)行時(shí)間大幅縮短。此外，其并行加速比較高，能夠充分體現(xiàn)出并行算法的優(yōu)勢(shì)。