基于時空模式的倉庫物流配送路徑優化

徐少堃

(安徽審計職業學院 商學系，安徽 合肥230001)

倉庫物流配送路徑優化的(Optimization of warehouse logistics distribution path，OWLDP)主要目的是找到從初始點出發并只經過一次給定點再返回初始點的最小成本路徑[1]。這也是最短路徑算法的實際應用，也是當前地理信息系統基礎軟件的重要功能[2]。回避方法[3]在部分尋優方面是具有較好的性能，然而這種方法對初始參數設置以及鄰接區結構具有很強的依賴性；蟻群算法[4]對于初始路徑選擇并沒有太大的依賴性，然而由于在初期缺乏相關信息，算法的收斂效率會受到影響[5]。

由上述分析可知，現有的方法具有較大的計算開銷，而且對于算法依賴于參數的選擇，對初始值具有較大的依賴性。當前關于OWLDP的研究主要為混合啟發式算法，即利用多種改善算法以及鄰接區查找結構來進行算法設計，以提高算法的整體效率，同時擴展了算法的適用范圍。混合啟發式算法還能夠增強OWLDP的準確率與效率，這也是當前OWLDP問題的重點研究方向。本文充分發揮了時空模式在整體尋優方面的強大能力，以及其在回避查找方面的獨有功能，進行OWLDP問題的求解，以增強OWLDP求解方案的尋優能力、運行效率、結果準時性。

1 倉庫物流配送路徑優化方法

1.1 倉庫物流配送方法選擇

回避查找是一種模擬人腦短期記憶功能的整體逐步尋優方法，它使用回避準則來避免進行無意義的循環計算，而且可基于藐視準則接受差解，確保在不同范圍內都能實現對有效路徑的探測，具有較強的部分查找能力。時空模式(Spatio-temporal pattern, SP)多用于對大規模、多目標問題的整體改善問題，能夠從解的范圍內的多個點、角度出發，實現一種自我學習式的搜索，具有十分突出的整體尋優能力。采取標準回避方法(Standard avoidance method，SAM)時，通過單純的優化操作建造的鄰接區。由于所得到的解具有較高相似性，故此方法容易陷入局部最優。同時，在采用時空模式時，變異計算單元會導致具有新特征個體的產生，由此增強了路徑組合的多樣性。

本文所提出的OWLDP首先使用時空模式作為彌漫方案建造鄰接區，由此使得群體個體廣泛地分布在解的大部分范圍內。通過這種方式能夠確保方法具有較好的尋優能力。隨后的聚合方案使用回避查找方法，該方法能夠突破以往的局部最優解，有效地避免過早的收斂。在彌漫決策中充分反映了群體智慧，極大地增加解的多樣性，而且利用聚合政策能夠促進整體執行力的提高，增加全局最優解的可能性。此外，隨著迭代次數的不斷增加，通過彌漫決策能夠形成對聚合決策的有效約束。通過這種相互作用，能夠有效的增強內部的競爭機制，從而得到最優解。

OWLDP的主要核心元素如下。

適應度函數：利用該函數能夠有效地分析回路的質量水平，一般而言，對于個體適應度的評價是通過路徑長度實現的。如公式(1)所示為計算第x條路徑長度的公式，dis(g)代表了相鄰兩點間之間的距離，Cn(i)代表了第i個點

(1)

當初始回路途徑點的位置發生改變時，會得到新的回路集合，將其稱之為鄰接區。利用SP方法的變異計算單元能夠增加解范圍的多樣性。為了能夠對鄰接區結構進行改善，擴展部分查找的范圍，本文采用多種方法構造初始回路的鄰接區，包括對變異計算單元進行逆序、交換、移位等。一次優化指的是當初始回路運動到其鄰接區中的最優回路，而下一次迭代的初始回路就是本次所最終采納的優化。通過對計算單元的選擇能夠向著最有可能的查找范圍進行探測，本文利用了精英選擇法，以提高回避查找的速度，即在鄰接區中確定最優的10個回路，將其作為候選解集，來進行回避查找。

1.2 物流配送路徑優化過程

圖1為本文OWLDP方法的詳細實現過程。

圖1 OWLDP時空模式具體過程

