鄭亮，白劍楠，何正鵬

考慮故障車回收的單車系統(tǒng)再平衡調(diào)度研究

鄭亮，白劍楠，何正鵬

(中南大學(xué) 交通運(yùn)輸工程學(xué)院，湖南 長(zhǎng)沙 410075)

為解決單車系統(tǒng)中站點(diǎn)需求不匹配問(wèn)題，研究需求確定條件下考慮故障車回收的有樁式共享單車系統(tǒng)再平衡單車調(diào)度問(wèn)題，建立完善的考慮故障車回收取送一體化旅行商調(diào)度模型，以車輛行駛時(shí)間、每個(gè)站點(diǎn)固定的檢查時(shí)間以及裝卸搬運(yùn)總服務(wù)時(shí)間為優(yōu)化目標(biāo)，運(yùn)用貪心-模擬退火算法求解最優(yōu)調(diào)度路徑。實(shí)驗(yàn)結(jié)果表明：優(yōu)化出合理的調(diào)度線路，減少平衡系統(tǒng)內(nèi)每個(gè)站點(diǎn)的需求的服務(wù)時(shí)間，同時(shí)對(duì)故障車進(jìn)行回收，提高了單車系統(tǒng)中單車?yán)寐?，進(jìn)而有效解決故障車回收的單車系統(tǒng)再平衡調(diào)度問(wèn)題。

再平衡問(wèn)題；取送一體化；故障車回收

共享單車的普及為緩解“最后一公里”問(wèn)題提供了無(wú)縫接駁的有效方案[1]，也為緩解交通堵塞等問(wèn)題提供了便捷和低碳環(huán)保的交通方式。但單車系統(tǒng)站點(diǎn)規(guī)模大、調(diào)度效率低以及故障車回收等問(wèn)題日益突出，給單車調(diào)度系統(tǒng)運(yùn)營(yíng)和管理帶來(lái)了困難[2]。因此，如何合理平衡各個(gè)站點(diǎn)的需求，對(duì)單車系統(tǒng)進(jìn)行合理的再平衡調(diào)度，提高單車?yán)眯?，同時(shí)降低系統(tǒng)運(yùn)營(yíng)成本，成為共享單車系統(tǒng)運(yùn)營(yíng)亟需解決的問(wèn)題。對(duì)于單車系統(tǒng)運(yùn)營(yíng)而言，合理的決策可以提高系統(tǒng)中單車的利用率來(lái)增加收益，降低運(yùn)營(yíng)和維修成本[3]。因此，單車系統(tǒng)再平衡問(wèn)題研究的一個(gè)重要方面就是在滿足站點(diǎn)間需求的同時(shí)，優(yōu)化單車調(diào)度路線，來(lái)降低運(yùn)輸成本，減少碳排放量。該問(wèn)題可以歸結(jié)為取送一體化的旅行商問(wèn)題(TSPPD)或車輛路徑問(wèn)題(VRPPD)[4]，都是NP-hard問(wèn)題。針對(duì)該問(wèn)題, Chemla等[5]假設(shè)每個(gè)站點(diǎn)可以訪問(wèn)多次，提出了一種精確算法求解總旅行成本最小的調(diào)度路線；Raidl等[6]以路線的總旅行時(shí)間最短為目標(biāo)，提出了可變鄰域搜索啟發(fā)式方法；Papazek等[7]提出了一種GRASP混合算法，其優(yōu)化目標(biāo)是所有站點(diǎn)的預(yù)定需求車輛數(shù)和最終平衡車輛數(shù)之間的絕對(duì)偏差最小。WANG 等[8]考慮逆向物流成本和客戶滿意度等因素，通過(guò)改進(jìn)的遺傳模擬退火算法(MGSA)來(lái)求解該問(wèn)題，但其沒(méi)有考慮站點(diǎn)庫(kù)存因素。馮佩雨[9]考慮非勻速的單車系統(tǒng)調(diào)度路徑優(yōu)化問(wèn)題，以調(diào)度費(fèi)用最小作為優(yōu)化目標(biāo)。Brinkmann等[10]考慮庫(kù)存問(wèn)題，提出了動(dòng)態(tài)前瞻策略(DLA)，研究單車共享系統(tǒng)的隨機(jī)動(dòng)態(tài)庫(kù)存路徑問(wèn)題(SDIRP)。張佩瑤[11]考慮故障車會(huì)對(duì)降低服務(wù)滿意度，以最小化服務(wù)滿意度成本期望、行駛成本和運(yùn)輸車配置成本的總和為目標(biāo)，解決了配置多少輛運(yùn)輸車、每輛車的行駛路徑及每個(gè)單車站應(yīng)撿取多少好車和壞車，同時(shí)投放多少好車等問(wèn)題；白雪等[12]針對(duì)正常自行車和待維修自行車的多商品路徑規(guī)劃問(wèn)題建立了整數(shù)規(guī)劃模型；徐國(guó)勛等[13]以運(yùn)營(yíng)商總成本最小化為目標(biāo)，并提出了一種混合禁忌搜索算法，結(jié)果表明回收懲罰系數(shù)能改變站點(diǎn)回收優(yōu)先級(jí)。而上述文獻(xiàn)中沒(méi)有考慮站點(diǎn)規(guī)模限制，即站樁對(duì)送貨需求的限制，當(dāng)前站點(diǎn)車輛數(shù)對(duì)取貨數(shù)量的限制；其次文獻(xiàn)大多數(shù)以費(fèi)用作為優(yōu)化目標(biāo)，沒(méi)有考慮服務(wù)時(shí)間對(duì)該問(wèn)題的影響。綜上，隨著單車系統(tǒng)再平衡調(diào)度問(wèn)題研究的深入，考慮因素也更加復(fù)雜，但多數(shù)研究考慮的因素不全面，且很少有研究考慮故障車回收問(wèn)題，有故障單車不僅降低顧客滿意度[14]，會(huì)造成了單車系統(tǒng)內(nèi)一定程度的資源浪費(fèi)。因而，考慮有故障單車回收更加貼近現(xiàn)實(shí)調(diào)度問(wèn)題。因此，本文綜合考慮站點(diǎn)當(dāng)前庫(kù)存、站點(diǎn)最大容量、站點(diǎn)空余站樁和故障車等因素，研究故障車回收的單車系統(tǒng)再平衡調(diào)度問(wèn)題，并采用改進(jìn)的模擬退火算法(貪心—模擬退火算法)求解最優(yōu)調(diào)度路徑。

