王天宇，韓 印，夏曉梅

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

0 引言

隨著全球油價的上漲、交通擁擠和噪音、空氣等污染，世界上許多城市鼓勵使用公共交通代替私家車出行[1]。最有趣的解決方案之一是自行車共享系統(tǒng)（BSS），它是一個日益流行的系統(tǒng)。一位顧客使用自行車從一個車站到另一個車站。只要有一個空的上鎖泊位，一輛自行車可以從任何一個車站取出，并可在任何時候返回任何站點。BSS需要的不僅僅是自行車和站點，各種其他設(shè)備和系統(tǒng)（例如：自行車車隊，停車和鎖定機制，用戶界面和結(jié)賬退出協(xié)議和站點網(wǎng)絡(luò)），以及需要維護和管理需求（例如：車隊和站點維修、狀態(tài)信息系統(tǒng)和自行車再分配系統(tǒng)）來維持自行車和站點功能保持在足夠的服務(wù)水平。

大多數(shù)有關(guān)自行車共享系統(tǒng)的研究都集中在其歷史和發(fā)展上[1]，促銷政策和安全問題[2]。在過去的幾年中，很多科學(xué)文章正在研究這些系統(tǒng)中的各種問題，包括戰(zhàn)略和運營設(shè)計。現(xiàn)有的關(guān)于公共自行車的研究主要集中在宏觀層面分析其發(fā)展所遇到的政策性問題[3]、立法監(jiān)管[4]、共享經(jīng)濟發(fā)展[5]以及共享單車調(diào)度優(yōu)化[6]等問題?？傮w而言，較為成熟的研究方向可以歸納為兩類：戰(zhàn)略設(shè)計和運營設(shè)計。

在戰(zhàn)略設(shè)計層面，一些工程研究BSS的戰(zhàn)略規(guī)劃，如選址、網(wǎng)絡(luò)設(shè)計和戰(zhàn)略規(guī)劃目標(biāo)的站點的能力等。國內(nèi)相關(guān)專家，例如吳瑤、龔翔等，都是選取我國某一個城市，將理論研究投入到設(shè)計案例中，進行分析解剖，根據(jù)公共自行車分擔(dān)率和居民出行需求測算出公共自行車的租借需求規(guī)模，再結(jié)合自行車和停車樁的周轉(zhuǎn)率預(yù)測公共自行車的總需求和停車樁的總規(guī)模大小，提出為強化不同的分區(qū)內(nèi)公共自行車的特色功能，各區(qū)站點布局應(yīng)各有所側(cè)重，有所不同，做到了針對性的研究和設(shè)計[7-8]。而國外專家研究則與國內(nèi)略有不同，例如Vogel等，提出了一個合適的模型來測試動態(tài)定位策略對系統(tǒng)性能的影響，但是模型對于戰(zhàn)略規(guī)劃來說是有效的，對于平衡運營卻沒有足夠的細節(jié)來支持[9]。

此外，在運營設(shè)計層面而言，系統(tǒng)的運營必須確保至少具有最低服務(wù)質(zhì)量，以滿足用戶的最大需求并降低運營成本。國外專家，Dell'Olio等調(diào)查了站點的選址問題，并為自行車共享系統(tǒng)的設(shè)計和實現(xiàn)開發(fā)了一種方法。核心是基于對一個給定時期的需求的估算，考慮到站點和租金的價格[10]。而Kadri,et al[11-13]，則是預(yù)測用戶未來的需求、自行車的可用性。我國學(xué)者則指出存在公共自行車系統(tǒng)不兼容、站點分布不合理、站點自行車保護措施欠佳等問題，認為要促進公共自行車的發(fā)展，不僅要解決以上問題，還應(yīng)尋求長期可靠的資金來源以維持系統(tǒng)的可持續(xù)發(fā)展[14]。

