多車型同時取送貨問題的低碳路徑研究

趙燕偉,李　文,張景玲,任設(shè)東

(浙江工業(yè)大學(xué) 特種裝備制造與先進加工技術(shù)教育部重點實驗室，浙江 杭州 310014)

多車型同時取送貨問題的低碳路徑研究

趙燕偉,李文,張景玲,任設(shè)東

(浙江工業(yè)大學(xué) 特種裝備制造與先進加工技術(shù)教育部重點實驗室，浙江 杭州 310014)

摘要：針對現(xiàn)代物流配送系統(tǒng)中提倡節(jié)能減排、配送中心多車型、車輛數(shù)量有限以及客戶存在取送貨需求的特點，建立了多車型同時取送貨的低碳路徑問題的模型，同時建立了考慮車輛裝載量、車型和距離的碳排放量的計算方法.基于問題的性質(zhì)，采用了量子進化算法對其進行求解，量子進化算法是一種通過將常用的整數(shù)編碼轉(zhuǎn)換成量子比特位的編碼方式，每一個染色體都代表某種車型的行車路線方案，通過基準測試實例驗證了算法的有效性和可行性，實驗分析表明，針對多車型同時取送貨問題，以總碳排放最小為目標函數(shù)，采用隨機選取車輛路徑安排比傳統(tǒng)的車輛路徑安排更加經(jīng)濟和環(huán)保.

關(guān)鍵詞：物流；車輛路徑；多車型；同時取送貨；量子進化算法；碳排放

中圖分類號：F224

文獻標志碼：A

文章編號：1006-4303(2015)01-0018-06

Low carbon for a multi-vehicle routing problem with

simultaneous pickups and deliveries

ZHAO Yanwei, LI Wen, ZHANG Jingling, RENG Shedong

(Key Laboratory of Special Purpose Equipment and Advanced Manufacturing Technology, Ministry of

Education, Zhejiang University of Technology, Hangzhou 310014, China)

Abstract:Aiming at the promotion of energy-saving for logistics, vehicles’ diversification and the customer has take and delivery requirements in the vehicle routing problem, a model that low carbon for a multi-vehicle routing problem with simultaneous pickups and deliveries was established, which put forwards the calculation of considering the loading capacity, the models and the distance for carbon emissions. Base on the nature of the problem, using the quantum evolutionary algorithm to solve it, an encoding method of converting Q-bit representation to integer representation was designed, every chromosome represented a kind of route, Some examples were tested to verify the feasibility and effectiveness of the algorithm, for the above-mentioned problems, low carbon vehicle arrangement was more economic and environmental than traditional vehicle touting arrangement.

Keywords:logistics； vehicle routing； multi-vehicle； simultaneous pickups and deliveries； quantum evolutionary algorithm； low carbon

隨著現(xiàn)代社會的高速發(fā)展，全球環(huán)境問題逐漸受到人們的關(guān)注，溫室氣體的不斷排放也越來越被世人所擔憂，當今物流社會，物流運輸產(chǎn)生大量的CO2排放，約占全社會排放量的30%，針對現(xiàn)在氣候環(huán)境的不斷改變，物流運輸業(yè)需要改變其發(fā)展的方式，提倡和實施“綠色運輸”已成為物流運輸活動中重要的發(fā)展趨勢.

車輛路徑問題(VRP)是Dantzig與Ramser在1959年提出的，后面的學(xué)者進行了許多的研究，出現(xiàn)了很多重要的研究成果，研究方向主要是在單車型單需求VRP[1]方面，然而，在實際的配送中，車輛擁有多種車型，且每種車型的裝載能力，單位旅行費用以及發(fā)車成本等都是各不相同的，考慮配送總資金的約束，配送中心每種車型的數(shù)量也是有限制的，客戶一般可以只具有取貨需求或送貨需求，也可以同時具有兩種需求，因此，研究多車型同時取送貨VRP問題更加接近實際的配送管理.在已有的文獻中，姚錦寶[2]在同時取送貨車輛路徑問題中用了改進的蟻群算法，建立了一個基于不確定的二級供應(yīng)鏈的模糊規(guī)劃模型；賈芳芳[3]對該問題用了改進的粒子群算法，采用慣性權(quán)重更新和路徑鏈接更新來擴大粒子的搜索空間，對模型的收斂速度有了明顯提升；劉晴[4]針對具有隨機需求的同時取送貨車輛路徑問題進行了研究；馬宇紅[5]利用遺傳算法研究了大規(guī)模的多配送中心多車型車輛調(diào)度問題；這些文獻分別對同時取送貨車輛路徑問題和多車型車輛路徑問題進行了研究，但卻沒有將兩者進行結(jié)合，且目標大多只關(guān)心經(jīng)濟效益，沒有考察CO2排放對環(huán)境造成的污染，傳統(tǒng)VRP問題在車輛路徑安排時只考慮經(jīng)濟成本[7]，而擴展傳統(tǒng)VRP問題的目標就是在車輛路徑安排時加入對環(huán)境影響的考慮，以有效的減少VRP問題中碳的排放量，楊培穎[13]從碳排放的角度建立了針對接送機場服務(wù)中心以車輛最新碳排放量為目標的非線性0-1混合整數(shù)規(guī)劃模型；王鈺青[14]建立了基于最小碳排放的廣義TSP模型；邱雅君[15]通過改進的遺傳算法求解了考慮碳排放因素的車輛路徑問題.對多車型同時取送貨問題的低碳研究，碳排放量與燃油消耗成正比例關(guān)系[12]，碳排放量的計算將考慮車型、距離、載重量等多個因素的影響；在模型算法方面，考慮到多車型與同時取送貨相結(jié)合的問題建模困難，采用高效率高尋優(yōu)的量子進化算法來進行求解運算.