1 問(wèn)題描述和符號(hào)說(shuō)明

1.1 問(wèn)題描述

取送一體化旅行商調(diào)度(PDTSP)問(wèn)題[15]，可描述為：一個(gè)起始的點(diǎn)作為車場(chǎng)，其他點(diǎn)作為客戶，客戶根據(jù)其需求類型可被劃分為送貨客戶和取貨客戶兩類，運(yùn)輸車從起始車場(chǎng)出發(fā)訪問(wèn)每一個(gè)站點(diǎn)的最短路徑。而本文在需求確定條件下考慮有故障車回收的逆向調(diào)度問(wèn)題，即要考慮故障車回收占用運(yùn)輸車容量，增加了問(wèn)題的難度，如圖1所示。

圖1中，方形表示調(diào)度中心，調(diào)度中心可以同時(shí)發(fā)出多輛運(yùn)輸車一起完成調(diào)度作業(yè)任務(wù)；圓形表示站點(diǎn)，站點(diǎn)的需求差用gap表示，站樁式站點(diǎn)都有最大容量限制為g，當(dāng)前站點(diǎn)現(xiàn)有車輛數(shù)為q。

圖1 考慮故障車回收的PDTSP調(diào)度示意圖

與經(jīng)典的1-PDTSP調(diào)度問(wèn)題[16]不同的是，在考慮故障車回收的1-PDTSP調(diào)度問(wèn)題中，要考慮運(yùn)輸車的車載容量合理配置，而從站點(diǎn)搬上運(yùn)輸車的故障單車需要占用運(yùn)輸車的容量，且直至回到配送中心才能卸載所有的故障單車。

