多類型公共自行車調(diào)運(yùn)問題

徐國勛， 李妍峰， 李 軍， 徐冠宇

(1.西南交通大學(xué) 經(jīng)濟(jì)管理學(xué)院，四川 成都 610031；2.成都飛機(jī)工業(yè)有限公司，四川 成都 610000)

0 引言

隨著城市化進(jìn)程的不斷加快，城市交通擁堵問題日益嚴(yán)峻，給居民出行帶來諸多不便。自杭州2008在國內(nèi)建立第一個公共自行車系統(tǒng)以來，我國城市公共自行車系統(tǒng)的建設(shè)取得了長足的發(fā)展。截止2016年初，我國共有118個城市擁有公共自行車系統(tǒng)[1]。公共自行車可以有效銜接長距離公共交通，與短距離公共交通形成優(yōu)勢互補(bǔ)，可以替代部分私家車出行，因而已經(jīng)成為城市公共交通系統(tǒng)的重要組成部分。同時，公共自行車還是一種零碳排放的出行工具，符合未來智慧城市的發(fā)展方向。

隨著公共自行車系統(tǒng)的大量建設(shè)和推廣，越來越多的問題產(chǎn)生并亟需解決。倪康康等[2]對國內(nèi)公共自行車系統(tǒng)的發(fā)展?fàn)顩r進(jìn)行了分析，指出目前公共自行車系統(tǒng)運(yùn)營過程中亟待解決的問題主要有：(1)道路騎行的安全問題；(2)道路的交通管理問題；(3)公共自行車借車難、還車難、易損壞；(4)公共自行車系統(tǒng)設(shè)備安裝運(yùn)營以及虧損問題。借車難、還車難是阻礙公共自行車系統(tǒng)發(fā)展的主要問題，即在需要租車的時候發(fā)現(xiàn)站點(diǎn)無車，在需要還車的時候發(fā)現(xiàn)站點(diǎn)無空位。為解決此類難題，需要進(jìn)行合理有效的車輛調(diào)運(yùn)，即調(diào)運(yùn)卡車在公共自行車租賃站點(diǎn)所組成的網(wǎng)絡(luò)中，將某些站點(diǎn)的自行車調(diào)運(yùn)到其它站點(diǎn)去。這類問題被稱為自行車調(diào)運(yùn)問題或者自行車再平衡問題。這類問題的研究又分為動態(tài)和靜態(tài)兩種。當(dāng)自行車系統(tǒng)使用率非常高時，根據(jù)每個站點(diǎn)的實(shí)時需求進(jìn)行實(shí)施調(diào)運(yùn)。當(dāng)自行車系統(tǒng)使用率較低時，選擇在某個時段內(nèi)(如夜間)對各站點(diǎn)進(jìn)行調(diào)運(yùn)。由于自行車系統(tǒng)一般是在晚上進(jìn)行調(diào)運(yùn)，因此現(xiàn)有研究以靜態(tài)模型為主，而對動態(tài)問題的研究非常少，只有文獻(xiàn)[3～7]進(jìn)行了研究。無論是動態(tài)問題還是靜態(tài)問題，已有研究主要以運(yùn)營成本最小和為滿足的需求最小為目標(biāo)，或是采用線性加權(quán)的方法同時考慮著兩個目標(biāo)。

通過對已有文獻(xiàn)的梳理，發(fā)現(xiàn)目前對靜態(tài)公共自行車的研究，除了Li等[17]之外都只針對單類型自行車，多類型自行車的研究處在起步階段。在實(shí)際中，很多城市(如中國的杭州、臺北，荷蘭的鹿特丹、海牙、烏得勒支，英國的倫敦，日本的愛知縣等)已經(jīng)開始將多類型公自行車(如單人座，雙人座，帶小孩座椅等)引入公共自行車系統(tǒng)，在景區(qū)中(如杭州西湖，武漢東湖等)更加普遍也更加受歡迎。針對多類型公共自行車的特點(diǎn)，本文做了以下研究：(1)提出了多類型公共自行車的再平衡問題。針對網(wǎng)絡(luò)中各類型自行車失衡的情況(如地鐵站附近很難租到單人座自行車，景點(diǎn)附近很難租到雙人座自行車等等)，設(shè)計(jì)了一個懲罰系數(shù)。該系數(shù)除了能衡量站內(nèi)已有自行車數(shù)目和目標(biāo)需求的偏差，還可以實(shí)現(xiàn)各租賃站點(diǎn)公共自行車的調(diào)運(yùn)組合優(yōu)化。(2)考慮了調(diào)配時間的限制。在現(xiàn)實(shí)生活中，對公共自行車的調(diào)配一般集中在某個時段(例如夜間)，因此本文將調(diào)配時間限制引入到多類型公共自行車問題。(3)將配送車輛數(shù)目擴(kuò)展至多輛車。Li等[17]對多類型自行車的研究是假定一輛調(diào)運(yùn)車負(fù)責(zé)所有租賃站點(diǎn)的調(diào)運(yùn)，而在現(xiàn)實(shí)中是由第三方物流公司派出多輛調(diào)運(yùn)車輛服務(wù)租賃站點(diǎn)。為了使問題更加貼近實(shí)際情況，本文研究了多輛調(diào)運(yùn)車輛的情況。