1多車型同時取送貨低碳路徑問題的描述及數(shù)學(xué)規(guī)劃模型

1.1問題描述

多車型同時取送貨的低碳路徑問題的描述為：配送中心擁有不同類型的車型，每種車型的數(shù)量有限制，配送中心分配車輛給客戶服務(wù)，客戶具有取貨需求和送貨需求，每輛車完成任務(wù)后返回配送中心且不再配送貨物；目標是在滿足客戶取送貨需求的條件下安排車輛路徑使得碳排放量最小.約束為：只有一個配送中心，車輛配送結(jié)束后立即返回配送中心且不再配送服務(wù)；每個客戶必須被訪問且只能被訪問一次；配送線路上貨車的裝載量至少能同時滿足任意一個客戶的兩種需求，每種車型的車輛數(shù)固定，且具有不同的載重量和燃油消耗參數(shù)[8](與計算碳排放量有關(guān)).

1.2模型的建立

1.2.1碳排量的計算

根據(jù)不同的精度要求和所采集的數(shù)據(jù)種類，二氧化碳排放量的計算可以選取不同的計算方法.文獻[8]有

F=GD(aL+b)

(1)

其中：F為貨物運輸過程中的燃油消耗；G為地形坡度因子；D為車輛行駛距離；L為車輛載重；a，b分別為燃油消耗參數(shù)(該參數(shù)隨車型的變化而變化).

計算出車輛的燃油消耗，需要將其轉(zhuǎn)化為直接碳排放量，同樣根據(jù)文獻[8]，有

W=Fη

(2)

其中：W為直接碳排放量；η為燃油轉(zhuǎn)換系數(shù).

根據(jù)上述方法計算車輛的二氧化碳排放量，從式(1,2)中可以看出：碳排放量和燃油消耗量成正比例關(guān)系；燃油消耗和車輛行駛距離成正比例關(guān)系；與載重量成正線性相關(guān)，同時為了驗證模型有效性，取地形坡度因子G為單位1，根據(jù)實際問題可以得出

(3)

1.2.2數(shù)學(xué)模型

多車型同時取送貨低碳路徑問題的數(shù)學(xué)模型如下：

(4)

s.tpij+qij≤Qmxijk,?i,j,m,k

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

p0j=0,?j∈V{0}

(13)

qi0=0,?i∈V{0}

(14)

(15)

(16)

(17)

pij≥pixijk,?i∈V{0},?j∈V,?k

(18)

qij≥djxijk,?i∈V,?j∈V{0},?k

(19)

xijk=0或1,?i,j,k,yik=0或1,?i,k

(20)

其中：S=(V,E)為配送網(wǎng)絡(luò)，V為節(jié)點集，V={0,1,…,n}，其中0表示配送中心，其余節(jié)點表示客戶；E為邊集，E={(i,j)|i,j∈V,i≠j}；m為車型，編號為1，2，…，M；k為車輛，編號為1，2，…，K；Qm為m類型車的容量，m∈{1,2,…,M}；pi為客戶i的取貨需求；dj為客戶j的送貨需求；nm為m類型車輛數(shù)限制；

k∈{1,2,…,K},i∈V,j∈V；

