呂 暢，張超勇+，張道德，任亞平，孟磊磊

(1.華中科技大學 數(shù)字制造裝備與技術(shù)國家重點實驗室，湖北 武漢 430074；2.湖北工業(yè)大學 機械工程學院，湖北 武漢 430068；3.聊城大學 計算機學院，山東 聊城 252059)

0 引言

共享單車系統(tǒng)(Bike Sharing System, BSS)1965年起源于荷蘭，是一種低碳環(huán)保的出行方式。國內(nèi)近10年發(fā)展勢頭猛烈，由其衍生而來的共享電動車，共享汽車也開始進入人們的視線。但無論如何變化，共享單車的再平衡問題(Bike Sharing Rebalancing Problem, BSRP)，即如何解決各個共享站點供需平衡﹑降低再平衡作業(yè)成本提升作業(yè)效率，是BSS亟需解決的關鍵問題之一。與一般的路徑規(guī)劃問題相比，BSRP需要在每一個站點處進行放置或取走多少數(shù)量貨物的決策，由于調(diào)度貨車載量的限制，該決策又勢必影響到訪問站點的選擇，極大增添了問題的復雜度。Ho等[1]在2014年已證明BSRP屬于NP-hard問題，由于該問題具有重要的理論和實際應用價值，受到社會以及學術(shù)界的廣泛關注。

實際的BSS通常規(guī)模大、站點數(shù)量多、倉庫不唯一，所需調(diào)度車輛較多，但若減少調(diào)度車輛，由于車載上限，將導致多次往返，增加行駛路程。因此，允許站點臨時?？恳约岸啻卧L問，極大增添了再平衡作業(yè)模型的靈活性，Chemla等[2]建立了允許站點的臨時?？恳约岸啻卧L問的共享單車再平衡問題的數(shù)學模型，并獲得了不錯的效果；Erdogan等[3]所提出的模型也允許多次訪問和臨時?？?，并通過精確算法獲得60站點內(nèi)的最優(yōu)解。

站點分組訪問的思想源于Baldacci等[4]所提出的集群車輛路徑(Grouping Vehicle Routing Problem, GVRP)模型，在該模型中站點被分為不同的站點族，每輛調(diào)度貨車必須訪問每個族內(nèi)的至少一個站點。Battarra等[5]2013年提出CVRP模型，將其訪問形式作了調(diào)整，規(guī)定調(diào)度貨車必須將該站點族內(nèi)所有站點全部訪問后才能進行下一個族的訪問。Forma等[6]將該分組思想成功應用到了BSRP中，3-step中的第一步便是根據(jù)站點的距離以及庫存特性生成站點族，其模型以及解決方案能獲得125站點以內(nèi)的較優(yōu)解。國內(nèi)學者葉錦程等[7]也提出了類似的分組訪問模型——子群劃分，較好地減少了調(diào)度點數(shù)量以及調(diào)度路程。類似于站點的分組訪問，分類訪問則是根據(jù)站點實際庫存和目標庫存之間的關系將其分為不足﹑過飽和和平衡站點。2014年Ho等[1]將該分類訪問方式應用于BSRP，通過禁忌搜索(Tabu Search, TS)求解取得了不錯的效果，并在2016年[8]結(jié)合站點之間路徑的相關性提出了基于貪婪隨機自適應搜索(Greedy Randomized Adaptive Search Procedure, GRASP)的求解模型，2017年[9]對該訪問模式進行了少許改進，規(guī)定并非所有過飽和站點都必須訪問，并結(jié)合混合大鄰域搜索(Hybrid Large Neighborhood Search, H-LNS)進行求解，效果顯著。

成本是衡量一個運作系統(tǒng)好壞的重要指標。在BSS再平衡作業(yè)中，單車的庫存成本對整個作業(yè)成本的貢獻不亞于運輸成本。Lin等[10]提出針對交通共享系統(tǒng)的中心位置庫存(Hub Location Inventory, HLI)模型，在解決實際案例時能較好地降低作業(yè)總成本，同時大大提升了BSS的服務水平。RAVIV等[11]也給出了關于BSS的庫存模型設計，通過數(shù)學建模求解驗證了其可行性。Lin等[12]將系統(tǒng)的服務水平加入了模型的約束中，提出了結(jié)合服務水平的目標函數(shù)。除了效率和成本，Caggiani等[13]還將客戶滿意度加入到了目標函數(shù)中作為衡量標準。2016年，Alvarez-Valdes等[14]提出了針對BSS系統(tǒng)服務水平的評價體系，并通過該評價結(jié)果進行了相應的再平衡作業(yè)調(diào)度，獲得了低成本高滿意度的調(diào)度方案。王涵霄等[15]提出了考慮共享單車臨時故障的調(diào)度模型，并結(jié)合調(diào)度滿意度概念，通過蟻群算法求解，獲得了不錯的效果。

