湯雅連 蔡延光 劉宏玉 江澤東

(廣東工業(yè)大學(xué) 自動化學(xué)院,廣州 510006)

貨物不相容車輛路徑問題的優(yōu)化

湯雅連 蔡延光 劉宏玉 江澤東

(廣東工業(yè)大學(xué) 自動化學(xué)院,廣州 510006)

考慮現(xiàn)實生活中每個客戶定制的貨物不可用同一輛車混裝，或者多個客戶的貨物不可混裝的問題，建立了基于車輛載重、行駛里程、多種車型等約束條件的貨物不相容的多車型車輛路徑問題的數(shù)學(xué)模型，應(yīng)用基于精英選擇、混沌變異及模擬退火機制的混合遺傳算法求解。將該算法應(yīng)用到benchmark算例上，并與分支定界算法求解的結(jié)果比較，結(jié)果表明提出的算法優(yōu)于分支定界算法。

貨物不相容的多車型車輛路徑問題；混合遺傳算法；模擬退火機制；3-opt局部搜索；混沌變異；分支定界算法

在貨物配送過程中,會經(jīng)常出現(xiàn)多個客戶需要的貨物不可混裝的情況,比如易腐產(chǎn)品和日用品,危險品和食品等。在合理安排車輛裝載及貨物分配的條件下,研究貨物不相容的多車型車輛運輸調(diào)度問題(heterogeneous vehicle routing problem with incompatible goods,HVRPIG)有一定的研究意義。車輛路徑問題(vehicle routing problem,VRP)是HVRPIG的基礎(chǔ),VRP[1-3]自1959年Dantzig和Ramser首先提出以來就引起了人們的高度重視。VRP的實用性強,應(yīng)用廣泛。車輛路徑問題一般定義為:對一系列送貨點和收貨點,組織適當(dāng)?shù)男熊嚶肪€,使車輛有序地通過它們,在滿足一定的約束條件(如貨物需求量、發(fā)送量、送發(fā)貨時間、車輛容量限制、行駛里程限制、時間限制等)下,達(dá)到一定的目標(biāo)(如路程最短、費用極小、時間盡量少、使用車輛數(shù)盡量少等)。貨物相容和不相容HVRP示意圖如圖1所示。

圖1 貨物相容和不相容HVRP示意圖

在過去的幾十年中,有不少學(xué)者研究了VRP。鄭麗英等人[4]為了保證染色體的多樣性和盡可能地降低問題求解復(fù)雜度,提出了五類遺傳交叉算子,求解單車場多車型VRP問題;楊浩雄等人[5]采用自適應(yīng)多態(tài)蟻群算法求解基于空駛成本、運輸成本和時間成本這三個維度的VRP;王曉博等人[6]為滿足電子商務(wù)客戶多樣化和個性化的需求,建立了多車型的裝卸混合車輛調(diào)度模型,對混合遺傳算法求得的精英種群進(jìn)行禁忌搜索,提高了搜索效率;陶胤強等人[7]考慮了車型與任務(wù)的相容性,建立了帶時間窗約束的多車型多費用非滿載車輛路徑問題數(shù)學(xué)模型,應(yīng)用啟發(fā)式算法求解;陳萍等人[8]基于變鄰域搜索,設(shè)計了變鄰域搜索中的“抖動”以及局部優(yōu)化過程的鄰域結(jié)構(gòu)結(jié)合,提出一種啟發(fā)式算法求解多車型車輛路徑問題。葛顯龍等人[9]采用量子比特位設(shè)計染色體結(jié)構(gòu),改進(jìn)遺傳算法中交叉與變異算子,避免優(yōu)秀基因被破壞,設(shè)計快速尋優(yōu)機制與最優(yōu)保留機制,求解基于車輛使用優(yōu)先原則的多車型車輛路徑問題。陳美軍等人[10]提出了一種自適應(yīng)的最大-最小蟻群算法,算法結(jié)合自適應(yīng)方法和最大-最小蟻群算法的優(yōu)點,適時地控制蟻群算法中的信息素更新過程,擴(kuò)大搜索范圍,避免了基本蟻群算法的早熟現(xiàn)象,并克服了求解速度慢的缺點,基于該改進(jìn)算法求解基于客戶優(yōu)先級、路況影響、多車型、時間窗和容量等多約束條件下的多車場車輛路徑問題。但是對研究HVRPIG的相關(guān)文獻(xiàn)還沒發(fā)現(xiàn),所以研究HVRPIG具有非常重要的意義。

1 建立數(shù)學(xué)模型

1.1 問題描述