1.2 符號(hào)說(shuō)明

針對(duì)上述描述的模型，本文將旅行商取送一體化問(wèn)題抽象為數(shù)學(xué)模型，需要建立如下假設(shè)：

1) 只有一個(gè)配送中心，每輛運(yùn)輸車都從該中心出發(fā)，完成任務(wù)后又回到該中心；

2) 運(yùn)輸車輛必須服務(wù)到所有的節(jié)點(diǎn)；

3) 每個(gè)客戶只能被服務(wù)一次；

4) 每輛運(yùn)輸車只服務(wù)一條路線。

相關(guān)符號(hào)說(shuō)明如下：

：={=0,1,2,…,}為節(jié)點(diǎn)集合，=0為配送中心，=1,2,…,為站點(diǎn)；

1：1{=1,2,…,}為站點(diǎn)集合；

：={=0,1,2,…,}車輛集合；

：表示運(yùn)輸車最大容量；

q：表示站點(diǎn)當(dāng)前擁有車輛數(shù)；

g：表示站點(diǎn)最大容量；

：每輛車有服務(wù)時(shí)間限制；

：表示運(yùn)輸車數(shù)量，且為正整數(shù)；

0k：表示第輛車從配送中心出發(fā)攜帶的單車數(shù)量；

s：表示第輛車回到配送中心攜帶的單車 數(shù)量；

t：表示第輛運(yùn)輸車從站點(diǎn)到站點(diǎn)行駛時(shí)間；

：表示檢查每個(gè)站點(diǎn)的時(shí)間；

：表示裝載單車所用單位搬運(yùn)時(shí)間；

：表示搬卸單車所用單位搬運(yùn)時(shí)間。

gap：表示站點(diǎn)的需求差，如果gap>0，則表示站點(diǎn)是取貨點(diǎn)，其值表示理論上需取走單車數(shù)量；如果gap<0，則其值表示站點(diǎn)是送貨點(diǎn)，其值表示理論上需補(bǔ)充單車數(shù)量；gap=0則表示站點(diǎn)既不取走也不補(bǔ)充，只進(jìn)行檢查；

：表示運(yùn)輸車行駛速度；

Z：表示每輛運(yùn)輸車所訪問(wèn)站點(diǎn)的真子集；

x：x為0-1變量，x=1表示第輛運(yùn)輸車從站點(diǎn)行駛至,∈,∈1，否則，表示第輛運(yùn)輸車未從站點(diǎn)行駛至；

y：表示第輛運(yùn)輸車剛到達(dá)從站點(diǎn)時(shí)，車上所裝載的單車數(shù)量。

2 數(shù)學(xué)模型的建立

本文研究在需求確定條件下考慮故障單車回收的單車取送一體化調(diào)度問(wèn)題，所建立的數(shù)學(xué)模型如下：

式(1)為目標(biāo)函數(shù)，優(yōu)化目標(biāo)總服務(wù)時(shí)間最小，其中式(1)中第1項(xiàng)為車輛行駛時(shí)間、第2項(xiàng)為每個(gè)站點(diǎn)固定的檢查時(shí)間以及裝卸搬運(yùn)時(shí)間。相應(yīng)的約束條件如下：

式(2)表示流量約束，指運(yùn)輸車從某個(gè)站點(diǎn)進(jìn)入那么必定也從該站點(diǎn)離開(kāi)。

式(3)表示每條路徑都是閉合回路。

式(4)表示每個(gè)站點(diǎn)最多被一輛運(yùn)輸車被服務(wù)。

式(5)表示子回路約束。

式(7)表示保證每輛運(yùn)輸車至下一個(gè)點(diǎn)有足夠單車可提供。

式(8)表示每輛運(yùn)輸車上單車數(shù)量(包括故障車)不超過(guò)最大容量限制。

式(10)送貨量不能超過(guò)站點(diǎn)當(dāng)前站點(diǎn)的空余站樁及移走故障車的站樁之和。

式(11)運(yùn)輸車行駛時(shí)間計(jì)算公式。

