帶軟時(shí)間窗的公共自行車調(diào)度路徑問(wèn)題

汪嵐， 吳永春， 陳海洋

( 黎明職業(yè)大學(xué) 智能制造工程學(xué)院， 福建 泉州 362000 )

0 引言

隨著城市交通日趨擁堵，公共自行車作為一種新型環(huán)保的交通工具，已成為了民眾短途出行的重要選擇.目前，公共自行車調(diào)度的路徑選擇多以人工經(jīng)驗(yàn)調(diào)度為主，缺乏科學(xué)性，容易出現(xiàn)無(wú)車可借、無(wú)樁可還的現(xiàn)象；因此，研究公共自行車系統(tǒng)的調(diào)度路徑問(wèn)題對(duì)于均衡租賃站點(diǎn)的自行車資源，提高自行車循環(huán)使用率具有現(xiàn)實(shí)意義.近年來(lái)，很多學(xué)者利用建模與算法來(lái)研究智能調(diào)度問(wèn)題[1-3].但在調(diào)度路徑模型研究中，相關(guān)研究大多僅考慮了硬時(shí)間窗約束，使得研究結(jié)果不能真實(shí)反映車輛的調(diào)度情況[4]；在相關(guān)算法研究中，研究者多采用模擬退火算法[5]、蟻群算法[6]和遺傳算法[7]等傳統(tǒng)算法，而這些算法難以解決日趨復(fù)雜的路徑問(wèn)題.為了尋求一種更合理的自行車調(diào)度路徑規(guī)劃方法，本文在不增加額外投入和變更租賃站點(diǎn)布局的前提下，針對(duì)帶軟時(shí)間窗的公共自行車調(diào)度路徑問(wèn)題，應(yīng)用一種新的改進(jìn)蟻群遺傳算法對(duì)其進(jìn)行求解，并通過(guò)實(shí)例計(jì)算驗(yàn)證本文方法的有效性.

1 帶軟時(shí)間窗的調(diào)度路徑模型

公共自行車調(diào)度問(wèn)題描述：調(diào)度中心根據(jù)各單車租賃站點(diǎn)的借還需求量和迫切度，安排調(diào)度車輛、租賃站點(diǎn)間的服務(wù)順序以及調(diào)度車輛的行駛路線，最終完成調(diào)度作業(yè)并返回調(diào)度中心.故本文中的調(diào)度路徑規(guī)劃原則為：已知調(diào)度中心、各租賃站點(diǎn)位置、自行車供需量和配送車輛的載重、配送時(shí)間以及配送車可達(dá)最遠(yuǎn)距離等信息，在滿足應(yīng)有約束的條件下，合理規(guī)劃車輛調(diào)度路線，最終實(shí)現(xiàn)調(diào)度路徑與成本綜合最優(yōu).

1.1 模型假設(shè)

1) 假設(shè)區(qū)域內(nèi)有且僅有一個(gè)調(diào)度中心負(fù)責(zé)區(qū)域內(nèi)公共自行車的調(diào)度工作，調(diào)度中心的調(diào)度車輛、自行車數(shù)量能夠滿足區(qū)域內(nèi)所有租賃站點(diǎn)的供需量； 2)調(diào)度中心、各租賃站點(diǎn)的位置、彼此之間的距離、各租賃站點(diǎn)的自行車供需量等信息已知； 3)每個(gè)租賃站點(diǎn)的調(diào)度時(shí)間窗已知，不在規(guī)定時(shí)間窗內(nèi)完成的調(diào)度任務(wù)其對(duì)應(yīng)的懲罰措施已知； 4)當(dāng)租賃站點(diǎn)自行車數(shù)量大于總樁數(shù)的80%或小于20%時(shí)，調(diào)度中心派出調(diào)度車對(duì)需要的站點(diǎn)進(jìn)行調(diào)度作業(yè).每輛調(diào)度車由調(diào)度中心出發(fā)，依次完成對(duì)應(yīng)的租賃站點(diǎn)調(diào)度任務(wù)后返回調(diào)度中心.

1.2 模型建立