式(4)表示目標函數(shù)，為車輛的總碳排放量最小；式(5)表示車的載重不大于它的載重能力；式(6)表示每個客戶都會被服務(wù)到；式(7，8)表示客戶有且僅被一輛車服務(wù)；式(9)表示離開配送中心的車輛和返回配送中心的車輛數(shù)量是一致的；式(10)表示兩個客戶服務(wù)時線路數(shù)不能超過1；式(11)表示客戶的送貨需求被滿足；式(12)表示客戶的取貨需求被滿足，這兩個約束同時保證了客戶的取送貨需求被滿足；式(13)表示剛從配送中心出發(fā)的車不會取貨；式(14)保證返回配送中心的車輛不再服務(wù)；式(15)保證返回配送中心的所有車輛取貨總和等于所有客戶的取貨需求總和；式(16)表示總車輛數(shù)約束；式(17)保證所有從配送中心出發(fā)車輛裝載的貨物總和等于所有客戶的送貨需求總和；式(18)保證離開客戶后車輛的取貨不能小于該客戶的取貨需求；式(19)表示到達任一客戶的車輛裝載的將要派送的貨物不能小于該客戶的送貨需求；式(20)表示變量的取值范圍.

2多車型同時取送貨低碳路徑問題的算法設(shè)計

2.1量子進化算法的求解過程

針對第1章建立的多車型同時取送貨低碳路徑問題的數(shù)學(xué)規(guī)模模型，我們采用量子進化算法進行求解的策略如圖1所示.

圖1　多車型同時取送貨低碳路徑問題求解策略Fig.1　The solving strategies of the low carbon for a multi-vehicle routing problem with simultaneous pickups and deliveries

采用量子進化算法對該問題就行求解，充分利用了量子進化算法的全局尋優(yōu)能力強和收斂速度快的特點，使問題可以找到比較滿意的解.

2.2量子進化算法

量子染色體是量子進化算法獨有的概念，采用量子比特進行編碼.每個量子比特位存在|0>和|1>兩個本征態(tài)，該量子比特位可以處于|0>和|1>兩個本征態(tài)的任意疊加狀態(tài)，一個包含m×n維矩陣的量子染色體可以表示為

(20)

其中：qij為量子比特，滿足|qij>=αij|0>+βij|1>,|αij|2+|βij|2=1，|αij|2和|βij|2分別表示量子位處于|0>的概率和量子位處于的|1>概率.一個包含m×n維矩陣的量子染色體可以表示2mn個狀態(tài)的疊加，這樣就使得量子進化算法具有非常廣泛的搜索空間.

量子進化算法的求解流程如圖2所示.

圖2　量子進化算法流程圖Fig.2　Quantum algorithm flow chart

算法具體的求解過程如下：

1) 初始化量子比特種群

隨機產(chǎn)生包含多個量子染色體的種群，針對客戶數(shù)量為L的問題，對于每個量子染色體，可以采用L×L×2的三維量子比特矩陣來表示，隨機初始化量子比特位，由計算機隨機0，1之間的隨機數(shù)，然后賦值給對應(yīng)的αij和βij.

2) 對量子比特種群解碼

解碼過程先生成客戶序列，然后再進行車輛分配.

產(chǎn)生客戶服務(wù)序列：首先產(chǎn)生[0,1]之間的隨機數(shù)，產(chǎn)生L×L的二維0～1觀測矩陣，并調(diào)整矩陣保證每行每列都只有1個1,1所在的橫坐標代表服務(wù)的順序，縱坐標代表所對應(yīng)的的客戶.例如對于配送客戶數(shù)L=6的問題，經(jīng)過量子塌陷得到二進制染色體P=[001000100000000010010000000001

000100]，然后對其進行分段，每段長度為L，然后根據(jù)對于橫坐標所在的1確定客戶服務(wù)順序，即初始化客戶服務(wù)序列為3→1→5→2→6→4.

車輛的分配：我們采用貪心算法形成路徑，首先隨機選用一種車型的車輛，當該車輛無法滿足下一個客戶需求時，我們再隨機選用一種車型的車輛(每次選取車輛時是獨立的，前后選取車輛的車型可能相同也可能不同)，當該種車型的車輛數(shù)超過已有車輛數(shù)時，我們重復(fù)選取車型的步驟，直到所選車型沒有超過該種車型的車輛數(shù)為止.例如對于上面的客戶服務(wù)序列，假設(shè)有3種類型的車型，每種車型的載重和數(shù)量各不相同，當開始隨機選用車型1的車輛配送客戶3和客戶1后無法再配送5，這是需再隨機選用某種車型進行配送，可能還是車型1或者其他車型，假設(shè)當某次隨機選取到車型2的車輛配送客戶5時發(fā)現(xiàn)車型2的車輛全部配送完，這是我們需要隨機選取其他沒配送完的車型來配送.

