基于改進Dijkstra算法的倉儲揀選最優路徑規劃研究

摘要：Dijkstra（迪科斯徹）算法是典型的單源最短路徑算法，用于計算一個節點到其他所有節點的最短路徑，其主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra算法是很有代表性的最短路徑算法。文章研究了叉車在倉儲作業選擇最優路徑的問題，主要根據倉儲巷道交通網絡數據，建立數學模型，確定叉車倉儲作業的最優路徑，并且對模型的優缺點進行分析，提出改進方法，以更好地研究叉車倉儲作業的最優路徑選擇問題。本研究選出在倉儲巷道作業車輛從起點到終點的最優路徑。結果表明，Dijkstra算法能夠計算出車輛作業的最優線路，對現場的司機指導、工作效率提高提供了很好的支持。

關鍵詞：加權平均法；迪杰斯徹算法；最優路徑

中圖分類號：TP18

文獻標志碼：A

0 引言

Dijkstra算法是典型最短路徑算法，用于計算一個結點到其他結點的最短路徑。它的主要特點是以起始點為中心向外層層擴展（廣度優先搜索思想），直到擴展到終點為止^［1］。本文通過Dijkstra算法及優化研究了叉車在倉儲作業選擇最優路徑的問題。

1 叉車倉儲作業路徑選擇

目前，倉儲叉車在復雜的作業環境下，尋找一條可靠、快速、安全的最優路徑，能夠有效地提升作業效率。本研究通過對倉儲內道路狀況的收集及運用相關數據建立相應數學模型進行有效的分析，進而選擇最優路徑^［2］。本研究采用Dijkstra算法。該算法是目前交通網絡圖在單源最短路徑問題上運用最普遍、完善的算法之一，也是公認在非負權值且所有的權大于等于零時，尋求最短路問題最好的算法。本論文通過查找道路交通數據，運用Dijkstra算法、加權平均法的方法去解決出行路徑的選擇問題。

2 Dijkstra算法

2.1 算法特點

迪科斯徹算法使用廣度優先搜索解決賦權有向圖或者無向圖的單源最短路徑問題，算法最終得到一個最短路徑樹^［3］。該算法常用于路由算法或者作為其他圖算法的一個子模塊。

2.2 算法的思路

算法思想：設G=（V，E）是一個帶權有向圖，把圖中頂點集合V分成兩組。

第一組為以求出最短路徑的頂點集合（用S表示，初始時S中只有一個源點，以后每求得一條最短路徑，就將其加入集合S，直到全部頂點都加入S中）。

第二組為其余未確定最短路徑的頂點集合（用U表示），按最短路徑長度的遞增次序依次把第二組頂點加入S。在加入的過程中，總保持從源點v到S中各頂點的最短路徑長度不大于從源點v到U中任何頂點的最短路徑長度。此外，每個頂點對應一個距離，S中的頂點的距離就是從v到此頂點的最短路徑長度，U中頂點的距離是從v到此頂點只包括S中的頂點為中間頂點的當前最短路徑長度^［4］。

（1）初始時，S只包含起點s；U包含除s外的其他頂點，且U中頂點的距離為“起點s到該頂點的距離”。例如：U中頂點v的距離（s，v）的長度，然后s和v不相鄰，則v的距離為正無窮。（2）從U中選出“距離最短的頂點k”，并將頂點k加入S；同時，從U中移除頂點k。（3）更新U中各個頂點到起點s的距離。之所以更新U中頂點的距離，是由于上一步中確定了k是求出最短路徑的頂點，從而可以利用k來更新其他頂點的距離；例如：（s，v）的距離可能大于（s，k）+（k，v）的距離。（4）重復（2）和（3），直到遍歷完所有頂點。

3 實現過程

在倉庫揀選過程中，是穿越巷道還是返回，以及揀選設備所處的位置是前通道、后通道還是中通道，決定了倉庫揀選路徑。本文根據倉庫巷是根據揀貨設備與巷道中最遠揀貨點之間的距離來判斷的，當揀貨點與揀貨設備之間的距離大于揀貨巷道長度的一半時，穿越巷道；否則返回。倉庫布局如圖1所示。

3.1 深度優先搜索（DFS）

首先實現對Ai所在連通子圖的深度優先搜索，用遞歸算法實現以下幾步基本過程：（1）深度優先遍歷圖的方法是，從圖中某頂點A1出發。（2）依次以Ai的未被訪問的鄰接點為出發點，對圖進行深度優先遍歷，直至圖中所有與Ai有路徑相通的頂點都被訪問。（3）若此時圖中尚有頂點未被訪問，則從一個未被訪問的頂點出發，重新進行深度優先遍歷，直到圖中所有頂點均被訪問過。（4）按深度優先搜索遞歸訪問A1的某個未被訪問的鄰接點A3、A4中的某一個。再訪問頂點A3的另一個鄰接點A5，再訪問頂點A5的鄰接點A7、A8中的某一個。同時，結點A2、A6已經在深度優先搜索中直接篩除出列，進行該優化步驟能避免傳統的Dijkstra算法盲目取點搜索的缺陷，最終得到全部解子圖。倉庫深度優先搜索如圖2所示。

