基于量子蟻群算法的隨機(jī)需求的動(dòng)態(tài)車(chē)輛路徑問(wèn)題

寧濤,焦璇,魏瑛琦,梁旭

(1.大連交通大學(xué) 軟件學(xué)院，遼寧 大連 116054; 2.大連東軟信息學(xué)院 會(huì)計(jì)學(xué)院,遼寧 大連 116023)*

0 引言

車(chē)輛路徑問(wèn)題(Vehicle Routing Problem，VRP)自1959年Dantzig和Ramser[1]提出以來(lái)，受到研究者們廣泛關(guān)注.在物流配送中可能出現(xiàn)新增客戶(hù)點(diǎn)、原客戶(hù)點(diǎn)的需求發(fā)生改變、交通堵塞或天氣狀況等問(wèn)題而重新調(diào)整配送路線(xiàn)，這類(lèi)問(wèn)題即為動(dòng)態(tài)車(chē)輛路徑問(wèn)題(Dynamic Vehicle Routing Problem,DVRP).近年來(lái)國(guó)內(nèi)外學(xué)者在該問(wèn)題上進(jìn)行了相關(guān)研究，Zhiwei Yang[2]等針對(duì)車(chē)輛配送過(guò)程中需求變更或時(shí)間窗變更的情況提出了一種多重蟻群算法，該算法具有強(qiáng)大的局部搜索能力.Briseida Sarasola[3]等研究了隨機(jī)需求或需求動(dòng)態(tài)變更的車(chē)輛路徑問(wèn)題，提出了可擴(kuò)展的變鄰域搜索算法.Yinan Guo[4]等針對(duì)帶有硬時(shí)間窗口和隨機(jī)需求的車(chē)輛路徑問(wèn)題，提出了局部?jī)?yōu)化策略的魯棒動(dòng)態(tài)車(chē)輛路徑方案.Nicolas Zufferey[5]等研究了擴(kuò)展環(huán)境下的動(dòng)態(tài)車(chē)輛路徑問(wèn)題.寧濤[6]針對(duì)動(dòng)態(tài)車(chē)輛問(wèn)題提出了車(chē)輛鏈和貨物鏈的雙鏈量子編碼方法和改進(jìn)的多向量子粒群算法.Michalis Mavrovouniotis[7]針對(duì)用蟻群算法求解動(dòng)態(tài)車(chē)輛路徑問(wèn)題提出了新的方案，該方案能夠保證種群的多樣性，避免過(guò)早收斂.Tao Ning 等[8]針對(duì)需求變更的動(dòng)態(tài)車(chē)輛路徑問(wèn)題，提出了一種基于可變鄰域搜索的元啟發(fā)式來(lái)求解.M. Schyns[9]等提出一種基于蟻群系統(tǒng)的算法來(lái)處理動(dòng)態(tài)時(shí)間窗口，分離交付和異構(gòu)車(chē)隊(duì)的車(chē)輛路徑問(wèn)題.Jalel Euchi[10]等提出了一種基于2_Opt本地搜索的人造蟻群來(lái)解決動(dòng)態(tài)車(chē)輛路徑問(wèn)題.S. Masrom[11]等提出將動(dòng)態(tài)參數(shù)化突變和交叉算子與粒子群算法相結(jié)合.

本文提出了用量子蟻群算法來(lái)求解隨機(jī)需求的動(dòng)態(tài)車(chē)輛路徑問(wèn)題，建立了兩階段模型，將DVRP轉(zhuǎn)化成了靜態(tài)VRP，考慮到客戶(hù)對(duì)物流配送的滿(mǎn)意程度，本文引入了模糊隸屬度函數(shù).

1 問(wèn)題描述

隨機(jī)需求的DVRP階段的數(shù)學(xué)模型可被描述為由1個(gè)配送中心和L個(gè)已知客戶(hù)點(diǎn)組成，派出K輛車(chē)對(duì)L個(gè)客戶(hù)點(diǎn)進(jìn)行服務(wù)，K輛車(chē)從配送中心出發(fā)，完成配送任務(wù)后再返回配送中心，K輛車(chē)均為同一車(chē)型，具有相同的車(chē)載量Q.

具體定義如下：

