重複運輸

重複運輸

重複運輸是指一種貨物本可以直達目的地,但由於某種原因而在中途停卸重複裝運的不合理運輸現象。簡言之就是,本來可以直接將貨物運到目的地,但是在未達目的地之處,或目的地之外的其它場所將貨卸下,再重複裝運送達目的地,這是重複運輸的一種形式。另一種形式是,同品種貨物在同一地點一面運進,同時又向外運出。重複運輸的最大毛病是增加了非必要的中間環節,這就延緩了流通速度,增加了費用,增大了貨損。

路徑優化


物流作為第三利潤源泉, 已經越來越引起人們的重視。降低物流成本成為人們考慮物流的一個重要方面,而在物流成本中運輸成本佔據著很大的比重。物流產業一直缺乏現代運輸及物流配送的路徑優化系統, 車輛在進行運輸配送集貨的時候,不得不行駛更多的路, 需要更多的車輛, 這就導致了貨運的空載率過高及空載行駛里程過大, 極大地浪費了物流資源,帶來了很大的物流運輸成本。
路徑優化問題是指行駛盡量少的路程來完成所有的任務。通過載重量一定的車輛對每一個結點完成集貨或配送等任務, 其中每一個結點都有一定量貨物的供給或需求任務。它要求不能超出車輛的載重限制,同時盡量使車輛行駛距離最短。國內外對路徑優化的研究主要集中在啟髮式演演算法, 遺傳演演算法、模擬退火演演算法、禁忌搜索演演算法和蟻群演演算法幾個方面。傳統的啟髮式演演算法多把重點放在路程的節約上面, 因此有眾多的學者對它提出了改進。如首先對車輛進行初始的估計, 將車輛出車費用和行駛費用共同考慮在一起, 而不是把節約路程作為唯一的指標, 以及以車輛載重約束分組, 然後在組內進行路線的設計。節約啟髮式演演算法還被應用於集送一體化問題。新的智能演演算法也被廣
泛應用於VRP問題,如用遺傳演演算法解決不確定車輛數的車輛路徑問題, 用混合遺傳演演算法來解決物流配送路徑的優化問題。另外, 基於模糊可能性的混合遺傳演演算法,研究了決策者的主觀嗜好對決策目標的影響。改變編碼的方式, 用隱含編碼方式進行計算以及雙種群遺傳演演算法也用來解決這一問題。各類蟻群演演算法也被廣泛應用於這一問題。為提高搜索效率, 提出了幾種結合演演算法, 如將粒子群優化演演算法與模擬退火演演算法結合,以及運用多初始解和全局禁忌表等各種措施來減小解的不穩定性和擴大搜索範圍。
目前國內外大部分的研究將注意力放在不可重複運輸上,即每項任務只能有某一輛車來完成, 這樣雖然降低了研究的複雜度,但同時也可能會造成需要更多的車輛來完成運輸配送的任務。由於出動一輛車的固定成本遠遠大於車輛的一定里程內的行駛成本,對於一個具體的問題,尋求能完成任務的最少車輛數是減少成本的有效方法。實際上有的時候一個任務點在被兩個車輛服務時,不但會減少車輛的使用數目,並且可能還會使總路程減少,進而降低總的運輸費用。因此,尋求在最少車輛的情況下,來降低行車距離就是本文將要研究的內容。

問題假設


假設有一個物流集貨中心,編號為0, 擁有多台載重量為q的車輛。現在有m項貨物運輸任務需要完成, 以1, 2, …, i, …, m表示,已知任務i的貨運量為gi(i=1, 2, …, m),且gi
(1)所有任務都是事先安排的, 調度問題是靜態的。
(2)每輛車在執行任務完畢后必須再回到原來所在位置,即再回到集貨中心。
(3)成本分為運輸成本(與路徑有關)和出車成本(與出車數量有關)。
(4)車輛的運營費用權數大於運輸成本的權數。啟髮式演演算法是一種簡單的、易實現的演演算法,它主要是從節約演演算法(Clarke-Wright演演算法)出發而得到的一種演演算法。由於VRP問題是NP問題,精確求解非常困難,啟髮式演演算法具有快速求解NP難題、對初值要求不嚴格等優點,便於計算機系統的實現。因此,研究啟髮式演演算法不失為一種可行的方向。本文將在節約演演算法的基礎上解決可重複運輸的路徑優化問題,通過合理的演演算法,以總成本最低為目標來實現。以cij表示車輛從點i行駛到點j的距離,得到點i和點j連接在一條線路上的費用節約值sij=c0i+c0j-cij。把cij排列成序,在安排路線時,盡量首先安排節約值大的,這樣使總路程最少。若超出車輛的行駛里程或者超出車輛的載重限制,則結束這條路線,重新進行選擇。在傳統節約演演算法搜索合併中,每次都是取M內的第一項sij, 即節約值最大的那個, 考察它們的貨程中的局部最優性,沒有考慮到整體最優性。為降低這種局部最優性, 我們在實施車輛合併后, 考察其車輛的剩餘載重量與總任務的、尚不滿足一輛車的貨物量, 根據大小, 確定是否進行下一步的貨物收集任務來進一步完善路徑,降低空載率。

結論


本文以節約式演演算法為基礎, 構造了路徑優化的可重複運輸數學模型, 並給出了有效解決這一問題的方法,實現了降低運輸總成本的目的, 具有很強的現實意義。最後通過算例證明了該做法是可行性, 結果也比以前的解決辦法需要更低的成本。在實際應用中, 如何在實現路徑優化的同時, 解決企業運輸的時效性, 即時間窗問題, 是路徑優化問題研究的難點,也是必須要解決的問題。特別是在允許等待和延遲的情況下, 如何建立一套模糊規則來衡量上述懲罰或損失來解決模糊時間窗問題是今後研究的一個方向。
  • 目錄