基于抽樣和變鄰域搜索的隨機共享單車重平衡問題

賈永基， 惲博文， 許媛媛

(東華大學 旭日工商管理學院， 上海 200051)

隨著我國經濟的迅猛發展，交通運輸需求快速增加，未來仍將長期呈現增長態勢，這導致交通運輸系統的碳排放所占份額越來越大。在2021年全國兩會上，“碳達峰”與“碳中和”首次被寫入政府工作報告。為了如期實現“雙碳”目標，降低交通系統碳排放，須大力推廣零排放的共享單車系統。近20年來，共享單車作為一種低碳、環保的短途出行方式在全球范圍內得到廣泛應用，在緩解交通擁堵、構建綠色出行體系方面做出了極大貢獻[1]。然而，隨著共享單車規模的不斷擴大，供需不匹配現象愈加嚴重，在加大企業運營成本的同時，降低用戶滿意度，這將極大阻礙共享單車行業的健康發展。因而實施有效的共享單車供需重新匹配操作，即共享單車重平衡問題(bike-sharing rebalance problem，BRP)[2]，顯得尤為重要。

在目前的研究成果中，所有參數都已知的確定性BRP研究已較為成熟[3]，而在實際運營場景中，客戶需求、行駛時間等參數都不可避免地會出現波動，因而隨機BRP逐漸引起研究人員的重視。目前隨機BRP的主要求解方法大致可分為4類：需求預測、馬爾可夫決策過程、滾動時域和隨機規劃。Zhang等[4]在預測單車庫存和用戶需求的基礎上建立BRP模型。靳文舟等[5]基于用戶預約數據進行需求預測，構建了考慮用戶滿意度的最小化總成本的BRP模型。陳菁等[6]基于小波神經網絡預測區域需求量構建BRP模型。Federico等[7]利用歷史數據來預測共享單車網絡狀況并在必要時采取重平衡操作。Pan等[8]建立了基于馬爾可夫決策過程的BRP模型，并提出一種基于確定性策略梯度算法的深度學習算法。Legros[9]則使用馬爾可夫決策過程開發一種可實施的決策支持工具，幫助運營商在任何時間決定站點優先級及單車庫存。Zhai等[10]同樣利用馬爾可夫決策過程和線性規劃方法來解決共享單車車隊規模和BRP問題。董紅召等[11]加入模糊時間窗約束，以站點滿意度最大為目標建立公共自行車系統調度模型，采用滾動時域算法來求解該模型。Shui等[12]也采用滾動時域獲得多個階段的靜態子問題，使用改進的人工蜂群算法和路線截斷算法來優化每個階段的重平衡車輛路徑。Maggioni等[13]考慮共享單車隨時間變化的隨機需求，提出兩階段和多階段隨機規劃模型，以確定在次日服務開始時每個站點的最優單車數量。

現實BRP系統中，客戶隨機取車、還車，使得各站點的單車數量時刻處于變化中，因而無法提前獲得較準確的預測數據，導致基于需求預測的重平衡模型的計算結果偏離實際值較大。馬爾可夫決策過程計算復雜，因而其不適合大規模的實際問題求解。滾動時域采用“wait and see”策略等待隨機需求的確定值出現，導致重平衡的時效性較差。隨機規劃是一種事前策略，同時不要求事先知道所有參數的確定值，因而具有更大的使用范圍。據筆者所知，目前還沒有文獻使用隨機規劃方法來研究需求隨機的共享單車重平衡問題(bike-sharing rebalancing problem with stochastic demands，BRPSD)。

使用共享單車企業的歷史數據，可以估計客戶隨機需求的分布概率。為了簡化計算，本文假設客戶需求的分布概率是已知的，因而可以使用拉丁超立方抽樣(Latin hypercube sampling，LHS)來生成一系列具有給定概率的離散場景來表示客戶需求的隨機性。在每個場景下，客戶需求是固定不變的，因而可以使用常規啟發式算法(例如變鄰域搜索算法)進行求解。LHS是一種基于蒙特卡洛模擬的方法。L?hndorf[15]研究流行的隨機場景生成方法，指出蒙特卡洛方法是目前最流行的方法，但其需要大量樣本以確保隨機變量概率分布的準確近似，該缺陷可以使用LHS加以緩解。Nikzad等[16]已證實基于LHS獲得的結果更接近基于大樣本獲得的結果，且在相同數量的場景中，LHS比蒙特卡洛方法可獲得更準確的近似值。因此，本文采用LHS來生成一系列隨機場景。此外，本文重新定義共享單車站點的平衡狀態，提出了表示站點平衡狀態的平衡區間概念，給出了衡量站點重平衡程度的重平衡效應度函數。在此基礎上，建立BRPSD的兩階段隨機規劃模型，并提出了求解該模型的基于LHS的變鄰域搜索算法。