3.2 廣度優先搜索（BFS）

對進行了深度優先搜索的起點A1到終點A8連通子圖進行廣度優先搜索。廣度優先搜索目的在于確定各結點在子圖中的層次關系，步驟：（1）將起始頂點放入隊列中。（2）從隊列首部選出一個頂點，并找出所有與之鄰接的頂點，將找到的鄰接頂點放入隊列尾部，將已訪問過頂點涂成黑色，沒訪問過的頂點是白色。如果頂點的顏色是灰色，表示已經發現并且放入了隊列，如果頂點的顏色是白色，表示還沒有發現。（3）按照同樣的方法處理隊列中的下一個頂點。對各結點做合理的分層安排，求解的所有結點分布在離起點最近的一層。把所有可能的路徑都搜索完后，輸出記錄的最優路徑。倉庫廣度優先搜索如圖3所示。

廣度優先搜索先用最優分層排序法，確定各結點所在的層次，再確定各層結點間是否存在關聯。使用Dijkstra算法求解最短路徑時，根據各結點間的權值來判定最終選哪個結點作為下一個層次節點，而將各結點放置在離起點最近的層次。該點若是在最終的最短路徑線路上，那么很快會被找到，比它權值大的結點均可直接篩除出列。

3.3 數據對象封裝

采用Python語言的面向對象的思想，創建結點、結點的相鄰邊、結點的相鄰結點、起點到該結點的最短路徑長度等多種信息。用遞歸方法設計好，它可以使得程序結構更簡捷易懂。實現深度優先搜索法占內存少但速度較慢，搜索時則會遍歷所有的結點，因為每次遍歷時間復雜度都是以指數的形式增長的，易超時。結合廣度優先搜索算法占內存多但速度較快，在距離和深度成正比的情況下能較快地求出最優解。相鄰節點處理邏輯如圖4所示。

4 現場路徑選擇求解

物流倉間提供有2臺搬運車輛，其載重量均為1.6 t，車輛每次配送的最大行駛距離為10 km，配送中心（編號為0）與8個貨位之間及8個貨位相互之間的距離及耗時權重dij（i，j=1，2，……，8）如表1所示。要求合理安排車輛搬運路線，使搬運總里程最短。

根據以上問題的數據信息，設置好遺傳算法的參數，通過遺傳算法求解該搬運車輛路徑問題得到最優解為【1-4-3-5-8】，最短距離權重為【12】。

5 結語

驗證發現，通過本研究所建數學模型求出的結果符合實際情況，該模型算法是綜合DFS和BFS的特點，通過對Dijkstra算法在數據結構和存儲結構上進行優化改進，縮短運算周期，在實際運用中能高效地處理問題。本研究通過模型中的路段時間期望值來選擇最優路線，哪條路的時間期望越小，哪條路就是最優路徑。

參考文獻

［1］吳祈宗.運籌學［M］.3版.北京：機械工業出版社，2013.

［2］賀景.交通咨詢系統的最短路徑算法與實現［D］.西安：西安財經學院，2015.

［3］郭耀煌.運籌學與工程系統分析［M］.北京：中國建筑工業出版社，1986.

［4］馬杰，宋建池.近8年我國化工事故統計與分析［J］.工業安全與環保，2009（9）：37-38.

（編輯 王永超）

Research on optimal path planning of warehouse picking based on improved Dijkstra algorithm

Yu Baoyi， Li Le， Shi Delun

（Hubei China Tobacco Industry Co.， Ltd.， Wuhan 430040， China）

Abstract： Dijkstra algorithm is a typical single source shortest path algorithm， which is used to calculate the shortest path from one node to all other nodes. The main feature is to expand outward layer by layer from the starting point to the end point. Dijkstra algorithm is a representative shortest path algorithm. This paper studies the problem of selecting the optimal path for forklift storage operations， mainly based on the data of storage roadway traffic network， establishes a mathematical model， determines the optimal path for forklift storage operations， analyzes the advantages and disadvantages of the model， and proposes an improved method to better study the optimal path selection problem for forklift storage operations. Select the optimal path from the starting point to the end point for vehicles working in the storage roadway. The results show that Dijkstra algorithm can calculate the optimal route of vehicle operation， which provides good support for on-site driver guidance and work efficiency improvement.

Key words： weighted average method; Dijkstra algorithm; best route