3) 適應(yīng)度計算

對種群的各個染色體解碼后，分別根據(jù)式(4)求得目標函數(shù)值Z；令染色體的適應(yīng)度函數(shù)為ffitness=Z，由此可見：適應(yīng)度函數(shù)越小，車輛配送的方案越有助于減少碳排放.

4) 量子旋轉(zhuǎn)門更新

量子進化算法也有“進化”的概念，而最為常用的“進化”機構(gòu)就是量子旋轉(zhuǎn)門，進化過程由量子旋轉(zhuǎn)門更新量子位概率幅來實現(xiàn)，具體參考文獻[16].

3實驗結(jié)果及分析

3.1實例測試

算法程序是java語言編寫的，在Penti-umDCPU2.0GHz，2.0GB的內(nèi)存上運行.用上述提到的算法來求解我們建立的模型，該物流系統(tǒng)只擁有1個配送中心，3種不同的車型，每種車型的載重量分別是150，120，100t，初始的客戶總數(shù)為39個，0為配送中心，1~39為客戶點，各客戶點的坐標和取送貨需求如表1所示.

表1　初始客戶點信息

對上述數(shù)據(jù)用算法進行求解，車輛隨機分配時得出最優(yōu)的車輛路徑分配方式如表2所示.

表2　各車型的路徑分配方式

模型算法的目標函數(shù)收斂圖如圖3所示.

圖3中分別包括車輛隨機選用、優(yōu)先選用碳排放系數(shù)低的車輛和優(yōu)先選用碳排放系數(shù)高的車輛的目標函數(shù)收斂圖.由此可以看出：當我們以碳排放最低為目標函數(shù)時，且車型以不同的方式分配，通過量子進化算法對模型進行求解，得出當車輛被隨機選用時最低碳排放量排放大約為195 t左右，當優(yōu)先選擇碳排放量低的車型時，得出的最低碳排放量也是大約190 t左右，和隨機選用車型時最低碳排放量相差不大.優(yōu)先選用碳排放系數(shù)高的車輛時最低碳排放量比優(yōu)先選擇碳排放系數(shù)低的車輛或者隨機選取車型時都要高，而碳排放系數(shù)高的車型載重量大，碳排放量低的車型所需要的車輛更多，發(fā)車成本會相應(yīng)增加，而用隨機選取車型時加適合，在成本和減排方面都可以做到比較滿意.

圖3　車輛不同方式選用時目標函數(shù)收斂圖Fig.3　The objective function convergence when vehicle is different chosen

上述采用的模型目標函數(shù)都是使碳排放量最小，為了對實驗結(jié)果有一個全面的了解，我們對總碳排放量最小為目標函數(shù)與車輛配送總路徑最小為目標函數(shù)下的試驗結(jié)果進行對比，兩種方式下都采用隨機分配車輛模型，兩種不同目標函數(shù)下的車輛總路徑和碳排放量的實驗結(jié)果如圖4，5所示.

圖4　總碳排放量最小時的總路徑曲線和總碳排放量曲線Fig.4　The total routing curve and Carbon emissions curve for the minimum carbon emission

圖5　總配送最小時的總路徑曲線和總碳排放量曲線Fig.5　The total routing curve and Carbon emissions curve for the minimum routing

由圖6，7比較可以看出：以總碳排放量最小為目標函數(shù)時的碳排放量為195 t左右，其對應(yīng)的總路徑為900 km，而以總路徑為目標函數(shù)時的碳排放量為210 t左右，其對應(yīng)的總路徑為890 km左右，由數(shù)據(jù)對比，選擇減少碳排放對總路徑的增加影響不大，但是碳排放的減少卻有很有效果，將近減10%的碳排放，所以以節(jié)能減排作為目標，對車輛配送調(diào)度有很重大的意義.

4結(jié)論

