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

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

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

0 引 言

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

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

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

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

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

1.1 問題描述及模型建立

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

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

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

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

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

1.2.1 有效不等式

在上面的基礎(chǔ)上需要考慮到有效不等式，用來改進(jìn)算法的收斂性。

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

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

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

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

1.2.2 分離過程

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

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

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

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

2 案例分析

共享單車市場上，掌握絕對主導(dǎo)權(quán)的當(dāng)屬摩拜和ofo?，F(xiàn)以摩拜為例，對上海市楊浦區(qū)五角場商業(yè)圈周邊的站點進(jìn)行調(diào)查，得出表1的數(shù)據(jù)。

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

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

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

圖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 結(jié)論與展望

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

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