黃戈文 蔡延光 湯雅連
(1.嘉應學院 信息網(wǎng)絡中心,廣東梅州 514015;2.廣東工業(yè)大學 自動化學院,廣州 510006)
VRP[1-2]自1959年Dantzig和Ramser首先提出以來就引起了人們的高度重視。VRP的實用性強,應用廣泛。車輛路徑問題一般定義為:對一系列送貨點和收貨點,組織適當?shù)男熊嚶肪€,使車輛有序地通過它們,在滿足一定的約束條件 (如貨物需求量、發(fā)送量、送發(fā)貨時間、車輛容量限制、行駛里程限制、時間限制等)下,達到一定的目標 (如路程最短、費用極小、時間盡量少、使用車輛數(shù)盡量少等)。在現(xiàn)實生活中存在這樣的情況,不同客戶需要多種零件商品,而這些零件商品由于性質(zhì)、特征和用途的差異,又存在某種聯(lián)系,即存在貨物性質(zhì)關聯(lián)性,客戶常常為了保證其需求不受影響而將所有的零件商品供貨交付給一個物流運輸公司來為其配貨,將關聯(lián)的貨物配套運輸更有利于后期的運作或經(jīng)營,如一臺手機的組件必須包括一個充電器,一個液晶屏、手機按鍵、外殼、電池等,一個螺栓對應一個螺釘,它們存在某種數(shù)量關系,客戶的這種需求我們稱之為需求關聯(lián)。零件商品在被客戶使用,即在加工組成成品的過程中,零件的使用也有一定的先后順序,我們稱零件商品具有時間關聯(lián)性。這時,物流公司為需要這種貨物性質(zhì)的客戶配送貨物,應該考慮怎樣進行貨物任務分配、車輛分配、時間分配,并尋求最優(yōu)配送路線以達到最低的物流成本,上述問題我們統(tǒng)稱為關聯(lián)運輸調(diào)度問題 (Incident Vehicle Routing Problem,IVRP),此類問題在現(xiàn)實生活中普遍存在,因而極具現(xiàn)實意義。
量子進化算法 (Quantum Evolutionary Algorithm,QEA)是20世紀90年代后期新興的一種進化算法。由于其良好的性能,已廣泛應用于諸多領域,如物流運輸調(diào)度、智能交通領域、網(wǎng)格入侵檢測、網(wǎng)格任務調(diào)度、非線性規(guī)劃等[3-4]。Mohammed A M等人[3]提出了基于量子交叉的量子遺傳算法 (quantum crossover-based quantum genetic algorithm,QXQGA)對非線性規(guī)劃問題求解;蔡延光等人[4]針對量子進化算法計算量大、收斂速度慢以及容易出現(xiàn)早熟等問題,提出混沌混合量子進化算法,并證明其可較好地應用在智能交通領域。研究車輛路徑優(yōu)化問題 (Vehicle Routing Problem,VRP)是研究IVRP的基礎。目前,國內(nèi)外采用QEA及其改進算法對VRP或其擴展問題的研究文獻不少,有一定的借鑒意義。Cui L等人[5]提出了一種帶混合局部搜索的改進量子進化算法 (improved quantum evolution algorithm,IQEA)對帶容量約束的VRP(capacitated vehicle routing problem,CVRP)求解;Wang L等人[6]提出了一種改進量子進化算法 (Quantum-Inspired Evolutionary Algorithm,IQEA)對帶時間窗的VRP(vehicle routing problem with time windows,VRPTW)求解;葛顯龍等人[7]根據(jù)隨機需求信息把動態(tài)配送問題轉(zhuǎn)換成一系列靜態(tài)配送問題,設計基于并行節(jié)約算法動態(tài)插入隨機需求信息的混合量子遺傳算法,對動態(tài)模型實時再優(yōu)化;之后,葛顯龍等人[8]又采用量子比特位設計染色體結構,改進遺傳算法中交叉與變異算子,避免優(yōu)秀基因被破壞,設計快速尋優(yōu)機制與最優(yōu)保留機制,增強求解效率對以配送總費用最小為優(yōu)化目標的數(shù)學模型求解;Zhang J等人[9]提出了一種自適應網(wǎng)格多目標量子進化算法 (multi-objective quantum evolutionary algorithm,MOQEA)對帶客戶滿意度的多目標VRP(multiobjective vehicle routing problem considering customer satisfaction,MVRPCS)求解;Michallet J等人[10]研究了非常嚴格的帶時間窗的周期性VRP,并提出了混合整數(shù)線性模型和多起點迭代局部搜索算法;Crispin A等人[11]提出了一種量子模擬算法對帶容量約束的VRP求解;Zheng T等人[12]提出了量子差分進化算法對調(diào)度問題求解;Zhou L等人[13]針對傳統(tǒng)的遺傳算法不能保證收斂到最優(yōu)解的最大概率,提出了對小規(guī)模求解具有快速收斂和良好搜索能力的量子遺傳算法,對VRP求解;Ning T等人[14]結合量子粒子群優(yōu)化算法和模擬退火算法,提出了混合量子粒子群優(yōu)化算法對帶時間窗的VRP求解;彭典軍[15]在其碩士論文中,主要研究了一種量子進化算法在車輛路徑問題中的應用,具體求解了有能力約束車輛路徑問題、開放式車輛路徑問題、動態(tài)網(wǎng)格車輛路徑問題、動態(tài)需求車輛路徑問題;劉勇等人[16]為求解給定期限條件的應急設施選址問題,將量子個體作為博弈者參與到競爭決策中,利用量子位、疊加態(tài)等理論提高競爭群體多樣性,縮小群體規(guī)模,提出了一種量子競爭決策算法;寧濤[17]在其博士論文中,提出混合量子粒子群優(yōu)化算法對帶時間窗車輛路徑問題求解;提出模擬退火算法與量子算法對不確定需求車輛路徑問題的數(shù)學規(guī)劃模型求解;結合精英量子均值和混沌擾動理論的量子進化算法對帶同時取送貨需求的車輛路徑問題求解;蔡蓓蓓等人[18]構造了一種混合量子遺傳算法,即在傳統(tǒng)量子遺傳算法隨機全局搜索的基礎上引入一個免疫算子,通過該算子的局部搜索實現(xiàn)線路內(nèi)次序的再優(yōu)化;李川[19]在其碩士論文中,對隨機需求的車輛路徑問題進行研究,通過設計不同混合量子進化算法對建立的帶時間窗和基于模糊預約時間的多目標問題模型求解;任偉[20]提出了一種混合量子免疫進化算法對帶時間窗的車輛調(diào)度問題求解;吳斌等人[21]針對量子進化算法中旋轉(zhuǎn)角取值的離散性使其解空間的搜索具有跳躍性,提出了基于混沌理論的精英均值計算旋轉(zhuǎn)角算法,對具有同時集送貨需求車輛路徑問題求解;趙燕偉等人[22]針對帶時間窗的隨機需求車輛路徑問題,建立了基于模糊滿意度的多目標數(shù)學規(guī)劃模型,提出了一種基于量子進化算法和粒子群算法分段優(yōu)化的方法求解Pareto解;李熠等人[23]提出了一種新的混合量子優(yōu)化算法,即量子蟻群算法對旅行商問題求解。以上學者或研究人員都取得了不錯的成果。IVRP由蔡延光教授首次提出,相關文獻還相當有限,且同時考慮關聯(lián)特征、載重約束、多車場多車型、車場與客戶硬時間窗等因素的IVRP的研究文獻還沒有發(fā)現(xiàn),本文提出混合混沌量子進化算法對該問題求解。
有 i個客戶 (1,2,…,l),第 i個客戶的需求量為 gi(i=1,2,…,l),m(m=1,2,…,M)個車場,車輛裝載貨物后,配送給相應的客戶。假設客戶i所需貨物有θ種,即該客戶的貨物種類可表示為,這θ種貨物之前的需求關系可表示為,則存在種數(shù)量關系,比如,關系式之一,,即表示個貨物就需要與個貨物關聯(lián)配送。車場m有h(h=1,2,…,H)種車型的貨車k(k=1,2,…,K)輛,每種車型車輛的載重為qh,已知qh,客戶硬時間窗為[eti,lti],假定一個客戶所有貨物的送貨時間窗一致。Ti表示車輛到達i的時間。不考慮裝卸貨時間。以表示車場m中車型h的車輛k從i到j的單位運輸成本 (距離、費用、時間等),路徑具有對稱性,即。車型h的車輛k從客戶i到j之間的距離為,車輛最大行駛里程約束為Dmax。為車輛從車場實際出發(fā)的時間,為車輛從返回原車場的時間,車場硬時間窗[etm,ltm]。v為通過交通數(shù)據(jù)擬合的平均速度。目標函數(shù)為考慮路況約束、載重約束、多車場多車型、客戶與車場硬時間窗等情況下,滿足客戶需求,并使總成本最小。
假設客戶編號為1,2,…,l,車場編號為l+m。決策變量如下:
目標函數(shù):
約束條件:
式 (3)為目標函數(shù),表示總成本最小。式 (4)和式 (5)表示每個客戶只能由某車場某車型中的一輛車服務。式 (6)表示車輛的行駛里程約束。式 (7)表示車輛從所在的車場出發(fā),完成配送任務后,回到原車場。式 (8)和式 (9)表示每輛車所運送的貨物重量不能超過此類型車輛的載重限制。式 (10)tij表示i到j的行駛時間。式 (11)-式 (12)表示車輛出發(fā)時間和返回時間必須嚴格遵守車場時間窗。式 (13)表示車輛送貨時間嚴格遵守客戶時間窗。式 (14)消除了車輛不是從車場出發(fā)的現(xiàn)象。
本文采用實數(shù)對個體進行編碼,與文獻[4]的方法一致,采用混沌初始化方法產(chǎn)生初始種群,采用簡單量子旋轉(zhuǎn)門更新當前種群中的非最優(yōu)個體,設計基于目標函數(shù)梯度信息和混沌變換序列的量子旋轉(zhuǎn)門更新當前種群中的最優(yōu)個體,采用混沌變異策略抑制早熟現(xiàn)象,提出了混合混沌量子進化算法。
設X=(x1,x2,…,xn)T為所求問題模型的可行解,則對任意xi(i=1,2,…,n),存在唯一實數(shù)θi∈[0,1]使 (15)成立,顯然,θi與xi是一一對應的。
設種群規(guī)模為 N ,隨機生成 n 個實數(shù) θ1,i,0 < θ1,i< 1 ,θ1,i≠0.5 ,i=1,2,…,n 。對每個 i(i=1,2,…,n),把 θ1,i作為 Logistic 映射的初始值,產(chǎn)生第 i個混沌序列 {θ2,i,θ3,i,…,θN,i},如式 (16)所示,其中,j=1,2,…,N 。
采用簡單量子旋轉(zhuǎn)門對當前種群中的非最優(yōu)個體進行更新。設全局最優(yōu)個體為B=(θ1b,θ2b,…,θnb)T,即進化到目前為止的最優(yōu)個體,Θ =(θ1,θ2,…,θn)T為當前種群中的任一非最優(yōu)個體。當前種群中的最優(yōu)個體是指當前種群中對應的目標函數(shù)值最小的個體,Θ的第i個基因θi的量子旋轉(zhuǎn)門的旋轉(zhuǎn)角Δθi按式 (17)選取,其中θ0為基本旋轉(zhuǎn)角,且0<θ0<1。
令
基于目標函數(shù)的梯度信息和混沌變換序列,構造量子旋轉(zhuǎn)門更新當前種群中的最優(yōu)個體。設preGen為當前進化代數(shù),maxGen為最大進化代數(shù),m為解連續(xù)為得到改進 (即無效進化)的進化代數(shù),無效進化代數(shù)的上限為M(預先給定的正整數(shù)),假定進化尚未結束且無效進化代數(shù)未達到上限 (即preGen<maxGen,m <M)。設Θ =(θ1,θ2,…,θn)T為當前種群中的最優(yōu)個體。接著,對Θ進行更新,當求解最小值時,只有沿著與目標函數(shù)負梯度方向成銳角的方向搜索,目標函數(shù)值才有可能下降。為此,根據(jù)目標函數(shù)的梯度信息設計量子進化擾動參數(shù)βi,i=1,2,…,n,βi按式 (20)選取,其中▽f(θi)為f在Θ處對θi的偏導數(shù),若f的偏導數(shù)不存在,則用f在Θ的某個充分小鄰域內(nèi)的任意點對θi的函數(shù)值變化率來代替,D為預先給定的大于1的常數(shù)。
Θ 的第i個基因 θi的量子旋轉(zhuǎn)門的旋轉(zhuǎn)角 Δθi按式 (21)選取,其中 θ*i=4θi(1 - θi)(i=1,2,…,n)是Logistic映射產(chǎn)生的混沌序列。
θ'i如式 (18)所示,Θ的第i個基因按式 (19)更新,其中θi″是Θ的第i個基因的新值。
通過此方法,當前種群中的最優(yōu)個體一般會沿著目標函數(shù)負梯度方向成銳角的方向進化,有利于引導整個種群朝著全局最優(yōu)解的方向進化。
假定進化尚未結束且無效進化代數(shù)達到上限,則意味著進化陷入局部最優(yōu),出現(xiàn)了早熟現(xiàn)象。采用Logistic映射對當前種群全部個體的基因進行混沌變異,以改變種群的個體分布,避免早熟現(xiàn)象。設(θk1,θk2,…,θkn)T為當前種群的第k個個體,k=1,2,…,N 。個體k的第i個基因按式 (22)更新,其中θ'ki為個體k的第i個基因的新值。
1)設定參數(shù):種群規(guī)模N,最大進化代數(shù)maxGen,正常數(shù)D,最大無效進化代數(shù)M,基本旋轉(zhuǎn)角 θ0。
2)初始化種群:置進化代數(shù)preGen=0,無效進化代數(shù)m=0,按2.2節(jié)方法產(chǎn)生初始種群。
3)對種群中的所有個體按式 (1)解碼得到對應的可行解,找出當前種群中的最優(yōu)個體。
4)若preGen=0,置當前種群中的最優(yōu)個體為全局最優(yōu)個體B(如果當前種群中的最優(yōu)個體不止一個,則任選一個作為全局最優(yōu)個體,下同)。
5)若preGen<maxGen,轉(zhuǎn)至下一步;否則輸出全局最優(yōu)個體B對應的解及對應的目標函數(shù)值fB,算法結束。
6)對于preGen>0,若當前種群中的最優(yōu)個體對應的目標函數(shù)值小于fB,置當前種群中的最優(yōu)個體為B,并置m=0;否則置m=m+1。
7)采用2.3節(jié)所述方法更新當前種群中的非最優(yōu)個體。
8)如果m<M,采用2.4節(jié)方法對當前種群中的最優(yōu)個體進行更新;否則按2.5節(jié)所述方法對當前種群中的每個個體基因進行混沌變異。
9)preGen<preGen+1,轉(zhuǎn)步驟3)。
以http://www.bernabe.dorronsoro.es/vrp/網(wǎng)站上的C101的50個客戶點位置作為某物流公司帶服務的客戶位置,原車場作為第1個車場,調(diào)換原車場的縱坐標和橫坐標位置,作為第2個車場。車場信息表如表1所示,客戶信息表如表2所示,這些客戶主要需要兩大類貨物 (I和II)或者傾向于某一類,其中每類貨物有多種型號。每個車場 (配送中心)都有這兩大類貨物。每輛車的最大配送里程為180個里程單位??蛻?6、19、49、40、20及22的時間窗為 [8∶00 10∶00],其余客戶的時間窗為[8∶00 11∶30]。為保證模型有可行解,將兩個車場的時間窗設為 [8∶00 12∶00],車輛平均速度為50個速度單位。
表1 車場信息
表2 客戶信息
客戶 坐標 需求關系 單位重量/kg 客戶 坐標 需求關系 單位重量/kg 13 (22,75) λ113 =30 λ113 =3 38 (0,40) λ318 =20,λ328 =40 g318 =2,g328 =1 14 (22,85) λ114 =20,λ124 =30 g114 =2,g124 =3 39 (0,45) λ319 =120,λ329 =20 g319 =1,g329 =2 15 (20,80) λ115 =20,λ125 =100 g115 =2,g125 =2 40 (36,18) λ410 =60 g410 =2 16 (20,85) λ126 =30 g126 =1 41 (35,32) λ411 =30,λ421 =10 g411 =2,g421 =3 17 (18,75) λ117 = λ127 =10 g117 =g127 =3 42 (33,32) λ412 = λ422 =100 g412 =2,g422 =1 18 (15,75) λ118 =50,λ128 =40 g118 =2,g128 =3 43 (33,35) λ413 =30 g413 =2 19 (15,80) λ119 =10,λ129 =20 g119 =4,g129 =2 44 (32,20) λ424 =10 g424 =4 20 (30,50) λ210 =40 g210 =3 45 (30,30) λ415 =60,λ425 =20 g415 =1,g425 =3 21 (30,56) λ211 =20,λ221 =10 g211 =2,g221 =4 46 (34,25) λ426 =20 g426 =4 22 (28,52) λ212 =10,λ222 =20 g212 =2,g222 =2 47 (30,35) λ417 =20,λ427 =100 g417 =1,g427 =1 23 (14,66) λ213 =30 λ213=3 48 (36,40) λ418=30 g418 =4 24 (25,50) λ214 =20,λ224 =30 g214 =2,g224 =3 49 (48,20) λ419 =200,λ429 =10 g419 =3,g429 =5 25 (22,66) λ215 =20,λ225 =10 g215 =2,g225 =2 50 (26,32) λ520 =20 g520 =4
在Intel(R)Core?i5 CPU 3.0GHz、內(nèi)存為8.0G、安裝系統(tǒng)為Windows7的PC機上采用Matlab R2010b編程實現(xiàn)。針對VRP模型和IVRP模型,首先采用HCQEA對這兩種模型求解,然后采用另外兩種算法對IVRP求解,各運行算法20次。
HCQEA參數(shù)設計:N=20,maxGen=200,D=1 000,θ0=0.005;QEA參數(shù)設計:可行解的每個分量用20個二進制位表示,群體規(guī)模m=20,maxGen=200,基本旋轉(zhuǎn)角自適應遺傳算法 (adaptive genetic algorithm,AGA)參數(shù)設計:種群規(guī)模m=20,最大迭代次數(shù)Gen=200,交叉概率pc=0.9,變異概率pm=0.04,采用最佳保留選擇法選擇算子,多點交叉,均勻變異。
圖1 MDVRPHTW配送網(wǎng)絡 (非關聯(lián))
圖2 MDVRPHTW配送網(wǎng)絡 (關聯(lián))
表3 MDVRPHTW的具體配送信息 (非關聯(lián))
表4 MDIVRPHTW的具體配送信息 (關聯(lián))
求解MDVRPHTW和MDIVRPHTW的配送網(wǎng)絡圖如圖1和圖2所示。具體配送信息分別如表3和表4所示,可見MDVRPHTW需要使用6輛車,MDIVRPHTW使用了5輛車,減少了一輛車的使用,且總成本降低了27.75%,所以該模型的提出是有意義的。
MDIVRPHTW的一次優(yōu)化過程如圖3所示,HCQEA在第110代求得的總成本為205.69個費用單位,QEA在第170代求得的總成本為213.52個費用單位,AGA在第120代求得的總成本是213.52個費用單位??梢?,雖然AGA能較早收斂,可是易陷入局部最優(yōu),而HCQEA的求解速度和得到的解結果總體來說優(yōu)于另外兩種算法,這主要歸因于引入了混合混沌搜索策略,提高了算法的收斂速度和全局搜索能力。
圖3 MDIVRPHTW的一次優(yōu)化過程
文中提出了引入混合混沌策略的混合混沌量子進化算法??紤]了關聯(lián)因素對物流配送的影響,提出了帶多種擴展特征 (考慮多車型、客戶和車場硬時間窗等約束)的IVRP模型,通過HCQEA、AGA和QEA對模型求解的結果相比較,證明其優(yōu)越性,也體現(xiàn)出提出模型的有效性,研究更大規(guī)模問題模型及包含多種擴展特性 (次序關聯(lián)、不對稱、隨機需求、多周期性、需求可拆分、同時取送貨、開放式、服務優(yōu)先級等)的IVRP及其求解算法將是今后的研究方向。
[1]Azi N,Gendreau M,Potvin J Y.An adaptive large neighborhood search for a vehicle routing problem with multiple routes[J].Computers&Operations Research,2014,41:167-173.
[2]Michallet J,Prins C,Amodeo L,et al.Multi-start iterated local search for the periodic vehicle routing problem with time windows and time spread constraints on services[J].Computers& Operations Research,2014,41:196-207.
[3]Mohammed A M,Elhefhawy N A,El-Sherbiny M M,et al.Quantum crossover based quantum genetic algorithm for solving non-linear programming[C]//Informatics and Systems(INFOS),2012 8th International Conference on.IEEE,2012:BIO -145-BIO-153.
[4]蔡延光,張敏捷,蔡顥,等.混合混沌量子進化算法[J].系統(tǒng)工程理論與實踐,2012,32(10):2207-2214.
[5]Cui L,Wang L,Deng J,et al.A new improved quantum evolution algorithm with local search procedure for capacitated vehicle routing problem[J].Mathematical Problems in Engineering,2013:17.
[6]Wang L,Kowk S K,Ip W H.Design of an improved quantum-inspired evolutionary algorithm for a transportation problem in logistics systems[J].Journal of Intelligent Manufacturing,2012,23(6):2227-2236.
[7]葛顯龍,王旭,代應.基于混合量子遺傳算法的隨機需求車輛調(diào)度問題[J].系統(tǒng)工程,2011,29(3):53-59.
[8]葛顯龍,許茂增,王偉鑫.多車型車輛路徑問題的量子遺傳算法研究[J].中國管理科學,2013,1:125-133.
[9]Zhang J,Wang W,Zhao Y,et al.Multiobjective quantum evolutionary algorithm for the vehicle routing problem with customer s atisfaction[J].Mathematical Problems in Engineering,2012:19.
[10]Michallet J,Prins C,Amodeo L,et al.Multi- start iterated local search for the periodic vehicle routing problem with time windows and time spread constraints on services[J].Computers& operations research,2014,41:196-207.
[11]Crispin A,Syrichas A.Quantum Annealing Algorithm for Vehicle Scheduling[C]//Systems,Man,and Cybernetics(SMC),2013 IEEE International Conference on.IEEE,2013:3523-3528.
[12]Zheng T,Yamashiro M.Quantum -inspired differential evolutionary algorithm for permutative scheduling problems[M].Rijeka,Croatia:In-Tech.Evolutionary Algorithms,2011,109 -132.
[13]Zhou L,Li R,Li Q.Research on Vehicle Routing Problem Based on Quantum Genetic Algorithm[C]//ICLEM 2010:Logistics For Sustained Economic Development:Infrastructure,Information,Integration.ASCE,2010:2965-2971.
[14]Ning T,Guo C.Using hybrid quantum algorithm to solve VRPTW[C]//Intelligent Control and Information Processing(ICICIP),2012 Third International Conference on.IEEE,2012:59-62.
[15]彭典軍.車輛路徑問題的量子進化算法研究[D].杭州:浙江工業(yè)大學,2009.
[16]劉勇,馬良,寧愛兵.給定限期條件下應急選址問題的量子競爭決策算法[J].運籌與管理,2011,20(3):66-71.
[17]寧濤.混合量子算法在車輛路徑問題中應用的研究[D].大連:大連海事大學,2013.
[18]蔡蓓蓓,張興華.混合量子遺傳算法及其在VRP中的應用[J].計算機仿真,2010,27(7):267-334.
[19]李川.基于混合量子進化算法的隨機車輛路徑問題的研究[D].杭州:浙江工業(yè)大學,2011.
[20]任偉.基于量子免疫算法的車輛調(diào)度問題的優(yōu)化[J].計算機科學,2013,40(5):233-236.
[21]吳斌,錢存華,董敏,等.具有同時集送貨需求車輛路徑問題的混沌量子進化算法研究[J].2010,25(3):383-387.
[22]趙燕偉,李川,張景玲,等.一種新的求解多目標隨機需求車輛路徑問題的算法[J].計算機集成制造系統(tǒng),2012,18(3):523-530.
[23]李熠,馬良.用量子蟻群算法求解大規(guī)模旅行商問題[J].上海理工大學學報,2012,34(4):355-358.