帶時間窗和同時送取貨的車輛路徑問題模型及算法

袁曉建, 張岐山，吳 伶，江義火

(1. 福州大學(xué)經(jīng)濟(jì)與管理學(xué)院, 福建 福州 350108； 2. 福州外語外貿(mào)學(xué)院理工學(xué)院，福建 福州 350202； 3. 福州大學(xué)數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院, 福建 福州 350108)

0 引言

帶時間窗和同時送取貨車輛路徑優(yōu)化問題(vehicle routing problem with simultaneous pickup-delivery and time windows，VRPSPDTW)作為車輛路徑優(yōu)化問題(vehicle routing problem，VRP)的擴(kuò)展，該問題整合了企業(yè)正向物流和逆向物流，具有較強(qiáng)的應(yīng)用價值，自提出以來得到了學(xué)者們的持續(xù)關(guān)注[1].

由于VRPSPDTW問題增加了同時送取貨和時間窗兩個約束，當(dāng)配送客戶規(guī)模的增大，求解的規(guī)模成指數(shù)級增長，傳統(tǒng)的精確求解算法難以在可接受的時間范圍內(nèi)求得最優(yōu)解. 隨著啟發(fā)式算法的提出，學(xué)者們開始嘗試結(jié)合該算法求解VRPSPDTW問題. 文獻(xiàn)[2]使用共同進(jìn)化的遺傳算法(genetic algorithm，GA)求解該問題，并在Solomon數(shù)據(jù)集基礎(chǔ)上設(shè)計了65個數(shù)據(jù)集. 文獻(xiàn)[3]使用遺傳算法和禁忌搜索算法對家庭醫(yī)療物流問題進(jìn)行求解. 文獻(xiàn)[4]設(shè)計了并行模擬退火算法(parallel simulated annealing，p-SA)求解該問題，并在超大客戶規(guī)模的測試集上驗(yàn)證了其算法的有效性. 文獻(xiàn)[5]又提出了基于離散布谷鳥算法(discrete cuckoo algorithm，DCA)的仿生算法對該問題進(jìn)行求解，并將部分算例的最優(yōu)解進(jìn)行更新.

文獻(xiàn)[6-7]提出了量子進(jìn)化算法，該算法將量子計算理論與進(jìn)化算法進(jìn)行巧妙結(jié)合，是一種概率搜索優(yōu)化算法. 由于量子進(jìn)化算法具有種群規(guī)模小、 收斂速度快和全局搜索能力強(qiáng)等特點(diǎn)，迅速得到了國內(nèi)外研究人員的關(guān)注[8-11]. 近年來，也有部分學(xué)者嘗試使用量子進(jìn)化算法解決VRP相關(guān)問題[10, 12-15]，但是利用量子算法求解VRP問題存在量子進(jìn)化方向引導(dǎo)、 算法域到問題域映射等難題，國內(nèi)外鮮見有學(xué)者進(jìn)行深入研究.

本研究基于車輛裝載率和客戶-中心點(diǎn)方向的權(quán)重距離公式，構(gòu)建量子元胞體完成算法域到問題域的映射，設(shè)計雙層的改進(jìn)量子算法，最后在VRPSPDTW問題通用測試集上對算法進(jìn)行有效性檢驗(yàn).

1 帶時間窗和同時送取的車輛路徑問題

1.1 問題描述

該問題的圖論描述如下：G(N,A)表示一個有向圖，N={0, 1, …,n}表示有向圖的節(jié)點(diǎn)集合，其中節(jié)點(diǎn)0表示中心車場，也是貨物配送中心，是車輛出發(fā)和返回地點(diǎn)，要求所有的車輛從中心車場出發(fā)，最后回到中心車場； 節(jié)點(diǎn)1, …,n表示客戶節(jié)點(diǎn)，每個客戶i∈N同時有貨物配送需求量Di>0和貨物取貨需求量Pi. 每兩個節(jié)點(diǎn)之間有兩條弧線相連，A={(i,j)∣i,j∈N;i≠j}表示所有弧的集合；cij{i,j∈N;i≠j}表示節(jié)點(diǎn)之間的配送成本，這里用兩點(diǎn)間的歐式距離表示，且cij=cji. 假設(shè)配送中心有m輛同種類型的配送車輛，每輛車的核定載重為Q.