綜上所述，系統(tǒng)平衡已經(jīng)成為一個重要的研究方向了，平衡運營可以在不同的模式下進行，有些操作人員使用靜態(tài)平衡，有些則使用動態(tài)平衡，也可以通過考慮這兩種平衡模式來實現(xiàn)[15-16]。在現(xiàn)有文獻中，靜態(tài)平衡問題（SBP）比動態(tài)平衡問題有更多的解決辦法。大多數(shù)研究采用混合整數(shù)規(guī)劃（MIP）技術(shù)。然而，對這些工作的比較是比較困難的，因為大多數(shù)文獻都考慮了不同的問題特征[17-19]。

針對這類問題的不足，本文將重點放在單一車輛路徑問題上，目標(biāo)是在不平衡狀態(tài)下最小化站點的總等待時間，以達到最大程度使用現(xiàn)有資源的目的。本文結(jié)構(gòu)如下：在第1節(jié)中，本文提出問題并對問題進行建模。在第2節(jié)中，本文描述了所提出的分支定界方法以及相關(guān)的下界和上界。在第3節(jié)中，本文案例仿真并討論了實驗結(jié)果。最后，以一些評論和總結(jié)來結(jié)束全文。

1 問題描述和數(shù)學(xué)建模

圖1 各區(qū)間示意圖

本文的問題可以正式定義如下。問題的輸入是一組站點，用一個指定的倉庫，每個站（i）的當(dāng)前狀態(tài)（Ei），一個已知的閾值水平和）表示對于每個車站（i）所需的最小和最大的自行車數(shù)量，最后，在車站之間的時間擴展矩陣（dij）表示從站點i到站點j的在分配車輛的位移時間。平衡車輛的路線是由一個給定的序列表示在訪問順序上的站點。其目的是將在不平衡狀態(tài)下等待時間總和的加權(quán)目標(biāo)最小化，直到車輛到達。一個站點（i）的不平衡（w）表示在平衡操作前的（i）車站的自行車數(shù)量（E）和之前那個站的自行車［R,R］的ii信用等級之間的差距。因此，目標(biāo)函數(shù)值取決于站點的不平衡和車輛的到達站點的時間（ti）。各區(qū)間示意圖如圖1所示：

1.1 問題描述

問題是找到再平衡車輛的一個最優(yōu)調(diào)度，使其加權(quán)時間Σiwi（ti- t0）的總和最小，這里 （ti- t0）是站點仍留在站點（i）的不平衡（wi）的時間。符合條件的問題解決方案的數(shù)量，即使是小的也相當(dāng)可觀，因為結(jié)構(gòu)類似于出行商的問題。因此，可行的Hamiltonian circuits（哈密頓回路） 的數(shù)量是平常的（n-1）!，這里n是站點的數(shù)量）。在多項式時間里精確地解決這個問題太難了。問題的復(fù)雜性變得越來越重要，尤其是當(dāng)n很大時。這一問題屬于強烈的NP—困難問題。

1.2 模型建立

在這一節(jié)中，本文提出SBP的數(shù)學(xué)公式。為了解決這個問題，首先引入以下符號、變量和參數(shù)。

符號：

n——站點的總數(shù)；

N——表示網(wǎng)絡(luò)站點的節(jié)點的集合，i=1,2,…,n；

N0——節(jié)點集合，包括站點和倉庫（0表示），i=0,1,…,n；

Ei——在重新定位操作開始之前，在節(jié)點i的自行車的當(dāng)前數(shù)量；

Ci——站點i的容量（i=1,2,…,n）；

di,j——從站點i到j(luò)的出行時間；

ti——到達站點i的時間，i=1,2,…,n；

wi——站點i的權(quán)重，表示Ei和Ri的自信水平之間的差；

決策變量：xi,j——二元變量，如果站點i在j之前被訪問就為1，否則為0，i=0,1,…,n;j=1,…,n且i≠j。

SBP問題可以由以下模型計算：

目標(biāo)函數(shù)式（1）使加權(quán)次數(shù)的總和最小。約束式（2）迫使從倉庫離開的車輛。約束式（3）表示車輛從倉庫出發(fā)的時間。約束式（4） 確保從（i）到（j）站的車輛的位移所需的最少時間。約束條件式（5） （或式（6）） 是車輛的流量守恒方程（即一個車站只能一次被一輛車訪問）。最后，式（7）是二元約束。