式(12)表示決策變量為0-1變量。

式(13)，(14)，(15)，(16)和(17)表示為非負(fù)整數(shù)約束。

3 算法設(shè)計(jì)流程及步驟

上述問(wèn)題可定義：考慮故障車回收的取送旅行商問(wèn)題，在各種限制條件下，如何確定運(yùn)輸車對(duì)每個(gè)站點(diǎn)服務(wù)先后順序以及確定平衡站點(diǎn)單車數(shù)量。研究問(wèn)題的實(shí)質(zhì)是PDTSP(Pickup and Delivery Traveling Salesman Problem)問(wèn)題變體，而傳統(tǒng)的TSP以及PDTSP都是NP-hard問(wèn)題[17]，加之考慮站點(diǎn)容量以及運(yùn)輸車最大載貨量等約束，使得問(wèn)題變得更復(fù)雜，因此需要設(shè)計(jì)符合問(wèn)題的智能優(yōu)化算法進(jìn)行求解。GA，SA和ACA等算法已被證明在求解TSP以及TSP變體問(wèn)題上取得較好效果[18]。其中，模擬退火算法常用于TSP及TSP變體問(wèn)題中，由于收斂效果好，可高效快速求解出結(jié)果。因此本文基于改進(jìn)模擬退火算法(貪心—模擬退火算法)對(duì)所建立的考慮故障單車回收的單車調(diào)度模型進(jìn)行求解。改進(jìn)模擬退火算法求解考慮故障單車回收的單車調(diào)度問(wèn)題流程圖如圖2所示。

改進(jìn)的模擬退火算法實(shí)現(xiàn)具體如下：

1) 控制參數(shù)設(shè)置

需設(shè)置的主要控制參數(shù)有降溫速率，初始溫度0，結(jié)束溫度end以及鏈長(zhǎng)等。

2) 數(shù)據(jù)及相關(guān)參數(shù)輸入

輸入數(shù)據(jù)為配送中心和站點(diǎn)相關(guān)信息，用于確定站點(diǎn)間距離、裝卸搬運(yùn)數(shù)量等，相關(guān)參數(shù)為模型中一些固定常量，包括車載最大容量、車速、裝卸搬運(yùn)時(shí)間、檢查時(shí)間等。

3) 基于貪心算法編碼產(chǎn)生初始解

貪心算法：在對(duì)問(wèn)題求解時(shí)，總是做出在當(dāng)前看來(lái)是最好的選擇。即所做出的僅是在某種意義上的局部最優(yōu)解[19]。

對(duì)于個(gè)站點(diǎn)規(guī)模的問(wèn)題而言，初始解的第1位、最后一位編碼均為0，表示從調(diào)度中心開(kāi)始，最終回調(diào)度中心，而第2位至+1位采用貪心算法求出。

圖2 改進(jìn)的模擬退火算法求解流程圖

本文將貪心選擇性質(zhì)定義為當(dāng)前點(diǎn)至下一點(diǎn)的距離最短，且可行(滿足模型中約束條件(7)和(8))，根據(jù)貪心選擇性質(zhì)可以求出局部最優(yōu)解。初始解的第一位編碼為0，那么距離起始調(diào)度點(diǎn)最近的站點(diǎn)作為預(yù)選，判斷是否是可行，滿足則把該站點(diǎn)編號(hào)作為下一位編碼，若不滿足，則搜索距次近的站點(diǎn)，并判斷是否是可行，滿足則把最近的站點(diǎn)作為下一位編碼，若不滿足，則繼續(xù)尋找，重復(fù)循環(huán)，直至找到可行的下一站點(diǎn)。因此，貪心算法編碼產(chǎn)生的初始解是可行解。

如對(duì)=10規(guī)模的問(wèn)題，假如根據(jù)上述貪心規(guī)則求解得初始路線0→3→2→1→4→0，則用0|3|2|1|4|0編碼表示基于貪心算法求解的初始解。

4) 多種方式產(chǎn)生新解