1 問題描述與數學模型

1.1 問題描述

在共享單車系統中，由于單車的單程性所導致的“潮汐現象”會使單車供需不匹配，從而導致用戶滿意度和單車利用率的下降，不利于共享單車行業的可持續發展。共享單車重平衡是指利用運輸車輛將單車從過剩站點運往不足站點，即重新在站點之間分配單車以達到供需平衡。如何經濟、高效地實現共享單車重平衡也就成為共享單車行業亟待解決的關鍵問題。

在共享單車企業實際運營中，為明確工作職責，往往將單車服務區域劃分成多個不關聯的子區域，每個子區域只由一輛運輸車單獨進行重平衡操作。考慮到隨機重平衡問題的復雜性，不失一般性，本文只考慮一輛運輸車輛的情形，且假設每個站點只能被服務一次。BRPSD問題可以描述為：車輛從車庫出發，依次訪問處于不平衡狀態的共享單車站點，通過取車或卸車操作使得所有站點趨于平衡狀態，最后返回車庫，同時考慮車輛行駛距離的最小化和重平衡效用度期望的最大化。

本文所使用的決策變量和符號如表1所示。

表1 決策變量和符號

1.2 平衡區間和重平衡效應度

現有研究多將共享單車站點的平衡狀態設為一個平衡點，但由于客戶取車、還車活動的隨機性，站點的單車數量是波動的，因而平衡點的設置使得重平衡操作不具有穩定性，提高了重平衡成本。因此，本文將站點的平衡狀態由平衡點改為平衡區間[14]，如圖1所示，其中aj是站點j的當前單車數量，bj和[(1-θ)bj,(1+θ)bj]分別是其平衡點和平衡區間。當站點的單車數量在其平衡區間內時，該站點就處于平衡狀態。即使站點單車數量由于客戶活動出現了隨機波動，只要波動范圍不超過平衡區間閾值，就無需進行重平衡操作，這可以大大減少共享單車系統的重平衡需求，從而提高共享單車企業的重平衡效率。

圖1 共享單車系統的平衡區間

由于站點單車數量的隨機性，本模型不強制要求所有站點在被服務后都處于平衡狀態，而采用重平衡效用度[14]來衡量重平衡操作的效益，如圖2所示。在重平衡操作后，若站點j的單車數量處于平衡區間[(1-θ)bj,(1+θ)bj]內，那么其重平衡效用度為1。當單車數量小于平衡區間下界(1-θ)bj或大于平衡區間上界(1+θ)bj時，其重平衡效用度隨aj與平衡區間差值的逐漸增大而逐漸減小。

圖2 站點的重平衡效用度

1.3 兩階段隨機規劃模型

基于LHS的兩階段隨機規劃模型的第一階段為運輸車輛路徑優化模型，最大化共享單車系統的總效益；第二階段基于第一階段所獲得的車輛路徑信息，最大化重平衡效用度期望。第二階段基于第一階段的路徑信息，又影響著第一階段的路徑決策。

第一階段模型(P1)：

(1)

s.t.

(2)

(3)

?S?V,2≤|S|≤n-1

(4)

xij∈{0,1} ?i,j∈V,i≠j

(5)

其中：式(1)表示共享單車系統的總效益，重平衡操作產生正效益，系數為ε1，而車輛行駛成本產生負效益，系數為ε2；式(2)表示每個站點只能被訪問一次；式(3)表示流量平衡；式(4)用于消除子回路；式(5)表示決策變量的取值范圍。

第二階段模型(P2)：

(6)

(7)

?j∈N,ω∈Ω

