基于混合整數線性規劃的不可用共享單車回收維修研究

劉海華，干宏程 （上海理工大學 管理學院，上海 200093）

LIU Haihua,GAN Hongcheng (Management School,University of Shanghai for Science and Technology,Shanghai 200093,China)

0 引 言

如今，隨著汽車的普及，道路上的汽車急劇增加，堵車事件每天都在發生，人們浪費在道路上的時間明顯增多，隨之一種可以代替私家車進行短途出行的共享單車應運而生，找到了它的生存空間。目前，在居民的出行方式選擇上，共享單車占據了它的一席之位，解決了“最后一公里”的問題。目前，我國好多大城市，共享單車的投放量已經達到飽和了，占據了大量的城市空間，因此不能再為了利益不斷地向市場投放共享單車，只有追求單車的高使用率才是每個企業可持續發展的關鍵。隨著單車的使用次數增多，共享單車的損壞率不斷提高，而運營商不再繼續投放單車，這樣單車的使用率會逐漸下降，造成了一定程度上的資源浪費，運營商的效益減少，同時用戶在連續碰到損壞車輛后的滿意度也在降低。因此，為了緩解因此造成的經濟損失，需要對這部分的損壞車輛進行回收維修，再投放到市場，從而增加運營商的收益，提高共享單車的利用率，還可以提高用戶的滿意度。

目前，國外學者對于共享單車的研究已經很多，但主要還是集中在城市公共自行車的調度上，總結為有能力的車輛路徑問題（CVRP）。Berbeglia等和Parragh等提出了接受和交付的車輛路徑問題（PDVRPs）的詳細綜述和分類；為了處理更大的實例，Hernández-Pérez和Salazar-González正式提出了一次性接受和交付出行商問題（1-PDTSP），并且提出了數學公式以及分支切割算法；Hernández-Pérez等引入了一個性能良好的鄰近變量下降啟發法；Martinovic等提出了模擬退火（熱處理）的方法；Zhao等則發展了一種遺傳算法。兩種啟發式解法的結果后來被Hosny和Mumford通過可變的鄰域搜索（VNS）法進行改進，但問題是需要很長的計算時間。Raviv等定義了靜態的自行車重新定位問題，提出了兩個MILP公式，一個弧指數和一個時間指數。Contardo等提出了一種自行車再平衡問題的動態版本的公式，允許使用多個車輛[1-3]。

國內對于共享單車的研究還只是停留在共享單車出現所呈現的現象、問題、發展趨勢、政策等分析層面。而對于共享單車的回收維修方面的研究相對較少。常山[4]等人提出了共享單車故障車輛回收的流程，采用K-means算法對共享單車故障車輛進行聚類。王涵霄[5]等人提出在調度作業中對于部分小故障單車進行當場維修，以優化調度模型。

綜上所述，國外主要是對公共自行車再平衡問題進行研究，包括靜態的和動態的。但是目前對于共享單車的回收維修的研究還留有很大空間。本文即對共享單車回收維修進行研究，使用MILP模型進行建模[6]，并考慮到運輸車輛的容量限制，建立有效不等式，并在MATLAB中對分支切割（B&C）算法[7]進行編程求解。

1 模型的建立及分支切割算法

1.1 問題描述及模型建立

本文主要討論的是不可用單車的靜態回收維修。相對于動態，靜態的更容易實現。運營商可以在用戶使用率非常低的時段對共享單車進行回收維修，比如凌晨1點到早5點。

目標函數式（1） 使得出行成本最小。約束式（2） 和式（3） 規定每個站點只訪問一次。約束式（4） 和式（5） 用來確保最多有m輛車離開倉庫，并且所有車輛在開始和結束時都在倉庫。約束式（6）是廣義子路徑消除約束，以保證可行回路的連通性，S為頂點集V｛｝0的任一子集合為集合S中所含圖G的頂點個數。

1.2 分支切割算法（B&C）

上一節的模型包含的約束，在本節中使用分支切割（B&C）算法來解決這些問題。并利用B&C算法解決每個節點上的MILP模型的線性松弛問題。

