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

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

0 引言

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

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

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

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

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

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

1 共享單車再平衡問(wèn)題描述及建模

1.1 問(wèn)題描述

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

1.2 問(wèn)題模型

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

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

min

C2ek)+C3K。

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

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

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

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

(10)

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

(11)

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

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

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

2.1 解的表達(dá)方式

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

2.2 分塊策略算法步驟

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

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

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

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

(4)計(jì)算每條子鏈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)行一一配對(duì)，每一個(gè)xdic選擇距離自己最近的xpic配對(duì)，xdic+xpic=xdpic，即xdi+xpi=xdpi，由xdpic所代表的站點(diǎn)集xdpi即為“零需”個(gè)體集(生成i個(gè)“零需”個(gè)體集)，如圖6所示。

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

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

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

3.1 編碼

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

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

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

3.2 初始解生成

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

3.3 算法設(shè)計(jì)

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

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

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

(2)禁忌對(duì)象

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

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

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

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

(4)禁忌列表和禁忌長(zhǎng)度

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

(5)變異算子

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

(13)

(6)評(píng)價(jià)函數(shù)

對(duì)于每個(gè)xdpi通過(guò)TS生成解的評(píng)價(jià)由評(píng)價(jià)函數(shù)式(14)計(jì)算，即生成解所對(duì)應(yīng)訪問(wèn)線路長(zhǎng)度之和的倒數(shù)：

(14)

3.4 算法流程

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

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

(15)

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

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

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

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

(16)

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

算法2改進(jìn)TS生成的訪問(wèn)順序

輸入：由分支定界算法獲得的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)系對(duì)站點(diǎn)進(jìn)行分塊形成“零需”站點(diǎn)集xdpi。

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)結(jié)果及分析

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

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

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

4.1 實(shí)驗(yàn)結(jié)果分析

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

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

續(xù)表1

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

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

續(xù)表3

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

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為算法求解時(shí)間，單位:s。

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

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

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

4.2 實(shí)驗(yàn)結(jié)果比較

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

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

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

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

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

5 結(jié)束語(yǔ)

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