基于雙層禁忌搜索算法的共享單車再平衡問題

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

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

0 引言

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

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

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

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

近幾年BSS規(guī)模不斷擴(kuò)大，對應(yīng)的再平衡作業(yè)規(guī)模也隨之?dāng)U大，針對大規(guī)模問題，研究者們也提出了適應(yīng)性的新算法與新思路。Raidl等[16]通過變鄰域搜索(Variable Neighborhood Search, VNS)算法結(jié)合最佳裝載(Optimal Loading Operations, OLO)策略給出了不錯的站點(diǎn)結(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，分別對該問題進(jìn)行了求解，均獲得了不錯的效果。Dell’Amico等[19]將分支定界結(jié)合整數(shù)規(guī)劃應(yīng)用于解決該問題，并測試了眾多標(biāo)準(zhǔn)實例，驗證了其可行性。更進(jìn)一步，Nair等[20]將“瓶頸”的思想融入了大規(guī)模BSS的運(yùn)作中，將各個站點(diǎn)的不平衡通過雙向流的作用形成互補(bǔ)，極大地降低了調(diào)度作業(yè)的成本。陳桂英等[21]通過一種資源應(yīng)急調(diào)度方法對BSS模型進(jìn)行改善，并將模擬退火機(jī)制引入遺傳算法對該問題進(jìn)行求解，獲得低成本應(yīng)急調(diào)度方案，有效提升了BSS服務(wù)水平。

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

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

1.1 問題描述

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

1.2 問題模型

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

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

min

C2ek)+C3K。

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

1.3 目標(biāo)函數(shù)

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

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

(10)

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

(11)

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

2 基于站點(diǎn)供需的分塊策略

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

2.1 解的表達(dá)方式

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

2.2 分塊策略算法步驟

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

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

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

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

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

(12)

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

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

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

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

3.1 編碼

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

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

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

3.2 初始解生成

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

3.3 算法設(shè)計

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

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

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

(2)禁忌對象

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

(3)特赦準(zhǔn)則

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

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

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

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

(5)變異算子

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

(13)

(6)評價函數(shù)

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

(14)

3.4 算法流程

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

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

(15)

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

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

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

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

(16)

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

算法2改進(jìn)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)基于供需關(guān)系對站點(diǎn)進(jìn)行分塊形成“零需”站點(diǎn)集xdpi。

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

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

步驟2以xdpic坐標(biāo)代表xdpi，對所有xdpi進(jìn)行求解生成其初始訪問路線X0。

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

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

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

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

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

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

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

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

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

4.1 實驗結(jié)果分析

如表1～表3所示分別為單車實驗測試、多車實驗測試和綜合實驗測試結(jié)果，具體內(nèi)容包括分支定界算法獲得的目標(biāo)函數(shù)下界(LB)、DL-TS算法獲得的目標(biāo)函數(shù)值及其與LB之間的Gap值、DL-TS算法的Cpu平均計算時間，并且給出了對比算法GA-TS求解相同案例獲得結(jié)果的Gap值以及Cpu平均計算時間。其中目標(biāo)函數(shù)下界(LB)是通過分支定界算法在2 h內(nèi)給出的，當(dāng)站點(diǎn)規(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為站點(diǎn)規(guī)模即站點(diǎn)數(shù)量；

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

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

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

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

Gap為W與LB的百分差；

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

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

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

對于調(diào)度貨車數(shù)量K，由于本文的分塊模式，一個xdpi僅由一輛調(diào)度貨車進(jìn)行作業(yè)，不會出現(xiàn)像其他算法中對多車調(diào)度線路分配的問題，因此調(diào)度貨車的數(shù)量K越多，調(diào)度作業(yè)時間越短。表3中，為了體現(xiàn)比較的客觀性，在目標(biāo)函數(shù)中沒有加入時間換算而來的成本，因為時間成本是一個較為主觀的成本，工期越緊迫，時間成本自然就越高。可以發(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算法詳細(xì)對比如表1﹑表2和表3。首先，單獨(dú)分析GA-TS算法結(jié)果，可以發(fā)現(xiàn)其與DL-TS在算法特性上極為相似，3大變量(n，Q，K)對其獲得的目標(biāo)函數(shù)值以及Cpu消耗影響幾乎與DL-TS算法一樣，在該條件下進(jìn)行兩種算法性能比較更為合理客觀。通過兩種算法獲得結(jié)果對比可以發(fā)現(xiàn)，GA-TS算法無論在目標(biāo)函數(shù)求解結(jié)果還是在Cpu消耗上均不及本文所提出的DL-TS算法。GA-TS在n=60時，部分案例已不能獲得最優(yōu)解，并且在求解大規(guī)模案例n=150時，Gap值已達(dá)10%左右，為DL-TS算法的兩倍以上。分析其原因，在Cpu的消耗上，GA-TS算法在模型優(yōu)化上未能有效解決規(guī)模增大所帶來的計算復(fù)雜度呈指數(shù)形式上升的問題；在目標(biāo)函數(shù)值上，DL-TS是在結(jié)合了供需關(guān)系模型的基礎(chǔ)上進(jìn)行算法設(shè)計的，模型與算法的有機(jī)結(jié)合，相互能較好地適應(yīng)與配合，達(dá)到目標(biāo)函數(shù)中庫存單項成本顯著降低的效果。以上對比均體現(xiàn)了本文算法與模型在針對該問題時的優(yōu)越性。

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

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

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

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

5 結(jié)束語

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