對于多車型同時取送貨問題，首先對問題進行了描述，然后建立了該問題的模型.并通過量子進化算法對問題進行了求解，同時通過對車型的不同分配方式，比較了優(yōu)先選用碳排放系數(shù)高的車型、碳排放系數(shù)低的車型和隨機選取車型時碳排放總量的變化，最后比較了以總碳排放量最小為目標與總路徑最小為目標時模型中碳排放和總路徑的變化.實驗表明，通過量子進化算法的求解，能夠有效的求解多車型同時取送貨問題，同時，隨機選取車輛有助于減少車輛配送時的碳排放和發(fā)車成本，而且，以碳排放為目標時對總路徑的增加影響不大，而對碳排放的減少有很好的效果.當然，研究還存在很多方面的不足，僅僅以碳排放量最低作為目標函數(shù)，而且也沒有考慮客戶的貨物配送的時間窗要求，在實際的配送系統(tǒng)中，目標函數(shù)中需要考慮經(jīng)濟成本的因素[20]，因為物流企業(yè)的發(fā)展就是要滿足客戶要求的同時使配送的成本最低，同時，客戶對于貨物的取送時間也有一定的要求，但是，低碳作為研究的目標對于物流企業(yè)配送降低碳排放提供了一定的參考意義，也可為相關(guān)政府部分節(jié)能減排政策提供一些有價值的借鑒.

參考文獻：

[1]張思亮.基于改進粒子群算法的車輛路徑問題研究[D].江南大學(xué):江南大學(xué),2011.

[2]姚錦寶,夏禾,賀興東,等.同時取送貨車輛路徑問題的改進的蟻群算法[J].物流技術(shù),2010(Z1):154-156.

[3]賈方方,孔德成.同時取送貨車輛路徑問題的改進粒子群優(yōu)化算法[J].物流技術(shù),2012(19):137-139.

[4]劉晴.隨機需求同時取送貨車輛路徑問題建模及優(yōu)化研究[D].南京航空航天大學(xué):南京航空航天大學(xué),2013.

[5]馬宇紅,姚婷婷,張浩慶.基于分區(qū)的多配送中心多車型車輛調(diào)度問題與遺傳算法設(shè)計[J].科技導(dǎo)報,2013(2):534-535.

[6]鐘石泉,賀國光.多車場有時間窗的多車型車輛調(diào)度及其禁忌算法研究[J].運籌學(xué)學(xué)報,2005(4):38-41.

[7]李進,傅培華.具有固定車輛數(shù)的多車型低碳路徑問題及算法[J].計算機集成制造系統(tǒng),2013(6):245-248.

[8]史春陽,趙磊.同時取送貨的車輛路徑問題中的低碳研究[J].計算機集成制造系統(tǒng),2011(5):122-126.

[9]關(guān)麗霞.帶軟時間窗和同時取送貨的車輛路徑問題研究[D].中南大學(xué):中南大學(xué),2012.

[10]葉志堅,葉懷珍,周道平,等.多車型車輛路徑問題的算法[J].公路交通科技,2005(5):89-91.

[11]經(jīng)懷明,張立軍.多車型車輛調(diào)度問題的建模與仿真[J].計算機仿真,2006(4):445-447.

[12]KIRBY H R, HUTTON B, MCQUAID R W, et al. Modeling the effects of transport policy levers on fuel efficiency and national fuel consumption[J]. Transport and Environment,2000(6):265-282.

[13]楊培穎,唐加福,于洋,等.面向最小碳排放量的接送機場服務(wù)的車輛路徑與調(diào)度[J].自動化學(xué)報,2013(4):367-369.

[14]王鈺青,許茂增.基于最小碳排放的廣義TSP模型研究[J].數(shù)學(xué)的實踐與認識,2012(8):56-58.

[15]邱雅君,宋國防.考慮碳排放因素的車輛路徑問題研究[J].物流技術(shù),2012(13):222-226.

[16]趙燕偉,彭典軍.有能力約束車輛路徑問題的量子進化算法[J].計算機集成制造系統(tǒng),2008(8):124-128.

[17]李川.基于混合量子進化算法的隨機車輛路徑問題的研究[D].杭州:浙江工業(yè)大學(xué),2012.

[18]秦本濤.基于遺傳算法的車輛調(diào)度系統(tǒng)設(shè)計[D].杭州:浙江工業(yè)大學(xué),2011.

[19]吳斌.車輛路徑問題的粒子群算法研究與應(yīng)用[D].杭州:浙江工業(yè)大學(xué),2008.

[20]陳曉瞇.基于混合禁忌搜索算法的動態(tài)車輛路徑研究[J].浙江工業(yè)大學(xué)學(xué)報，2009，37(5)：24-28.

(責任編輯：劉巖)

作者簡介：趙燕偉(1962—)，女，河南鄭州人，教授，主要從事數(shù)字化產(chǎn)品現(xiàn)代設(shè)計理論與方法、數(shù)字制造/數(shù)字裝備建模與仿真的基礎(chǔ)理論等，E-mail：zyw@zjut.edu.cn.

基金項目：國家自然科學(xué)基金資助項目(61402409)；Foudation items：Project supported by the National Natural Science Foundation，China(61402409)

收稿日期：2014-09-18