配送中心和顧客均有時間窗限制，配送中心的時間窗為[a0,b0]，即車輛只能在a0之后(包含a0)離開，且只能在b0之前(包含b0)返回. 對于編號為i顧客也有預(yù)先設(shè)定的時間窗[ai,bi]，車輛服務(wù)該顧客的時間必須在此區(qū)間內(nèi)，即ai車輛提供配送服務(wù)的時間不能早于ai且不能晚于bi，同時設(shè)車輛為顧客i提供服務(wù)的時長為ti. 為研究方便，假設(shè)車輛的行駛速度為1，則車輛從客戶i到客戶j的行駛時間等于他們之間的歐氏距離，即tij=dij.

每輛車的啟動成本設(shè)置為cd，考慮到市場實(shí)際的資源配置，本研究的第一優(yōu)化目標(biāo)為車輛數(shù)最少； 車輛數(shù)相等的條件下，第二優(yōu)化目標(biāo)為配送距離最短.

VRPSPDTW問題的目標(biāo)函數(shù)是以最小的成本(最少配送車輛和最短配送距離)完成配送任務(wù)，并滿足以下假設(shè)：① 所有顧客的配送需求和時間窗要求均要滿足，且需求不可拆分，即每個顧客只能由同一輛車同時完成取貨和送貨； ② 每輛車從中心倉庫出發(fā)并返回中心倉庫； ③ 車輛在服務(wù)顧客時，先卸貨后裝貨； ④ 車輛的最大載重不允許超過車輛的核定載重.

1.2 數(shù)學(xué)模型

為方便建模，現(xiàn)將使用到的集合、 參數(shù)和變量定義如下：

集合.N為節(jié)點(diǎn)集(顧客集和中心倉庫)，N={0, 1, …,n}表示有向圖的節(jié)點(diǎn)集合，其中0表示配送中心；N0為顧客集，N0={1, 2, …,n}；K為車輛集，K={1, 2, …,m}.

參數(shù).Q為車輛的額定裝載量，即最大裝載限制；cd為每啟動一輛車的成本；ct為單個車輛單位距離的行駛成本；dij為顧客i和j之間的歐式距離,i∈N0,j∈N0,i≠j；Pi為顧客i的取貨需求量，i∈N0；Di為顧客i的送貨需求量，i∈N0；ai為顧客i允許最早開始服務(wù)的時間，i∈N0；bi為顧客i截止服務(wù)的時間，i∈N0；ti為車輛服務(wù)顧客i所需的時間，i∈N0；λ為權(quán)衡分派成本和行駛成本的參數(shù)，λ∈[0, 1]；M為一個任意大的正數(shù).

決策變量.xijk為車輛k(k∈K)的行駛變量，xijk∈{0, 1}, 如果車輛k從點(diǎn)i∈N行駛到點(diǎn)j∈N，則xijk=1，否則xijk=0；L0k為車輛k(k∈K)離開配送中心時的載貨量；Li為車輛服務(wù)顧客i∈N0后的載貨量；Sik為車輛開始服務(wù)顧客i∈N0的時間，如果車輛k沒有服務(wù)顧客i，則Sik=0.

基于以上變量，參考文獻(xiàn)[2]給出該問題MIP模型：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

ai≤sik≤bi;xijk∈{0, 1} (?i∈N, ?j∈N, ?k∈K)

(9)

其中，式(1)為該問題目標(biāo)函數(shù); 約束(2)表示每個顧客只能被一輛車服務(wù)，即服務(wù)不可拆分； 約束(3)避免形成不包含配送中心的回路； 約束(4)保證車輛的初始出發(fā)點(diǎn)和最終點(diǎn)均為配送中心; 約束(5)～(7)表示車輛載重約束條件，即車輛在配送全程任何時候的載重均不可超過其核定載重.

2 量子進(jìn)化算法

2.1 經(jīng)典量子進(jìn)化算法