1 問題描述及模型建立

1.1 問題描述

本問題定義在完備圖G=(V,A)上。V表示點(diǎn)的集合{0,1…,n}，包括車場和租賃站點(diǎn)，其中0點(diǎn)表示車場，其余為租賃站點(diǎn)。由于自行車調(diào)運(yùn)有第三方物流公司運(yùn)作，因此車場內(nèi)自行車保有數(shù)量為0。A表示弧的集合，A={(i,j);i,j∈V,i≠j}，每條弧對應(yīng)著一個運(yùn)輸成本。

此外，本問題考慮了不同類型車輛之間需求的替代性。即某類自行車缺貨時，有可能由其他類自行車替代使用。若某站點(diǎn)沒有單人自行車，租賃者可使用雙人自行車作為替代。反之，若使用者想租賃一輛雙人自行車，而站點(diǎn)沒有此類車時，可轉(zhuǎn)向使用2輛單人自行車作為替代。而某些情形則不允許替代，如帶小孩的租賃者打算租賃一輛帶小孩座椅的自行車，但該站點(diǎn)沒有此類車，這時租賃者沒有辦法使用其他類自行車作為替代。替代策略可以有效緩解需求，但同時也會產(chǎn)生一個替代懲罰成本，這是由于它的替代，會導(dǎo)致其他站點(diǎn)可供此類自行車使用的數(shù)量減少。

本問題需要合理地安排車輛的調(diào)運(yùn)路線，同時確定在每個站點(diǎn)每類自行車的裝載或卸載數(shù)量，從而使得總成本(包括公共自行車運(yùn)營公司支付給物流公司的運(yùn)輸成本、非均衡懲罰成本和替代懲罰成本)最小化。

2.2 符號說明

在建模過程中需要用到以下符號：

(1)集合

K:調(diào)運(yùn)車輛集合；M:行車種類集合；N:租賃站點(diǎn)集合。

(2)參數(shù)

(3)決策變量

2.3 數(shù)學(xué)模型

(1)

s.t.

輔助約束：

(2)

(3)

裝卸載約束:

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

路徑約束：

(15)

(16)

(17)

(18)

(19)

(20)

其它約束：

(21)

(22)

(23)

3 求解算法

由于本問題是混合整數(shù)規(guī)劃問題，因此是NP問題。當(dāng)問題規(guī)模較小的時候可以用Gurobi，CPLEX等商業(yè)優(yōu)化軟件求解，但當(dāng)問題規(guī)模變大后，這些商業(yè)優(yōu)化軟件在規(guī)定的時間內(nèi)甚至無法求得可行解。因此，本文設(shè)計(jì)了一種混合禁忌搜索算法來求解本問題。在所有的啟發(fā)式算法中，禁忌搜索算法可以在較短時間內(nèi)成功求解TSP問題(如文獻(xiàn)[24])，VRP問題(如文獻(xiàn)[25])，dial-a-ride問題(如文獻(xiàn)[26～28])，Pickup and delivery問題(如文獻(xiàn)[29,30])等一系列路線優(yōu)化問題?？紤]到公共自行車問題也是一類路線優(yōu)化問題，故本文亦采用禁忌搜索算法作為主干算法，用來確定調(diào)運(yùn)車輛的路線。當(dāng)路線被確定后，本文將大規(guī)模數(shù)學(xué)規(guī)劃優(yōu)化器Gurobi 7.0嵌入到禁忌搜索算法中，用以確定多類型公共自行車的調(diào)運(yùn)策略。算法具體流程如下所示：

Step1生成當(dāng)前可行解p；

Step2用p更新Pbest；

Step3將精英集合S設(shè)為空集；

Step4如果滿足終止條件轉(zhuǎn)Step15，否則繼續(xù)執(zhí)行Step5～12，否則轉(zhuǎn)Step13；

