馬艷利,陳明秀

(1.寧夏大學(xué)新華學(xué)院 信息與計(jì)算機(jī)科學(xué)系, 寧夏 銀川 750021; 2.寧夏大學(xué)新華學(xué)院 工程與應(yīng)用科學(xué)系，寧夏 銀川 750021)

0 引言

隨著我國(guó)經(jīng)濟(jì)的快速發(fā)展，城市交通問題和擁堵問題日益嚴(yán)重.共享車作為一種新型的出行工具，解決了城市“最后一公里”問題.共享車在運(yùn)行過程中自發(fā)地產(chǎn)生了供需不平衡問題，為了解決這一問題，需要對(duì)車輛進(jìn)行調(diào)度，這個(gè)調(diào)度過程被稱為共享車調(diào)度問題(bikesharing rebalance problem，BRP).

現(xiàn)有研究中，共享車調(diào)度大致分為兩類：靜態(tài)共享車調(diào)度(SBRP)和動(dòng)態(tài)共享車調(diào)度(DBRP).靜態(tài)調(diào)度相關(guān)文獻(xiàn)大多都圍繞著再平衡操作而確定車輛路線，將所研究區(qū)域分割成小區(qū)域，用平衡工具進(jìn)行再平衡操作.不同的文獻(xiàn)對(duì)所考慮的假設(shè)、要優(yōu)化的目標(biāo)和要整合的約束條件各不相同，且各有優(yōu)缺點(diǎn).文獻(xiàn)[1]通過構(gòu)建最小化貨車訪問路線總成本的目標(biāo)函數(shù)來實(shí)現(xiàn)靜態(tài)調(diào)運(yùn)，采用迭代局部搜索的啟發(fā)式算法求解；文獻(xiàn)[2]提出若干有效不等式，建立了數(shù)學(xué)模型，利用禁忌搜索算法求解.由于調(diào)度周期長(zhǎng)，最優(yōu)解局限于局部，部分文獻(xiàn)考慮調(diào)度周期的問題.文獻(xiàn)[3]為了滿足共享車快速響應(yīng)調(diào)運(yùn)和降低調(diào)運(yùn)成本的需求，構(gòu)造了基于分形數(shù)的多車場(chǎng)協(xié)同調(diào)運(yùn)模型；對(duì)動(dòng)態(tài)調(diào)度，文獻(xiàn)[4]研究的是時(shí)變環(huán)境下，結(jié)合不同類型單車之間的替代特性，建立了混合整數(shù)規(guī)劃模型，并設(shè)計(jì)了混合禁忌搜索算法對(duì)問題進(jìn)行求解；Kadri[5]提出了一個(gè)已知的閾值水平，表示每個(gè)站點(diǎn)平衡共享車數(shù)量，再平衡需求僅用于滿足閾值水平即可.文獻(xiàn)[5]采用一個(gè)平衡點(diǎn)，平衡操作次數(shù)較大，平衡時(shí)間較長(zhǎng).本文將站點(diǎn)的平衡定義為平衡區(qū)間，代替文獻(xiàn)[5-6]中的平衡點(diǎn)，站點(diǎn)內(nèi)的共享車庫(kù)存處于這個(gè)區(qū)間，都屬于平衡，可減少平衡次數(shù).另外，本文定義新的評(píng)價(jià)滿意度的指標(biāo)函數(shù)-再平衡效益衡量函數(shù)，在此基礎(chǔ)上建立以總行程距離最小和再平衡效益衡量函數(shù)最大的雙目標(biāo)函數(shù)，提出基于變領(lǐng)域搜索的粒子群-禁忌搜索算法對(duì)問題進(jìn)行求解.

本文研究靜態(tài)共享車再平衡問題(SBRP).文章結(jié)構(gòu)是：第2節(jié)介紹了實(shí)用的平衡彈性間隔概念，在此基礎(chǔ)上定義站點(diǎn)平衡程度的指標(biāo)-再平衡效益衡量函數(shù)，建立以路線最小化和再平衡效益衡量函數(shù)最大化的混合整數(shù)規(guī)劃雙目標(biāo)模型，這是本文的主要內(nèi)容之一；第3節(jié)介紹粒子群-禁忌搜索算法，為避免陷入局部最優(yōu)，提高探索能力，引入3種結(jié)構(gòu)的變異算子；第4節(jié)主要是對(duì)改進(jìn)的粒子群-禁忌搜索算法進(jìn)行收斂性分析.