近幾年BSS規(guī)模不斷擴大，對應的再平衡作業(yè)規(guī)模也隨之擴大，針對大規(guī)模問題，研究者們也提出了適應性的新算法與新思路。Raidl等[16]通過變鄰域搜索(Variable Neighborhood Search, VNS)算法結(jié)合最佳裝載(Optimal Loading Operations, OLO)策略給出了不錯的站點結(jié)合性鄰域結(jié)構(gòu)，局部優(yōu)化效果顯著。Gaspero[17]通過新型約束規(guī)劃結(jié)合蟻群算法，Rainer-Harbach等[18]通過VNS結(jié)合變鄰域下降(Variable Neighborhood Descent, VND)，Chemla等[2]通過Branch-and-Cut結(jié)合TS，分別對該問題進行了求解，均獲得了不錯的效果。Dell’Amico等[19]將分支定界結(jié)合整數(shù)規(guī)劃應用于解決該問題，并測試了眾多標準實例，驗證了其可行性。更進一步，Nair等[20]將“瓶頸”的思想融入了大規(guī)模BSS的運作中，將各個站點的不平衡通過雙向流的作用形成互補，極大地降低了調(diào)度作業(yè)的成本。陳桂英等[21]通過一種資源應急調(diào)度方法對BSS模型進行改善，并將模擬退火機制引入遺傳算法對該問題進行求解，獲得低成本應急調(diào)度方案，有效提升了BSS服務水平。

由于大規(guī)模BSRP需要進行調(diào)度的站點較多，調(diào)度貨車數(shù)量與周轉(zhuǎn)庫存均顯著增加，導致作業(yè)成本大幅上升，且線路規(guī)劃復雜。已有研究大多基于求解算法的創(chuàng)新，在求解模型的改進方面研究甚少。因此，在解決大規(guī)模問題時，多數(shù)已有模型與相應算法明顯乏力。本文面向大規(guī)模共享單車問題，提出一種基于站點供需狀態(tài)的分塊策略及其相應雙層禁忌搜索算法(Double-Layer Tabu Search, DL-TS)。在提出策略中，基于站點供需的配對模式有效降低了周轉(zhuǎn)庫存，基于調(diào)度貨車載量上限的線路規(guī)劃方式有效減少了作業(yè)所需車輛，嚴格的分塊訪問模式極大地簡化了調(diào)度線路規(guī)劃的復雜度。對分塊后的站點集進行內(nèi)外兩層的禁忌搜索，并在其中加入一個變異算子用于兩層之間的信息交流。

1 共享單車再平衡問題描述及建模

1.1 問題描述

該問題的物理模型描述如下：規(guī)定區(qū)域內(nèi)有若干共享單車取用站點(station)，用集合S={0,1,2,…,n}表示，其中S0為車庫。根據(jù)規(guī)劃時的數(shù)據(jù)統(tǒng)計和調(diào)查，每個除S0以外的站點Si都有預先設定的目標需求量qi，經(jīng)過一天的客戶隨機取用歸還后，每個站點的自行車數(shù)量pi會與目標需求量qi有所差異(demand)，用di表示，di=pi-qi。di>0，則Si站點過飽和，需要移出di輛自行車；di<0，則Si站點不足，需要補充di輛自行車。進行調(diào)度作業(yè)的是標準運輸貨車(vehicle)，用集合V={0,1,2,…,m}表示。每輛貨車的載量上限Q已知。在整個調(diào)度作業(yè)過程中，每輛作業(yè)貨車的實時載量e必須滿足0≤e≤Q。站點i到站點j之間的運輸距離Dij已知。單位運輸成本包括路費﹑燃油費等，與路程成正比，用C1表示，C2為自行車的單位庫存成本，C3為貨車的單位使用成本。再平衡作業(yè)就是通過貨車從車庫S0出發(fā)經(jīng)過有需求的站點，使其達到供需平衡，最后回到車庫，同時將運輸和庫存費用降至最低。本文不考慮多次訪問和臨時?？康葐栴}，每一個站點只能被一輛貨車訪問一次，且盡可能使該站點達到平衡，沒有需求的站點(di=0)禁止訪問。

1.2 問題模型