量子進(jìn)化算法(quantum evolution algorithm，QEA)是由量子計算理論與進(jìn)化算法相結(jié)合的算法，是一種概率搜索優(yōu)化算法，其基本原理是：用量子位編碼表示染色體，用量子門作用和量子旋轉(zhuǎn)完成進(jìn)化搜索[16-17].

量子進(jìn)化算法的工作機(jī)理為：使用量子染色體表征問題解空間中任意解的疊加態(tài)，隨機(jī)觀測量子染色體，量子染色體以一定的概率觀測到一個以二進(jìn)制形式表示的解； 算法采用量子旋轉(zhuǎn)門作為進(jìn)化策略，原理是將需要的結(jié)果以概率的形式增加，不需要的結(jié)果以概率的形式減弱，保證解向著最優(yōu)的方向進(jìn)化.

(10)

其中：θi=S(αi,βi)Δθi，Δθi為量子旋轉(zhuǎn)門旋轉(zhuǎn)角，其大小控制算法的收斂速度；S(αi,βi)控制旋轉(zhuǎn)角的方向，使算法向最優(yōu)解方向搜素.S(αi,βi)和Δθi的取值可通過查表法[18]獲得.

2.2 量子進(jìn)化算法的改進(jìn)

為避免由量子染色體坍塌為二進(jìn)制解時出現(xiàn)不變解的情況，文獻(xiàn)[17]對式(10)中(α′i,β′i)T，作如下處理：

(11)

式中：ε是一個較小的正數(shù)(本研究ε取值為0.01).

3 VRPSPDTW問題的改進(jìn)量子算法設(shè)計

3.1 初始解設(shè)計

3.1.1初始解參數(shù)設(shè)計

由于初始解對算法的收斂速度影響較大，僅僅使用貪心算法又容易減少初始解的多樣性. 如圖1，車輛配送貨物至客戶i時，車輛已經(jīng)接近滿載，按照常理，此時車輛應(yīng)該準(zhǔn)備回場，最優(yōu)的做法是“順路配送”，即下一個客戶盡量是在配送中心的方向上. 圖1中，黑色原點(diǎn)表示中心車場，此時車輛在顧客i處，顧客i+1和顧客j+1相比較，明顯顧客i+1距離車輛最近，如果單純使用貪心算法則顧客i+1被加入到配送序列，以此類推，車輛距離中心車場越來越遠(yuǎn)，直至顧客i+n車輛滿載，車輛必須回程，此時車輛距離配送中心比較遠(yuǎn)，最后車輛不得不長距離的回場. 理想狀況是，車輛配送至顧客i時，車輛已經(jīng)接近滿載，即使顧客j與顧客i+1相比，顧客j比較遠(yuǎn)，但是由于j在車輛回場的方向上，優(yōu)先選擇顧客j作為下一個配送目標(biāo)，依次類推，直至顧客j+k車輛滿載，車輛距離配送中心越來越近. 為了實(shí)現(xiàn)此功能，本研究定義帶回場權(quán)重的權(quán)重距離，具體如下：

圖1 權(quán)重距離示意圖Fig.1 Weight distance diagram

圖2 向心角示意圖Fig.2 Centripetal angle diagram

3.1.2初始解算法設(shè)計

初始解生成算法設(shè)計如下：① 啟動一輛新車，隨機(jī)選擇一個客戶作為路徑起點(diǎn)； ②i為當(dāng)前路徑最后一個客戶，j為下一個配送候選客戶, 如果ωi≤ω0，車輛需要行駛的距離取i與j之間的歐式距離dij=dij, 否則，車輛需要行駛的距離取值帶有權(quán)重的距離dij=wdij； ③ 遍歷所有未配送的客戶，建立車輛行駛dij由小到大的臨時列表； ④ 遍歷臨時列表，校驗(yàn)時間窗與裝載約束. 如果時間窗和車輛裝載約束校驗(yàn)均通過，則當(dāng)前候選客戶入到當(dāng)前路徑尾部，算法返回步驟②, 不滿足則繼續(xù)校驗(yàn)臨時列表的下一個客戶, 直至臨時列表中不再有未配送的客戶，則當(dāng)前車輛的配送方案生成完成； ⑤ 重復(fù)步驟①，直到所有客戶均被添加進(jìn)配送方案，返回整體配送方案.