①2-opt：通過(guò)對(duì)當(dāng)前解1進(jìn)行變換，產(chǎn)生新的序列就可以構(gòu)成一個(gè)初始新解，用二鄰域變換法，即產(chǎn)生隨機(jī)數(shù)表示需要交換的站點(diǎn)，以=1，線路：0→3→2→1→4→0為例，隨機(jī)取整數(shù)1=1，2=4，即將第1個(gè)位置的3站點(diǎn)要與第4位置的1站點(diǎn)進(jìn)行交換，如下：

3|2|1|4 → 4|2|1|3

得到新解為：0|4|2|2|3|0，并判斷是否可行，如不可行重復(fù)該步驟。

插入法：隨機(jī)產(chǎn)生2位整數(shù)表示要插入的站點(diǎn)。以=1，線路：0→3→2→1→4→0為例，隨機(jī)取整數(shù)1=2，2=4，如果1<2，則2位置的站點(diǎn)要插入1后，否則1插入2后，如下：

3|2|1|4 → 3|2|4|1

得到新解為：0|3|2|4|1|0，并判斷是否可行，如不可行重復(fù)該步驟。

②逆序排列法：隨機(jī)產(chǎn)生兩位整數(shù)，判斷大小，進(jìn)行逆排序。以=1，線路：0→3→2→1→4→0為例，隨機(jī)取整數(shù)1=1，2=4，如果1＜2，則將1至2這一段逆排序，如下：

3|2|1|4 → 4|1|2|3

得到新解為：0|4|1|2|3|0，并判斷是否可行，如不可行重復(fù)該步驟。

5) Metropolis準(zhǔn)則

其中，當(dāng)d差值小于0，接受最新解變?yōu)樽顑?yōu)解；否則，以一定概率接受該解作為最優(yōu)解。

6) 降溫及終止條件

4 算例分析

4.1 測(cè)試算例及相關(guān)參數(shù)

為了驗(yàn)證算法的有效性，本文選取=1，=13的單車系統(tǒng)調(diào)度為研究對(duì)象，其調(diào)度中心坐標(biāo)、站點(diǎn)坐標(biāo)、站點(diǎn)需求、站點(diǎn)當(dāng)前數(shù)量、站點(diǎn)最大容量、站點(diǎn)空余站樁和故障車數(shù)量如表1。

表1 坐標(biāo)以及站點(diǎn)需求相關(guān)數(shù)據(jù)

表1中，對(duì)于站點(diǎn)1的1=3，表示站點(diǎn)1需取走3輛車，但站點(diǎn)1當(dāng)前現(xiàn)有的單車1=14，且需移出故障車輛1=4，將站點(diǎn)1所有故障車移出站，就滿足該站點(diǎn)需求平衡，因此，站點(diǎn)1實(shí)際取走4輛故障車。對(duì)于站點(diǎn)2的2=?2，表示站點(diǎn)2需配送2單車，但是站點(diǎn)2僅剩2?2=1個(gè)空余站樁，且無(wú)故障單車需移出站，配送車輛不能超過(guò)站點(diǎn)剩余最大空樁，因此，站點(diǎn)2實(shí)際配送1輛單車。其它站點(diǎn)以此類推。除了上表中數(shù)據(jù)外，其他相關(guān)參數(shù)具體設(shè)置如表2。

表2 相關(guān)參數(shù)

4.2 測(cè)試結(jié)果

通過(guò)模擬退火算法和改進(jìn)的算法(貪心—模擬退火算法)2種算法對(duì)考慮故障單車回收的單商品取送一體化旅行商問(wèn)題進(jìn)行求解，算法的初始參數(shù)設(shè)置如下：初始溫度0=1 000，終止溫度end=1e-3，鏈長(zhǎng)=400，降溫速率=0.98。初始解采用隨機(jī)產(chǎn)生和貪心算法產(chǎn)生2種方式進(jìn)行對(duì)比，產(chǎn)生新解運(yùn)用3種方式隨機(jī)產(chǎn)生。

