王天宇,韓 印,夏曉梅
(上海理工大學(xué) 管理學(xué)院,上海 200093)
隨著全球油價(jià)的上漲、交通擁擠和噪音、空氣等污染,世界上許多城市鼓勵(lì)使用公共交通代替私家車(chē)出行[1]。最有趣的解決方案之一是自行車(chē)共享系統(tǒng)(BSS),它是一個(gè)日益流行的系統(tǒng)。一位顧客使用自行車(chē)從一個(gè)車(chē)站到另一個(gè)車(chē)站。只要有一個(gè)空的上鎖泊位,一輛自行車(chē)可以從任何一個(gè)車(chē)站取出,并可在任何時(shí)候返回任何站點(diǎn)。BSS需要的不僅僅是自行車(chē)和站點(diǎn),各種其他設(shè)備和系統(tǒng)(例如:自行車(chē)車(chē)隊(duì),停車(chē)和鎖定機(jī)制,用戶(hù)界面和結(jié)賬退出協(xié)議和站點(diǎn)網(wǎng)絡(luò)),以及需要維護(hù)和管理需求(例如:車(chē)隊(duì)和站點(diǎn)維修、狀態(tài)信息系統(tǒng)和自行車(chē)再分配系統(tǒng))來(lái)維持自行車(chē)和站點(diǎn)功能保持在足夠的服務(wù)水平。
大多數(shù)有關(guān)自行車(chē)共享系統(tǒng)的研究都集中在其歷史和發(fā)展上[1],促銷(xiāo)政策和安全問(wèn)題[2]。在過(guò)去的幾年中,很多科學(xué)文章正在研究這些系統(tǒng)中的各種問(wèn)題,包括戰(zhàn)略和運(yùn)營(yíng)設(shè)計(jì)。現(xiàn)有的關(guān)于公共自行車(chē)的研究主要集中在宏觀層面分析其發(fā)展所遇到的政策性問(wèn)題[3]、立法監(jiān)管[4]、共享經(jīng)濟(jì)發(fā)展[5]以及共享單車(chē)調(diào)度優(yōu)化[6]等問(wèn)題。總體而言,較為成熟的研究方向可以歸納為兩類(lèi):戰(zhàn)略設(shè)計(jì)和運(yùn)營(yíng)設(shè)計(jì)。
在戰(zhàn)略設(shè)計(jì)層面,一些工程研究BSS的戰(zhàn)略規(guī)劃,如選址、網(wǎng)絡(luò)設(shè)計(jì)和戰(zhàn)略規(guī)劃目標(biāo)的站點(diǎn)的能力等。國(guó)內(nèi)相關(guān)專(zhuān)家,例如吳瑤、龔翔等,都是選取我國(guó)某一個(gè)城市,將理論研究投入到設(shè)計(jì)案例中,進(jìn)行分析解剖,根據(jù)公共自行車(chē)分擔(dān)率和居民出行需求測(cè)算出公共自行車(chē)的租借需求規(guī)模,再結(jié)合自行車(chē)和停車(chē)樁的周轉(zhuǎn)率預(yù)測(cè)公共自行車(chē)的總需求和停車(chē)樁的總規(guī)模大小,提出為強(qiáng)化不同的分區(qū)內(nèi)公共自行車(chē)的特色功能,各區(qū)站點(diǎn)布局應(yīng)各有所側(cè)重,有所不同,做到了針對(duì)性的研究和設(shè)計(jì)[7-8]。而國(guó)外專(zhuān)家研究則與國(guó)內(nèi)略有不同,例如Vogel等,提出了一個(gè)合適的模型來(lái)測(cè)試動(dòng)態(tài)定位策略對(duì)系統(tǒng)性能的影響,但是模型對(duì)于戰(zhàn)略規(guī)劃來(lái)說(shuō)是有效的,對(duì)于平衡運(yùn)營(yíng)卻沒(méi)有足夠的細(xì)節(jié)來(lái)支持[9]。
此外,在運(yùn)營(yíng)設(shè)計(jì)層面而言,系統(tǒng)的運(yùn)營(yíng)必須確保至少具有最低服務(wù)質(zhì)量,以滿足用戶(hù)的最大需求并降低運(yùn)營(yíng)成本。國(guó)外專(zhuān)家,Dell'Olio等調(diào)查了站點(diǎn)的選址問(wèn)題,并為自行車(chē)共享系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)開(kāi)發(fā)了一種方法。核心是基于對(duì)一個(gè)給定時(shí)期的需求的估算,考慮到站點(diǎn)和租金的價(jià)格[10]。而Kadri,et al[11-13],則是預(yù)測(cè)用戶(hù)未來(lái)的需求、自行車(chē)的可用性。我國(guó)學(xué)者則指出存在公共自行車(chē)系統(tǒng)不兼容、站點(diǎn)分布不合理、站點(diǎn)自行車(chē)保護(hù)措施欠佳等問(wèn)題,認(rèn)為要促進(jìn)公共自行車(chē)的發(fā)展,不僅要解決以上問(wèn)題,還應(yīng)尋求長(zhǎng)期可靠的資金來(lái)源以維持系統(tǒng)的可持續(xù)發(fā)展[14]。
綜上所述,系統(tǒng)平衡已經(jīng)成為一個(gè)重要的研究方向了,平衡運(yùn)營(yíng)可以在不同的模式下進(jìn)行,有些操作人員使用靜態(tài)平衡,有些則使用動(dòng)態(tài)平衡,也可以通過(guò)考慮這兩種平衡模式來(lái)實(shí)現(xiàn)[15-16]。在現(xiàn)有文獻(xiàn)中,靜態(tài)平衡問(wèn)題(SBP)比動(dòng)態(tài)平衡問(wèn)題有更多的解決辦法。大多數(shù)研究采用混合整數(shù)規(guī)劃(MIP)技術(shù)。然而,對(duì)這些工作的比較是比較困難的,因?yàn)榇蠖鄶?shù)文獻(xiàn)都考慮了不同的問(wèn)題特征[17-19]。
針對(duì)這類(lèi)問(wèn)題的不足,本文將重點(diǎn)放在單一車(chē)輛路徑問(wèn)題上,目標(biāo)是在不平衡狀態(tài)下最小化站點(diǎn)的總等待時(shí)間,以達(dá)到最大程度使用現(xiàn)有資源的目的。本文結(jié)構(gòu)如下:在第1節(jié)中,本文提出問(wèn)題并對(duì)問(wèn)題進(jìn)行建模。在第2節(jié)中,本文描述了所提出的分支定界方法以及相關(guān)的下界和上界。在第3節(jié)中,本文案例仿真并討論了實(shí)驗(yàn)結(jié)果。最后,以一些評(píng)論和總結(jié)來(lái)結(jié)束全文。
圖1 各區(qū)間示意圖
本文的問(wèn)題可以正式定義如下。問(wèn)題的輸入是一組站點(diǎn),用一個(gè)指定的倉(cāng)庫(kù),每個(gè)站(i)的當(dāng)前狀態(tài)(Ei),一個(gè)已知的閾值水平和)表示對(duì)于每個(gè)車(chē)站(i)所需的最小和最大的自行車(chē)數(shù)量,最后,在車(chē)站之間的時(shí)間擴(kuò)展矩陣(dij)表示從站點(diǎn)i到站點(diǎn)j的在分配車(chē)輛的位移時(shí)間。平衡車(chē)輛的路線是由一個(gè)給定的序列表示在訪問(wèn)順序上的站點(diǎn)。其目的是將在不平衡狀態(tài)下等待時(shí)間總和的加權(quán)目標(biāo)最小化,直到車(chē)輛到達(dá)。一個(gè)站點(diǎn)(i)的不平衡(w)表示在平衡操作前的(i)車(chē)站的自行車(chē)數(shù)量(E)和之前那個(gè)站的自行車(chē)[R,R]的ii信用等級(jí)之間的差距。因此,目標(biāo)函數(shù)值取決于站點(diǎn)的不平衡和車(chē)輛的到達(dá)站點(diǎn)的時(shí)間(ti)。各區(qū)間示意圖如圖1所示:
問(wèn)題是找到再平衡車(chē)輛的一個(gè)最優(yōu)調(diào)度,使其加權(quán)時(shí)間Σiwi(ti- t0)的總和最小,這里 (ti- t0)是站點(diǎn)仍留在站點(diǎn)(i)的不平衡(wi)的時(shí)間。符合條件的問(wèn)題解決方案的數(shù)量,即使是小的也相當(dāng)可觀,因?yàn)榻Y(jié)構(gòu)類(lèi)似于出行商的問(wèn)題。因此,可行的Hamiltonian circuits(哈密頓回路) 的數(shù)量是平常的(n-1)!,這里n是站點(diǎn)的數(shù)量)。在多項(xiàng)式時(shí)間里精確地解決這個(gè)問(wèn)題太難了。問(wèn)題的復(fù)雜性變得越來(lái)越重要,尤其是當(dāng)n很大時(shí)。這一問(wèn)題屬于強(qiáng)烈的NP—困難問(wèn)題。
在這一節(jié)中,本文提出SBP的數(shù)學(xué)公式。為了解決這個(gè)問(wèn)題,首先引入以下符號(hào)、變量和參數(shù)。
符號(hào):
n——站點(diǎn)的總數(shù);
N——表示網(wǎng)絡(luò)站點(diǎn)的節(jié)點(diǎn)的集合,i=1,2,…,n;
N0——節(jié)點(diǎn)集合,包括站點(diǎn)和倉(cāng)庫(kù)(0表示),i=0,1,…,n;
Ei——在重新定位操作開(kāi)始之前,在節(jié)點(diǎn)i的自行車(chē)的當(dāng)前數(shù)量;
Ci——站點(diǎn)i的容量(i=1,2,…,n);
di,j——從站點(diǎn)i到j(luò)的出行時(shí)間;
ti——到達(dá)站點(diǎn)i的時(shí)間,i=1,2,…,n;
wi——站點(diǎn)i的權(quán)重,表示Ei和Ri的自信水平之間的差;
決策變量:xi,j——二元變量,如果站點(diǎn)i在j之前被訪問(wèn)就為1,否則為0,i=0,1,…,n;j=1,…,n且i≠j。
SBP問(wèn)題可以由以下模型計(jì)算:
目標(biāo)函數(shù)式(1)使加權(quán)次數(shù)的總和最小。約束式(2)迫使從倉(cāng)庫(kù)離開(kāi)的車(chē)輛。約束式(3)表示車(chē)輛從倉(cāng)庫(kù)出發(fā)的時(shí)間。約束式(4) 確保從(i)到(j)站的車(chē)輛的位移所需的最少時(shí)間。約束條件式(5) (或式(6)) 是車(chē)輛的流量守恒方程(即一個(gè)車(chē)站只能一次被一輛車(chē)訪問(wèn))。最后,式(7)是二元約束。
由于問(wèn)題的復(fù)雜性和分支定界(B&B)方法的搜索策略,本文開(kāi)發(fā)了這種類(lèi)型的算法來(lái)解決問(wèn)題。這種方法的目的是通過(guò)減少搜索空間找到一個(gè)最優(yōu)解。該方法基于不同的工具(下界、支配規(guī)則、上界)。在此部分,給出了建議分支和定界過(guò)程的特征。
搜索樹(shù)最初由一個(gè)根節(jié)點(diǎn)組成,在過(guò)程中以動(dòng)態(tài)的方式開(kāi)發(fā)。上界由最佳可行解的值初始化,這是由一個(gè)或多個(gè)元啟發(fā)式算法預(yù)先計(jì)算的。選擇的方法是,通過(guò)使用選擇策略,從對(duì)應(yīng)于未開(kāi)發(fā)的可行子問(wèn)題的活節(jié)點(diǎn)組中選擇一個(gè)節(jié)點(diǎn)探究。選擇基本上是基于節(jié)點(diǎn)下界的值,它代表了車(chē)輛的部分調(diào)度。
分支方案包括在部分調(diào)度之后分配一個(gè)新任務(wù)。然后研究選定的節(jié)點(diǎn),并構(gòu)造節(jié)點(diǎn)的子節(jié)點(diǎn)(序列中未調(diào)度的站點(diǎn))。這樣,子空間就被分成了其他子空間。然后,為每個(gè)子空間計(jì)算一個(gè)下界。如果這樣一個(gè)下界的值等于或大于上界,則會(huì)消除子問(wèn)題(因此,子問(wèn)題的可行解不可能比最優(yōu)解更好)。使用深度優(yōu)先和最佳優(yōu)先策略來(lái)探索搜索空間,它允許在可能的情況下快速更新上界,因此當(dāng)它們的下界值等于或大于上界時(shí),就會(huì)消除節(jié)點(diǎn)。
邊界函數(shù)是B&B算法效率的主要組成部分,不能被節(jié)點(diǎn)選擇和分支的應(yīng)用策略所抵消。在最好的情況下,給定子問(wèn)題的邊界函數(shù)的值應(yīng)該等于最優(yōu)解的值,然而,在大多數(shù)情況下,實(shí)現(xiàn)這樣的目標(biāo)是NP—困難的。
由于目標(biāo)的目的是使函數(shù)最小化,因此有必要開(kāi)發(fā)低邊界的良好質(zhì)量。一般來(lái)說(shuō),計(jì)算下界包括放松一些約束,然后解決一個(gè)更簡(jiǎn)單的問(wèn)題。
這個(gè)從模型SBP的約束式(5)和式(6)放松的下界結(jié)果和加權(quán)最短處理時(shí)間的應(yīng)用規(guī)則(WSPT和被稱(chēng)為史密斯的規(guī)則) 是最優(yōu)的單機(jī)調(diào)度問(wèn)題 (1| Σ wjCj),目的在于加權(quán)總完成時(shí)間的最小化。這個(gè)規(guī)則包括排序工作,以增加它們的比率pj/wj(pj表示工作j的持續(xù)時(shí)間,wj表示那項(xiàng)工作的相關(guān)權(quán)重,wj≥0,pj>0)。
在構(gòu)建路徑(序列)時(shí),放松授權(quán)重新使用相同的弧。下界的值是基于到達(dá)節(jié)點(diǎn)j的最小的出行時(shí)間di,j,對(duì)于給定的節(jié)點(diǎn),本文分兩步來(lái)計(jì)算這個(gè)下界:
(1)對(duì)于已執(zhí)行的調(diào)度,本文將累積次數(shù)的總和加上相應(yīng)的值wi。
(2)對(duì)于未執(zhí)行的(未調(diào)度的)作業(yè),本文將關(guān)聯(lián)人工調(diào)度問(wèn)題1|ΣwjCj,其中x(x是未執(zhí)行作業(yè)之一)的處理時(shí)間是到達(dá)相關(guān)節(jié)點(diǎn)的最短運(yùn)行時(shí)間,并且權(quán)重等于wi。人工問(wèn)題由史密斯的規(guī)則解決,加權(quán)完成時(shí)間被添加到步驟(1)中發(fā)現(xiàn)的值中。
利用上界的質(zhì)量是提高B&B算法效率的關(guān)鍵因素?;谶@個(gè)原因,本文利用遺傳算法來(lái)定義上界。
(1)解決方法編碼。使用遺傳算法解決問(wèn)題的編碼過(guò)程通常是最困難的方面。將它們應(yīng)用于特定的問(wèn)題時(shí),通常很難找到解決方案的適當(dāng)表示,從而易于執(zhí)行交叉過(guò)程。SBP解決方案的良好編碼必須確定被訪問(wèn)站點(diǎn)的順序。一個(gè)合適的表示是一個(gè)染色體組成的站點(diǎn)的路線。應(yīng)該按照它們?cè)谌旧w中出現(xiàn)的順序來(lái)訪問(wèn)每個(gè)站點(diǎn)。圖2給出了一個(gè)9站點(diǎn)的網(wǎng)絡(luò)表示的例子。
(2)交叉。主要的遺傳算子是交叉,它模擬了兩個(gè)個(gè)體(或者同卵)之間的繁殖。 這是通過(guò)從父母的其中一個(gè)基因的某些部分和另一人的其他部分進(jìn)行的,并且在同一個(gè)孩子中進(jìn)行。
(3)停止條件。在遺傳算法中使用的停止條件是給定的迭代次數(shù)。即使本文沒(méi)有找到局部或全局最優(yōu),也不可能收斂,但在給定的時(shí)間之后,程序就停止了。停止遺傳算法的其他標(biāo)準(zhǔn)也可以使用(例如,如果在固定的迭代次數(shù)下沒(méi)有改進(jìn)最好的記錄解決方案)。
在本節(jié)中,本文將進(jìn)行數(shù)值實(shí)驗(yàn),以評(píng)估和比較算法。在區(qū)間[0,+10]內(nèi)選取代表各站不平衡的權(quán)重值。對(duì)于n={10,20 },本文定義了8組實(shí)例,具體結(jié)果見(jiàn)表1和表2。對(duì)于n=30,本文簡(jiǎn)單定義了5個(gè)組,具體結(jié)果見(jiàn)表3。因?yàn)锽&B算法的時(shí)間要求更大。本文注意到所有的CPU時(shí)間都是秒。為了評(píng)估B&B的性能,計(jì)算實(shí)驗(yàn)是在相同的實(shí)例上進(jìn)行的,用于評(píng)估下界和上界。計(jì)算時(shí)間限制在7 200s。B&B的性能表現(xiàn)在下面兩張表中,本文使用“BB-NxGy”這個(gè)符號(hào),其中x是n的值,y表示組號(hào)。報(bào)告的參數(shù)如下:
圖2 9站點(diǎn)網(wǎng)絡(luò)示意圖
OPT——最優(yōu)值的平均值;
UB*——最好上界值的平均值;
CPU——在幾秒內(nèi)分支定界計(jì)算時(shí)間的平均值;
Nbr——探索節(jié)點(diǎn)的平均數(shù)量;
Nd——消除節(jié)點(diǎn)的平均數(shù)量;
Np——在初步消除過(guò)程中消除節(jié)點(diǎn)的平均數(shù)量;
Gap(%)——最優(yōu)上限與最優(yōu)值之間的平均差值。
表1 10個(gè)站點(diǎn)實(shí)驗(yàn)結(jié)果匯總
表2 20個(gè)站點(diǎn)實(shí)驗(yàn)結(jié)果匯總
由上表可以得到以下幾點(diǎn)結(jié)論:
B&B能夠解決多達(dá)30個(gè)站點(diǎn)的實(shí)例;
(1)當(dāng)n更大的時(shí)候,初步排除是更有效的,因?yàn)橥ㄟ^(guò)消除一個(gè)節(jié)點(diǎn)包含x剩余任務(wù)(x<n)本文避免x!可能性和結(jié)果本文減少了B&B的計(jì)算時(shí)間;
(2)當(dāng)n較大時(shí),所探索的節(jié)點(diǎn)的計(jì)算時(shí)間和平均數(shù)量都較高。這是由于搜索空間的增加引起的。因此,搜索樹(shù)越大,問(wèn)題就越難解決。
表3 30個(gè)站點(diǎn)實(shí)驗(yàn)結(jié)果匯總
得到的結(jié)果表明,在合理的時(shí)間內(nèi)可以計(jì)算出(n≤30)的最優(yōu)解。此外,開(kāi)發(fā)的B&B算法可以轉(zhuǎn)化為一種貪婪的搜索算法,它能夠在非常短的計(jì)算時(shí)間內(nèi)提供良好的解決方案。
本文研究了考慮靜態(tài)模式的自行車(chē)共享系統(tǒng)中的單個(gè)車(chē)輛調(diào)度問(wèn)題。本文定義并制定了一個(gè)數(shù)學(xué)模型,它的動(dòng)機(jī)是需要將不平衡狀態(tài)下的車(chē)站等待時(shí)間降到最低。在分支定界的算法中,提出并使用了下界和上界。為了評(píng)估和比較本文的算法,在大量的實(shí)例上進(jìn)行了數(shù)值實(shí)驗(yàn)。結(jié)果表明,B&B算法可以解決多達(dá)30個(gè)節(jié)點(diǎn)的實(shí)例。但是,此方法在短計(jì)算時(shí)間內(nèi)解決更大數(shù)量問(wèn)題仍然有些力不從心。
在未來(lái)的工作中,本文的目標(biāo)是在其他類(lèi)型的放松的基礎(chǔ)上開(kāi)發(fā)新的下界,以及一個(gè)分支切割的方法來(lái)加速本文的算法。此外,新的元啟發(fā)式算法和表示方法的研究似乎很有趣,以提高上界質(zhì)量,從而提高B&B的性能。