首先定義一個0-1變量：Aink：當站點i是貨車k的第n個訪問站點時(n∈P)，Aink=1；否則，Aink=0。其中P為訪問路段，P={0,1,2,…,N+1}，0為起始路段，N+1為返回路段，N是該貨車該次訪問的站點數(shù)。

多輛標準調(diào)度貨車同時作業(yè)，每個有需求的站點僅訪問一次，在不使貨車超載的條件下盡可能使該站點達到目標需求qi。目標函數(shù)以及相關約束可表示如下：

min

C2ek)+C3K。

目標函數(shù)(1)中第一項為行程消耗成本，第二項為庫存成本，第三項為貨車調(diào)用成本，通過對站點和路段的依次求和，對滿足AinkAj(n+1)k≠0的路段，即實際作業(yè)行駛路段，進行成本計算求和，ek表示貨車k初始載量。約束(2)保證了每一個站點只能被一輛貨車訪問一次；約束(3)保證了一輛貨車在一個時間段中最多只能出現(xiàn)在一個站點；約束(4)保證了每輛貨車在尚未訪問緊前站點之前不允許訪問其下一站點，即不允許跳過訪問，這是多車模型中避免遺漏訪問的約束手段；約束(5)和約束(6)保證了每輛貨車從車庫S0出發(fā)，之后還要返回車庫S0一次；約束(7)保證了每一輛貨車在整個調(diào)度作業(yè)過程中的載量不超過上限Q；約束(8)和約束(9)分別對ek和Aink進行了說明。

1.3 目標函數(shù)

本文通過站點的需求狀態(tài)進行站點分組，生成站點族，并且通過所設計的分塊算法使得生成的站點族內(nèi)部可以自給自足，因此將每一個站點族稱為“零需”站點集，用xdpi表示，下一節(jié)將對其生成方式進行詳細介紹。對于每一個“零需”站點集xdpi，保證其由一輛調(diào)度貨車完成作業(yè)，因此只需對“零需”站點集xdpi進行訪問路線生成。

單車作業(yè)成本函數(shù)：

(10)

多車作業(yè)成本函數(shù)：

(11)

本文對“零需”站點集xdpi的提出，使得∑ek趨近于“0”，庫存成本不用考慮；同時，單車﹑多車作業(yè)均是以xdpi為單位展開的，∑D不會有較大差異。因此，最終導致兩者成本較大差異的就是多車中的貨車調(diào)度成本C3K。若只考慮成本函數(shù)(11)，顯然調(diào)度車輛數(shù)K越多，成本越高，因為式(11)沒有考慮調(diào)度作業(yè)的時間成本。很多調(diào)度項目，不僅對作業(yè)成本有要求，還對作業(yè)時間有要求，而多車作業(yè)在本文所給出的算法中顯然能降低作業(yè)時間，因此在作業(yè)時間較為緊張時采用多車同時作業(yè)模式。

2 基于站點供需的分塊策略

本文通過站點需求配對策略所生成的“零需”站點集，有效地避免了每一個站點處進行放置或取走多少數(shù)量單車的決策，極大地降低了問題的復雜度。具體思想是在站點分類訪問的基礎上，將分類后的站點進行需求配對，形成“零需”站點集。在該站點集內(nèi)，通過相互調(diào)度達到每個站點的目標需求而無需外界干預。因此，在理論上，調(diào)度貨車在對該站點集進行再平衡作業(yè)時無需攜帶單車，作業(yè)完成后也不會有剩余單車攜帶，從而可以直接進行下一個站點集的訪問。該種分類訪問的理論依據(jù)是：系統(tǒng)運行之初，各個站點均處于供需平衡狀態(tài)，理想狀況下，整個BSS的單車數(shù)量是不會變化的，有站點不足必定有站點過飽和，而總的供需關系是平衡的，由此將整個系統(tǒng)劃分為一個個可以自給自足的“零需”站點集，調(diào)度貨車只需搬運，無需提供或移出單車，這就使得理想狀況下，周轉(zhuǎn)庫存可以設置為零。但考慮到實際系統(tǒng)運作中，存在部分共享單車未按庫停放以及報廢等意外情況，應結(jié)合實際數(shù)據(jù)統(tǒng)計設置一個根據(jù)系統(tǒng)總規(guī)模按一定比例生成的安全周轉(zhuǎn)庫存，保障意外情況下系統(tǒng)的正常運作，由于安全周轉(zhuǎn)庫存對總成本影響極小，本文不對其作具體設置。標準案例求解結(jié)果顯示，在該策略下，原庫存量減少達80%以上。

