基于自行車(chē)共享系統(tǒng)靜態(tài)再平衡問(wèn)題的分支定界算法

王天宇，韓 印，夏曉梅

（上海理工大學(xué) 管理學(xué)院，上海 200093）

0 引言

隨著全球油價(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 問(wèn)題描述和數(shù)學(xué)建模

圖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所示：

1.1 問(wèn)題描述

問(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)題。

1.2 模型建立

在這一節(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）是二元約束。

2 分支定界方法

由于問(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)。

2.1 下 界

邊界函數(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)的值中。

2.2 上界

利用上界的質(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)最好的記錄解決方案）。

3 案例仿真與分析

在本節(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)提供良好的解決方案。

4 結(jié)束語(yǔ)

本文研究了考慮靜態(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的性能。