1 BBS平衡問題描述和數(shù)學(xué)建模

混合整數(shù)非線性規(guī)劃模型是經(jīng)典的求解路徑最短問題模型，下面是標(biāo)準(zhǔn)的規(guī)劃模型[7]：

由于整數(shù)問題較難求解，將INLP問題轉(zhuǎn)化成其相應(yīng)的松弛問題NLP,即不考慮決策變量的整數(shù)要求，

1.1 平衡彈性區(qū)間

在以往的研究中，BSS站的平衡被定義為一個(gè)預(yù)先指定的平衡點(diǎn)，即站點(diǎn)共享車數(shù)量需要達(dá)到預(yù)定的數(shù)量，如文獻(xiàn)[5-6]采用這種定義方法.這種定義法需要多次平衡操作，平衡時(shí)間較長(zhǎng).本文將平衡點(diǎn)擴(kuò)展到平衡區(qū)間，共享車數(shù)量落到預(yù)定平衡區(qū)間，可視為達(dá)到平衡，這種定義法可減少平衡時(shí)間，減少旅行成本.

當(dāng)α=0時(shí)，平衡間隔區(qū)間為平衡點(diǎn)，是平衡間隔區(qū)間的一個(gè)特例.顯然，α的值不同會(huì)導(dǎo)致平衡區(qū)間的大小不同.一條訪問路線的各站點(diǎn)庫(kù)存情況如表1所列.假設(shè)站點(diǎn)j的目標(biāo)庫(kù)存為30，α=0.2.采用平衡間隔后，平衡區(qū)間為[24,36]，則1、2、4、14站的庫(kù)存處于平衡區(qū)間.

表1 站點(diǎn)庫(kù)存情況

另外每個(gè)站點(diǎn)既需要足夠的共享車以滿足用戶的租賃需求，又需要足夠的空位來滿足用戶歸還共享車的需求.因此，站點(diǎn)服務(wù)功能包括共享車租賃功能和歸還功能.

1.2 再平衡效益衡量函數(shù)

Li[9]考慮未滿足需求的懲罰函數(shù).本文考慮將未滿足需求的懲罰轉(zhuǎn)換成滿足需求的程度，表現(xiàn)為共享車租賃功能和歸還功能的使用程度.

站點(diǎn)可分為3個(gè)間隔：(0,(1-α)aj]，((1-α)aj,(1+α)aj]，((1+α)aj,Hj].在左側(cè)間隔內(nèi)，當(dāng)車站為空時(shí)，共享車不能租用，所有插槽都可返回，因此租賃能力為0，返還能力是1.隨著共享車數(shù)量的增加，租賃能力也增加了，也有足夠的空地來滿足用戶的退貨請(qǐng)求，返還能力仍然是1.當(dāng)共享車的數(shù)量增加到(1-α)aj時(shí)，有足夠的共享車出租，租賃能力增加到1，返還能力仍然是1.左側(cè)間隔內(nèi)站點(diǎn)服務(wù)能力取決于租賃能力.在中間間隔，即平衡間隔內(nèi)，車站有足夠的共享車和足夠的空地，所以站點(diǎn)的服務(wù)能力保持在1.在右側(cè)的區(qū)間內(nèi)，如果共享車增加，租賃能力保持在1，但空置空間越來越少，返回能力減少.當(dāng)車站車滿了，租賃能力仍然為1，返回能力變?yōu)?.右側(cè)間隔內(nèi)的站點(diǎn)服務(wù)能力取決于返回能力.

再平衡效益函數(shù)在三個(gè)間隔(0,(1-α)aj]、((1-α)aj,(1+α)aj]、((1+α)aj,Hj]上的值越大，說明需求滿足的程度越高，站點(diǎn)服務(wù)能力越好.

1.3 模型的建立

