基于Dijkstra 算法的搬運車省時路徑規劃研究

閆恩雪 YAN En-xue；張石強 ZHANG Shi-qiang

（河北工程大學，邯鄲 056038）

0 引言

隨著現代工業技術的不斷提高，越多越多的企業車間使用智能搬運車，智能搬運車在很多領域都得到了認可，目前國內外都在擴展使用智能搬運車。智能搬運車一般多用于制造業、物流倉儲等行業，代替人工進行高體力勞動，隨著國家對工業化、智能化的重視，智能搬運車行業逐漸壯大起來。在多數發達國家，智能搬運車的應用更為廣泛，自引進智能搬運車后，不僅車間的安全性提高，而且工作效率也大大提高，如今智能搬運車正在向更多行業進行邁進。

智能搬運車被使用和認可的同時，如何更高效的利用智能搬運車成為了大家的關注點。智能搬運車的高效使用與其行駛路徑息息相關，一條好的行駛路徑不僅路程最短，還要行駛時間更節省，這樣以來既省電又省時，大大提高工作效率。路徑規劃是當今的一個研究重點，經典的路徑規劃算法有：Dijkstra 算法、蟻群算法、遺傳算法、A*算法等。在這些路徑規劃算法中，僅有Dijkstra 算法能夠穩定地實現全局最優路徑的搜索，而其它算法都有可能因為陷入局部最優而搜索出次優路徑，因此本文選擇Dijkstra算法進行研究，對Dijkstra 算法進行改進，保留既短又省時的路徑，提高工作效率，降低工作成本。

1 Dijkstra 算法概述

1.1 Dijkstra 算法介紹

Dijkstra 算法是當今最短路徑的經典算法之一，是荷蘭計算機科學家狄克斯特拉在1959 年提出的“貪心算法”模式，是解決有權圖的最短路徑問題的方法。按照路徑遞增次序產生算法，算法復雜度為n2，通過以某個頂點作為起點向其他所有點擴展，把他們之間的距離保存下來，再篩選出各兩點之間的最短距離，作為最終的最短路徑。Dijkstra 算法具有適用廣、不存在負權邊的特點，有效計算有向圖的最短路徑問題。

Dijkstra 算法具體步驟如下：

步驟一：初始化。初始集合S 中只有S0點，剩余節點都在U 集合，從S0向各點延伸，與S0相鄰的點之間的距離為s，標記為臨時標號T=s，與S0不相鄰的點，標記為T=+∞。

步驟二：在集合U 中，同一節點經對比所有T 標號中選擇最小值標記為永久標號P，此時P 標號的來源即為一條最短路徑。

步驟三：將P 標號從U 集合轉移到S 集合。

步驟四：重復步驟二和步驟三，至所有節點都轉移到S 集合時運算結束。

1.2 改進Dijkstra 算法

傳統Dijkstra 算法最終只保留一條最短路徑，而在計算的過程中可能會出現多個最優解，就有可能出現被篩除掉的路線是最多因素影響下最佳的路線。本文對Dijkstra算法進行改進，在路線規劃時，將所有搜索到的最短節點不進行選擇，都保留下來。再從這些節點搜索所用時間最短的路徑，改進算法是考慮了相同路程長度時，由于拐彎時減速-拐彎-加速的過程導致的時間不同，改進單純的最短路徑，得到高效低成本的方案。

改進Dijkstra 算法具體步驟如下：

步驟一：初始化。設置初始集合S 與其余節點集合U，找到與S0點相鄰距離最短的節點Si，將Si節點從集合U轉移到集合S。其余集合U 中與S0不相鄰的點，標記為T=+∞。

步驟二：從Si出發，在集合U 中尋找相鄰節點Sj，同一節點經對比所有T 標號中選擇最小值標記為永久標號P，同時將Si節點放入前驅節點集合B 中，此時保留P 標號的來源即為一條最短路徑，放入最短路徑集合C 中。

步驟三：將P 標號從U 集合轉移到S 集合。

步驟四：重復步驟二和步驟三，至U 集合變為空集時，將保留的不唯一的最短路徑分別計算其運行時間。

步驟五：對最短路徑集合C 進行時間計算，并篩選保留運作耗時最少的路徑為最優路徑，計算結束。具體步驟如圖1。

圖1 改進Dijkstra 算法流程圖

2 E 公司生產車間省時路徑規劃案例分析

E 公司是一家微波爐制造商，其生產車間采用柔性生產線，由于產品的組成重量大、體積大、易磕碰，為了在生產過程中搬運更方便安全，生產車間引進了智能搬運車。現為了使智能搬運車運行效率更高，將對E 公司生產車間的智能搬運車的行駛路線進行更新。

2.1 電子地圖建模

地圖建模通常有三種：柵格圖法、可視圖法、拓撲結構圖法。本文的案例E 公司生產車間布局規整，搬運車行駛路程簡單，車間內工作臺、貨物存放等清晰明了，可以看作為矩形。因此柵格圖法更適合E 公司生產車間的環境地圖建模。

根據E 公司生產車間的實地情況，采用16×16 的柵格計算結果會更精準，將生產車間智能搬運車可行駛的區域用白色表示；將操作臺、貨物、流水線看做障礙物，用黑色表示。

可行駛區域用0 代表，障礙物區域用1 代表，在MATLAB 中運用公式F={0，1}

輸入每個格子的屬性；用坐標（x，y）表示每個格子的位置，左下角為（1，1），右上角為（16，16），來表示16×16 的柵格圖。其中右下角為生產車間的入口，根據E 公司生產車間的情況，建模地圖如圖2 所示。