HVRPIG是指某車場有多種不同類型的車輛,為多個客戶送貨,每個客戶需要的多種貨物或客戶與客戶需要的貨物不相容,不可用同一輛車配送,組織適當(dāng)?shù)呐渌陀媱澕靶熊嚶肪€,在滿足一定的約束條件下(客戶需求量、車輛載重等),使配送距離最短。不考慮裝卸貨時間。

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

1)優(yōu)化模型符號。

客戶編號:i=1,2,…,l;客戶i的需求量:gi(i=1,2,…,l);車輛類型:h(h=1,2,…,H);貨物類型:n(n=1,2,…,N);每種類型貨物的重量:gn(n=1,2,…,N);車輛載重:qh,gi＜qh,gn＜qh;車輛最大里程約束:Dh;每種類型的車輛數(shù)量:Kh;客戶i與j之間的距離:dij;客戶i與j的平均速度:vij;車輛服務(wù)的客戶數(shù)量:Cnh;中心車場的編號:0;貨物相容系數(shù):Cpq(1≤p,q≤N), Cpq=1,則可以混裝;否則,不可以混裝。

2)定義變量。

3)建立數(shù)學(xué)模型

目標(biāo)函數(shù):

約束條件:

目標(biāo)函數(shù)式(3)表示總距離最短;式(4)表示車場派出的車輛數(shù)不能超過該車場的車輛總數(shù);式(5)表示車輛從所在的車場出發(fā),完成配送任務(wù)后,回到原車場;式(6)和式(7)表示每輛車的載重限制;式(8)為車輛里程約束;式(9)消除了車輛不是從車場出發(fā)的現(xiàn)象;式(10)表示車輛服務(wù)的顧客數(shù)不小于1,則參與配送,否則沒有參與。

2 算法設(shè)計

2.1 產(chǎn)生初始種群及編碼

采用文獻(xiàn)[2]的方法,染色體表示為基因序列(G1,G2,…,Gm),Gi由三部分構(gòu)成,車場編號DepotNum、車輛編號VehicleNum和排序值SortValue,表示客戶i由n車場h類型的車輛服務(wù),根據(jù)車輛所有客戶的SortValue決定客戶在路徑中的位置。DepotNum、VehicleNum和SortValue隨著初始群體的產(chǎn)生而生成。

2.2 適應(yīng)度值計算

計算相應(yīng)的目標(biāo)函數(shù)值以及適應(yīng)度函數(shù)值fj,j=1,2,…,m。我們用當(dāng)前群體中最佳染色體的目標(biāo)函數(shù)值z與當(dāng)前染色體的目標(biāo)函數(shù)值zi的比值作為適應(yīng)度值,如式(11)所示。

2.3 精英選擇策略

精英選擇[11]是群體收斂到優(yōu)化問題最優(yōu)解的一種基本保障。如果下一代群體的最佳個體適應(yīng)值小于當(dāng)前群體最佳個體的適應(yīng)值,則將當(dāng)前群體最佳個體或者適應(yīng)值大于下一代最佳個體適應(yīng)值的多個個體直接復(fù)制到下一代,隨機替代或替代最差的下一代群體中的相應(yīng)數(shù)據(jù)的個體。對于給定的t代規(guī)模為n的群體P(t)=｛a1(t),a2(t),…,an(t)｝,一般描述為

2.4 自適應(yīng)交叉

交叉算子[1]主要用于產(chǎn)生新個體,實現(xiàn)算法的全局搜索能力?？紤]到整個種群的變化趨勢及每個個體的變異機會,本節(jié)設(shè)計了與進(jìn)化代數(shù)相關(guān)而與個體適應(yīng)度無關(guān)的交叉概率計算公式,如式(12)所示。t為當(dāng)前進(jìn)化代數(shù),Tgen為預(yù)設(shè)的最大進(jìn)化代數(shù),pcmax為預(yù)設(shè)最大概率,pcmin為預(yù)設(shè)最小概率,pc(t)為當(dāng)前種群的交叉概率,采取均勻交叉的方式進(jìn)行交叉操作。假設(shè)兩個父代為A和B,均勻操作如下。

1)隨機產(chǎn)生一個與個體編碼串長度等長的染色體C,C=c1c2…ci…cl,l為染色體編碼長度;

2)若ci=0,A′在第i個基因座上的基因值繼承A的基因值,B′在第i個基因座上的基因值繼承B的基因值;

3)若ci=1,A′在第i個基因座上的基因值繼承B的基因值,B′在第i個基因座上的基因值繼承A的基因值。

2.5 混沌變異

