鄭亮,白劍楠,何正鵬
考慮故障車回收的單車系統(tǒng)再平衡調(diào)度研究
鄭亮,白劍楠,何正鵬
(中南大學 交通運輸工程學院,湖南 長沙 410075)
為解決單車系統(tǒng)中站點需求不匹配問題,研究需求確定條件下考慮故障車回收的有樁式共享單車系統(tǒng)再平衡單車調(diào)度問題,建立完善的考慮故障車回收取送一體化旅行商調(diào)度模型,以車輛行駛時間、每個站點固定的檢查時間以及裝卸搬運總服務時間為優(yōu)化目標,運用貪心-模擬退火算法求解最優(yōu)調(diào)度路徑。實驗結(jié)果表明:優(yōu)化出合理的調(diào)度線路,減少平衡系統(tǒng)內(nèi)每個站點的需求的服務時間,同時對故障車進行回收,提高了單車系統(tǒng)中單車利用率,進而有效解決故障車回收的單車系統(tǒng)再平衡調(diào)度問題。
再平衡問題;取送一體化;故障車回收
共享單車的普及為緩解“最后一公里”問題提供了無縫接駁的有效方案[1],也為緩解交通堵塞等問題提供了便捷和低碳環(huán)保的交通方式。但單車系統(tǒng)站點規(guī)模大、調(diào)度效率低以及故障車回收等問題日益突出,給單車調(diào)度系統(tǒng)運營和管理帶來了困難[2]。因此,如何合理平衡各個站點的需求,對單車系統(tǒng)進行合理的再平衡調(diào)度,提高單車利用效率,同時降低系統(tǒng)運營成本,成為共享單車系統(tǒng)運營亟需解決的問題。對于單車系統(tǒng)運營而言,合理的決策可以提高系統(tǒng)中單車的利用率來增加收益,降低運營和維修成本[3]。因此,單車系統(tǒng)再平衡問題研究的一個重要方面就是在滿足站點間需求的同時,優(yōu)化單車調(diào)度路線,來降低運輸成本,減少碳排放量。該問題可以歸結(jié)為取送一體化的旅行商問題(TSPPD)或車輛路徑問題(VRPPD)[4],都是NP-hard問題。針對該問題, Chemla等[5]假設每個站點可以訪問多次,提出了一種精確算法求解總旅行成本最小的調(diào)度路線;Raidl等[6]以路線的總旅行時間最短為目標,提出了可變鄰域搜索啟發(fā)式方法;Papazek等[7]提出了一種GRASP混合算法,其優(yōu)化目標是所有站點的預定需求車輛數(shù)和最終平衡車輛數(shù)之間的絕對偏差最小。WANG 等[8]考慮逆向物流成本和客戶滿意度等因素,通過改進的遺傳模擬退火算法(MGSA)來求解該問題,但其沒有考慮站點庫存因素。馮佩雨[9]考慮非勻速的單車系統(tǒng)調(diào)度路徑優(yōu)化問題,以調(diào)度費用最小作為優(yōu)化目標。Brinkmann等[10]考慮庫存問題,提出了動態(tài)前瞻策略(DLA),研究單車共享系統(tǒng)的隨機動態(tài)庫存路徑問題(SDIRP)。張佩瑤[11]考慮故障車會對降低服務滿意度,以最小化服務滿意度成本期望、行駛成本和運輸車配置成本的總和為目標,解決了配置多少輛運輸車、每輛車的行駛路徑及每個單車站應撿取多少好車和壞車,同時投放多少好車等問題;白雪等[12]針對正常自行車和待維修自行車的多商品路徑規(guī)劃問題建立了整數(shù)規(guī)劃模型;徐國勛等[13]以運營商總成本最小化為目標,并提出了一種混合禁忌搜索算法,結(jié)果表明回收懲罰系數(shù)能改變站點回收優(yōu)先級。而上述文獻中沒有考慮站點規(guī)模限制,即站樁對送貨需求的限制,當前站點車輛數(shù)對取貨數(shù)量的限制;其次文獻大多數(shù)以費用作為優(yōu)化目標,沒有考慮服務時間對該問題的影響。綜上,隨著單車系統(tǒng)再平衡調(diào)度問題研究的深入,考慮因素也更加復雜,但多數(shù)研究考慮的因素不全面,且很少有研究考慮故障車回收問題,有故障單車不僅降低顧客滿意度[14],會造成了單車系統(tǒng)內(nèi)一定程度的資源浪費。因而,考慮有故障單車回收更加貼近現(xiàn)實調(diào)度問題。因此,本文綜合考慮站點當前庫存、站點最大容量、站點空余站樁和故障車等因素,研究故障車回收的單車系統(tǒng)再平衡調(diào)度問題,并采用改進的模擬退火算法(貪心—模擬退火算法)求解最優(yōu)調(diào)度路徑。
取送一體化旅行商調(diào)度(PDTSP)問題[15],可描述為:一個起始的點作為車場,其他點作為客戶,客戶根據(jù)其需求類型可被劃分為送貨客戶和取貨客戶兩類,運輸車從起始車場出發(fā)訪問每一個站點的最短路徑。而本文在需求確定條件下考慮有故障車回收的逆向調(diào)度問題,即要考慮故障車回收占用運輸車容量,增加了問題的難度,如圖1所示。
圖1中,方形表示調(diào)度中心,調(diào)度中心可以同時發(fā)出多輛運輸車一起完成調(diào)度作業(yè)任務;圓形表示站點,站點的需求差用gap表示,站樁式站點都有最大容量限制為g,當前站點現(xiàn)有車輛數(shù)為q。
圖1 考慮故障車回收的PDTSP調(diào)度示意圖
與經(jīng)典的1-PDTSP調(diào)度問題[16]不同的是,在考慮故障車回收的1-PDTSP調(diào)度問題中,要考慮運輸車的車載容量合理配置,而從站點搬上運輸車的故障單車需要占用運輸車的容量,且直至回到配送中心才能卸載所有的故障單車。
針對上述描述的模型,本文將旅行商取送一體化問題抽象為數(shù)學模型,需要建立如下假設:
1) 只有一個配送中心,每輛運輸車都從該中心出發(fā),完成任務后又回到該中心;
2) 運輸車輛必須服務到所有的節(jié)點;
3) 每個客戶只能被服務一次;
4) 每輛運輸車只服務一條路線。
相關符號說明如下:
:={=0,1,2,…,}為節(jié)點集合,=0為配送中心,=1,2,…,為站點;
1:1{=1,2,…,}為站點集合;
:={=0,1,2,…,}車輛集合;
:表示運輸車最大容量;
q:表示站點當前擁有車輛數(shù);
g:表示站點最大容量;
:每輛車有服務時間限制;
:表示運輸車數(shù)量,且為正整數(shù);
0k:表示第輛車從配送中心出發(fā)攜帶的單車數(shù)量;
s:表示第輛車回到配送中心攜帶的單車 數(shù)量;
t:表示第輛運輸車從站點到站點行駛時間;
:表示檢查每個站點的時間;
:表示裝載單車所用單位搬運時間;
:表示搬卸單車所用單位搬運時間。
gap:表示站點的需求差,如果gap>0,則表示站點是取貨點,其值表示理論上需取走單車數(shù)量;如果gap<0,則其值表示站點是送貨點,其值表示理論上需補充單車數(shù)量;gap=0則表示站點既不取走也不補充,只進行檢查;
:表示運輸車行駛速度;
Z:表示每輛運輸車所訪問站點的真子集;
x:x為0-1變量,x=1表示第輛運輸車從站點行駛至,∈,∈1,否則,表示第輛運輸車未從站點行駛至;
y:表示第輛運輸車剛到達從站點時,車上所裝載的單車數(shù)量。
本文研究在需求確定條件下考慮故障單車回收的單車取送一體化調(diào)度問題,所建立的數(shù)學模型如下:
式(1)為目標函數(shù),優(yōu)化目標總服務時間最小,其中式(1)中第1項為車輛行駛時間、第2項為每個站點固定的檢查時間以及裝卸搬運時間。相應的約束條件如下:
式(2)表示流量約束,指運輸車從某個站點進入那么必定也從該站點離開。
式(3)表示每條路徑都是閉合回路。
式(4)表示每個站點最多被一輛運輸車被服務。
式(5)表示子回路約束。
式(7)表示保證每輛運輸車至下一個點有足夠單車可提供。
式(8)表示每輛運輸車上單車數(shù)量(包括故障車)不超過最大容量限制。
式(10)送貨量不能超過站點當前站點的空余站樁及移走故障車的站樁之和。
式(11)運輸車行駛時間計算公式。
式(12)表示決策變量為0-1變量。
式(13),(14),(15),(16)和(17)表示為非負整數(shù)約束。
上述問題可定義:考慮故障車回收的取送旅行商問題,在各種限制條件下,如何確定運輸車對每個站點服務先后順序以及確定平衡站點單車數(shù)量。研究問題的實質(zhì)是PDTSP(Pickup and Delivery Traveling Salesman Problem)問題變體,而傳統(tǒng)的TSP以及PDTSP都是NP-hard問題[17],加之考慮站點容量以及運輸車最大載貨量等約束,使得問題變得更復雜,因此需要設計符合問題的智能優(yōu)化算法進行求解。GA,SA和ACA等算法已被證明在求解TSP以及TSP變體問題上取得較好效果[18]。其中,模擬退火算法常用于TSP及TSP變體問題中,由于收斂效果好,可高效快速求解出結(jié)果。因此本文基于改進模擬退火算法(貪心—模擬退火算法)對所建立的考慮故障單車回收的單車調(diào)度模型進行求解。改進模擬退火算法求解考慮故障單車回收的單車調(diào)度問題流程圖如圖2所示。
改進的模擬退火算法實現(xiàn)具體如下:
1) 控制參數(shù)設置
需設置的主要控制參數(shù)有降溫速率,初始溫度0,結(jié)束溫度end以及鏈長等。
2) 數(shù)據(jù)及相關參數(shù)輸入
輸入數(shù)據(jù)為配送中心和站點相關信息,用于確定站點間距離、裝卸搬運數(shù)量等,相關參數(shù)為模型中一些固定常量,包括車載最大容量、車速、裝卸搬運時間、檢查時間等。
3) 基于貪心算法編碼產(chǎn)生初始解
貪心算法:在對問題求解時,總是做出在當前看來是最好的選擇。即所做出的僅是在某種意義上的局部最優(yōu)解[19]。
對于個站點規(guī)模的問題而言,初始解的第1位、最后一位編碼均為0,表示從調(diào)度中心開始,最終回調(diào)度中心,而第2位至+1位采用貪心算法求出。
圖2 改進的模擬退火算法求解流程圖
本文將貪心選擇性質(zhì)定義為當前點至下一點的距離最短,且可行(滿足模型中約束條件(7)和(8)),根據(jù)貪心選擇性質(zhì)可以求出局部最優(yōu)解。初始解的第一位編碼為0,那么距離起始調(diào)度點最近的站點作為預選,判斷是否是可行,滿足則把該站點編號作為下一位編碼,若不滿足,則搜索距次近的站點,并判斷是否是可行,滿足則把最近的站點作為下一位編碼,若不滿足,則繼續(xù)尋找,重復循環(huán),直至找到可行的下一站點。因此,貪心算法編碼產(chǎn)生的初始解是可行解。
如對=10規(guī)模的問題,假如根據(jù)上述貪心規(guī)則求解得初始路線0→3→2→1→4→0,則用0|3|2|1|4|0編碼表示基于貪心算法求解的初始解。
4) 多種方式產(chǎn)生新解
①2-opt:通過對當前解1進行變換,產(chǎn)生新的序列就可以構(gòu)成一個初始新解,用二鄰域變換法,即產(chǎn)生隨機數(shù)表示需要交換的站點,以=1,線路:0→3→2→1→4→0為例,隨機取整數(shù)1=1,2=4,即將第1個位置的3站點要與第4位置的1站點進行交換,如下:
3|2|1|4 → 4|2|1|3
得到新解為:0|4|2|2|3|0,并判斷是否可行,如不可行重復該步驟。
插入法:隨機產(chǎn)生2位整數(shù)表示要插入的站點。以=1,線路:0→3→2→1→4→0為例,隨機取整數(shù)1=2,2=4,如果1<2,則2位置的站點要插入1后,否則1插入2后,如下:
3|2|1|4 → 3|2|4|1
得到新解為:0|3|2|4|1|0,并判斷是否可行,如不可行重復該步驟。
②逆序排列法:隨機產(chǎn)生兩位整數(shù),判斷大小,進行逆排序。以=1,線路:0→3→2→1→4→0為例,隨機取整數(shù)1=1,2=4,如果1<2,則將1至2這一段逆排序,如下:
3|2|1|4 → 4|1|2|3
得到新解為:0|4|1|2|3|0,并判斷是否可行,如不可行重復該步驟。
5) Metropolis準則
其中,當d差值小于0,接受最新解變?yōu)樽顑?yōu)解;否則,以一定概率接受該解作為最優(yōu)解。
6) 降溫及終止條件
為了驗證算法的有效性,本文選取=1,=13的單車系統(tǒng)調(diào)度為研究對象,其調(diào)度中心坐標、站點坐標、站點需求、站點當前數(shù)量、站點最大容量、站點空余站樁和故障車數(shù)量如表1。
表1 坐標以及站點需求相關數(shù)據(jù)
表1中,對于站點1的1=3,表示站點1需取走3輛車,但站點1當前現(xiàn)有的單車1=14,且需移出故障車輛1=4,將站點1所有故障車移出站,就滿足該站點需求平衡,因此,站點1實際取走4輛故障車。對于站點2的2=?2,表示站點2需配送2單車,但是站點2僅剩2?2=1個空余站樁,且無故障單車需移出站,配送車輛不能超過站點剩余最大空樁,因此,站點2實際配送1輛單車。其它站點以此類推。除了上表中數(shù)據(jù)外,其他相關參數(shù)具體設置如表2。
表2 相關參數(shù)
通過模擬退火算法和改進的算法(貪心—模擬退火算法)2種算法對考慮故障單車回收的單商品取送一體化旅行商問題進行求解,算法的初始參數(shù)設置如下:初始溫度0=1 000,終止溫度end=1e-3,鏈長=400,降溫速率=0.98。初始解采用隨機產(chǎn)生和貪心算法產(chǎn)生2種方式進行對比,產(chǎn)生新解運用3種方式隨機產(chǎn)生。
模擬退火算法和改進的算法(貪心—模擬退火算法)2種算法產(chǎn)生初始可行解。模擬退火算法的隨機編碼,最初產(chǎn)生的初始可行解為:0→9→8→ 4→ 6→10→5→2→1→3→13→11→7→12→0,具體如圖3;基于改進的算法(貪心—模擬退火算法)的貪心算法編碼最初產(chǎn)生的初始可行解為:0→6→10→ 12→1→7→3→13→2→4→11→5→8→9→0,具體如圖4。
圖3 模擬退火算法初始可行解
圖4 改進模擬退火算法初始可行解
原算法初始可行解的總距離為:60.162 8 km,而改進模擬退火算法初始可行解的總距離為:50.094 4 km,因此改進模擬退火算法(貪心—模擬退火算法)初始可行解較好。除此之外,分析2種算法運算迭代圖發(fā)現(xiàn),優(yōu)化結(jié)果在迭代300~400代之間趨于收斂,具體如圖5~6所示。
圖5 模擬退火算法運算迭代圖
圖6 改進模擬退火算法運算迭代圖
對比圖4和圖5發(fā)現(xiàn)2種方式產(chǎn)生初始解的收斂速度均較快,當初始解迭代到350代左右達到相對滿意解,且之后迭代結(jié)果沒有發(fā)生變化,解趨于穩(wěn)定,相比較初始解來說,最終解取得很大改進,但改進模擬退火算法結(jié)果更優(yōu),收斂后得到最優(yōu)解的線路圖如圖7~8所示。
運輸車容量以及站點庫存,從每個站點實際取出多余車輛(不包括故障車)或配送的車輛數(shù)如下(正的表示取出,負的表示配送):[?5, 1, ?6, 2, 0, ?4, ?1, 2, 0, 3, ?3, 3, ?7],與實際需求[?5, 1, ?6, 10, 0, ?4, ?2, 2, 3, 5, ?3, 3, ?7]對比發(fā)現(xiàn)部分站點發(fā)生偏差,具體如下:站點1原需取走3量,但有4量故障車,因此沒有取走當前站點非故障車;站點5,本來需取走10量單車,但因當前站樁只有2個(也無故障車),因此只能取走2量,站點2原需配送2量車,但當前站樁只有1量,因此只能取走1量車;站點7原需取走5量,但有2量故障車,因此只取走當前站點3輛非故障車;站點5,本來需取走10量單車,但因當前站樁只有2個(也無故障車),因此只能取走2量,這是由于故障車對運輸車庫容的占據(jù),導致了取送貨物量發(fā)生改變。而從每個站點實際取出故障車數(shù)量如下:=[0,0,0,0,0,5,0,0,4,2,0, 0,1],最后帶回配送中心的故障車數(shù)量為12輛,0=15表示站點間供需不平衡,需從配送中心帶出15輛車來滿足取貨和送貨需求平衡。
圖7 模擬退火算法運算最優(yōu)線路
圖8 改進模擬退火算法運算最優(yōu)線路
1) 在對該問題進行建模時,考慮了單車系統(tǒng)的每個站點的最大容量和現(xiàn)有車輛數(shù)的限制,在優(yōu)化時對站點的需求做出調(diào)整,相較于無樁式站點問題更加復雜;同時也考慮故障單車回收問題,在實際應用中能夠有效減少故障車占用站點庫存現(xiàn)象,提高顧客滿意度。
2) 在算法改進方面,通過貪心算法產(chǎn)生初始可行解,在一定程度上提高模擬退火算法的收斂速度,并通過測試算例進行有效驗證,可快速為企業(yè)運營提供最優(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] 汪慎文, 楊鋒, 徐亮, 等. 離散差分進化算法求解共享單車調(diào)度問題[J]. 鄭州大學學報(工學版), 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]. 南京: 東南大學, 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] 張佩瑤. 考慮車輛損壞的共享單車再平衡問題研究[D]. 北京: 清華大學, 2018. ZHANG Peiyao. Research on shared bicycle rebalancing considering vehicle damage[D]. Beijing: Tsinghua University, 2018.
[12] 白雪, 周支力, 錢桂生, 等. 考慮維修車輛的公共自行車系統(tǒng)再平衡問題[J]. 系統(tǒng)工程理論與實踐, 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] 徐國勛, 李妍峰, 向婷, 等. 考慮損壞自行車回收的共享單車調(diào)度問題[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] 時中朝, 郝偉娜, 董紅召. 基于樸素貝葉斯分類器的公共自行車系統(tǒng)故障診斷方法[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問題及其遺傳算法求解[J]. 計算機工程與應用, 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] 趙麗娜, 張麗華, 竇冰潔, 等. 帶油耗的單商品取送貨旅行商問題研究[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問題的改進蟻群系統(tǒng)[J]. 內(nèi)江師范學院學報, 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]. 計算機工程, 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
國家自然科學基金資助項目(71871227);中南大學研究生自主探索創(chuàng)新項目(2019zzts953)
鄭亮(1984?),男,湖南衡陽人,副教授,博士,從事交通流預測、系統(tǒng)仿真優(yōu)化等研究;E?mail:zhengliang@csu.edu.cn
(編輯 陽麗霞)