Step5在p的領(lǐng)域中找到最好的解p′；

Step6如果p′優(yōu)于pbest，用p′更新pbest；

Step7將pbest放入精英集合S，然后更新精英集合S；

Step8用p′更新p；

Step9如果經(jīng)過IT次迭代仍無法改進(jìn)pbest，則執(zhí)行Step10～12；

Step10從精英集合S中隨機(jī)選出一個解pr，然后將pr從S刪除；

Step11用pr更新p；

Step12重置禁忌表；

Step13返回pbest。

Step 1～3是算法的初始化步驟。在每次迭代過程中采用了最先改進(jìn)下降策略來尋找最好的解(Step 5)。根據(jù)本文所設(shè)計(jì)的藐視準(zhǔn)則，無法改進(jìn)pbest的移動不能放入禁忌表中。如果pbest得到了改進(jìn)，則將pbest放入精英集合S中(Step6～8)。如果經(jīng)過次迭代仍無法改進(jìn)pbest，則從精英集合中隨機(jī)選出一個解pr，然后更新當(dāng)前解p，并將禁忌表清空(Step 9～12)。

3.1 解的表示

假定n個租賃站點(diǎn)由k輛調(diào)運(yùn)車輛來服務(wù)，則解p的長度為(k+n)。其中k個0表示從車場出發(fā)的調(diào)運(yùn)車輛，其余n個自然數(shù)表示各個需要被服務(wù)的租賃站點(diǎn)。圖1給出了k=3，n=7的例子，表示了3條路線：0→1→2→0,0→5→7→4→0和0→6→3→0。

0120574063

圖1 解的表示

3.2 初始解的生成

本文設(shè)計(jì)了一種隨機(jī)選擇機(jī)制的最近鄰算法來生成初始可行解。傳統(tǒng)的最近鄰算法在每次迭代中選擇的是最近的且未被訪問的站點(diǎn)，通過這種簡單的貪心機(jī)制來構(gòu)造可行解。本文所設(shè)計(jì)的算法用隨機(jī)選擇機(jī)制替代了簡單的貪心機(jī)制。算法流程如下：

Step1將客戶點(diǎn)集合S初始化為φ；

Step2將路線的初始點(diǎn)設(shè)置為0；

Step3在所有未被服務(wù)過的站點(diǎn)中選擇總成本fcost最小的三個站點(diǎn)，隨機(jī)選取一個站點(diǎn)j加入到路線末端的站點(diǎn)i之后，然后將j放入S中；

Step4如果未被服務(wù)過的站點(diǎn)只剩s,t最后兩個，則二者被優(yōu)先訪問的概率為Ps和Pt的關(guān)系為Ps+Pt=1，Ps和Pr隨機(jī)分布于區(qū)間(0,1)；

Step5如果S包含所有客戶點(diǎn)，繼續(xù)執(zhí)行以下步驟，否則轉(zhuǎn)Step 3；

Step6將剩余k-1個0點(diǎn)隨機(jī)插入到路線當(dāng)中，構(gòu)造成3.1節(jié)表示的解；

Step7如果生成的解不滿足服務(wù)時間守恒條件，則轉(zhuǎn)Step 1，否則算法結(jié)束。

在Step 3中，fcost的計(jì)算公式如式(22)所示。

(22)

3.3 解的評估

3.4 鄰域算子

鄰域算子是用來從當(dāng)前解中生成新的解。本文設(shè)計(jì)了6中鄰域算子，分別是：子序列隨機(jī)交換，單點(diǎn)隨機(jī)插入，子序列隨機(jī)插入，子序列逆序，子序列逆序后隨機(jī)插入和子序列逆序后隨機(jī)交換。在每次迭代過程中，每個鄰域算子采用均最先改進(jìn)下降策略：一旦某個算子改進(jìn)了當(dāng)前解，則局部搜索從改進(jìn)后新的當(dāng)前解重新開始，直到所有鄰域算子都無法改進(jìn)當(dāng)前解為止。

圖2 鄰域算子

①子序列隨機(jī)交換：在解中隨機(jī)選擇兩條獨(dú)立的子序列，交換這兩條序列的位置。如圖2-a所示。

②單點(diǎn)隨機(jī)插入：在解中隨機(jī)刪除一個點(diǎn)，然后將這個被刪除點(diǎn)重新隨機(jī)插入到解中。如圖2-b所示。

③子序列隨機(jī)插入：在解中隨機(jī)刪除一條子序列，然后將這個被刪除的子序列重新隨機(jī)插入到解中。如圖2-c所示。

