基于時空模式的倉庫物流配送路徑優(yōu)化

徐少堃

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

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

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

1 倉庫物流配送路徑優(yōu)化方法

1.1 倉庫物流配送方法選擇

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

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

OWLDP的主要核心元素如下。

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

(1)

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

1.2 物流配送路徑優(yōu)化過程

圖1為本文OWLDP方法的詳細實現(xiàn)過程。

圖1 OWLDP時空模式具體過程

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

1.3 物流配送路徑優(yōu)化建模

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

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

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

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

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

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

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

本文將倉庫物流配送路徑優(yōu)化問題建模成混合整數(shù)規(guī)劃，如下所示：

(2)

(3)

(4)

(5)

(6)

(7)

(8)

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

2 試驗與討論

2.1 試驗環(huán)境

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

表1 測試環(huán)境

2.2 實驗結(jié)果

根據(jù)現(xiàn)有方法的參數(shù)設(shè)置經(jīng)驗，各參數(shù)取值如表2所示，N為結(jié)點個數(shù)。

表2 方法的參數(shù)設(shè)置

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

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

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

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

圖3 約束方法針對不同結(jié)點數(shù)求解OWLDP的結(jié)果

3 結(jié)論

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