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

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

0 引 言

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

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

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

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

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

1.1 問題描述及模型建立

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

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

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

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

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

1.2.1 有效不等式

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

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

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

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

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

1.2.2 分離過程

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

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

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

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

2 案例分析

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

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

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

利用MATLAB進(jìn)行編程求得上面的站點(diǎn)滿足需求的最短距離，結(jié)果如圖1所示（圖中前面數(shù)字代表站點(diǎn)，括號(hào)里的數(shù)字表示站點(diǎn)的不可用單車數(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，因此會(huì)選擇此4條路徑為最短路徑。

3 結(jié)論與展望

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

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