路徑最佳化
物流作為第三利潤源泉, 已經越來越引起人們的重視。降低物流成本成為人們考慮物流的一個重要方面,而在物流成本中運輸成本占據著很大的比重。物流產業一直缺乏現代運輸及物流配送的路徑最佳化系統, 車輛在進行運輸配送集貨的時候,不得不行駛更多的路, 需要更多的車輛, 這就導致了貨運的空載率過高及空載行駛里程過大, 極大地浪費了物流資源,帶來了很大的物流運輸成本。
路徑最佳化問題是指行駛儘量少的路程來完成所有的任務。通過載重量一定的車輛對每一個結點完成集貨或配送等任務, 其中每一個結點都有一定量貨物的供給或需求任務。它要求不能超出車輛的載重限制,同時儘量使車輛行駛距離最短。國內外對路徑最佳化的研究主要集中在啟發式算法, 遺傳算法、模擬退火算法、禁忌搜尋算法和蟻群算法幾個方面。傳統的啟發式算法多把重點放在路程的節約上面, 因此有眾多的學者對它提出了改進。如首先對車輛進行初始的估計, 將車輛出車費用和行駛費用共同考慮在一起, 而不是把節約路程作為唯一的指標, 以及以車輛載重約束分組, 然後在組內進行路線的設計。節約啟發式算法還被套用於集送一體化問題。新的智慧型算法也被廣
泛套用於VRP問題,如用遺傳算法解決不確定車輛數的車輛路徑問題, 用混合遺傳算法來解決物流配送路徑的最佳化問題。另外, 基於模糊可能性的混合遺傳算法,研究了決策者的主觀嗜好對決策目標的影響。改變編碼的方式, 用隱含編碼方式進行計算以及雙種群遺傳算法也用來解決這一問題。各類蟻群算法也被廣泛套用於這一問題。為提高搜尋效率, 提出了幾種結合算法, 如將粒子群最佳化算法與模擬退火算法結合,以及運用多初始解和全局禁忌表等各種措施來減小解的不穩定性和擴大搜尋範圍。
目前國內外大部分的研究將注意力放在不可重複運輸上,即每項任務只能有某一輛車來完成, 這樣雖然降低了研究的複雜度,但同時也可能會造成需要更多的車輛來完成運輸配送的任務。由於出動一輛車的固定成本遠遠大於車輛的一定里程內的行駛成本,對於一個具體的問題,尋求能完成任務的最少車輛數是減少成本的有效方法。實際上有的時候一個任務點在被兩個車輛服務時,不但會減少車輛的使用數目,並且可能還會使總路程減少,進而降低總的運輸費用。因此,尋求在最少車輛的情況下,來降低行車距離就是本文將要研究的內容。
問題假設
假設有一個物流集貨中心,編號為0, 擁有多台載重量為q的車輛。現在有m項貨物運輸任務需要完成, 以1, 2, …, i, …, m表示,已知任務i的貨運量為gi(i=1, 2, …, m),且gi<q, gi要遠小於q(多批次, 小批量)。各任務點之間的距離為cij, 考慮到司機的最大工作時間以及車輛的最遠行駛距離, 我們將設定一個合理的最大路程來對該問題進行限制。另外給定以下假設:
(1)所有任務都是事先安排的, 調度問題是靜態的。
(2)每輛車在執行任務完畢後必須再回到原來所在位置,即再回到集貨中心。
(3)成本分為運輸成本(與路徑有關)和出車成本(與出車數量有關)。
(4)車輛的運營費用權數大於運輸成本的權數。啟發式算法是一種簡單的、易實現的算法,它主要是從節約算法(Clarke-Wright算法)出發而得到的一種算法。由於VRP問題是NP問題,精確求解非常困難,啟發式算法具有快速求解NP難題、對初值要求不嚴格等優點,便於計算機系統的實現。因此,研究啟發式算法不失為一種可行的方向。本文將在節約算法的基礎上解決可重複運輸的路徑最佳化問題,通過合理的算法,以總成本最低為目標來實現。以cij表示車輛從點i行駛到點j的距離,得到點i和點j連線在一條線路上的費用節約值sij=c0i+c0j-cij。把cij排列成序,在安排路線時,儘量首先安排節約值大的,這樣使總路程最少。若超出車輛的行駛里程或者超出車輛的載重限制,則結束這條路線,重新進行選擇。在傳統節約算法搜尋合併中,每次都是取M內的第一項sij, 即節約值最大的那個, 考察它們的貨程中的局部最優性,沒有考慮到整體最優性。為降低這種局部最優性, 我們在實施車輛合併後, 考察其車輛的剩餘載重量與總任務的、尚不滿足一輛車的貨物量, 根據大小, 確定是否進行下一步的貨物收集任務來進一步完善路徑,降低空載率。
結論
本文以節約式算法為基礎, 構造了路徑最佳化的可重複運輸數學模型, 並給出了有效解決這一問題的方法,實現了降低運輸總成本的目的, 具有很強的現實意義。最後通過算例證明了該做法是可行性, 結果也比以前的解決辦法需要更低的成本。在實際套用中, 如何在實現路徑最佳化的同時, 解決企業運輸的時效性, 即時間窗問題, 是路徑最佳化問題研究的難點,也是必須要解決的問題。特別是在允許等待和延遲的情況下, 如何建立一套模糊規則來衡量上述懲罰或損失來解決模糊時間窗問題是今後研究的一個方向。