圖2 E 公司生產車間柵格圖法電子地圖

2.2 建立省時路徑規劃模型

根據E 公司生產車間實地情況，現對生產車間進行路徑規劃建模前，先進行相關條件假設與相關參數設置。以下求解計算基于該數據進行。

相關條件假設：

①智能搬運車拐彎時是直角原地拐彎，拐彎半徑看作為0。

②智能搬運車拐彎時先減速到拐彎速度，進行拐彎，再加速為直線勻速行駛的速度。

③不考慮貨物的重量對搬運車的速度影響。

④智能搬運車一趟只送一種貨物，完成該任務后再進行下一項任務。

E 公司生產車間智能搬運車的相關參數設置如表1。

表1 智能搬運車相關參數設定

本文在計算最短路徑的基礎上多加了該路徑對應的時間計算，更詳細的解釋了選擇該路徑的優點。將一條路徑的總時間分為減速運動總時間、加速運動總時間、勻速運動總時間這三個部分計算。

減速運動總時間Ta1：

加速運動總時間Ta2：

其中，減速運動行駛的路程為：

加速運動行駛的路程為：

勻速直線所行駛的路程Lv1：

勻速直線運動總時間Tv1：

將減速運動總時間、加速運動總時間、勻速運動總時間相加的到一條路徑的總時間Ttotal：

約束條件為：

優化目標為：

上述公式中i 為需要減速拐彎的節點，j 為拐彎后需要加速的節點，L原始為原來的智能搬運車的行駛路徑的長短，T原始為原來的智能搬運車行駛路徑所需的時間，使用MATLAB 進行路徑及時間的建模，經過計算比較得出更省時、低成本、高效的路徑。

2.3 改進算法流程的實施

求解過程使用到MATLAB，將改進的Dijkstra 算法代碼輸入進行運行求解，得到最終路徑最短中的最省時路徑。具體步驟如下：

①調查E 公司生產車間的實地情況，設計黑白兩色柵格圖，黑色代表障礙物，白色代表可通行。

②讀取數據，設置初始集合S 與其余節點集合U，找到與起始點S0點相鄰距離最短的節點Si，將Si節點從集合U 轉移到集合S。

③從Si出發，在集合U 中尋找相鄰節點Sj，同時將Si節點放入前驅節點集合B 中，此時保留P 標號的來源即為一條最短路徑，放入最短路徑集合C 中。將P 標號從U集合轉移到S 集合。

④重復③，至U 集合變為空集時，保留所有最短路徑。

⑤對最短路徑集合C 進行時間計算，并篩選保留運作耗時最少的路徑來源為最優路徑，計算結束，輸出結果。（圖3）

圖3 改進Dijkstra 算法的重點部分

3 搬運車路徑優化前后對比

根據圖2，將E 公司生產車間看作為256 個小方格，E公司生產車間共有5 項智能搬運車的運輸任務，5 項任務分 別 為：（5，3）→（14，11）；（14，11）→（3，15）；（3，15）→（14，14）；（14，14）→（6，5）；（6，5）→（14，6），結合智能搬運車的相關參數，不受其他因素的影響，經過計算優化前后智能搬運車的路徑具體信息如表2 所示。

表2 搬運車路徑優化前后對比

優化前后對比可以看出，路程長度相等的情況下，也可能出現耗時不同，由于加速減速的過程可能會耗費不必要的時間，因此本次路徑優化可以有效減少智能運輸車的行駛時間，節省時間可以提高效率。任務一，在優化前路程長為17 米，所耗時間為19.78 秒，優化后路程長為17 米，所耗時間為18.6 秒，節省了1.18 秒；任務二，在優化前路程長為15 米，所耗時間為23 秒，優化后路程長為15 米，所耗時間為17.4 秒，節省了5.6 秒；任務三，在優化前路程長為12 米，所耗時間為14.6 秒，優化后路程長為12 米，所耗時間為13.8 秒，節省了0.8 秒；任務四，在優化前路程長為17 米，所耗時間為19.6 秒，優化后路程長為17 米，所耗時間為18.6 秒，節省了1 秒；任務五，在優化前路程長為13 米，所耗時間為15.4 秒，優化后路程長為9 米，所耗時間為10.8 秒，節省了4.6 秒。優化后的路徑在長度的時間上優于優化前的，選擇優化后的將更有利于E 公司生產車間的發展。

4 結語

當今制造業發展蓬勃，智能搬運車的使用也在快速普及。工作效率受到多重因素影響，只考慮路程長短已經不能被滿足，路徑規劃中可以選擇路程和時間雙因素，全面計算更高效的路徑方案，為企業實現降本增效。

本文基于改進Dijkstra 算法對E 公司生產車間的智能搬運車的路徑進行重新規劃，先是對Dijkstra 算法的后續加上了不進行篩選，保留所有最短路徑，再對保留的所有路徑進行時間計算。由于智能搬運車在行駛的過程中遇到拐彎時會出現變速的情況，進而影響到整體的運行時間，通過將保留的最短路徑進行時間計算，可以有效的篩選出既路程短，又耗時少的路徑，節省下來的時間可以做更多的工作，以提高整體的工作效率。通過E 公司生產車間的智能搬運車的五個任務線案例，數據清晰的表明了該Dijkstra 改進方法可以實現省時省力的目標，在未來可為企業帶來更大的利潤。