公共自行車調度路徑優化算法

馬智超, 徐海濤

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

0 引 言

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

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

1 問題描述與構建數學模型

1.1 問題描述

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

1.2 構建數學模型

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

(1)

如果運輸車k從站點vi向站點vj運行xijk=1，否則，xijk=0。如果對站點vi服務的是運輸車k，yik=1，否則，yik=0。則優化目標如式(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)指運輸車在調度過程中，其車上的自行車的數滿足車輛的載運能力；式(4)指每個租賃點的調度量不超過運輸車的最大載運能力；式(5)指運輸車輛均從車場出發最終回到車場；式(6)指每一個租賃點僅由一輛運輸車輛服務；式(7)指運輸車在某租賃點的服務時刻必須滿足時間窗約束。

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

2.1 算法步驟

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

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

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

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

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

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

c.更新水滴當前動態變量。

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

5)更新最優路徑上的泥土量。

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

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

2.2 調度服務站點的選擇

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

(8)

則改進的概率矩陣為

(9)

(10)

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

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

2.3 水滴動態變量的更新

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

2.4 路徑泥土量的更新

設在第t迭代的最優解為TIB，更新泥土量

(15)

2.5 改進的變鄰域搜索

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

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

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

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

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

圖1 兩種鄰域結構說明

3 仿真實驗與算法分析

3.1 實驗設計

本文共設計了10個樣例來測試算法，表1是樣例1數據，其他樣例數據格式如表1所示。其他參數如下：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 實驗數據樣例

3.2 實驗算法對比分析

本文提出的算法對表1數據進行求解，求得結果模擬如圖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是本文提出增加了啟發式因子和節約算子以及最大最小調制機制后的改進智能水滴算法。IWD是改進的智能水滴算法，對這個算法改進是為了使其可以用于求解本文中的模型，可以用來對比。如圖3。

表2 樣例的測試結果

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

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

4 結束語

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

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

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