2 分支定界方法

由于問題的復(fù)雜性和分支定界（B&B）方法的搜索策略，本文開發(fā)了這種類型的算法來解決問題。這種方法的目的是通過減少搜索空間找到一個最優(yōu)解。該方法基于不同的工具（下界、支配規(guī)則、上界）。在此部分，給出了建議分支和定界過程的特征。

搜索樹最初由一個根節(jié)點組成，在過程中以動態(tài)的方式開發(fā)。上界由最佳可行解的值初始化，這是由一個或多個元啟發(fā)式算法預(yù)先計算的。選擇的方法是，通過使用選擇策略，從對應(yīng)于未開發(fā)的可行子問題的活節(jié)點組中選擇一個節(jié)點探究。選擇基本上是基于節(jié)點下界的值，它代表了車輛的部分調(diào)度。

分支方案包括在部分調(diào)度之后分配一個新任務(wù)。然后研究選定的節(jié)點，并構(gòu)造節(jié)點的子節(jié)點（序列中未調(diào)度的站點）。這樣，子空間就被分成了其他子空間。然后，為每個子空間計算一個下界。如果這樣一個下界的值等于或大于上界，則會消除子問題（因此，子問題的可行解不可能比最優(yōu)解更好）。使用深度優(yōu)先和最佳優(yōu)先策略來探索搜索空間，它允許在可能的情況下快速更新上界，因此當(dāng)它們的下界值等于或大于上界時，就會消除節(jié)點。

2.1 下 界

邊界函數(shù)是B&B算法效率的主要組成部分，不能被節(jié)點選擇和分支的應(yīng)用策略所抵消。在最好的情況下，給定子問題的邊界函數(shù)的值應(yīng)該等于最優(yōu)解的值，然而，在大多數(shù)情況下，實現(xiàn)這樣的目標(biāo)是NP—困難的。

由于目標(biāo)的目的是使函數(shù)最小化，因此有必要開發(fā)低邊界的良好質(zhì)量。一般來說，計算下界包括放松一些約束，然后解決一個更簡單的問題。

這個從模型SBP的約束式（5）和式（6）放松的下界結(jié)果和加權(quán)最短處理時間的應(yīng)用規(guī)則（WSPT和被稱為史密斯的規(guī)則） 是最優(yōu)的單機調(diào)度問題 （1｜ Σ wjCj），目的在于加權(quán)總完成時間的最小化。這個規(guī)則包括排序工作，以增加它們的比率pj/wj（pj表示工作j的持續(xù)時間，wj表示那項工作的相關(guān)權(quán)重，wj≥0，pj＞0）。

在構(gòu)建路徑（序列）時，放松授權(quán)重新使用相同的弧。下界的值是基于到達節(jié)點j的最小的出行時間di,j，對于給定的節(jié)點，本文分兩步來計算這個下界：

（1）對于已執(zhí)行的調(diào)度，本文將累積次數(shù)的總和加上相應(yīng)的值wi。

（2）對于未執(zhí)行的（未調(diào)度的）作業(yè)，本文將關(guān)聯(lián)人工調(diào)度問題1｜ΣwjCj，其中x（x是未執(zhí)行作業(yè)之一）的處理時間是到達相關(guān)節(jié)點的最短運行時間，并且權(quán)重等于wi。人工問題由史密斯的規(guī)則解決，加權(quán)完成時間被添加到步驟（1）中發(fā)現(xiàn)的值中。

2.2 上界

利用上界的質(zhì)量是提高B&B算法效率的關(guān)鍵因素?；谶@個原因，本文利用遺傳算法來定義上界。

（1）解決方法編碼。使用遺傳算法解決問題的編碼過程通常是最困難的方面。將它們應(yīng)用于特定的問題時，通常很難找到解決方案的適當(dāng)表示，從而易于執(zhí)行交叉過程。SBP解決方案的良好編碼必須確定被訪問站點的順序。一個合適的表示是一個染色體組成的站點的路線。應(yīng)該按照它們在染色體中出現(xiàn)的順序來訪問每個站點。圖2給出了一個9站點的網(wǎng)絡(luò)表示的例子。