采用混沌變異策略[1],混沌變異形式如式(13)所示。K(0,1)為(-2,2)按混沌規(guī)律變化的序列。根據(jù)Logistic映射[1],如式(14)所示。式中,u表示種群序號,u=0,1,…,n;β表示混沌變量, 0≤β≤1;μ表示吸引子,當(dāng)μ取0～4時,Logistic映射為[0,1]間的不可逆映射,μ=4時,完全處于混沌的狀態(tài),此時產(chǎn)生的混沌變量β(u)具有很好的遍歷性。β(u)經(jīng)過放大和平移可得K(0,1)。變異算子的變化尺度對算法的性能有一定的影響。既要達(dá)到精度,又要搜索到全局最優(yōu)解,所以在進(jìn)化初期應(yīng)采用逐漸縮小的變異尺度,利用文獻(xiàn)[2-3]提出的變異策略,如式(15)所示。kc為當(dāng)前代數(shù), Gen為最大迭代次數(shù),δ為當(dāng)前群體中某個體的某分量的變異尺度,α,β,γ為控制尺度收縮參數(shù)。

2.6 引入模擬退火機制

退火初始溫度為T0,終止溫度為Tend,溫度冷卻系數(shù)qcool。以fi為當(dāng)前解,計算每一個個體的適應(yīng)值fi′。若f′i＞fi,則以新個體替換舊個體;否則,以概率exp(fi-f′i)T接受新個體,舍棄舊個體。

2.7 終止條件

當(dāng)算法運行達(dá)到最大迭代次數(shù)或者Ti＜Tend,算法終止。

2.8 3-opt局部搜索

采用3-opt局部搜索[12]方法,可以增強遺傳算法的局部搜索能力。

步驟1從路徑中刪除3條邊,并在路徑的其他地方加上3條新的邊,使路徑保持完整。如果更換之后使路徑長度變短,保留切換結(jié)果;否則,通過刪除添加不同的邊,并嘗試其他更換方式。

步驟2重復(fù)步驟1,直到嘗試了所有可能的更換方式,且不能再提高解的質(zhì)量,則輸出最優(yōu)路徑,退出算法。

3 仿真

3.1 實例

Benchmark算例可從http://www.bernabe.dorronsoro.es/vrp/上獲得,主要以Solomon中C101的25客戶和50客戶的數(shù)據(jù)作為測試對象。坐標(biāo)位置不變,某類型的車輛只能配送相應(yīng)類型的貨物。車輛信息如表1所示。客戶所需貨物信息如表2所示。

表1 車輛信息

表2 客戶所需貨物信息

本實驗是在SONY i5-4200U CPU2.6GHz、內(nèi)存為4.0G、安裝系統(tǒng)為win7的PC機上采用Matlab R2010b編程實現(xiàn)的?；旌线z傳算法參數(shù)設(shè)計:種群規(guī)模為size pop=50,最大迭代次數(shù)TGen=300,pcmax=0.4,pcmin=0.004,變異概率pm=0.005,均勻交叉,單點變異,尺度收縮參數(shù)為α=1,β=10, γ=0.6,δ=0.6,T0=100,Tend=0,qcool=0.8。運行算法20次,取最好的結(jié)果。

3.2 結(jié)果分析

Solomon-25客戶和Solomon-50客戶的最優(yōu)行駛網(wǎng)絡(luò)如圖2和圖3所示。Solomon-25客戶和Solomon -50客戶的配送計劃表如表3和表4所示,最優(yōu)值分別為309.49和572.10。本文算法與分支定界法的算法比較如表5所示,可見兩種算法都能獲得最優(yōu)值,但是當(dāng)問題規(guī)模增大時,分支定界算法尋優(yōu)的能力就開始減弱了,且尋優(yōu)時間比本算法長,進(jìn)一步說明了本算法在尋優(yōu)能力和尋優(yōu)時間方面都優(yōu)于分支定界法。

圖2 Solomon-25客戶的最優(yōu)行駛網(wǎng)絡(luò)

圖3 Solomon-50客戶的最優(yōu)行駛網(wǎng)絡(luò)

表3 Solomon-25客戶配送計劃表

表4 Solomon-50客戶配送計劃表

表5 算法比較

4 結(jié)語