本文重點(diǎn)考慮訪問站點(diǎn)的旅程和站點(diǎn)服務(wù)能力，建立雙目標(biāo)函數(shù).該函數(shù)定義在完全圖G=(V,A)上，A={(i,j)}是路線弧的集合，dij是頂點(diǎn)i和頂點(diǎn)j之間的距離.如果車輛從站點(diǎn)i行駛到站點(diǎn)j，二元決策變量xij=1；否則xij=0，決策變量xij是0,1整數(shù)變量.變量yij表示在弧線(i,j)∈A上流動(dòng)的共享車的數(shù)量，yij也是整數(shù)變量.

本文在平衡彈性區(qū)間的基礎(chǔ)上建立模型：

(1)

(2)

(1)是行駛路線最小化；(2)是再平衡效益指標(biāo)函數(shù)最大化.變量滿足如下約束條件：

(3)

該條件確保每個(gè)站點(diǎn)必須恰好訪問一次.

(4)

規(guī)定進(jìn)入和離開j站的流量之間的差等于再平衡需求.

(5)

該條件確保一個(gè)站點(diǎn)只進(jìn)行交付或者收集這兩種操作之一.

(6)

該條件確保在站點(diǎn)收集的車輛不能超過車輛的剩余量.

(7)

該條件確保交付到j(luò)站的車輛不能超過再平衡操作車輛持有的庫(kù)存.

下面將(1)、(2)的可行區(qū)域進(jìn)行松馳，形成兩個(gè)規(guī)劃問題：

(8)

(9)

顯然所有路徑之和是(8)的上界，無平衡操作是(8)的下界，則

是需求滿足程度的指標(biāo)，每個(gè)站點(diǎn)的平衡滿足程度指標(biāo)：

達(dá)到最大，使整體滿足程度變大，則

記

與單目標(biāo)模型相比，多目標(biāo)模型可以生成一組非支配最優(yōu)解，根據(jù)不同的實(shí)際情況選擇合適的方案.

2 粒子群-禁忌搜索算法

本文采用粒子群-禁忌搜索算法(TS-PSO)進(jìn)行布局優(yōu)化，并在粒子群迭代過程中引入3種變異粒子，增加粒子群的多樣性，避免陷入局部最優(yōu).

假設(shè)在二維搜索空間中，有m個(gè)粒子組成一群體，第i個(gè)粒子在二維空間中的位置表示為xi=(xi1,xi2)，第i個(gè)粒子經(jīng)歷過的最好位置(有最好適應(yīng)度)記為Pi=(pi1,pi2)，每個(gè)粒子的飛行速度為Vi=(vi1,vi2),i=1,2,…，m.在整個(gè)群體中，所有粒子經(jīng)歷過的最好位置為Pg=(pg1,pg2)，每一代粒子根據(jù)下面公式更新自己的速度和位置：

vid=wvid+c1r1(pid-xid)+c2r2(pgd-xid)，

(10)

xid=xid+vid，

(11)

其中：w為慣性權(quán)重；c1和c2為學(xué)習(xí)因子；r1和r2是[0,1]之間的隨機(jī)數(shù).

2.1 領(lǐng)域變異操作

為了增加粒子的多樣性，同時(shí)使搜索范圍變大，粒子隨機(jī)執(zhí)行3種結(jié)構(gòu)的變異，具體如下：

(1)隨機(jī)選取一個(gè)位置，將其從原位置移開，插入到另一個(gè)隨機(jī)位置；

(2)隨機(jī)選擇兩個(gè)位置，交換位置；

(3)隨機(jī)選擇幾個(gè)位置，按逆序排列.粒子變異操作后，如果新粒子優(yōu)于原粒子，則新粒子將取代原粒子;如果原粒子支配新粒子，則新粒子將被丟棄.否則，如果這兩個(gè)粒子之間沒有優(yōu)勢(shì)關(guān)系，則隨機(jī)選擇其中一個(gè).通過改變站點(diǎn)的排列，可以確定一條新的車輛路線.為了生成初始解種群，可以采用上述隨機(jī)變異的方式形成不同的粒子.

2.2 改進(jìn)算法設(shè)計(jì)

由于粒子群算法具有局部搜索能力弱，容易陷入局部最優(yōu)等缺點(diǎn)，本文對(duì)粒子群算法進(jìn)行改進(jìn)，提出一種粒子群-禁忌搜索算法(TS-PSO).

TS-PSO算法流程如下：