2.1 解的表達方式

分塊算法中，解的表達較為簡單，采用基于調(diào)度貨車和站點的編碼方式，例如：調(diào)用編號為1的貨車V1依次訪問站點3﹑站點2﹑站點5﹑站點4﹑站點1，則解x={V1|S3，S2，S5，S4，S1}，其中第一位為貨車編號，后面為按訪問順序依次排列的站點編號。在算法部分將進一步詳細介紹本文編碼和解碼方式。

2.2 分塊策略算法步驟

分塊策略算法具體步驟如下：

(1)根據(jù)調(diào)度作業(yè)開始時各個站點的狀態(tài)將站點分為3類：piqi，即需要移出(pick-up)共享單車站點集合Sp；pi=qi，即供需平衡(balanced)的站點集合Sb，無需訪問，如圖1所示。

(2)分別對站點集合Sd和Sp內(nèi)所有站點隨機選擇起始站點S1，通過基于距離的貪婪搜索算法進行旅行商問題(Traveling Sales-man Problem, TSP)求解，生成單條總鏈Xd和Xp,如圖2所示。

(3)對Xd(Xp)進行切斷操作。從每條鏈的起始站點S1開始，依次計算訪問站點需求度之和T，當訪問下一站點將導致T>Q時，由此處切斷Xd(Xp)，T初始化為0，繼續(xù)訪問下一站點，直到單鏈Xd(Xp)被分割成一系列需求度近似為Q的子鏈xdi(xpi)，如圖3和圖4所示。

(4)計算每條子鏈xdi(xpi)的站點幾何中心(center)坐標xdic(xpic)(式(12))，即每條子鏈xdi(xpi)內(nèi)站點坐標的均值作為其幾何中心坐標，如圖5所示。

(12)

(5)用幾何中心坐標xdic(xpic)代表子鏈xdi(xpi)進行一一配對，每一個xdic選擇距離自己最近的xpic配對，xdic+xpic=xdpic，即xdi+xpi=xdpi，由xdpic所代表的站點集xdpi即為“零需”個體集(生成i個“零需”個體集)，如圖6所示。

每一個通過該方法生成的“零需”站點集均可僅由一輛標準作業(yè)貨車完成再平衡作業(yè)，即在整個作業(yè)過程中車載不會超過載量上限Q。因為|Txdi|≤Q,|Txpi|≤Q，而Txdi,Txpi異號，所以在“零需”站點集xdpi內(nèi)的任一訪問次序的實時需求度之和Txdpi都將滿足|Txdpi|≤Q。

3 雙層禁忌搜索算法(DL-TS)求解共享單車再平衡問題

較大規(guī)模的BSRP站點數(shù)量一般在100個以上，其調(diào)度作業(yè)貨車和倉庫數(shù)量一般不唯一。由于該問題的NP-hard特性，其決策復雜度和計算復雜度急劇上升。本文所提算法針對較大規(guī)模問題，主要思路便是將整個優(yōu)化問題劃分為許多各自相互獨立的子問題，即本文所提出的“零需”站點集xdpi，利用TS高效的局部搜索能力，最優(yōu)化每個子問題，獲得每個“零需”站點集xdpi內(nèi)部的最優(yōu)調(diào)度路線；再對優(yōu)化后的“零需”站點集xdpi進行訪問排序，從而給出整體調(diào)度路線的最優(yōu)解。所設計的雙層禁忌搜索，內(nèi)層針對“零需”站點集內(nèi)部調(diào)度路線的優(yōu)化，外層針對“零需”站點集訪問路線的優(yōu)化；設計的變異算子用來提升各個子問題之間的交互作用，根據(jù)當前解的實際情況對之前的“零需”站點集分塊進行微調(diào)，以獲得最優(yōu)解。該改進算法類似分治思想，化大規(guī)模問題為相互獨立子問題，將子問題和總問題分別分配給相互獨立的兩層算法同時由變異算子進行聯(lián)系，極大地降低了原問題的計算復雜度。

3.1 編碼

本文提出的雙層禁忌搜索算法解的編碼分為內(nèi)層和外層，即“每個零需站點集xdpi內(nèi)部站點”和“所有零需站點集xdpi”兩層，均采用自然數(shù)編碼。