假設(shè)某區(qū)域內(nèi)公共自行車調(diào)度中心有m輛調(diào)度車輛，車輛的最大載重為Q， 最大行駛距離為D， 已有自行車數(shù)量為q0.假設(shè)節(jié)點(diǎn)標(biāo)號(hào)為i(i=0為調(diào)度中心，i=1，…,n為租賃站點(diǎn))，節(jié)點(diǎn)i到節(jié)點(diǎn)j的距離為di j(di j≠dj i;i，j=0,1,…,n).當(dāng)租賃站點(diǎn)i為自行車調(diào)入狀態(tài)時(shí)，需求量定義為qi(i=1,2,…,n)， 供應(yīng)量為0； 反之，為調(diào)出狀態(tài)時(shí)，供應(yīng)量定義為pi(i=1,2,…,n)， 需求量為0.ci j為節(jié)點(diǎn)i到節(jié)點(diǎn)j的調(diào)度成本.

決策變量定義如下：

1.2.1目標(biāo)函數(shù) 本文將調(diào)度路徑與成本綜合最小作為目標(biāo)函數(shù)，其計(jì)算公式為

(1)

式中，w1、w2為路徑函數(shù)和成本函數(shù)對(duì)應(yīng)的權(quán)重，p(ti)為調(diào)度成本的懲罰函數(shù)，其具體函數(shù)表達(dá)式為

(2)

1.2.2約束條件 調(diào)度過(guò)程的影響因素主要考慮調(diào)度車輛需求變化、行駛距離、調(diào)度時(shí)間以及車輛安排等.除調(diào)度時(shí)間約束(已融入目標(biāo)函數(shù)中)外，其他約束如下：

(3)

式(3)中：約束1限制任意時(shí)刻每輛車上的自行車數(shù)量不大于車輛的最大載重；約束2限制任意一條調(diào)度路徑的總長(zhǎng)度不超過(guò)調(diào)度車輛的最大行駛距離；約束3限制每個(gè)租賃站點(diǎn)的調(diào)度任務(wù)有且只有一輛車負(fù)責(zé)；約束4—6則限制參與調(diào)度的車輛數(shù)不超過(guò)m， 且到達(dá)和離開(kāi)某一租賃站點(diǎn)的車輛只能是一輛.

2 改進(jìn)的蟻群遺傳算法

公共自行車調(diào)度路徑問(wèn)題屬于多旅行商問(wèn)題(MTSP).鑒于蟻群算法含有正反饋機(jī)制，能收斂到最優(yōu)解，但搜索時(shí)間長(zhǎng)；遺傳算法具有較強(qiáng)的全局搜索性能且搜索時(shí)間短，但容易陷入局部最優(yōu)； 2-opt算法適合局部?jī)?yōu)化：因此，本文將改進(jìn)的蟻群算法和2-opt算法融入到改進(jìn)的遺傳算法中，形成一種新的改進(jìn)蟻群遺傳算法.新算法先利用改進(jìn)的蟻群算法生成全局較優(yōu)解，再將較優(yōu)解作為改進(jìn)的遺傳算法的初始種群進(jìn)行求解.

2.1 改進(jìn)的蟻群算法

1)狀態(tài)轉(zhuǎn)移規(guī)則.假設(shè)m只螞蟻，n個(gè)租賃站點(diǎn)，dij、τij(t)分別為任意兩個(gè)節(jié)點(diǎn)之間的距離和信息素.t時(shí)刻時(shí)，螞蟻k將根據(jù)路徑上的信息素強(qiáng)弱從站點(diǎn)i移動(dòng)到站點(diǎn)j， 其狀態(tài)轉(zhuǎn)移規(guī)則[8]為：

(4)

2) 信息素更新.為了防止早熟，對(duì)信息素更新操作進(jìn)行如下改進(jìn)：

① 摒棄傳統(tǒng)蟻群算法中只針對(duì)單只表現(xiàn)最優(yōu)的螞蟻進(jìn)行信息素更新，而是針對(duì)若干精英螞蟻進(jìn)行信息素更新.迭代結(jié)束后，對(duì)各螞蟻移動(dòng)的路徑長(zhǎng)度進(jìn)行排序，排序靠前的l只螞蟻為精英螞蟻.每次迭代僅對(duì)精英螞蟻行走過(guò)的優(yōu)質(zhì)路徑進(jìn)行信息素更新，更新規(guī)則為[9-10]：

(5)

② 信息素更新后，引入最大-最小約束原則，即各路徑信息素必須限制在[τmin，τmax]區(qū)間.當(dāng)信息素超過(guò)極值時(shí)，信息素等于極值，反之信息素維持原值.τmin和τmax的計(jì)算公式為:

τmax(t)=l/ρ·S(Lbest),τmin(t)=τmax(t)/50.

(6)

2.2 改進(jìn)的遺傳算法

1)編碼.采用自然數(shù)編碼，將調(diào)度中心與租賃站點(diǎn)共同排列.假設(shè)0為調(diào)度中心， 1、2、…、n為租賃站點(diǎn)，m為調(diào)度車輛數(shù)，生成長(zhǎng)度為n+m+1的染色體基因串.例如，用3輛調(diào)度車完成7個(gè)租賃站點(diǎn)的自行車配送，其解為03501240670，對(duì)應(yīng)的調(diào)度路線方案為：

車輛1: 0→3→5→0； 車輛2: 0→1→2→4→0； 車輛3: 0→6→7→0.

2) 適值函數(shù)的設(shè)置.適值高低決定個(gè)體進(jìn)入下一代的概率.考慮到適值函數(shù)與目標(biāo)函數(shù)的映射關(guān)系，故本文將適值函數(shù)設(shè)置為

(7)

3) 選擇、交叉操作.選擇操作采用最優(yōu)保存與錦標(biāo)賽法綜合的選擇策略.首先將當(dāng)代最優(yōu)的前30%的精英個(gè)體備份至精英區(qū)；其次將當(dāng)代最優(yōu)個(gè)體直接保留至下一代，剩余個(gè)體采用錦標(biāo)賽的選擇方式，兩兩隨機(jī)進(jìn)行比較，選出較高適值的個(gè)體保留至下一代.重復(fù)錦標(biāo)賽選擇這一過(guò)程，直至達(dá)到種群規(guī)模.這種方式既能保證適值高的個(gè)體較大概率地進(jìn)入到下一代，又能保證種群的多樣性.

交叉操作采用可自適應(yīng)變化的Pc進(jìn)行，交叉率隨迭代變化情況進(jìn)行自適應(yīng)的動(dòng)態(tài)調(diào)整，以有效地控制新個(gè)體生成的速率，相關(guān)設(shè)置詳見(jiàn)文獻(xiàn)[11].

4) 基于2-opt算法的變異操作.為了進(jìn)一步提高算法的收斂速度，引入2-opt算法[12]和翻轉(zhuǎn)完成變異操作.具體方法如下：

(a)原基因串 (b) 變異后的基因串 圖1 基于2-opt算法和翻轉(zhuǎn)變異的示意圖

① 假設(shè)染色體基因串的長(zhǎng)度為n， 隨機(jī)確定一個(gè)下標(biāo)為i(i=1，…，n-3)的基因位置，di,i+1為第i個(gè)基因與第i+1個(gè)基因之間的距離.

② 判斷路徑距離是否滿足di,i+1+di+2,i+3>di,i+2+di+1,i+3， 滿足則判斷路徑可優(yōu)化.將第i+1個(gè)基因與第i+2個(gè)基因進(jìn)行位置調(diào)換，同時(shí)翻轉(zhuǎn)原來(lái)的路徑方向，見(jiàn)圖1.若不滿足，則維持原基因串位置不變.

通過(guò)2-opt算法和路徑翻轉(zhuǎn)的變異操作，能對(duì)基因串起到局部?jī)?yōu)化的作用，使種群的整體性比之前有所提高，使變異操作趨向更優(yōu).

5)算法終結(jié)條件.本文設(shè)定的算法終結(jié)條件為：達(dá)到算法最大進(jìn)化代數(shù)，或一定進(jìn)化代數(shù)范圍內(nèi)適值無(wú)明顯波動(dòng)[13].

2.3 改進(jìn)的蟻群遺傳算法的步驟

第1步 設(shè)定基本參數(shù)，如租賃站點(diǎn)調(diào)入/調(diào)出需求量、調(diào)度車輛最大載重、行駛距離等；改進(jìn)遺傳算法的參數(shù)，如種群規(guī)模popsize、最大進(jìn)化代數(shù)Gen max等；改進(jìn)蟻群算法的參數(shù)，如螞蟻數(shù)量m、 最大進(jìn)化代數(shù)Ncmax、Nc=0、k=1、τij=t0等.采用自然數(shù)編碼，將螞蟻放置調(diào)度中心，螞蟻數(shù)等于車輛數(shù).