（2）交叉。主要的遺傳算子是交叉，它模擬了兩個個體（或者同卵）之間的繁殖。 這是通過從父母的其中一個基因的某些部分和另一人的其他部分進行的，并且在同一個孩子中進行。

（3）停止條件。在遺傳算法中使用的停止條件是給定的迭代次數(shù)。即使本文沒有找到局部或全局最優(yōu)，也不可能收斂，但在給定的時間之后，程序就停止了。停止遺傳算法的其他標(biāo)準(zhǔn)也可以使用（例如，如果在固定的迭代次數(shù)下沒有改進最好的記錄解決方案）。

3 案例仿真與分析

在本節(jié)中，本文將進行數(shù)值實驗，以評估和比較算法。在區(qū)間［0,+10］內(nèi)選取代表各站不平衡的權(quán)重值。對于n=｛10,20 ｝，本文定義了8組實例，具體結(jié)果見表1和表2。對于n=30，本文簡單定義了5個組，具體結(jié)果見表3。因為B&B算法的時間要求更大。本文注意到所有的CPU時間都是秒。為了評估B&B的性能，計算實驗是在相同的實例上進行的，用于評估下界和上界。計算時間限制在7 200s。B&B的性能表現(xiàn)在下面兩張表中，本文使用“BB-NxGy”這個符號，其中x是n的值，y表示組號。報告的參數(shù)如下：

圖2 9站點網(wǎng)絡(luò)示意圖

OPT——最優(yōu)值的平均值；

UB*——最好上界值的平均值；

CPU——在幾秒內(nèi)分支定界計算時間的平均值；

Nbr——探索節(jié)點的平均數(shù)量；

Nd——消除節(jié)點的平均數(shù)量；

Np——在初步消除過程中消除節(jié)點的平均數(shù)量；

Gap（%）——最優(yōu)上限與最優(yōu)值之間的平均差值。

表1 10個站點實驗結(jié)果匯總

表2 20個站點實驗結(jié)果匯總

由上表可以得到以下幾點結(jié)論：

B&B能夠解決多達30個站點的實例；

（1）當(dāng)n更大的時候，初步排除是更有效的，因為通過消除一個節(jié)點包含x剩余任務(wù)（x＜n）本文避免x!可能性和結(jié)果本文減少了B&B的計算時間；

（2）當(dāng)n較大時，所探索的節(jié)點的計算時間和平均數(shù)量都較高。這是由于搜索空間的增加引起的。因此，搜索樹越大，問題就越難解決。

表3 30個站點實驗結(jié)果匯總

得到的結(jié)果表明，在合理的時間內(nèi)可以計算出（n≤30）的最優(yōu)解。此外，開發(fā)的B&B算法可以轉(zhuǎn)化為一種貪婪的搜索算法，它能夠在非常短的計算時間內(nèi)提供良好的解決方案。

4 結(jié)束語

本文研究了考慮靜態(tài)模式的自行車共享系統(tǒng)中的單個車輛調(diào)度問題。本文定義并制定了一個數(shù)學(xué)模型，它的動機是需要將不平衡狀態(tài)下的車站等待時間降到最低。在分支定界的算法中，提出并使用了下界和上界。為了評估和比較本文的算法，在大量的實例上進行了數(shù)值實驗。結(jié)果表明，B&B算法可以解決多達30個節(jié)點的實例。但是，此方法在短計算時間內(nèi)解決更大數(shù)量問題仍然有些力不從心。

在未來的工作中，本文的目標(biāo)是在其他類型的放松的基礎(chǔ)上開發(fā)新的下界，以及一個分支切割的方法來加速本文的算法。此外，新的元啟發(fā)式算法和表示方法的研究似乎很有趣，以提高上界質(zhì)量，從而提高B&B的性能。