多車物流協同運輸調度研究

摘 "要：隨著我國物流業的不斷發展，傳統單一物流配送模式逐漸向多配送中心轉運調撥等方向發展，物流企業也逐漸象多物流企業外包轉運進行協同運輸的運輸方式發展。為了降低空駛率和提高貨車裝載率，如何整合同向運輸任務，解決物流協同運輸中的小批量貨物集配，成了物流系統運輸亟待解決的問題。

關鍵詞：多車物流協同運輸;聚類;調度研究

一、多車物流協同運輸調度的內涵

國內外將物流車輛的行駛線路優化調度問題歸結與VSP或VRP，去是運籌學和組合優化領域中的熱點研究問題。該問題是對多個裝卸貨點，在滿足一定的約束條件情況下，組織合理的行車路線，從而達到一定的目標。車輛調度問題很難得到全局最優解或者滿意解，屬于NP-hard難題。目前，多采用啟發式算法來解決這一問題，但是研究都將關注點集中在了車輛路徑最少，花費時間較少等方面，大多把物流實體和資源看作整體進行研究，雖然從整體物流鏈或者價值鏈的角度上來說，是具有顯著地成效，但是由于對個體物流企業不具備參與物流協同的動機，可能將配送人物直接交給了別人，降低了自己的盈利。

為了使物流企業公同承擔運輸任務，物流協同運輸通過物流企業之間共享的物流信息、資源等，根據車輛出發地的不同、裝運點的不同，安排運輸線路和裝卸階段，從而降低物流運輸成本，達到提高物流資源利用率，使物流企業進行協同運輸且愿意進行協同袁術，提高物流運輸效率和服務水平。

二、基于聚類的遺傳算法設計

（一）聚類生成初始種群。對于運輸車輛的途徑地點來說，集貨點屬于模糊信息，但是有客戶需求卸貨點是肯定的，因此，可用模糊聚類的方法來確定集貨點。首先將運輸車輛初始運輸線路上所有可能途徑的地點作為節點，為建立一個無向帶權圖，節點之間的權重是地點之間的距離。其中，配送中心和運輸車輛途徑的地點，兩個地點之間的距離是連線上的權重，根據車輛協同的情況，車輛途徑地點的集合為U={x1，X2…，xN}。先去具有最多鄰接點的節點組成中心點集，通過地圖提供的距離，由中心點出發，求得其他節點的最短路徑長度dik=MapDistance（xi，xk）.

聚類流程：步驟（1）根據節點間的相似度公式計算中心集各中心點到各階段的相似度;步驟（2）將相似度uikgt;λ的節點歸到由中心點組成的集貨點類中;步驟（3）從沒有歸類的節點中找出具有最大鄰接點的中心點集，重復步驟1、2，直到都被歸入到類中。步驟（4）以各類的中心點作為節點集合，根據目標函數定義公式，重復步驟1到3，采用新的分類，直到類內的對象不再變化，最后沒有歸入類的節點作為孤立點的存在。

其次，如何算染色體的初始種群。本文將配送中心定義為染色體基因段的起點和重點，當只有一個地點時，該基因有最后一個運輸任務地點1構成，其表示在當前，車輛沒有運輸任務。在染色體中，以配件中心為起點的基因為一個染色體段的起始，一個染色體段的結束就是配送任務1，這樣就組成了染色體中的一個基因段，也構成了一個運輸車輛的運輸任務。染色體校驗規則如下：（1） 以最后一個運輸任務點作為結束基因的起點，每個基因段以配件中心作為結束基因的終點。（2）后一個基因段的起點是染色體前一個基因段的終點。（3）前基因運輸任務的某一點是染色體基因段的終點。（4）有兩個基因的起點和終點相同時，染色體基因段中了可以合并兩個基因為一個基因。

并且可以按照以下步驟生成初始種群：（1） 按照重量和體積約束，從配件中心節點出發，將由配送需求地點隨機插入孤立點。（2） 隨機插入地點，如：車輛出發點、配送中心等。（3） 如不滿足重量約束，要增加運輸車輛。（4） 構成遺產算法的初始種群，轉換生成規則。

（二）遺傳算法求最優解。首先評價函數是用來判斷群體中個體的優劣程度指標，根據物流運輸協同后物流企業利潤最大化的原則。其次，交叉和變異。交叉采用插入和交換的方法。插入采用兩個父代的染色體隨機選取的集貨類點進行插入操作。交換從一個父代染色體中隨機選擇集貨點類中的點為起點，選取另一個父代染色體中其他基因段中的和進行交換操作。最后按照變異概率選擇染色體基因中的點作為變異點，在不停響運輸任務的前提下，將該點變換為同類的其他點，變更運輸線路，生成新的染色體。

另外，遺傳算法求解步驟。具體算法流程：（1） 最近鄰啟發式方法構造初始染色體。（2） T=1，c=0計算適應度。（3） 按照交叉變異的概率，選擇并保留適應度最大的兩個染色體，進行交叉與變異，并按照染色體校驗規則，將形成新的染色體修正后形成新的種群。（4） 計算新染色體的使用度可以按照新染色體描述的路線進行任務分解。同時t++。（5） 將檔案適應度最高的染色體作為初始染色體轉到步驟3.（6） 判定個體物流企業較協同利潤增加，直到t大于max（t）。

由此可見，在確定配送任務等約束條件下，減少了物流公司在配送過程中的損害，提高了運輸純利潤，實現了雙贏。

參考文獻：

[1] 孫國華.帶時間窗的開放式滿載車輛路徑問題建模及其求解算法[J].系統工程理論與實踐，2012，32（8）：1801-1807.

[2] 盧冰原，何力，賈兆紅.模糊環境下的多目標非滿載車輛調度問題[J].公路交通科技，2011，28（8）：147-153.