模擬退火算法和改進(jìn)的算法(貪心—模擬退火算法)2種算法產(chǎn)生初始可行解。模擬退火算法的隨機(jī)編碼，最初產(chǎn)生的初始可行解為：0→9→8→ 4→ 6→10→5→2→1→3→13→11→7→12→0，具體如圖3；基于改進(jìn)的算法(貪心—模擬退火算法)的貪心算法編碼最初產(chǎn)生的初始可行解為：0→6→10→ 12→1→7→3→13→2→4→11→5→8→9→0，具體如圖4。

圖3 模擬退火算法初始可行解

圖4 改進(jìn)模擬退火算法初始可行解

原算法初始可行解的總距離為：60.162 8 km，而改進(jìn)模擬退火算法初始可行解的總距離為：50.094 4 km，因此改進(jìn)模擬退火算法(貪心—模擬退火算法)初始可行解較好。除此之外，分析2種算法運(yùn)算迭代圖發(fā)現(xiàn)，優(yōu)化結(jié)果在迭代300～400代之間趨于收斂，具體如圖5~6所示。

圖5 模擬退火算法運(yùn)算迭代圖

圖6 改進(jìn)模擬退火算法運(yùn)算迭代圖

對(duì)比圖4和圖5發(fā)現(xiàn)2種方式產(chǎn)生初始解的收斂速度均較快，當(dāng)初始解迭代到350代左右達(dá)到相對(duì)滿意解，且之后迭代結(jié)果沒(méi)有發(fā)生變化，解趨于穩(wěn)定，相比較初始解來(lái)說(shuō)，最終解取得很大改進(jìn)，但改進(jìn)模擬退火算法結(jié)果更優(yōu)，收斂后得到最優(yōu)解的線路圖如圖7~8所示。

運(yùn)輸車容量以及站點(diǎn)庫(kù)存，從每個(gè)站點(diǎn)實(shí)際取出多余車輛(不包括故障車)或配送的車輛數(shù)如下(正的表示取出，負(fù)的表示配送)：[?5, 1, ?6, 2, 0, ?4, ?1, 2, 0, 3, ?3, 3, ?7]，與實(shí)際需求[?5, 1, ?6, 10, 0, ?4, ?2, 2, 3, 5, ?3, 3, ?7]對(duì)比發(fā)現(xiàn)部分站點(diǎn)發(fā)生偏差，具體如下：站點(diǎn)1原需取走3量，但有4量故障車，因此沒(méi)有取走當(dāng)前站點(diǎn)非故障車；站點(diǎn)5，本來(lái)需取走10量單車，但因當(dāng)前站樁只有2個(gè)(也無(wú)故障車)，因此只能取走2量，站點(diǎn)2原需配送2量車，但當(dāng)前站樁只有1量，因此只能取走1量車；站點(diǎn)7原需取走5量，但有2量故障車，因此只取走當(dāng)前站點(diǎn)3輛非故障車；站點(diǎn)5，本來(lái)需取走10量單車，但因當(dāng)前站樁只有2個(gè)(也無(wú)故障車)，因此只能取走2量，這是由于故障車對(duì)運(yùn)輸車庫(kù)容的占據(jù)，導(dǎo)致了取送貨物量發(fā)生改變。而從每個(gè)站點(diǎn)實(shí)際取出故障車數(shù)量如下：=[0,0,0,0,0,5,0,0,4,2,0, 0,1]，最后帶回配送中心的故障車數(shù)量為12輛，0=15表示站點(diǎn)間供需不平衡，需從配送中心帶出15輛車來(lái)滿足取貨和送貨需求平衡。

圖7 模擬退火算法運(yùn)算最優(yōu)線路

圖8 改進(jìn)模擬退火算法運(yùn)算最優(yōu)線路

5 結(jié)論

1) 在對(duì)該問(wèn)題進(jìn)行建模時(shí)，考慮了單車系統(tǒng)的每個(gè)站點(diǎn)的最大容量和現(xiàn)有車輛數(shù)的限制，在優(yōu)化時(shí)對(duì)站點(diǎn)的需求做出調(diào)整，相較于無(wú)樁式站點(diǎn)問(wèn)題更加復(fù)雜；同時(shí)也考慮故障單車回收問(wèn)題，在實(shí)際應(yīng)用中能夠有效減少故障車占用站點(diǎn)庫(kù)存現(xiàn)象，提高顧客滿意度。