3.1.3初始解轉(zhuǎn)化成二進(jìn)制解

上述步驟生成十進(jìn)制的整體配送方案后，按照下述3.2編碼設(shè)計生成二進(jìn)制的初始解.

3.2 客戶與車輛的量子編碼設(shè)計

傳統(tǒng)量子算法在解決VRP問題中，每次迭代本地搜索后，生成的全局最優(yōu)解轉(zhuǎn)化成對應(yīng)的二進(jìn)制解，但是量子的每次進(jìn)化，無論是啟用車輛數(shù)減少還是總距離減少，對應(yīng)的量子的長度和位置均已發(fā)生改變，二進(jìn)制的最優(yōu)解失去了引導(dǎo)進(jìn)化的意義. 針對上述問題，這里提出量子元胞體、 特定條件初始化和互換α和β位的解決方法.

3.2.1量子元胞體設(shè)計

取量子染色體的α位為觀測位，設(shè)計長度一定的量子染色體，其中：初始的量子長度=量子胞體的個數(shù)×客戶個數(shù).

量子元胞體定義為：固定長度的量子染色體作為一個獨(dú)立的觀測單元，觀測單元在染色體中的順序代表客戶編號.

元胞體具體形式為(車輛編號|配送順序)，其中該固定長度的前半段觀測得到車輛編號的二進(jìn)制數(shù)，后半段觀測得到該配送車輛服務(wù)的順序的二進(jìn)制數(shù). 這里，車輛編號位數(shù)的長度LV= log2NV，NV為當(dāng)前最優(yōu)解使用的車輛數(shù)； 配送順序位數(shù)長度LC=log2n，n表示客戶數(shù). 定義量子胞體的長度為L0，L0= LV+ LC； 定義當(dāng)前最優(yōu)解下的量子染色體長度為Lq，Lq=nL0. 量子元胞體的具體設(shè)計如圖3所示.

圖3 量子胞體結(jié)構(gòu)圖Fig.3 Quantum cell structure

3.2.2量子染色體對齊操作設(shè)計

將現(xiàn)有量子染色體觀測到的二進(jìn)制，與由本地搜索到的最優(yōu)解反向生成的二進(jìn)制進(jìn)行逐位對比，一致則對應(yīng)量子位不變，不一致則交換對應(yīng)量子位的α位和β位.

3.2.3量子染色體進(jìn)化機(jī)制設(shè)計

量子染色體進(jìn)化機(jī)制設(shè)計如下：

ⅱ) 由當(dāng)前最優(yōu)解(第一代則為初始解)引導(dǎo)方向，根據(jù)改進(jìn)量子算法進(jìn)行進(jìn)化，并進(jìn)行觀測、 本地搜索操作；

ⅲ) 當(dāng)車輛數(shù)NV變小，產(chǎn)生新的最優(yōu)解，返回i)，重新生成并初始化量子； 當(dāng) NV不變且配送總路程變小，產(chǎn)生新的最優(yōu)解，進(jìn)行量子對齊操作，并返回ii)；

ⅳ) 有限回溯的全局優(yōu)化操作；

ⅴ) 迭代達(dá)最大設(shè)定，輸出最優(yōu)配送方案.

3.3 全局優(yōu)化設(shè)計

3.3.1初始解多樣化

經(jīng)驗(yàn)證，算法的初始解對收斂速度和解的質(zhì)量有較大的影響，為擴(kuò)大搜索空間，這里使用3.1定義的滿載率和權(quán)重距離生成多種初始解. 如ω0=1時，則滿載率和權(quán)重距離設(shè)置失效，ω0取值不同，得到的初始解不同，靈活實(shí)現(xiàn)初始解的多樣化.

3.3.2有限回溯操作