(8)

lj,ω2=lj,ω1-sj,ω++sj,ω-?j∈N,ω∈Ω

(9)

sj,ω+×sj,ω-=0 ?j∈N,ω∈Ω

(10)

(11)

(12)

(13)

sj,ω+，sj,ω-，fij,ω≥0 ?i,j∈V,i≠j,ω∈Ω

(14)

其中：式(6)表示最大化隨機場景下的重平衡效用度期望；式(7)表示場景ω下運輸車輛的裝載量不大于車輛容量；式(8)表示場景ω下車輛服務站點前后的裝載量之差等于站點被滿足的單車數量；式(9)表示場景ω下站點被服務前后的單車數量之差等于站點被滿足的單車數量；式(10)表示場景ω下站點不能同時具有取車和卸車需求；式(11)表示場景ω下的站點重平衡效用度；式(12)表示決策變量sj,ω+不能超過車輛訪問站點時的剩余容量；式(13)表示決策變量sj,ω-不能超過車輛訪問站點時的裝載量；式(14)表示決策變量的取值范圍。

2 基于LHS的變鄰域搜索算法

2.1 算法流程

BRPSD模型的解由兩部分決定：第一階段的車輛路徑和第二階段一系列隨機場景下的重平衡需求。其中，車輛路徑可表示為(0,i1,i2,…,in,0)，其中0是車庫，而i1,i2,…,in是車輛所訪問站點的一個排列。通過改變站點的順序，可以獲得車輛的不同行駛路徑。顯然，可以通過求解一個旅行商問題來獲得第一階段的最優車輛路徑。本文設計了基于拉丁超立方抽樣的變鄰域搜索(Latin hypercube sampling based variable neighbourhood search，LHS-VNS)算法來求解BRPSD問題，該算法流程如圖3所示。

圖3 LHS-VNS算法流程圖

首先，采用LHS生成一系列隨機場景，每個場景都具有相同的概率。接著，使用商業優化軟件CPLEX求解第一階段模型P1，獲得車輛最優路徑。然后，將車輛最優路徑代入第二階段模型P2，求解該路徑在所有場景下完成重平衡操作后達到的重平衡效用度期望的最大值。如果沒有達到停止條件，則利用變鄰域搜索(variable neighbourhood search，VNS)算法來獲得新的車輛路徑，并將其代入模型P2進行計算，否則結束迭代，輸出車輛最優路徑及目標函數F的值。

2.2 隨機場景生成

選擇適當的場景生成方法并確定最佳場景數是求解BRPSD的首要問題。為了獲得好的場景分布，本文使用LHS來生成隨機場景。LHS是一種分層隨機抽樣，具有均勻分層的特性，可以在較少抽樣的情況下保證每個變量范圍的全覆蓋。假設有k個變量x1,x2,…,xk,要從規定的區間中取出N個樣本，首先計算每個變量的累積分布，并將其分成N個相同的小區間，隨后從每個區間中隨機選擇一個值，如圖4所示，這樣每一個變量都會獲得N個值，最后將不同變量的值進行隨機組合，從而獲得所需樣本。在進行抽樣時，為了簡化計算，本文假設每個抽樣的概率都是相同的。

圖4 拉丁超立方抽樣

2.3 站點重平衡需求計算

在第一階段結果的基礎上，第二階段求解一系列隨機場景下共享單車站點的重平衡需求。設站點j的最佳單車數量L=0.5Hj，其在場景ω下的重平衡需求計算過程如圖5所示。如果lj,ω1L，站點j需要取走單車，若此時車輛剩余容量足夠，則將多余單車移走使得站點j的單車降低到最佳數量L，否則將車輛裝滿即可。

圖5 場景ω下重平衡需求計算過程

2.4 VNS算法

Mladenovic等[17]在1997年提出VNS算法，該算法容易實現，通用性強，目前已經被廣泛用于求解各類組合優化問題[18]。本文采用包括3種鄰域結構(見圖6)的VNS算法來生成新的運輸車輛路徑，每次隨機選擇其中一種鄰域結構來執行。(1)點插入：隨機選擇一個站點，將其從原始位置上移除，并插入到另外一個隨機位置，如圖6(a)所示。(2)節點交換：隨機選擇兩個站點，交換其位置，如圖6(b)所示。(3)2-opt：隨機選擇兩個站點，將它們之間的站點逆序，如圖6(c)所示。