④子序列逆序：在解中隨機(jī)選擇一條子序列，然后將該序列逆序。如圖2-d所示。

⑤子路線逆序后隨機(jī)插入：在解中隨機(jī)選擇一條子序列并刪除，然后將該序列逆序后隨機(jī)插入到解中。如圖2-e所示。

⑥子路線逆序后隨機(jī)交換：在解中隨機(jī)選擇兩條獨(dú)立的子序列并且逆序，然后交換這兩條序列的位置。如圖2-f所示。

3.5 禁忌表和藐視準(zhǔn)則

3.6 多樣化策略

本文設(shè)計(jì)了一種基于精英集合的多樣化策略。Nguyen等[31]設(shè)計(jì)了一種精英集合，此集合是由高品質(zhì)解組成的具有多樣性特征的解池，其中這些高品質(zhì)的解在禁忌搜索算法迭代過程中發(fā)現(xiàn)的。當(dāng)算法開始停滯時，精英集合可以使得算法更好地跳出局部最優(yōu)，使得搜索方向朝著全局最優(yōu)前進(jìn)。

精英集合有最大規(guī)模上限，并且在算法開始的時候是空集。精英集合的多樣性是通過不斷地加入新的高質(zhì)量的解，并刪除現(xiàn)有的存在于集合中的某些解來實(shí)現(xiàn)的。與Nguyen等[31]的做法不同，本文對解的刪除是基于解之間的相似度來決定。相似度Δ(pi,pj)表示解pi和pj之間相同弧的總數(shù)，其中Δ(pi,pj)≤n-1，n表示站點(diǎn)的數(shù)目，若有Δ(pi,pj)=n-1，則解pi和pj完全相同。舉例如下，假定解p1=(0,1,2,3,4,0,5,6,7,8),p2=(0,1,2,5,4,0,6,8,3,7)，則p1和p2之間相同弧為(0,1)和(1,2)，因此Δ(p1,p2)=2。算法每次迭代都會將產(chǎn)生的最好的解pbest放入精英集合，但對解做刪除操作時需考慮兩種情況：1)當(dāng)精英集合未達(dá)到規(guī)模上限時，將滿足條件Δ(p,pbest)≥n-2的解全部刪除，目的是提高精英集合的質(zhì)量和多樣性。2)當(dāng)精英集合達(dá)到規(guī)模上限時，刪除與pbest相似度最高的解即可。

4 數(shù)值實(shí)驗(yàn)

本節(jié)通過數(shù)值實(shí)驗(yàn)對問題特性進(jìn)行了描述，并對算法性能進(jìn)行了分析?；旌辖伤阉魉惴ú捎肅#編寫，所有實(shí)驗(yàn)均在i7-2600CPU主頻3.40GHz內(nèi)存16GB的PC上進(jìn)行。

4.1 非均衡懲罰系數(shù)對調(diào)運(yùn)決策的影響

表1 算例參數(shù)設(shè)置

場景1基本場景。

場景2租賃站點(diǎn)2雙人座自行車需求量很大，保有量無法滿足需求，需增加調(diào)入量。

場景3租賃站點(diǎn)3雙人座自行車的需求量很小，同時保有量過多，需增加調(diào)出量。

表2 四種場景下各類型自行車的調(diào)運(yùn)數(shù)量

注：表中負(fù)值表示從配送車上卸載，即站點(diǎn)自行車增加。同理，正值表示往配送車上裝載，即站點(diǎn)自行車減少。

表3 四種場景下目標(biāo)函數(shù)值和調(diào)運(yùn)車輛路線

表3給出了4中場景下調(diào)運(yùn)車輛的運(yùn)行路線以及目標(biāo)函數(shù)值。與場景1相比，場景2，3和4的目標(biāo)函數(shù)值和運(yùn)行路線都發(fā)生了變化。這是由于，不同的懲罰系數(shù)會產(chǎn)生了如表2所示不同的自行車調(diào)運(yùn)組合，進(jìn)而產(chǎn)生了不同了懲罰成本。同時，不同的調(diào)運(yùn)組合會影響調(diào)運(yùn)車輛的訪問順序，故產(chǎn)生了不同的運(yùn)行路線。

4.2 替代策略對調(diào)運(yùn)決策的影響

表4 不同替代策略下的結(jié)果

表4結(jié)果表明替代策略能夠獲得更低成本，因?yàn)榈谝活愖孕熊嚲哂邢鄬^高的非均衡單位懲罰成本，采用替代策略能夠降低第一類自行車非均衡的程度，并使得總的成本降低。該分析表明調(diào)運(yùn)方在操作過程中可采取更加靈活的替代策略，以滿足不同類型自行車的需求。

