多車物流協(xié)同運(yùn)輸調(diào)度研究

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

關(guān)鍵詞：多車物流協(xié)同運(yùn)輸;聚類;調(diào)度研究

一、多車物流協(xié)同運(yùn)輸調(diào)度的內(nèi)涵

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

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

二、基于聚類的遺傳算法設(shè)計(jì)

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

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

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

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

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

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

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

參考文獻(xiàn)：

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

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