L:初始階段客戶(hù)總數(shù)，i={0，1，2，…，L} ；其中i=0表示配送中心，i=1，2，…，L表示客戶(hù)點(diǎn)；K表示配送中心車(chē)輛數(shù)，K={1，2，…，K}；F表示派出一輛車(chē)的固定成本；Q表示車(chē)輛最大容載量；qi表示每個(gè)客戶(hù)的需求；dij表示從i到j(luò)距離；cij表示從i到j(luò)的單位運(yùn)輸費(fèi)用；ωijk表示車(chē)輛K從i到j(luò)的運(yùn)輸量.

決策變量定義如下：

目標(biāo)函數(shù)如下：

(1)

其中,Z為衡量客戶(hù)滿(mǎn)意度的度量，取值范圍為0～1，本文將最小化車(chē)輛費(fèi)用與最小化客戶(hù)不滿(mǎn)意度相加求和，但Z的數(shù)量級(jí)與車(chē)輛配送成本的數(shù)量級(jí)相差甚遠(yuǎn)，所以本文采用公式α=F×β將客戶(hù)滿(mǎn)意度與車(chē)輛配送費(fèi)用變?yōu)橥粩?shù)量級(jí)別，本文β取0.5.

約束條件：

含義如下：式(1)為目標(biāo)函數(shù)，式(2)為車(chē)輛能力約束，式(3)表示每個(gè)客戶(hù)都被服務(wù)一次，式(4)、(5)表示客戶(hù)被且僅被一輛車(chē)服務(wù)，式(6)表示車(chē)輛從i到j(luò)的運(yùn)輸量大于客戶(hù)j的需求量.

2 改進(jìn)量子蟻群算法

蟻群算法是一種具有較強(qiáng)尋優(yōu)能力且魯棒性強(qiáng)的算法，但當(dāng)種群規(guī)模較大時(shí)，容易陷入局部最優(yōu)，許多研究者將蟻群算法與其他算法結(jié)合，量子算法是近年來(lái)研究的熱點(diǎn)，該算法因其優(yōu)越的編碼方式能夠同時(shí)表達(dá)多個(gè)態(tài)的疊加，事實(shí)證明，該算法在求解組合優(yōu)化問(wèn)題上具有明顯的優(yōu)勢(shì)，本文將量子算法與蟻群算法結(jié)合并，用改進(jìn)的量子蟻群算法(QACO)來(lái)求解隨機(jī)需求的DVRP.

2.1 狀態(tài)轉(zhuǎn)移規(guī)則

(7)

其中,l表示所有可能的取值;τij為邊弧(i,j)的軌跡強(qiáng)度;α(α>0)為信息啟發(fā)式因子，表示軌跡的相對(duì)重要性 ,其值越大,螞蟻越傾向于選擇有較多螞蟻經(jīng)過(guò)的路徑;ηij為邊弧(i,j)的能見(jiàn)度，其表達(dá)式為：

(8)

其中,dij為相鄰兩個(gè)客戶(hù)間的距離;β(β>0)為期望的啟發(fā)式因子, 表示能見(jiàn)度的相對(duì)重要性, 其值越大螞蟻越傾向于選擇路徑較短的路徑;μj為客戶(hù)節(jié)點(diǎn)j的量子信息強(qiáng)度, 其表達(dá)式為：

(9)

2.2 信息素的更新

螞蟻在進(jìn)行路徑搜索的過(guò)程中，之前路徑上的信息素會(huì)不斷的揮發(fā)，而螞蟻在走過(guò)的路徑上會(huì)釋放新的信息素，信息素的更新方程為：

τij=(1-ρ)τij+Δτij

(10)

(11)

(12)

Q為信息素量，是一個(gè)常值，Lk為第k只螞蟻已經(jīng)構(gòu)建路徑的長(zhǎng)度，本文把量子概率幅引入，在進(jìn)行信息素更新時(shí)，螞蟻經(jīng)過(guò)的路徑上量子信息素會(huì)越來(lái)越多，而螞蟻未經(jīng)過(guò)的路徑隨著量子信息素的揮發(fā)，該路徑上所剩的量子信息素會(huì)越來(lái)越少，這將導(dǎo)致不同的邊量子信息素相差越來(lái)越大，容易陷入局部最優(yōu).本文設(shè)計(jì)的量子信息素更新策略會(huì)隨著螞蟻構(gòu)建的路徑的增加，量子信息素所增加的量將逐漸減少，從而避免某條邊上信息素積累過(guò)多導(dǎo)致陷入局部最優(yōu)的問(wèn)題.