4.3 混合禁忌搜索性能分析

Nguyen等[31]發(fā)現(xiàn)精英集合規(guī)模增加到一定程度后，對解得改進(jìn)作用開始不顯著。他們的實(shí)驗(yàn)結(jié)果表明精英集合規(guī)模為5時，可以在解的質(zhì)量和求解時間之間達(dá)到均衡。本文采用Nguyen等[30]的做法，將精英集合規(guī)模設(shè)置為5。此外出于求解時間的考慮，本文將設(shè)置為10，算法終止時間設(shè)置為100代。

表5 算法性能比較

表5詳細(xì)給出全部數(shù)據(jù)的求解結(jié)果，Gurobi求解模型(終止時間為2小時)得到的上界(UB)、下界(LB)和反應(yīng)Gurobi求解質(zhì)量的gap。表5還給出了混合禁忌搜索求解結(jié)果，包括運(yùn)行20次得到的求得的目標(biāo)函數(shù)平均值(Avg.obj.)，平均運(yùn)行時間(Avg.cpu)和標(biāo)準(zhǔn)差(Std)，以及反應(yīng)與Gurobi求解下界(LB)差距的相關(guān)gap，其中g(shù)ap=(Avg.obj-LB)/LB。

當(dāng)|N|=10，Gurobi運(yùn)行約100秒后求得了最優(yōu)解。當(dāng)問題規(guī)模逐漸增大(|N|=20,30,60,90)，gap逐漸變大，這種情形下Gurobi在規(guī)定時間內(nèi)只得到了可行解。當(dāng)問題規(guī)模進(jìn)一步變大(|N|=120，Gurobi在規(guī)定的時間內(nèi)無法求得可行解。這表明精確求解方法求解本問題上具有很大局限性。而文本所設(shè)計(jì)的混合禁忌搜索算法穩(wěn)定性較好(標(biāo)準(zhǔn)差均值約25)，同時能在短時間內(nèi)(平均運(yùn)行時間不到4分鐘)可求得所有規(guī)模數(shù)據(jù)的可行解，與精確算法形成了明顯的對比。

為了比較混合禁忌搜索算法的求解質(zhì)量，計(jì)算了相對于Gurobi求解下界的gap。由表5可得，當(dāng)|N|=10，gap=0.2%，而平均運(yùn)行時間約8秒。這意味著當(dāng)問題規(guī)模較小的時候，混合禁忌搜索算法可在非常短的時間內(nèi)求得十分接近最優(yōu)值的可行解。當(dāng)|N|=20,30，混合禁忌搜索求解gap雖然高于Gurobi求解gap，但差距在逐漸變小。當(dāng)|N|=60,90，混合禁忌搜索求解gap比Gurobi求解gap要小，這意味著前者在600秒內(nèi)求解效果比Gurobi求解兩小時還要好。當(dāng)|N|=120，混合禁忌搜索在短時間內(nèi)仍然可以求得可行解。

5 結(jié)束語

本文研究了靜態(tài)環(huán)境下多類型公共自行車問題，以運(yùn)營成本最小目標(biāo)建立了相應(yīng)的混合整數(shù)規(guī)劃模型。為求解問題，設(shè)計(jì)了混合禁忌搜索算法。其中禁忌搜索用來處理調(diào)運(yùn)車輛路線的搜索空間，而租賃站點(diǎn)的各類型公共自行車的調(diào)配組合由嵌入的精確算法來確定。在數(shù)值分析部分，通過不同規(guī)模的算例比較，測試了混合禁忌搜索的性能。結(jié)果混合禁忌搜索能在較短時間內(nèi)求解更大規(guī)模的問題，并且求解質(zhì)量較好。測試算例還展示了非均衡懲罰系數(shù)對調(diào)配策略的影響，結(jié)果表明非均衡懲罰系數(shù)的變化可以決定了租賃站點(diǎn)各類自行車數(shù)量的增減和調(diào)配車輛的運(yùn)行路線，本問題引入的懲罰系數(shù)成功地實(shí)現(xiàn)了不同租賃站點(diǎn)的公共自行車調(diào)運(yùn)組合優(yōu)化的目標(biāo)。不同類型的自行車需求的替代使得調(diào)運(yùn)決策更加靈活。下一步研究可考慮對損壞自行車的回收，動態(tài)環(huán)境下的調(diào)運(yùn)以及和共享單車的比較等等。