馬智超, 徐海濤

(杭州電子科技大學(xué) 計(jì)算機(jī)學(xué)院，浙江 杭州 310018)

0 引 言

研究公共自行車調(diào)度路徑優(yōu)化問題對提高市民對公共自行車使用的滿意度，緩解交通擁堵，綠色出行具有重大意義。目前已經(jīng)有一些人對該問題進(jìn)行了研究，但相應(yīng)的模型和算法還需要改進(jìn)。文獻(xiàn)[1，2]模型的優(yōu)化目標(biāo)只考慮了油費(fèi)，文獻(xiàn)[3]的模型考慮了用戶的滿意度，分別提出軟時(shí)間窗和硬時(shí)間窗模型。為了求解自行車調(diào)度問題，文獻(xiàn)[4]提出了改進(jìn)的遺傳算法，文獻(xiàn)[5]提出了自適應(yīng)遺傳算法，文獻(xiàn)[6]提出了用改進(jìn)的蟻群算法，文獻(xiàn)[7]提出了模擬退火算法。這類算法均容易陷入停滯。智能水滴算法在短時(shí)間內(nèi)可以得到更優(yōu)的解，并在多個(gè)領(lǐng)域得到驗(yàn)證，文獻(xiàn)[8]用其求解旅行商問題(TSP)，文獻(xiàn)[9，10]用其求解車輛路徑問題，但該算法本身也具有陷入停滯特點(diǎn)。變鄰域搜索具有很強(qiáng)的搜索能力，從文獻(xiàn)[11，12]可以看出，如果變鄰域搜索有一個(gè)合適的領(lǐng)域結(jié)構(gòu)和較優(yōu)的初始解，其效率將會大大提高。為此本文將二者融合。

本文提出了一種帶有混合時(shí)間窗的數(shù)學(xué)模型，既考慮了用戶的滿意度又考慮了調(diào)度成本。提出了一種混合智能水滴算法，與變鄰域搜索融合，提出了兩種適用于路徑優(yōu)化問題的鄰域結(jié)構(gòu)，提出了節(jié)約算子、啟發(fā)式因子和最大最小調(diào)制的改進(jìn)策略。仿真對比實(shí)驗(yàn)驗(yàn)證了算法的有效性。

1 問題描述與構(gòu)建數(shù)學(xué)模型

1.1 問題描述

假設(shè)有不同的工作區(qū)域，每個(gè)工作區(qū)域都有一個(gè)調(diào)度中心用于管理屬于同一區(qū)域的自行車站點(diǎn)。系統(tǒng)會一直檢查站點(diǎn)的狀態(tài)，看是否需要調(diào)度。系統(tǒng)會計(jì)算出相應(yīng)的需求，包含這個(gè)站點(diǎn)需要調(diào)度的自行車數(shù)量，最佳調(diào)度服務(wù)時(shí)間以及運(yùn)輸車和各個(gè)站點(diǎn)的位置信息。如何根據(jù)這些信息來計(jì)算調(diào)度方案，是本文要研究的問題。調(diào)度方案包括需要派出幾輛運(yùn)輸車、每輛運(yùn)輸車的行駛路線。

1.2 構(gòu)建數(shù)學(xué)模型

假設(shè)有1個(gè)調(diào)度中心({0})，公共自行車租賃站點(diǎn)N={s1,s2,…,sN}，需要K個(gè)運(yùn)輸車，每個(gè)最多可載Q輛自行車；運(yùn)輸車到達(dá)站點(diǎn)si的時(shí)刻為ti；從站點(diǎn)si到sj所需要的時(shí)間為tij(s)，路程為dij(km)。wij是運(yùn)輸車從si到sj運(yùn)行過程中裝載的自行車數(shù)量，wi是在站點(diǎn)si的等待時(shí)間。定義Cw為每秒給工作人員的薪資，Cp為單位里程的油費(fèi)，單位均為人民幣。di為站點(diǎn)si的調(diào)度量，如果di≥0,就意味著si需要輛di輛自行車，否則就意味著該站點(diǎn)需要帶走di輛自行車。該調(diào)度的服務(wù)時(shí)刻必須在時(shí)間窗[ci,di]內(nèi)，且最佳服務(wù)時(shí)間窗為[ai,bi]。本文定義懲罰條件：如果運(yùn)輸車對站點(diǎn)vj服務(wù)的時(shí)刻在[ai,bi]外且在[ci,di]內(nèi)，系統(tǒng)將予以懲罰，如式(1)所示

(1)