2) 在算法改進(jìn)方面，通過(guò)貪心算法產(chǎn)生初始可行解，在一定程度上提高模擬退火算法的收斂速度，并通過(guò)測(cè)試算例進(jìn)行有效驗(yàn)證，可快速為企業(yè)運(yùn)營(yíng)提供最優(yōu)決策的調(diào)度線路。

[1] LIN J, YANG T, CHANG Y, et al. A hub location inventory model for bicycle sharing system design: Formulation and solution[J]. Computers & Industrial Engineering, 2013, 65(1): 77?86.

[2] 汪慎文, 楊鋒, 徐亮, 等. 離散差分進(jìn)化算法求解共享單車調(diào)度問(wèn)題[J]. 鄭州大學(xué)學(xué)報(bào)(工學(xué)版), 2019, 40(4): 48?53. WANG Shenwen, YANG Feng, XU Liang, et al. Discrete differential evolutionary algorithm for shared single vehicle scheduling[J]. Journal of Zhengzhou University (Engineering Edition), 2019, 40(4): 48?53.

[3] CHEN Y , WANG D , CHEN K , et al. Optimal pricing and availability strategy of a bike-sharing firm with time-sensitive customers[J]. Journal of Cleaner Production, 2019, 228(10): 208?221.

[4] Dumitrescu I, Ropke S, Cordeau J, et al. The traveling salesman problem with pickup and delivery polyhedral results and a branch-and-cut algorithm[J]. Mathematical Programming, 2009, 121(2): 269?305.

[5] Chemla D, Meunier F, Calvo R W, et al. Bike sharing systems: Solving the static rebalancing problem[J]. Discrete Optimization, 2013, 10(2): 120?146.

[6] Raidl G R, HU B, Rainer-Harbach M, et al. Balancing bicycle sharing systems: Improving a VNS by efficiently determining optimal loading operations[M]. Berlin: Lecture Notes in Computer Science, 2013: 130?143.

[7] Papazek P, Kloimullner C, HU B, et al. Balancing bicycle sharing systems: An analysis of path relinking and recombination within a GRASP hybrid[C]// 13th International Conference on Parallel Problem Solving from Nature, Ljubljana, Slovenia, 2014.

[8] WANG X, ZHAO M, HE H, et al. Reverse logistic network optimization research for sharing bikes[J]. Procedia Computer Science, 2018, 126: 1693?1703.

[9] 馮佩雨. 公共自行車系統(tǒng)調(diào)度管理優(yōu)化方法研究[D]. 南京: 東南大學(xué), 2018. FENG Peiyu. Research on optimization method of public bicycle system scheduling management[D]. Nanjing: Southeast University, 2018.

[10] Brinkmann J, Ulmer M W, Mattfeld D C. Dynamic lookahead policies for stochastic-dynamic inventory routing in bike sharing systems[J]. Computers & Operations Research, 2019, 106: 260?279.

[11] 張佩瑤. 考慮車輛損壞的共享單車再平衡問(wèn)題研究[D]. 北京: 清華大學(xué), 2018. ZHANG Peiyao. Research on shared bicycle rebalancing considering vehicle damage[D]. Beijing: Tsinghua University, 2018.

[12] 白雪, 周支力, 錢桂生, 等. 考慮維修車輛的公共自行車系統(tǒng)再平衡問(wèn)題[J]. 系統(tǒng)工程理論與實(shí)踐, 2018, 38(9): 2326?2334. BAI Xue, ZHOU Zhili, QIAN Guisheng, et al. Rebalancing of public bicycle system considering maintenance vehicles[J]. Theory and Practice of System Engineering, 2018, 38(9): 2326?2334.

[13] 徐國(guó)勛, 李妍峰, 向婷, 等. 考慮損壞自行車回收的共享單車調(diào)度問(wèn)題[J]. 系統(tǒng)工程, 2019, 37(2): 91?99. XU Guoxun, LI Yanfeng, XIANG Ting, et al. Shared bicycle scheduling problem considering damaged bicycle recycling[J]. Systems Engineering, 2019, 37(2): 91?99.

