多車物流協(xié)同運輸調度研究

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

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

一、多車物流協(xié)同運輸調度的內涵

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

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

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

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

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

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

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

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

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

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

參考文獻：

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

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