通過貪婪的優化算法[12-13]獲得一個初始解，從倉庫開始擴展路徑，一次擴展一個站點，當出現不能繼續擴展的時候，車輛返回到倉庫。然后再以迭代的方式開始一條新的路徑。從而xii=0，以及對所有的

1.2.1 有效不等式

在上面的基礎上需要考慮到有效不等式，用來改進算法的收斂性。

首先給出簡單的3個站點的不等式集合，對于一點對i,j，令｝的不可用單車總和大于Q的站點子集，即S則有下面的有效不等式：

上面式子表明由于約束程度，在xjh變量中最多有一個可以取1，且與xij是不相容的。

第二個有效不等式，需要一些額外的說明。這里令P為從倉庫開始的站點序列組成的路徑表示路徑P上的站點數，以及P（）

這里的P是不可行路徑的集合。

1.2.2 分離過程

本節的目的是確定上面的有效不等式是否違反了給定解x的過程。

S1和S2：不等式（8）、式（9）完全被分離，通過枚舉所有可能的站點對i和j，計算集合Sij，看不等式涉及的解x是否大于1。

S3：對于約束式（6）需要建立一個新的圖約束式（6） 和一般的TSP（旅行商問題）一樣，通過計算上的最大流量。需要將其擴展到1-PDTSP的有向情況，在的基礎上添加一個虛點n+1，形成將n+1連接到任意一個i∈V點上，作為接受點。然后計算上的最大流量。接下來對最小切割引起的集合S所對應的約束式（6）進行檢查，看是否可行。

S4：對于約束式（10），通過從倉庫開始，產生所有可能的路徑。以P（）0=0來初始化矢量P，通過選擇一個有正值x的路段并對于選定的路段設置P（）1=i，以擴展路徑。然后不斷重復這個過程。每添加一個站點時，都需要檢查是否可行。如果不可行，就將增加分割，并回到上一站點，否則就繼續擴展路徑。當xij的總和嚴格大于路徑將會繼續擴展；否則需進行分割。

2 案例分析

共享單車市場上，掌握絕對主導權的當屬摩拜和ofo。現以摩拜為例，對上海市楊浦區五角場商業圈周邊的站點進行調查，得出表1的數據。

表1 站點間的距離以及不可用單車的數量

在這里假設共有4輛容量為25的運輸車輛，對這些站點的不可用單車進行回收維修，以便再次投放到市場，增加運營商的收益，同時提高用戶的滿意度。

利用MATLAB進行編程求得上面的站點滿足需求的最短距離，結果如圖1所示（圖中前面數字代表站點，括號里的數字表示站點的不可用單車數量）。

圖1 路徑圖

4條路徑分別為：

第1輛車路徑為0—2—1—8—7—6—0，行程為2 997m；

第2輛車路徑為0—3—5—18—11—12—0，行程為4 303m；

第3輛車路徑為0—4—13—19—14—15—0，行程為3 832m；

第4輛車路徑為0—9—10—17—16—0，行程為3 666m。

得到最短的路徑總路程為14.798km，因此會選擇此4條路徑為最短路徑。

3 結論與展望

本文研究了考慮靜態模式的共享單車系統中關于不可用單車的回收維修。通過建立混合整數線性規劃（MILP）模型，考慮到滿足實際的兩個不等式，提高收斂性，用分支切割（B&C）算法求解，并利用MATLAB進行編程，從而得出理想的結果。

本文中研究的是對稱的運輸分配問題，但是在有些路段是單向行駛的，這樣就存在一定的距離差異。對于我國的共享單車的現狀來說，在以后的研究中可以將其作為一個方向去研究，克服其中的缺陷。由于本文樣本的數量不夠多，存在一定的局限性，在后面的研究中可以擴大樣本數量，以及共享單車的種類，不局限于摩拜，還可以對ofo等其他的共享單車企業進行研究。同時還可以使用不同容量的運輸車輛，從而尋求最小的回收成本，更加深入地進行研究。