(1)內(nèi)層 針對每個“零需”站點集xdpi內(nèi)部站點訪問排序，采用基于調(diào)度貨車和站點的編碼方式，即如果編號為1的調(diào)度貨車V1需要訪問編號為1～5的所有站點，訪問的順序為站點4、站點1、站點3、站點5、站點2，則可得到解x={V1|S4，S1，S3，S5，S2}，其中第一位為貨車編號，后面為順次排列的站點編號，當未確定訪問貨車編號時，首位置為0。解碼過程為編碼的逆過程，即如果獲得解x={V2|S7，S9，S6，S8}，則表示編號為2的調(diào)度貨車V2順次訪問站點7、站點9、站點6、站點8。

(2)外層 針對全部“零需”站點集xdpi訪問排序，采用基于調(diào)度貨車和“零需”站點集xdpi的編碼方式，即如果編號為1的調(diào)度貨車V1需要訪問編號為1～5的“零需”站點集xdpi，訪問順序為xdp3、xdp2、xdp1、xdp5、xdp4，則可得到解X={V1|xdp3，xdp2，xdp1，xdp5，xdp4}，其中第一位為貨車編號，后面為順次排列的“零需”站點集xdpi編號，當未確定訪問貨車編號時，首位置為0。解碼時，如果獲得解X={V2|xdp7，xdp9，xdp6，xdp8}，則表示編號為2的調(diào)度貨車V2順次訪問“零需”站點集xdp7、xdp9、xdp6、xdp8。

3.2 初始解生成

內(nèi)層初始解x0i生成方式為：對于每一個站點集xdpi，在其內(nèi)部進行基于距離的貪婪搜索生成內(nèi)部站點的訪問序列作為初始解。外層初始解X0生成方式為：以每一個站點集xdpi中心坐標xdpic代表其地理位置，進行基于距離的貪婪搜索生成站點集xdpi的訪問序列作為初始解。

3.3 算法設計

(1)鄰域結(jié)構(gòu)

1)2-opt算子?！傲阈琛闭军c集xdpi內(nèi)相鄰順次訪問的兩個站點之間(Sa，Sb)交換訪問次序，如圖7所示。

2)貪心移位算子。隨機選擇xdpi內(nèi)一站點Srand，將xdpi中距離該站點最近的站點Snear移位至Srand的緊鄰訪問站點位置(Srand，μ)，包括緊前(Srand，-1)或緊后(Srand，+1)，如圖8所示。

(2)禁忌對象

將移動屬性作為禁忌對象，對于2-opt算子，禁忌對象為(Sa，Sb)；對于貪心移位算子，禁忌對象為(Srand，μ)。

(3)特赦準則

1)當前鄰域中的被禁移動將產(chǎn)生歷史最好解時，破禁。

2)當前鄰域中所有移動均被禁時，選擇剩余禁忌步長最短的移動進行破禁。

(4)禁忌列表和禁忌長度

禁忌列表長度指被禁忌解的個數(shù)以及被禁忌的步長，該長度設置直接影響到算法跳出局部最優(yōu)和快速收斂的能力。因此，本文將根據(jù)xdpi的規(guī)模和特性動態(tài)的設置禁忌表長度。

(5)變異算子

本文設計的變異算子作用于兩個不同的“零需”站點集，對滿足變異條件的站點集進行內(nèi)部站點隨機交換操作，生成兩個新的“零需”站點集。具體內(nèi)容如下：

(13)

(6)評價函數(shù)

對于每個xdpi通過TS生成解的評價由評價函數(shù)式(14)計算，即生成解所對應訪問線路長度之和的倒數(shù)：

(14)

3.4 算法流程

(1)“零需”站點集xdpi作業(yè)優(yōu)化流程

1)由式(15)計算每一個“零需”站點集xdpi的幾何中心坐標xdpic，即每個“零需”站點集xdpi內(nèi)站點坐標的均值作為其幾何中心坐標：

(15)

2)以xdpic坐標代表xdpi，通過本文所提出的TS對所有xdpi進行訪問線路求解生成其最優(yōu)訪問路線XB。

3)在每個“零需”站點集xdpi內(nèi)部，通過本文所提出的改進TS進行求解，生成內(nèi)部最優(yōu)訪問路線xBi?！傲阈琛眰€體xdpi內(nèi)部起始站點通過遍歷每一個內(nèi)部站點S從中選擇使得內(nèi)部訪問總線路di最小的點作為最優(yōu)隨機起始站點SS，由此產(chǎn)生的結(jié)束站點為Se，通過SS生成的訪問路線作為xBi。

4)由式(13)進行變異操作判斷，滿足則進行變異操作，產(chǎn)生較優(yōu)解則替換原有解，否則不變異。