以搜索中間狀態(tài)的所需車輛數(shù)劃分階段，當(dāng)a階段(a輛車)連續(xù)若干代無最優(yōu)解更新認(rèn)為陷入局部最優(yōu)，回到a+1階段的關(guān)鍵點(diǎn)，重新進(jìn)行迭代，靈活實(shí)現(xiàn)大范圍搜索.

4 實(shí)驗(yàn)及分析

4.1 測試算例

為便于衡量算法的有效性，采用文獻(xiàn)[2]構(gòu)造的通用標(biāo)準(zhǔn)測試集. 該測試集包含65個VRPSPDTW測試算例，其中包括9個中小型顧客規(guī)模算例和56個大型顧客規(guī)模的算例(客戶規(guī)模為100).

4.2 實(shí)驗(yàn)環(huán)境和算法參數(shù)確定

實(shí)驗(yàn)環(huán)境如下：Intel i5-5200U 2.2 GHz CPU，4 GB內(nèi)存，操作系統(tǒng)為Windows 7，編程環(huán)境為Matlab R2014a.

從10、 25和50個客戶規(guī)模中隨機(jī)選取一個算例進(jìn)行測試，考慮收斂速度和平均最優(yōu)值，參數(shù)設(shè)置為：量子種群數(shù)目=3，最大迭代次數(shù)5 000，θ0=0.15和ω0=0.7對全部的9個算例進(jìn)行有效性分析.

4.3 實(shí)驗(yàn)

選取中小規(guī)模的9個算例在每個算例上獨(dú)立運(yùn)行10次，記錄運(yùn)行結(jié)果的最優(yōu)值進(jìn)行算法有效性驗(yàn)證，運(yùn)行結(jié)果與GA算法[2]、 p-SA算法[4]和離散布谷鳥(DCS)算法[5]的運(yùn)算結(jié)果進(jìn)行對比，如表1所示.

表1 四種算法的運(yùn)算效果對比Tab.1 Comparison of the effects of the four algorithms

4.4 有效性分析

為了衡量不同算法在同一個數(shù)據(jù)集上表現(xiàn)出來的優(yōu)劣，大多數(shù)車輛路徑優(yōu)化算法的分析多采用求解質(zhì)量和求解速度進(jìn)行對比. 文獻(xiàn)[19]提出了使用非參數(shù)檢驗(yàn)的方法，使用Friedman檢驗(yàn)和Wilcoxon檢驗(yàn)分別將不同算法計算結(jié)果進(jìn)行比較排序(Rank)，檢驗(yàn)算法在置信區(qū)間內(nèi)是否存在顯著差異.

在上面的算例實(shí)驗(yàn)中，由于求解的是測試集中的中小規(guī)模算例，因此求解的車輛數(shù)均一樣，不具備檢驗(yàn)條件，這里選取最短路徑進(jìn)行檢驗(yàn)，檢驗(yàn)統(tǒng)計量如表2所示.

表2 檢驗(yàn)統(tǒng)計量Tab.2 Test statistics

由表2可以看出，在0.01顯著性水平條件下，四種算法無顯著性差異. 鑒于在Friedman檢驗(yàn)中，漸近顯著性為0.012，如果在常用的0.05顯著性水平條件下，四種算法在Friedman檢驗(yàn)中結(jié)論為有顯著性差異，而算法兩兩之間顯著性不明顯.

綜上所述，NIQA算法與目前幾個著名優(yōu)化算法不存在顯著性差異.

5 結(jié)論

本研究針對帶時間窗和同時取送貨的車輛路徑問題，提出一種新的改進(jìn)量子算法(NIQA). 通過Wang和Chen測試集的測試以及與現(xiàn)有最優(yōu)解的比較，表明NIQA是有效的. 雖然所提的量子胞體、 特定條件初始化及互換α和β位等方法解決了量子算法在求解此類問題中的部分困難，給出了些許的思路，但是受限于算法設(shè)計能力，在求解大規(guī)?？蛻舻膯栴}上，并沒有完全展現(xiàn)出量子算法的優(yōu)越性. 如何設(shè)計從量子域到二進(jìn)制域再到問題域完整的映射，尤其是量子域到二進(jìn)制的映射，做到盡量少地丟失有效信息是今后的研究方向.