如果運(yùn)輸車k從站點(diǎn)vi向站點(diǎn)vj運(yùn)行xijk=1，否則，xijk=0。如果對站點(diǎn)vi服務(wù)的是運(yùn)輸車k，yik=1，否則，yik=0。則優(yōu)化目標(biāo)如式(2)所示，表示車輛運(yùn)行的成本，既包括運(yùn)輸車所耗油費(fèi)，又包括不滿足時(shí)間窗的懲罰成本

(2)

式(2)需要滿足以下幾個(gè)約束條件

0≤dj+wijk≤Q(i,j∈N∪{0}，k∈{1,2,…,K})

(3)

|di|≤Q(i∈N∪{0})

(4)

(5)

(6)

cj≤ti+si+tij-k(1-xijk)≤dj(i,j∈N∪{0})

(7)

式(3)指運(yùn)輸車在調(diào)度過程中，其車上的自行車的數(shù)滿足車輛的載運(yùn)能力；式(4)指每個(gè)租賃點(diǎn)的調(diào)度量不超過運(yùn)輸車的最大載運(yùn)能力；式(5)指運(yùn)輸車輛均從車場出發(fā)最終回到車場；式(6)指每一個(gè)租賃點(diǎn)僅由一輛運(yùn)輸車輛服務(wù)；式(7)指運(yùn)輸車在某租賃點(diǎn)的服務(wù)時(shí)刻必須滿足時(shí)間窗約束。

2 改進(jìn)的混合智能水滴算法

2.1 算法步驟

水流在地面上流動(dòng)會自動(dòng)繞開障礙物，水流可以看成水滴iwd組成的群體，水滴流動(dòng)時(shí)速度為veliwd，水所攜帶泥土量為soiliwd，路徑泥土量矩陣為sw，各量會隨著水滴在河道中的流動(dòng)而發(fā)生變化直至找到最優(yōu)路徑。定義arc(i,j)代表從站點(diǎn)si到sj的路徑，TIB為每次迭代的最優(yōu)解。為了使其可以求解調(diào)度路徑優(yōu)化問題，且能夠提高算法的效率，對水滴算法進(jìn)行了改進(jìn)，改進(jìn)后算法一般步驟為：

1)初始化算法的各個(gè)參數(shù)，如更新參數(shù)av,bv,cv,as,bs,cs等。

2)重復(fù)步驟(3)～步驟(7)步操作直到迭代次數(shù)達(dá)到iterMax。

3)每只雨滴重復(fù)步驟(a)～步驟(c)操作直到所有雨滴都構(gòu)造了解決方案:

a.當(dāng)一個(gè)雨滴完成了對所有站點(diǎn)的調(diào)度,則計(jì)算下一個(gè)雨滴,否則,轉(zhuǎn)步驟(b);

b.選擇下一個(gè)要服務(wù)的站點(diǎn);

c.更新水滴當(dāng)前動(dòng)態(tài)變量。

4)從本次迭代中得到的所有水滴完整路徑中，找到其中最優(yōu)解。

5)更新最優(yōu)路徑上的泥土量。

6)如果迭代次數(shù)大于一定的值后執(zhí)行變鄰域搜索。

7)更新全局最優(yōu)解TTB:如果cost(TIB)

2.2 調(diào)度服務(wù)站點(diǎn)的選擇

uij=di0+d0j-dij,(0∈{depot}；i,j∈{1,2,…,N})

(8)

則改進(jìn)的概率矩陣為

(9)

(10)

式中r=0.01,FV為可以訪問的站點(diǎn)集合。

雨滴從調(diào)度中心出發(fā)，根據(jù)賭輪法按照式(9)來選擇FV中的站點(diǎn)來服務(wù)，判斷如果對站點(diǎn)進(jìn)行調(diào)度服務(wù)，是否能滿足約束條件，包括時(shí)間窗和容量約束，如果FV中站點(diǎn)都不滿足約束條件則返回調(diào)度中心，將水滴的動(dòng)態(tài)變量恢復(fù)初始值，執(zhí)行換車操作。如果滿足約束條件了，則該站點(diǎn)即為雨滴要服務(wù)的下一站點(diǎn)。

2.3 水滴動(dòng)態(tài)變量的更新

在得到要服務(wù)的站點(diǎn)sj后，將該站點(diǎn)添加到路徑中，更新當(dāng)前的路徑，根據(jù)tj=ti+tij，Q(j)=Q(j)+dj更新到達(dá)新站點(diǎn)的時(shí)間tj和運(yùn)輸車裝載量Q(j)。然后判斷是否滿足懲罰條件，如果滿足懲罰條件,根據(jù)式(1)增加懲罰值。

更新水滴中攜帶的泥土量soiliwd和路徑arc(i,j)中的泥土量sw(i,j)

soiliwd=soiliwd+Δsoil(i,j)

(11)

sw(i,j)=sw(i,j)-αΔsoil(i,j)

(12)

(13)

(14)