(1)初始化算法參數(shù)，隨機(jī)生成粒子的初始位置和速度；

(2)計(jì)算每個(gè)粒子的目標(biāo)值f1*,f2*；

(3)對(duì)每個(gè)粒子，比較目標(biāo)值f1*,f2*和目前的最優(yōu)f1(pbest),f2(pbest)，如果f1*f2(pbest)，則更新目前最優(yōu)pbest=pnow，T=N(pbest)；

(4)對(duì)每個(gè)粒子，判斷是否符合變異條件，如果符合進(jìn)入步驟5；

(5)對(duì)pbest(j)進(jìn)行變異操作，如果變異后的粒子目標(biāo)函數(shù)值更優(yōu)，則保留變異，否則取消當(dāng)前變異；

(6)將所有粒子的最優(yōu)值中最優(yōu)的個(gè)體存儲(chǔ)在全局最優(yōu)gbest中；

(7)更新每個(gè)粒子的位置和速度；

(8)進(jìn)行邊界條件處理；

(9)判斷是否滿足粒子群迭代終止條件，若是，則結(jié)束粒子群算法迭代進(jìn)入下一步；否則返回步驟2；

(10)將得到的最佳微粒解碼，進(jìn)行禁忌搜索；

(11)禁忌搜索操作結(jié)束，輸出結(jié)果.

3 收斂性分析

粒子群-禁忌搜索算法是在二維搜索空間中進(jìn)行，可選擇10塊平面區(qū)域，每塊區(qū)域設(shè)定800 m×800 m，隨機(jī)選擇一塊研究區(qū)域，在區(qū)域內(nèi)選擇潛在站點(diǎn).潛在站點(diǎn)的選擇基于以下規(guī)則:①站點(diǎn)應(yīng)位于距離重要交通樞紐(如火車站、公交終點(diǎn)站和地鐵站)和主要路口300～500m處；②站點(diǎn)應(yīng)靠近較大的居住區(qū)、機(jī)關(guān)、企業(yè)、商業(yè)區(qū)、學(xué)校、醫(yī)院、旅游景點(diǎn)等；③站點(diǎn)應(yīng)避免直接進(jìn)入繁忙的機(jī)動(dòng)車道和十字路口.基于上面原則選定60個(gè)潛在的共享車站點(diǎn)和一個(gè)倉(cāng)庫(kù).容量為Q的平衡車從倉(cāng)庫(kù)出發(fā)開始訪問站點(diǎn)，一條訪問路線，即為目標(biāo)函數(shù)的一條典型的解或者一個(gè)粒子.訪問站點(diǎn)的同時(shí)也對(duì)站點(diǎn)進(jìn)行再平衡.

算法流程如下：

表1是包含15個(gè)站點(diǎn)的訪問路線和站點(diǎn)庫(kù)存.若共享車數(shù)量在平衡間隔內(nèi)，則該站點(diǎn)可以視為處于平衡狀態(tài)，不需要重新平衡.沿用2.1的假設(shè)，站點(diǎn)j的目標(biāo)庫(kù)存為30，α=0.2，平衡區(qū)間為[24,36].對(duì)于不平衡的站點(diǎn)用平衡車再平衡，具體平衡結(jié)果如表2所列.訪問路線如表2的第一行.其中“+”表示提貨再平衡需求，“-”表示配送再平衡需求.

通過再平衡，可使其余站點(diǎn)達(dá)到平衡.從表2可以看出10、12站未達(dá)到目標(biāo)庫(kù)存，但已經(jīng)在平衡間隔內(nèi)，再平衡程度相對(duì)滿意，這也體現(xiàn)了平衡間隔的優(yōu)勢(shì).

表2 初始解決方案的一個(gè)示例

4 結(jié)語(yǔ)

本文引入平衡區(qū)間和再平衡效用函數(shù)，建立雙目標(biāo)函數(shù)，提出粒子群-禁忌搜索算法，加入三種變異粒子，改進(jìn)了算法，使得平衡次數(shù)和時(shí)間變少.由于α的不同會(huì)影響平衡區(qū)間及目標(biāo)函數(shù)，下一步會(huì)探討不同的參數(shù)值對(duì)目標(biāo)函數(shù)的影響.