5)實際線路解Xa生成。將由XB確定的“零需”站點集xdpi間的連接路線換成xdpi內(nèi)部站點SS與Se之間的路線，根據(jù)每個xdpi個體內(nèi)部最優(yōu)訪問路線xBi，計算最終總體實際線路解Xa長度之和LXa(如式(16)所示)及該線路下作業(yè)總成本W(wǎng)。

(16)

“零需”站點集xdpi作業(yè)優(yōu)化實現(xiàn)偽代碼如下：

算法2改進TS生成的訪問順序

輸入：由分支定界算法獲得的W的下界WLB和w的下界wLB

1：Construct XB

Calculate all xdpic

X0=GreedySearch,W0=W(X0),X*=X0,W*=W0

While W*>WLB

End if

End while

Return XB

2：Construct xBi

Set i=1

While i

Do x0=GreedySearch,w0=w(x0)

Set x*=x0,w*=w0

While w*>wLB

End if

End while

End while

Return xBi

(2)算法總體流程

本文所提出的雙層禁忌搜索算法可分為兩部分：

1)基于供需關系對站點進行分塊形成“零需”站點集xdpi。

2)基于DL-TS算法的各個站點族內(nèi)部訪問線路生成以及針對xdpi個體的總路線規(guī)劃。

步驟1基于站點供需的分塊算法生成“零需”站點集xdpi。

步驟2以xdpic坐標代表xdpi，對所有xdpi進行求解生成其初始訪問路線X0。

步驟3在xdpi內(nèi)部選擇隨機初始站點，依據(jù)基于距離的貪婪搜索算法生成xdpi內(nèi)部初始解x0i。

步驟4根據(jù)式(14)計算解的適值函數(shù)，判斷是否滿足終止條件，滿足則轉(zhuǎn)步驟8，否則轉(zhuǎn)步驟5。

步驟5對每一個xdpi的初始解x0i采用本文所設計的TS算法進行內(nèi)部優(yōu)化使其達到內(nèi)部最優(yōu)解xBi。

步驟7計算變異后的xdpi和xdpic，并對變異后的xdpi進行求解，生成其改進訪問路線Xi，返回步驟4。

步驟8算法結(jié)束。

4 實驗結(jié)果及分析

本文測試實例采用國外標準案例——法國巴黎的Vélib共享單車系統(tǒng)。本文選取了其中150個常用站點，獲取其相對地理位置﹑站點容量以及平均供需量等必要信息。該標準案例為大規(guī)模BSRP實例，其調(diào)度貨車及車庫均不唯一，且該實例已經(jīng)過國外眾多學者測試，其中近五年來較為成功的有文獻[4]和文獻[9]等。

在實驗中，目標函數(shù)下界采用分支定界獲得，在CPLEX 12.7軟件運行；雙層禁忌搜索算法采用C++語言進行編譯，在Microsoft Visual Studio 2013上運行，計算機處理器Intel(R)Core(TM)i5-4200H CPU @2.80 GHz,RAM8.00 GB。本文測試的樣本分類如下：站點規(guī)模n：20/40/60/80/100/125/150；貨車載量Q：15/25/45；貨車數(shù)量K：1/2/3。

雙層禁忌搜索算法參數(shù)設計如下：相關參數(shù)設計依賴于具體問題規(guī)模n0，在內(nèi)層搜索中n0為每個站點集內(nèi)所含站點的個數(shù)；在外層搜索中，n0為站點集的總個數(shù)。根據(jù)本文具體問題規(guī)模和貨車載量Q的實際情況，供需策略分組后生成的n0范圍均在30以內(nèi)，因此設計最小禁忌步長Lmin=3，最小迭代總次數(shù)Itermin=1000，無改進最大迭代次數(shù)Iterno=100。動態(tài)參數(shù)設計，禁忌步長L=Lmin+[n0/5]，迭代總次數(shù)Iter=Itermin+100[n0/5]，其中[x]表示不超過x的最大整數(shù)。

4.1 實驗結(jié)果分析

如表1～表3所示分別為單車實驗測試、多車實驗測試和綜合實驗測試結(jié)果，具體內(nèi)容包括分支定界算法獲得的目標函數(shù)下界(LB)、DL-TS算法獲得的目標函數(shù)值及其與LB之間的Gap值、DL-TS算法的Cpu平均計算時間，并且給出了對比算法GA-TS求解相同案例獲得結(jié)果的Gap值以及Cpu平均計算時間。其中目標函數(shù)下界(LB)是通過分支定界算法在2 h內(nèi)給出的，當站點規(guī)模n超過100時，分支定界在2 h內(nèi)已無法給出最優(yōu)解，而提出DL-TS算法能在100 s以內(nèi)獲得較優(yōu)解。

