公共自行車調(diào)度路徑優(yōu)化算法

馬智超, 徐海濤

(杭州電子科技大學 計算機學院，浙江 杭州 310018)

0 引 言

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

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

1 問題描述與構建數(shù)學模型

1.1 問題描述

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

1.2 構建數(shù)學模型

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

(1)

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

(2)

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

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

2 改進的混合智能水滴算法

2.1 算法步驟

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

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

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

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

a.當一個雨滴完成了對所有站點的調(diào)度,則計算下一個雨滴,否則,轉步驟(b);

b.選擇下一個要服務的站點;

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

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

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

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

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

2.2 調(diào)度服務站點的選擇

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

(8)

則改進的概率矩陣為

(9)

(10)

式中r=0.01,FV為可以訪問的站點集合。

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

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

在得到要服務的站點sj后，將該站點添加到路徑中，更新當前的路徑，根據(jù)tj=ti+tij，Q(j)=Q(j)+dj更新到達新站點的時間tj和運輸車裝載量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為當前最優(yōu)解，n為水滴到達目的地的個數(shù)。

2.4 路徑泥土量的更新

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

(15)

2.5 改進的變鄰域搜索

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

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

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

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

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

圖1 兩種鄰域結構說明

3 仿真實驗與算法分析

3.1 實驗設計

本文共設計了10個樣例來測試算法，表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ù)據(jù)樣例

3.2 實驗算法對比分析

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

圖2 樣例1運算結果模擬

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

表2 樣例的測試結果

圖3 每代路徑最小代價對比

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

4 結束語

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

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

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