HVRPIG問題實質(zhì)上是一個多任務(wù)的VRP問題。應(yīng)用基于精英選擇策略、自適應(yīng)交叉、混沌變異,并引入了模擬退火機制的HGA求解,最后應(yīng)用3-opt局部搜索策略對解進(jìn)行調(diào)整,得到最優(yōu)解。本算法的優(yōu)點在于:分析不同客戶所需貨物的類型,專車配送相應(yīng)的貨物類型,簡化了問題模型;考慮到收斂精度與進(jìn)化代數(shù)的關(guān)系,混沌變異結(jié)合了“尺度收縮”思想,并采用了避免近親繁殖的策略,引入模擬退火機制能有效克服傳統(tǒng)遺傳算法易早熟的現(xiàn)象;3-opt局部搜索對解的調(diào)整,從而提高算法的性能。下一步將要探討的問題是考慮更為復(fù)雜的問題模型,如規(guī)模更大、道路因素、客戶需求緊急程度、個性化送貨時間窗、周期性、開放式、客戶隨機性需求等,以及研究如何改進(jìn)算法,使算法的性能更優(yōu)。

[1] 湯雅連,蔡延光,郭帥,等.單車場關(guān)聯(lián)物流運輸調(diào)度問題的混沌遺傳算法[J].廣東工業(yè)大學(xué)學(xué)報,2013,30:53-57.

[2] 湯雅連,蔡延光,趙學(xué)才.關(guān)聯(lián)物流運輸調(diào)度問題的改進(jìn)遺傳算法[J].微型機與應(yīng)用,2012,31(17):69-71.

[3] 湯雅連,蔡延光,章云,等.易腐產(chǎn)品運輸調(diào)度問題的優(yōu)化[J].計算機系統(tǒng)應(yīng)用,2013(8):136-140.

[4] 鄭麗英,賈海鵬.全局搜索聚類的多車場多車型調(diào)度算法研究[J].蘭州交通大學(xué)學(xué)報,2009,28(6):19-22.

[5] 楊浩雄,胡靜,何明珂.配送中多車場多任務(wù)多車型車輛調(diào)度研究[J].Computer Engineering and Applications,2013,49(10):243-246.

[6] 王曉博,李一軍.多車場多車型裝卸混合車輛路徑問題研究[J].控制與決策,2009,24(12):1769-1774.

[7] 陶胤強,?；菝?帶時間窗的多車型多費用車輛路徑問題的模型和算法[J].交通運輸系統(tǒng)工程與信息,2008,8(1):113-117.

[8] 陳萍,黃厚寬,董興業(yè).求解多車型車輛路徑問題的變鄰域搜索算法[J].系統(tǒng)仿真學(xué)報,2011,23(9):1945-1950.

[9] 葛顯龍,許茂增,王偉鑫.多車型車輛路徑問題的量子遺傳算法研究[J].中國管理科學(xué),2013,1:125-133.

[10] 陳美軍,張志勝,史金飛.多約束下多車場車輛路徑問題的蟻群算法研究[J].中國機械工程,2008,19(16):1939-1944.

[11] 汪勇,楊海琴,張瑞軍.基于強基因模式組織算法的VRPTW研究[J].控制與決策,2011,26(4):606-610.

[12] 王華秋,曹長修.一種結(jié)合O3-opt局部優(yōu)化的智能螞蟻算法研究[J].計算機應(yīng)用與軟件,2010,27(10):89-91.

The Optimization of Vehicle Routing Problem with In compatible Good s

TANG Ya-lian CAIYan-guang LIU Hong-yu JIANG Ze-dong
(School of Automation,Guangdong University of Technology,Guangzhou 510006,China)

Considering the incompatibility of the many goods of every customer’s or many customers’in the real life,we establish the heterogeneous vehicle routing problem with incompatible goods(HVRPIG)mathematical model based on vehicle load, vehicle mileage constraints,heterogeneous vehicles etc.Using hybrid genetic algorithm(HGA)based on elite selection,chaotic mutation and simulated annealing mechanism solves the model.By measuring the performance of the algorithm by the simulation research of benchmark examples,and comparing the results between the HGA and branch and bound algorithm(BBD),the results show that the proposed algorithm is better than BBD.

heterogeneous vehicle routing problem with incompatible goods;hybrid genetic algorithm;simulated annealing mechanism;3-opt local search;chaotic mutation;branch and bound algorithm

TP301

A

1009-0312(2015)01-0019-06

2014-04-01

國家自然科學(xué)基金(61074147,61074185);廣東省自然科學(xué)基金(S201101000505983510090010000 02);廣東省教育部產(chǎn)學(xué)研結(jié)合項目(2012B091000171,2011B090400460);廣東省科技計劃項目(2012B050600028,2010B090301042)。

湯雅連(1986—),女,湖南常德人,博士生,主要從事物流信息技術(shù)及智能算法研究。