[14] 時(shí)中朝, 郝偉娜, 董紅召. 基于樸素貝葉斯分類器的公共自行車系統(tǒng)故障診斷方法[J]. 中國(guó)機(jī)械工程, 2019, 30(8): 983?987. SHI Zhongchao, HAO Weina, DONG Hongzhao. Public bicycle system fault diagnosis based on naive bayesian classifier[J]. China Mechanical Engineering, 2019, 30(8): 983?987.

[15] 趙方庚, 李蘇劍, 劉偉民, 等. 一類特殊的集送一體化TSP問(wèn)題及其遺傳算法求解[J]. 計(jì)算機(jī)工程與應(yīng)用, 2009, 45(2): 250?252. ZHAO Fanggeng, LI Sujian, LIU Weimin, et al. Genetic algorithm for a special pickup and delivery traveling salesman problem[J]. Computer Engineering and Applications, 2009, 45(2): 250?252.

[16] 趙麗娜, 張麗華, 竇冰潔, 等. 帶油耗的單商品取送貨旅行商問(wèn)題研究[J]. 物流科技, 2016, 39(4): 10?13. ZHAO Lina, ZHANG Lihua, DOU Bingjie, et al. Study on a one commodity pick-up and delivery with fuel consumption[J]. Logistics Sci-Tech, 2016, 39(4): 10?13.

[17] 付慧琳, 牟廉明, 戴錫笠, 等. 求解1-PDTSP問(wèn)題的改進(jìn)蟻群系統(tǒng)[J]. 內(nèi)江師范學(xué)院學(xué)報(bào), 2013, 28(12): 13?16. FU Huilin, MOU Lianming, DAI Xili, et al. Improved ant colony system for solving 1-pdtsp problem[J]. Journal of Neijiang Normal University, 2013, 28(12): 13?16.

[18] Breedam A V. Improvement heuristics for the vehicle routing problem based on simulated annealing[J]. European Journal of Operational Research, 1995, 86(3):480?490.

[19] 鄭金金, 羅志年. LTE-A系統(tǒng)載波聚合下基于貪心算法的資源管理[J]. 計(jì)算機(jī)工程, 2017, 43(11): 50?54. ZHENG Jinjin, LUO Zhinian. Resource management based on greedy algorithm for carrier aggregation in LTE-A system[J]. Computer Engineering, 2017, 43(11): 50?54.

Study on the rebalancing problem in the bike-sharing system considering the recovery of the faulty bikes

ZHENG Liang, BAI Jiannan, HE Zhengpeng

(School of Traffic and Transportation Engineering, Central South University, Changsha 410075, China)

To reduce the occurrence of station demand mismatch in the bike-sharing system, and to rebalance problem in the bike-sharing system, a model was established on the recovery of faulty bikes under the condition of demand. The model could consider the recovery of faulty bikes, calculate the driving time of vehicles, fix inspection time of each station and the loading, unloading time as the objective function. The simulated annealing algorithm combined with greedy algorithm was used to solve the test case. It can optimize the reasonable scheduling line, reduce the time to balance stations, and recover the faulty bikes at each station. This study improved the utilization rate in the bike-sharing system, and effectively solved the rebalancing problem of faulty vehicle recovery in the bike-sharing system.

rebalancing problem; pickups and deliveries; the recovery of the faulty bikes

U491

A

1672 ? 7029(2021)03 ? 0786 ? 08

10.19713/j.cnki.43?1423/u.T20200431

2020?05?22

國(guó)家自然科學(xué)基金資助項(xiàng)目(71871227)；中南大學(xué)研究生自主探索創(chuàng)新項(xiàng)目(2019zzts953)

鄭亮(1984?)，男，湖南衡陽(yáng)人，副教授，博士，從事交通流預(yù)測(cè)、系統(tǒng)仿真優(yōu)化等研究；E?mail：zhengliang@csu.edu.cn

(編輯 陽(yáng)麗霞)