圖6 鄰域結構

3 仿真測試

使用MATLAB R2014b軟件編程實現LHS-VNS算法，所有試驗都是在Intel Core i5-8265U和8 GB RAM的筆記本電腦上運行。

3.1 測試算例與參數設置

為測試LHS-VNS算法的有效性，隨機生成站點規模分別為15、20、25和30的4組測試實例，每組3個算例。站點的坐標是在緯度31.17°～31.23°和經度121.37°～121.45°內隨機生成的，車庫位于區域中心，其坐標為(31.20°，121.41°)。站點容量均為100。假設客戶需求服從正態分布，所有算例中客戶需求的均值和標準差如表2所示。其他參數如下：平衡區間閾值θ=0.2，站點平衡區間均為[40,60]；運輸車輛容量為50，出庫時的裝載量為10；系數ε1和ε2分別取0.5和0.8；抽取的樣本數分別為75、100、125和150，迭代次數為10 000。

表2 客戶需求的均值與標準差

3.2 場景生成效果分析

本節計算LHS所獲得樣本的均值和標準差，以及與所設定的均值及標準差的絕對差，并與蒙特卡洛抽樣的結果進行了對比。算例1的對比結果如表3所示，樣本量均為75。由表3可以看出，LHS所獲樣本的均值絕對差和標準差絕對差的絕大部分都優于蒙特卡洛抽樣，且LHS樣本的均值與設定均值的絕對差值都小于0.10，標準差的絕對差值都小于0.40，而蒙特卡洛抽樣的波動較大，其均值絕對差值和標準差絕對差值最高都超過了1.00。由此說明LHS的抽樣效果優于蒙特卡洛抽樣。

表3 LHS與蒙特卡洛抽樣對比結果

將算例6的樣本量分別設為50、75、100、125、150和175，LHS的抽樣結果如表4所示。由表4可以看出，隨著樣本量的增大，F的最大值趨于穩定，所有樣本的車輛路徑均相同，但抽樣運行時間卻隨著樣本量的增加而增加。這也驗證了LHS的優勢，可以使用較小的樣本量來生成隨機場景，在縮短計算時間的同時獲得大致相同的計算結果。

表4 樣本量分析

3.3 求解結果分析

基于樣本量為100的一系列隨機場景，每個算例均運行10次，所求得目標F的最大值、最小值、均值和標準差如表5所示。由表5可以看出，同一規模算例的F均值和運行時間均相差不大，而規模越大的算例，其F值和運行時間越大。此外，所有算例的標準差都小于1.00，說明算法具有良好的穩健性，其中小規模算例1和算例3的標準差為0，說明這兩個算例10次的運算結果均相同。

表5 求解結果

為了進一步驗證本文算法求解大規模算例的性能，采用同樣的方法生成站點規模分別為50(算例13～15)和60(算例16～18)的兩組算例。設樣本量為100，每組算例均運行10次的求解結果如表6所示。由表6可以看出，所求得結果的穩定性可以接受，但運行時間差異較大。

表6 大規模算例求解結果

4 結 語

針對需求隨機的共享單車重平衡問題，引入平衡區間代替平衡點來表示站點的平衡狀態，提出了衡量站點平衡程度的重平衡效應度，通過LHS得到一系列具有相同概率的隨機場景來表示客戶的隨機需求，提出了BRPSD兩階段隨機規劃模型的數學表達。由于該問題是NP-hard問題，因此提出了求解該模型的LHS-VNS啟發式算法。為了驗證該算法的有效性，設計了多種規模的測試算例，測試結果表明：(1)與蒙特卡洛抽樣相比，LHS的抽樣效果更優也更穩定，其運行時間更短；(2)LHS-VNS可在較短時間內獲得BRPSD的穩定結果，具有良好的穩健性。

未來的研究方向：一方面可以關注提高LHS-VNS的運行效率，以縮短較大規模算例的運行時間；另一方面可以研究使用多輛運輸車同時進行重平衡操作，從而擴展本文提出的BRPSD模型。