表1 單車實驗求解結(jié)果(C1=0.001，C2=0.5，C3=10/15/20)

續(xù)表1

表2 多車實驗求解結(jié)果(C1=0.001，C2=0.5，C3=10/15/20)

表3 單車和多車實驗結(jié)果綜合比較(C1=0.001，C2=0.5，C3=10/15/20)

續(xù)表3

表中參數(shù)說明如下：

n為站點規(guī)模即站點數(shù)量；

Q為度作業(yè)貨車載量上限；

K為調(diào)度作業(yè)貨車數(shù)量；

LB為分支定界在CPLEX上運行2 h內(nèi)獲得的目標函數(shù)下界Lower Bound；

W為目標函數(shù)值；

Gap為W與LB的百分差；

Cpu為算法求解時間，單位:s。

影響目標函數(shù)以及Cpu耗時的自變量包括站點規(guī)模n、貨車載量Q、調(diào)度貨車數(shù)量K。站點規(guī)模對目標函數(shù)以及Cpu的影響是顯而易見的，由表1～表3均可看出，n越大，W以及Cpu越大，且由于該問題的超NP-hard特性，普通算法在解決該問題上消耗的Cpu與n呈指數(shù)級別的增長(如分支定界，線性規(guī)劃等)。本文在啟發(fā)式算法基礎上，進一步利用供需關系將大規(guī)模問題進行分塊求解，使得Cpu隨問題規(guī)模增加而急速上升的指數(shù)型增長趨勢轉(zhuǎn)化為了線性型增長趨勢，大大提高了算法的效率。對于100以內(nèi)的站點，能在較短的時間內(nèi)獲得解，并通過與分支定界下界的求解(LB)比較，能證明其為最優(yōu)解；當n超過100時，分支定界已無法在2 h內(nèi)給出結(jié)果，將其在2 h內(nèi)獲得的LB與DL-TS算法獲得結(jié)果進行比較，Gap均小于5%，DL-TS算法消耗Cpu始終在100 s以內(nèi)。如圖10所示顯示了作業(yè)規(guī)模n對算法Cpu的影響。

對于調(diào)度貨車載量上限Q，許多學者在該問題的求解上并沒有過多考慮其對調(diào)度作業(yè)的影響，如Forma等[6]僅考慮一種標準作業(yè)貨車，也是有一定道理的，畢竟同一地區(qū)的作業(yè)貨車一般為同一型號。本文將其作為一個重要自變量，并分為15/25/45三種載量上限，一是由于本文站點的分塊與Q關系緊密，二是調(diào)度所用貨車的載量上限Q對于調(diào)度作業(yè)確實具有較大影響，大致可概述為Q越大，成本目標函數(shù)W越小，當在大規(guī)模作業(yè)時(n>80)尤為明顯；但在小規(guī)模作業(yè)時(n<60)反而會出現(xiàn)Q越大，成本目標函數(shù)W越大的情況，尤其是多車作業(yè)(如表2)。這是由于Q增大，貨車在調(diào)度過程中不易達到載量上限而不用返回車庫，在本文的分塊算法中表現(xiàn)為“零需”站點集xdpi規(guī)模更大，個數(shù)更少，減少了貨車往返次數(shù)。但Q增大意味著調(diào)用成本C3更大，因此需要根據(jù)問題的規(guī)模選擇適當載量的貨車，能很好地降低作業(yè)成本。其次，在對算法性能的影響上，由于Q增大，導致xdpi個數(shù)減少，減少了計算量，使得Cpu降低。如圖10顯示了車載上限Q對算法Cpu的影響。

對于調(diào)度貨車數(shù)量K，由于本文的分塊模式，一個xdpi僅由一輛調(diào)度貨車進行作業(yè)，不會出現(xiàn)像其他算法中對多車調(diào)度線路分配的問題，因此調(diào)度貨車的數(shù)量K越多，調(diào)度作業(yè)時間越短。表3中，為了體現(xiàn)比較的客觀性，在目標函數(shù)中沒有加入時間換算而來的成本，因為時間成本是一個較為主觀的成本，工期越緊迫，時間成本自然就越高?？梢园l(fā)現(xiàn)，隨著調(diào)度貨車數(shù)量增多，W普遍減小，規(guī)模較大時較為明顯，但也會出現(xiàn)反例(n=80，Q=45；n=100，Q=15)。Cpu的情況則較為簡單，隨著K增多，Cpu增加，如圖11所示。