式中TTB為當(dāng)前最優(yōu)解，n為水滴到達(dá)目的地的個(gè)數(shù)。

2.4 路徑泥土量的更新

設(shè)在第t迭代的最優(yōu)解為TIB，更新泥土量

(15)

2.5 改進(jìn)的變鄰域搜索

變鄰域搜索主要包含兩個(gè)步驟鄰域變換和局部搜索：

1)用智能水滴算法的最優(yōu)解作為初始解s，sb=s。

2)重復(fù)步驟(3)步操作直到終止條件滿足，最后sb即更新后的解。

3)在鄰域內(nèi)變換解的結(jié)構(gòu)s′:=Nk(s)，在每種鄰域結(jié)構(gòu)里執(zhí)行鄰域搜索：s″:=localsearch(s′)。若新解s″的代價(jià)值小于sb，sb:=s′，依此繼續(xù)在鄰域結(jié)構(gòu)搜索。其中，Nk(s)為s的k鄰域結(jié)構(gòu)。

本文提出了兩種鄰域結(jié)構(gòu)，如圖1所示，在圖1中最上部分為從最優(yōu)解中隨機(jī)選取的兩個(gè)路線，后兩個(gè)圖給出了子路線交換和站點(diǎn)重置法，據(jù)此可以得到兩種鄰域結(jié)構(gòu)N1(s),N2(s)。

圖1 兩種鄰域結(jié)構(gòu)說明

3 仿真實(shí)驗(yàn)與算法分析

3.1 實(shí)驗(yàn)設(shè)計(jì)

本文共設(shè)計(jì)了10個(gè)樣例來測試算法，表1是樣例1數(shù)據(jù)，其他樣例數(shù)據(jù)格式如表1所示。其他參數(shù)如下：as=1，bs=0.1，cs=1，av=1，bv=0.1，cv=1，Cp=0.6，Cw=0.3，α=1，β=1，tij=150dij，ci=ai-120(s)，di=bi+120(s)。

表1 實(shí)驗(yàn)數(shù)據(jù)樣例

3.2 實(shí)驗(yàn)算法對比分析

本文提出的算法對表1數(shù)據(jù)進(jìn)行求解，求得結(jié)果模擬如圖2所示。

圖2 樣例1運(yùn)算結(jié)果模擬

計(jì)算得出共需要4輛車，每輛車的路線如下所示：

第一輛車：1→18→3→21→8→6→10→12→1

第二輛車：1→16→17→24→19→4→1

第三輛車：1→2→13→22→5→1

第四輛車：1→7→23→14→1

算法對10個(gè)樣例測試對比結(jié)果，如表2所示。其中,IHIWD是本文最終的算法，IWD—1是本文提出增加了啟發(fā)式因子和節(jié)約算子以及最大最小調(diào)制機(jī)制后的改進(jìn)智能水滴算法。IWD是改進(jìn)的智能水滴算法，對這個(gè)算法改進(jìn)是為了使其可以用于求解本文中的模型，可以用來對比。如圖3。

表2 樣例的測試結(jié)果

圖3 每代路徑最小代價(jià)對比

從表2中和圖3可以看出改進(jìn)算法的效果，圖3為樣例4 測試結(jié)果，顯示兩種算法每次迭代中路徑的最小代價(jià)的對比，可以看到IWD—1優(yōu)于IWD。如果不對水滴中的泥土量限制，就會出現(xiàn)某條路線泥土量過多過少，算法會過早陷入停滯。節(jié)約算子和啟發(fā)式因子是一種貪心策略，偶爾的貪心策略可得到更優(yōu)的解。而對其融合變鄰域可以提高搜索全局最優(yōu)解的能力。

4 結(jié)束語

1)本文對公共自行車調(diào)度路徑優(yōu)化問題建立了數(shù)學(xué)模型，獨(dú)特地從到達(dá)站點(diǎn)時(shí)間的角度去建立混合時(shí)間窗，以滿足實(shí)際應(yīng)用。對模型的建立既考慮了調(diào)度成本又考慮了居民對自行車使用的滿意度。

2)本文提出了一種求解該問題的改進(jìn)的混合智能水滴算法，在算法改進(jìn)上，融合了改進(jìn)的變鄰域算法，并引入節(jié)約算子等策略，使得得到的結(jié)果更優(yōu)。通過算法對比驗(yàn)證了新算法的有效性和優(yōu)越性，并分析了原因。

本文的算法還存在一些不足，解決方案中沒有計(jì)算出初始時(shí)每輛車的載運(yùn)量和最佳出發(fā)時(shí)間，這個(gè)是未來工作中需要考慮的，下一步工作會對公共自行車智能調(diào)度問題和算法融合策略進(jìn)行更深一步研究。