基于自行車共享系統靜態再平衡問題的分支定界算法

王天宇，韓 印，夏曉梅

（上海理工大學 管理學院，上海 200093）

0 引言

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

大多數有關自行車共享系統的研究都集中在其歷史和發展上[1]，促銷政策和安全問題[2]。在過去的幾年中，很多科學文章正在研究這些系統中的各種問題，包括戰略和運營設計。現有的關于公共自行車的研究主要集中在宏觀層面分析其發展所遇到的政策性問題[3]、立法監管[4]、共享經濟發展[5]以及共享單車調度優化[6]等問題。總體而言，較為成熟的研究方向可以歸納為兩類：戰略設計和運營設計。

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

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

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

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

1 問題描述和數學建模

圖1 各區間示意圖

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

1.1 問題描述

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

1.2 模型建立

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

符號：

n——站點的總數；

N——表示網絡站點的節點的集合，i=1,2,…,n；

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

Ei——在重新定位操作開始之前，在節點i的自行車的當前數量；

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

di,j——從站點i到j的出行時間；

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

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

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

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

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

2 分支定界方法

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

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

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

2.1 下 界

邊界函數是B&B算法效率的主要組成部分，不能被節點選擇和分支的應用策略所抵消。在最好的情況下，給定子問題的邊界函數的值應該等于最優解的值，然而，在大多數情況下，實現這樣的目標是NP—困難的。

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

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

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

（1）對于已執行的調度，本文將累積次數的總和加上相應的值wi。

（2）對于未執行的（未調度的）作業，本文將關聯人工調度問題1｜ΣwjCj，其中x（x是未執行作業之一）的處理時間是到達相關節點的最短運行時間，并且權重等于wi。人工問題由史密斯的規則解決，加權完成時間被添加到步驟（1）中發現的值中。

2.2 上界

利用上界的質量是提高B&B算法效率的關鍵因素。基于這個原因，本文利用遺傳算法來定義上界。

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

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

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

3 案例仿真與分析

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

圖2 9站點網絡示意圖

OPT——最優值的平均值；

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

CPU——在幾秒內分支定界計算時間的平均值；

Nbr——探索節點的平均數量；

Nd——消除節點的平均數量；

Np——在初步消除過程中消除節點的平均數量；

Gap（%）——最優上限與最優值之間的平均差值。

表1 10個站點實驗結果匯總

表2 20個站點實驗結果匯總

由上表可以得到以下幾點結論：

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

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

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

表3 30個站點實驗結果匯總

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

4 結束語

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

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