4.2 實驗結(jié)果比較

本文提出的DL-TS算法與已有GA-TS算法詳細對比如表1﹑表2和表3。首先，單獨分析GA-TS算法結(jié)果，可以發(fā)現(xiàn)其與DL-TS在算法特性上極為相似，3大變量(n，Q，K)對其獲得的目標函數(shù)值以及Cpu消耗影響幾乎與DL-TS算法一樣，在該條件下進行兩種算法性能比較更為合理客觀。通過兩種算法獲得結(jié)果對比可以發(fā)現(xiàn)，GA-TS算法無論在目標函數(shù)求解結(jié)果還是在Cpu消耗上均不及本文所提出的DL-TS算法。GA-TS在n=60時，部分案例已不能獲得最優(yōu)解，并且在求解大規(guī)模案例n=150時，Gap值已達10%左右，為DL-TS算法的兩倍以上。分析其原因，在Cpu的消耗上，GA-TS算法在模型優(yōu)化上未能有效解決規(guī)模增大所帶來的計算復雜度呈指數(shù)形式上升的問題；在目標函數(shù)值上，DL-TS是在結(jié)合了供需關系模型的基礎上進行算法設計的，模型與算法的有機結(jié)合，相互能較好地適應與配合，達到目標函數(shù)中庫存單項成本顯著降低的效果。以上對比均體現(xiàn)了本文算法與模型在針對該問題時的優(yōu)越性。

為進一步驗證本文所提模型與算法的有效性，選取兩位前人研究成果進行對比分析。本文提出的DL-TS算法與Chemla等[2]提出的BC-TS(brunch-and-cut & tabu search)算法比較如表4所示，BC-TS算法未采用分塊訪問，直接通過分支定界結(jié)合禁忌搜索獲得的結(jié)果。顯然，本文的分塊策略在改善計算復雜度上具有顯著效果，大大縮短了相同規(guī)模問題的計算時間，并且由于增添變異算子，使得目標函數(shù)更接近函數(shù)下界，顯著提高了最優(yōu)解的獲得概率，充分體現(xiàn)了本文采用的供需分塊模型的有效性。

本文提出的DL-TS算法與Forma等[6]提出的3-step算法比較如表5所示，3-step與本文所提出的分塊訪問類似，其第一步是將站點進行分塊，但分塊方式是基于距離主導的形式，需求次之，其結(jié)果同樣可以證明分塊訪問對解決該類問題的有效性，但其結(jié)果略遜于本文所提出的基于供需關系的分塊模式，他將各個站點的庫存水平分為3種：Light/Real/Heavy，3種情況下的求解結(jié)果平均Gap普遍大于本文所提算法，如圖12所示，充分體現(xiàn)了本文所提算法與供需分塊模型有機結(jié)合的效果顯著。

表4 DL-TS算法與BC-TS算法結(jié)果對比

表5 基于供需的分塊與基于距離的分塊結(jié)果對比

5 結(jié)束語

共享單車系統(tǒng)近幾年在國內(nèi)逐步興起，發(fā)展勢頭迅猛。然而，國內(nèi)期刊針對共享單車再平衡問題進行深入研究的論文甚少，并且求解算法陳舊，模型創(chuàng)新性嚴重不足。本文提出一種結(jié)合供需關系的站點分類策略模型，并設計了相應的雙層禁忌搜索算法解決大規(guī)模共享單車再平衡作業(yè)問題。其中，供需關系的站點分類策略是通過過飽和站點和不足站點之間的配對，形成能自給自足的站點集，對這樣的站點集進行再平衡作業(yè)，能有效避免一般模型中調(diào)度貨車在各個站點進行取走或放置單車數(shù)量的決策過程，同時由于站點間的自給自足，使單車的庫存成本降低了80%以上；在算法上，采用改進的雙層禁忌搜索算法，分別基于分塊站點集合和站點集合內(nèi)部進行禁忌搜索，并通過一個嵌套變異算子，增強兩層搜索間的信息交流，在提高算法搜索能力的同時增添了解的多樣性。經(jīng)過標準案例測試，能在Cpu消耗100 s內(nèi)獲得150站點以內(nèi)較優(yōu)解，同時保證了較低的作業(yè)成本，證實了該策略針對較大規(guī)模再平衡作業(yè)的有效性。未來考慮將LNS以及VNS結(jié)合的分治思想，使更大規(guī)模再平衡作業(yè)中所涉及的多個NP-Hard問題能轉(zhuǎn)化為一個NP-Hard問題，降低其計算復雜度和時間復雜度。