2.3 算法步驟

(1)初始調(diào)度階段：

步驟3：如果螞蟻k=(k=1,2,…,n)走完全部客戶(hù)點(diǎn)即所有客戶(hù)點(diǎn)都在當(dāng)前解集中，記下螞蟻個(gè)數(shù)Nk；

步驟4：計(jì)算各目標(biāo)函數(shù)Wk(k=1,2,…,m)，得到當(dāng)前最優(yōu)解；

步驟5：對(duì)各邊信息素進(jìn)行更新，用量子Hε門(mén)對(duì)量子蟻群進(jìn)行更新；

步驟6：判斷當(dāng)前迭代次數(shù)是否達(dá)到最大迭代次數(shù)，否則轉(zhuǎn)步驟2；

步驟7：輸出當(dāng)前得到的最優(yōu)解.

(2)動(dòng)態(tài)優(yōu)化階段：

步驟1：執(zhí)行初始調(diào)度階段的配送方案并更新客戶(hù)信息；

步驟2：若有新的客戶(hù)請(qǐng)求出現(xiàn)，判斷新增客戶(hù)點(diǎn)數(shù)量是否達(dá)到上限，若達(dá)到上限，轉(zhuǎn)到步驟3，否則判斷是否到達(dá)下一重調(diào)度時(shí)間點(diǎn)，若到達(dá)下一重調(diào)度時(shí)間點(diǎn)，執(zhí)行步驟3，否則轉(zhuǎn)到步驟1；

步驟3：根據(jù)模糊需求概率公式判斷是否將該客戶(hù)點(diǎn)插入到當(dāng)前配送路徑中，如果S大于下一客戶(hù)點(diǎn)需求量的臨界值，則將該點(diǎn)插入到當(dāng)前路徑中，用量子蟻群算法生成新路徑，否則轉(zhuǎn)到步驟4；

步驟4：新增車(chē)輛來(lái)完成新增客戶(hù)點(diǎn)的配送任務(wù).

3 仿真實(shí)驗(yàn)

仿真實(shí)驗(yàn)借助Matlab7.0軟件來(lái)驗(yàn)證改進(jìn)的量子蟻群算法的可行性和有效性，本文以一個(gè)配送中心坐標(biāo)為(300，270)、14個(gè)靜態(tài)客戶(hù)點(diǎn)、4個(gè)動(dòng)態(tài)客戶(hù)點(diǎn)為例，配送區(qū)域?yàn)?50 km×450 km的正方形區(qū)域，重調(diào)度周期為1 h，對(duì)隨機(jī)需求的動(dòng)態(tài)車(chē)輛路徑問(wèn)題進(jìn)行仿真實(shí)驗(yàn)，不同客戶(hù)的位置如表1和表2所示.

表1 14個(gè)靜態(tài)客戶(hù)的地理坐標(biāo)

表2 4個(gè)動(dòng)態(tài)客戶(hù)的地理坐標(biāo)

圖1靜態(tài)階段配送路線(xiàn)圖2動(dòng)態(tài)階段配送路線(xiàn)

(2)在某時(shí)間片內(nèi)增加了a、b、c、d四個(gè)動(dòng)態(tài)客戶(hù)點(diǎn)，根據(jù)動(dòng)態(tài)階段重調(diào)度策略，將新增客戶(hù)點(diǎn)插入到當(dāng)前配送路徑中，可得更新后的配送路徑如圖2所示.

(3)根據(jù)圖2的路線(xiàn)圖生成的動(dòng)態(tài)階段重調(diào)度表如表3所示.

表3 動(dòng)態(tài)重調(diào)度表

4 結(jié)論

本文提出將量子計(jì)算與蟻群算法相結(jié)合并加以改進(jìn)，求解隨機(jī)需求的DVRP問(wèn)題.對(duì)各路徑上的信息素進(jìn)行量子比特編碼，采用Hε門(mén)對(duì)量子蟻群更新；為了避免搜索陷入局部最優(yōu)，改進(jìn)了信息素更新方程.采用重調(diào)度判斷公式來(lái)處理新增客戶(hù)點(diǎn)問(wèn)題，最后進(jìn)行Matlab仿真實(shí)驗(yàn)，驗(yàn)證了本算法在求解隨機(jī)需求的動(dòng)態(tài)車(chē)輛路徑問(wèn)題上的有效性.