第2步 迭代次數(shù)Nc=Nc+1.

第4步 判斷螞蟻k是否訪問(wèn)完所有站點(diǎn)，若未完成，則跳轉(zhuǎn)至第3步；否則令k=k+1.

第5步 判斷m只螞蟻是否都訪問(wèn)完所有站點(diǎn)，若未完成，則跳轉(zhuǎn)至第3步.

第6步 判斷改進(jìn)的蟻群算法是否達(dá)到最大迭代次數(shù)，若未達(dá)到，根據(jù)式(5)和式(6)更新路徑信息素并跳轉(zhuǎn)至第2步.

第7步 將禁忌表里的路徑作為遺傳算法的初始種群P0， 根據(jù)式(7)計(jì)算各個(gè)體的適值.

第8步 將種群中高適值個(gè)體備份至精英區(qū)，然后進(jìn)行選擇、自適應(yīng)交叉、2-opt算法變異操作，生成種群P1(t)， 計(jì)算個(gè)體適值并排序.

第9步 將精英區(qū)個(gè)體替換P1(t)中的靠后個(gè)體，生成種群P2(t).

第10步 判斷遺傳算法終止條件是否滿足，若不滿足，進(jìn)化代數(shù)加1，跳轉(zhuǎn)至第8步；否則算法結(jié)束，輸出全局綜合最優(yōu)調(diào)度路徑和調(diào)度成本.

3 實(shí)例計(jì)算與分析

以某區(qū)域單調(diào)度中心的公共自行車智能調(diào)度系統(tǒng)為例對(duì)本文提出的算法進(jìn)行驗(yàn)證.該區(qū)域共設(shè)有公共自行車租賃站點(diǎn)17個(gè)，同規(guī)格調(diào)度車輛8輛，統(tǒng)一由調(diào)度中心出發(fā).每輛調(diào)度車可運(yùn)載自行車30輛，最大行駛距離為20 km.各租賃站點(diǎn)間的距離、調(diào)入/調(diào)出需求量及時(shí)間窗具體數(shù)據(jù)已知(略).算法的主要參數(shù)設(shè)置為：m=10,Q=30,D=20 km,N=60， Genmax=100，M=1 000，l=u=2，Pc1=0.6,Pc2=0.9，Pm1=0.001,Pm2=0.1,Ncmax=150，α=1，β=2，γ=1，ρ=0.15，l=3，τ0max=1，τ0min=0.05.分別采用模擬退火算法、蟻群算法、遺傳算法和改進(jìn)的蟻群遺傳算法求解調(diào)度路徑，路徑的優(yōu)化結(jié)果如表1所示，路徑的仿真效果如圖2所示.

表1 不同算法優(yōu)化后的結(jié)果

圖2 不同算法優(yōu)化后的調(diào)度路徑圖

從表1和圖2可以看出，改進(jìn)的蟻群遺傳算法的調(diào)度路徑為：0→5→13→0→9→11→17→0→15→14→0→3→10→8→0→2→6→12→16→0→1→7→0→4→0，路徑總長(zhǎng)為143.02 km，比其他3種算法分別縮短了18.4%、24.3%和13.0%，同時(shí)還節(jié)約了調(diào)度成本.

4 結(jié)論

本文運(yùn)用改進(jìn)的蟻群遺傳算法對(duì)自行車調(diào)度路徑模型進(jìn)行求解，以獲得自行車調(diào)度的最優(yōu)路徑.研究表明： ①調(diào)度路徑模型中加入軟時(shí)間窗因素可增強(qiáng)調(diào)度系統(tǒng)的柔性，更符合實(shí)際調(diào)度中車輛實(shí)際存在的情況； ②本文方法比較模擬退火算法等3種傳統(tǒng)算法不僅縮短了調(diào)度路徑，而且節(jié)約了調(diào)度成本,因此本文方法對(duì)自行車調(diào)度路徑規(guī)劃具有很好的參考價(jià)值.本文在建模過(guò)程中僅針對(duì)單調(diào)度中心進(jìn)行了研究，具有一定的局限性，因此后續(xù)將對(duì)多調(diào)度中心的調(diào)度問(wèn)題進(jìn)行研究，以建立一個(gè)更為合理的調(diào)度路徑模型.