由于最優回避對象可能在查找過程中被刪除，故此，候選解集是不會處于完全回避之中的。如果候選解集屬于空集，則會在上一次初始解附近范圍內進行查找，本文方法具有O(n2)的時間復雜度。

1.3 物流配送路徑優化建模

物流公司將商品送到合肥市二環內的客戶地點。所有這些交付都是從配送中心開始的。運輸問題是如何將不同的顧客分成不同的運輸路線，這樣就減少了運輸車的數量，減少了總行程。此外，客戶配對或路徑選擇應遵守以下限制：

● 運輸車的容量為136個單位的商品；

● 司機每天工作時間不超過11小時；

● 每輛卡車在3個以上的位置不停車；

● 一些客戶必須是路線上的第一站；

● 有些客戶不能與其他客戶配對，因此需要一輛運輸車單獨為他們服務；

● 所有客戶的實際交貨期必須在客戶確定的最早和最新的交貨期之間。

本文將倉庫物流配送路徑優化問題建模成混合整數規劃，如下所示：

(2)

(3)

(4)

(5)

(6)

(7)

(8)

式(2)是路徑優化問題的目標函數，目標是最小化的物流配送總成本。plm是指從點l到點m的運輸成本。當運輸車n使用經過節點l和節點m時，ilmn=1；否則ilmn=0。變量tlm是運輸車從節點l到節點m的時間。um是運輸車在節點m卸貨的時間。約束條件(3)確保了每次只有一輛運輸車進入或者離開中間節點。約束條件(4)是流守恒條件。約束條件(5)限制了每輛運輸車僅能被使用一次。約束(6)限制了每輛運輸車最大停經的站點數量，max_s是最大的停經站點數。約束(7)保證了每輛車的商品不超過車的最大容量，max_c是運輸車的最大容量。約束(8)限制了運輸車司機的工作時間，其中，max_T是最大的工作時間。

2 試驗與討論

2.1 試驗環境

本文在SuperMap二次開發平臺上驗證了OWLDP時空模式，而且結合合肥市二環內的路徑測試了本文所提出的方法，在路徑中共有2764個路段，結點共有1769個。在本次實驗中，從配送路徑中通過隨機抽取的方式確定了三組結點，確定的數據規模分別為5、10、20，并將計算結果與回避查找、時空模式和MapInfo軟件的結果進行對比。測試環境如表1所示。

表1 測試環境

2.2 實驗結果

根據現有方法的參數設置經驗，各參數取值如表2所示，N為結點個數。

表2 方法的參數設置

基于SAM的方法具有較低的平均及時性，因此本文實驗將該方法具有的計算及時性作為基準，對本文方法的收斂效果進行分析。圖2是方法具有的及時性以及其耗費時間之間的關系。分析實驗結果能夠得出，如果能夠將及時性增長率保持在[-10%，0]范圍中，與SP相比，OWLDP將會具有更高的平均收斂速度；當設定的及時性不斷提高時，OWLDP在效率方面的優勢是不斷突出的，而如果得到的解的質量要好于參考值，則每將及時性提高1%，需要耗費的時間將會呈現出指數級增長的趨勢，然而，即便如此，OWLDP仍舊具有十分突出的運行效率優勢。

圖2 OWLDP方法及時性——耗時曲線

如果將及時性誤差保持在1%以內，則與SAM和SP方法相比，OWLDP方法不管在運行效率，還是在準時性等方面都是具有更好的性能的，而且與MapInfo的水平是一致的。如圖3表示了OWLDP方法對數據進行計算的最終結果。

故此，考慮將本文提出的時空模式實施優化處理，進而實現對物流配送路徑的高效利用，以推動方法運行效率的有效提高。相較于傳統方法，本文的主要優點在于，具有較好的實時性，而且具有較高的準確性。

圖3 約束方法針對不同結點數求解OWLDP的結果

3 結論

本文設計了一種求解倉庫物流配送路徑優化問題的時空模式。方法采用時空模式增強優化路徑的效率。相較于簡單的單純的回避查找和SP方法而言，如果具有相同的求解及時性，那么通過本文方法能夠得到更好的運行效率，具有更強的魯棒性，更好的準時性。假定將解的及時性損失設定在1%以內在，則通過本文方法能夠得到與MapInfo方法相當的運行效率。而且，由于時空模式是具有并行特性的，因此在本文方法中也是可以實現物流配送路徑的并行化。