帶時(shí)間窗裝卸一體化車輛路徑問(wèn)題的混合離散粒子群優(yōu)化算法

周　蓉　沈維蕾　劉明周　趙　韓

合肥工業(yè)大學(xué)，合肥，230009

帶時(shí)間窗裝卸一體化車輛路徑問(wèn)題的混合離散粒子群優(yōu)化算法

周蓉沈維蕾劉明周趙韓

合肥工業(yè)大學(xué)，合肥，230009

摘要：為了同時(shí)實(shí)現(xiàn)總配送成本最低、車輛數(shù)最少和車輛行駛距離最短等目標(biāo)，考慮車輛指派成本及運(yùn)輸路徑成本的相對(duì)重要性，建立了帶時(shí)間窗裝卸一體化車輛路徑問(wèn)題的混合整數(shù)規(guī)劃模型。針對(duì)該問(wèn)題搜索空間的離散性和求解算法的局部收斂性，提出了一種混合離散粒子群求解算法。算法基于客戶排列的直觀無(wú)分段大路徑解表示法，采用改進(jìn)深度優(yōu)先搜索分割法對(duì)問(wèn)題解進(jìn)行解碼與評(píng)價(jià)；嵌入一種變鄰域下降搜索程序并在個(gè)體粒子每次迭代時(shí)以一定概率選擇執(zhí)行，利用混合粒子群算法在多鄰域深度搜索和在全局空間廣度搜索進(jìn)行尋優(yōu)，同時(shí)應(yīng)用模擬退火思想和比例選擇性變異最差個(gè)體來(lái)改善個(gè)體搜索停滯現(xiàn)象。采用兩個(gè)不同目標(biāo)算例進(jìn)行尋優(yōu)測(cè)試，驗(yàn)證了所提算法的可行性和有效性。

關(guān)鍵詞：帶時(shí)間窗車輛路徑問(wèn)題；裝卸一體化；離散粒子群優(yōu)化算法；變鄰域下降搜索

0引言

車輛在完成客戶配送或取貨過(guò)程中普遍存在回程或去程空載現(xiàn)象，如何有效整合正向和逆向物流，減少運(yùn)輸資源浪費(fèi)，降低物流運(yùn)作成本，是逆向物流系統(tǒng)規(guī)劃中的重要決策問(wèn)題。當(dāng)客戶同時(shí)具有送貨和取貨需求時(shí)存在兩種車輛服務(wù)策略，一種策略是車輛將貨物送至客戶的同時(shí)從該處取走貨物，車輛裝卸操作同時(shí)完成；另一種策略是車輛完成所有送貨需求后按原路徑返回完成取貨需求，車輛裝卸操作分時(shí)完成。這兩種策略問(wèn)題分別稱為裝卸一體化車輛路徑問(wèn)題和帶回程車輛路徑問(wèn)題[1-2]。如果帶回程問(wèn)題去程的取貨量或回程的送貨量為零，則問(wèn)題轉(zhuǎn)變?yōu)檠b卸一體化車輛路徑問(wèn)題。文獻(xiàn)[2]的研究結(jié)果表明，裝卸一體化車輛路徑問(wèn)題較帶回程車輛路徑問(wèn)題具有更低的運(yùn)作成本。裝卸一體化車輛路徑問(wèn)題最早由Min[3]提出，用于解決1個(gè)中心圖書(shū)館與22個(gè)鄉(xiāng)村圖書(shū)館之間的圖書(shū)發(fā)送與回館問(wèn)題。有關(guān)該問(wèn)題的研究文獻(xiàn)比較多，但因其是NP-Hard問(wèn)題，求解方法大多集中在啟發(fā)式方法和元啟發(fā)方法。啟發(fā)式方法主要以經(jīng)典C-W節(jié)約算法為基礎(chǔ)，考慮不同的啟發(fā)式規(guī)則進(jìn)行求解[4-6]；元啟發(fā)方法以群體智能為基礎(chǔ)，考慮不同的信息傳遞與更新方式進(jìn)行求解[7-8]?，F(xiàn)實(shí)中客戶對(duì)送貨與取貨通常有一定的時(shí)間要求，即要求車輛在指定的時(shí)間范圍內(nèi)完成裝卸操作，這就是帶時(shí)間窗裝卸一體化車輛路徑問(wèn)題(vehicleroutingproblemwithtimewindowsandsimultaneouspickupanddelivery，VRPTWSPD)。該問(wèn)題較裝卸一體化車輛路徑問(wèn)題更能反映實(shí)際情況，因而具有更為廣闊的應(yīng)用前景，但由于決策目標(biāo)、決策影響因素和約束條件較多造成求解困難，目前相關(guān)研究還比較少。

現(xiàn)有VRPTWSPD相關(guān)研究多以最小化車輛行駛距離為目標(biāo)，雖然少數(shù)研究增加了車輛數(shù)目方面的分析，但缺乏對(duì)總配送成本、車輛數(shù)目、車輛行駛距離等多種目標(biāo)的系統(tǒng)性分析。如：Angelelli等[9]以最小化車輛行駛距離為目標(biāo)，采用分支定界算法解決了20個(gè)客戶的小規(guī)模VRPTWSPD問(wèn)題；Lai等[10]運(yùn)用改進(jìn)的差分進(jìn)化算法求解了相同目標(biāo)問(wèn)題，并分別采用由8個(gè)客戶和40個(gè)客戶組成的兩個(gè)不同規(guī)模算例進(jìn)行了算法準(zhǔn)確性和有效性驗(yàn)證；Wang等[11]以最小化車輛數(shù)目、最小化車輛行駛距離為目標(biāo)，提出采用聯(lián)合進(jìn)化遺傳算法進(jìn)行求解，并將Solomon的經(jīng)典VRPTW(vehicleroutingproblemwithtimewindows)問(wèn)題集擴(kuò)展為65個(gè)10～100個(gè)客戶規(guī)模的VRPTWSPD算例，計(jì)算結(jié)果證明該方法較基本遺傳算法和數(shù)學(xué)規(guī)劃工具Cplex具有更好的穩(wěn)定性。此外，王超等[12]還采用改進(jìn)的模擬退火算法，以文獻(xiàn)[11]擴(kuò)展的部分VRPTWSPD問(wèn)題為測(cè)試算例，證明了該方法在部分算例中較文獻(xiàn)[11]的聯(lián)合進(jìn)化算法求解性能更好；Boubahri等[13]以最大化站點(diǎn)服務(wù)能力為目標(biāo)，提出采用多蟻群算法對(duì)多校車站點(diǎn)的VRPTWSPD問(wèn)題進(jìn)行求解，但未進(jìn)行算法驗(yàn)證。

粒子群優(yōu)化(particleswarmoptimization，PSO)算法是一種基于群體智能的自適應(yīng)元啟發(fā)算法，在許多車輛路徑與調(diào)度問(wèn)題的求解應(yīng)用中已被證明具有良好的優(yōu)化性能[7,14-15]。PSO算法在搜索處理后期階段容易出現(xiàn)早熟收斂從而陷入局部最優(yōu)，因此通常與局域搜索相結(jié)合，利用其拓展局域深度搜索的特點(diǎn)提高整體搜索性能[7,15]。受到該思想的啟發(fā)，本文將變鄰域下降搜索程序嵌入基本離散粒子群算法，提出一種混合離散粒子群算法求解包含多種目標(biāo)的VRPTWSPD問(wèn)題，并通過(guò)算例仿真和結(jié)果對(duì)比驗(yàn)證了所提出算法的可行性和有效性。

1問(wèn)題描述與模型

VRPTWSPD問(wèn)題可以描述為：物流中心擁有一定數(shù)量的相同車輛，車輛從配送中心出發(fā)，在一定時(shí)間內(nèi)完成確定數(shù)量客戶集的送貨與取貨后返回物流中心。每個(gè)客戶的送貨與取貨由同一車輛同時(shí)完成。每個(gè)客戶具有確定的位置及獨(dú)立的服務(wù)時(shí)間窗，每輛車在指定的時(shí)間范圍離開(kāi)和返回物流中心。要求合理安排車輛配送路線，在派出車輛數(shù)目最小、車輛行駛距離最短情況下，實(shí)現(xiàn)總配送成本最小。采用符號(hào)體系描述如下：假設(shè)物流中心共有N個(gè)客戶，采用i、j表示客戶編號(hào)(i = 1, 2, …, N; j = 1, 2, …,N), 0表示物流中心；Z為總配送成本；客戶的送貨量和取貨量分別為di、pi；客戶之間的距離為cij，物流中心到客戶i的距離為c0i；車輛單位距離行駛成本為g，單車指派成本為f，最大裝載量為Q；車輛總數(shù)為K，車輛k(k = 1, 2, …, K)到達(dá)客戶i的時(shí)間為Tik，在節(jié)點(diǎn)i的等待時(shí)間為tik，在i、j兩個(gè)節(jié)點(diǎn)之間的行駛時(shí)間為tijk，離開(kāi)客戶i時(shí)車上載重量為Uik，離開(kāi)和返回物流中心的時(shí)間分別為L(zhǎng)0k、R0k(也可以由車輛的最大行駛距離L進(jìn)行限制)；客戶i要求的服務(wù)時(shí)間窗為[ai,bi]，服務(wù)時(shí)間為si；物流中心0對(duì)車輛的時(shí)間窗要求為[a0,b0]；m、n分別為車輛指派成本、運(yùn)輸路徑成本對(duì)總配送成本的重要性指數(shù)，m∈[0,1)，n∈(0,1]。

根據(jù)上述描述，建立VRPTWSPD問(wèn)題的混合整數(shù)規(guī)劃模型如下：

(1)

滿足約束條件：

(2)

(3)

?j=1,2,…,N

(4)

?i=0，1,…,N;k=1,2,…,K

(5)

(6)

(7)

?i=1,2,…,N;j=0,1,…,N

(8)

tik=max(ai-Tik,0)

?i=1,2,…,N;k=1,2,…,K

(9)

ai≤Tik+tik≤bi

?i=1,2,…,N;k=1,2,…,K

(10)

a0≤L0k?k=1,2,…,K

(11)

R0k≤b0?k=1,2,…,K

(12)

(13)

(14)

?i,j=0,1,…,N;k=1,2,…,K

其中，式(1)為考慮了車輛指派成本、運(yùn)輸路徑成本的總配送成本Z最小目標(biāo)，隱含車輛數(shù)目最小、車輛行駛距離最短兩個(gè)子目標(biāo)；式(2)確保每個(gè)客戶只被服務(wù)一次且僅由一輛車服務(wù)；式(3)確保使用車輛數(shù)不超過(guò)車輛總數(shù)K；式(4)為流量守恒式，即到達(dá)和離開(kāi)每個(gè)客戶的車輛相同；式(5)～式(7)為容量約束；式(8)～式(10)為客戶的時(shí)間窗約束，其中式(8)中的M為一個(gè)很大的正數(shù)；式(11)～式(12)為物流中心的時(shí)間窗約束；式(13)確保車輛的最大行駛距離不超過(guò)L；式(14)為決策變量屬性約束。調(diào)整m和n的值，可以使式(1)目標(biāo)發(fā)生改變。如令m = 0、n = 1，模型目標(biāo)為行駛距離最小化，與文獻(xiàn)[10]相同；令n = 1- m，模型目標(biāo)為配送成本最小化，與文獻(xiàn)[11]相同。

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

2.1離散粒子群算法基本原理

離散粒子群算法通過(guò)重新定義粒子操作算子[16]，用問(wèn)題的一個(gè)排列作為粒子的一個(gè)位置，用問(wèn)題的所有排列構(gòu)成問(wèn)題的搜索空間，并通過(guò)遺傳、變異和交叉操作，綜合粒子的當(dāng)前狀態(tài)、個(gè)體思考及社會(huì)合作三部分信息實(shí)現(xiàn)粒子位置更新，其位置更新公式為[15]

(15)

2.2混合離散粒子群算法

本文將變鄰域下降搜索引入離散粒子群算法作為個(gè)體粒子的一種概率變異，通過(guò)擴(kuò)大局域搜索空間實(shí)現(xiàn)個(gè)體深度搜索，從而提高群體尋優(yōu)能力。

2.2.1解的表示、解碼與評(píng)價(jià)

(1)解的表示。產(chǎn)生N個(gè)1 ～ N之間的互不重復(fù)自然數(shù)的排列，作為具有N個(gè)客戶的帶時(shí)間窗裝卸一體化車輛路徑問(wèn)題的抽象解。該抽象解是一條以自然數(shù)序列表示客戶服務(wù)順序的無(wú)分段大路徑[17]，對(duì)于單車場(chǎng)車輛路徑問(wèn)題通常在序列最前面加上0表示帶物流中心的大路徑。大路徑解圖示方法包括直觀圖和有向無(wú)圈圖，直觀圖給出物流中心及所有客戶的地理位置、客戶的送貨與取貨需求量、客戶及物流中心的服務(wù)時(shí)間窗等信息，如圖1a所示(圖中N = 5)；有向無(wú)圈圖給出客戶之間滿足約束條件的所有可行配送路徑的相關(guān)信息，如圖1b所示。

有向無(wú)圈圖(圖1b)中弧(i,j)為大路徑X={0,1,…,N}上第i個(gè)節(jié)點(diǎn)與第j個(gè)節(jié)點(diǎn)之間的可行配送路徑，表示車輛從物流中心出發(fā)依次服務(wù)第i +1、i +2、…、j -1、j個(gè)節(jié)點(diǎn)后返回物流中心?？尚信渌吐窂綕M足車容量、客戶及物流中心時(shí)間窗、車輛最大行駛距離等相關(guān)約束。設(shè)弧(i,j)上車輛的行駛距離為Dij，總配送成本為zij，其計(jì)算式如下：

(16)

zij=mDX(i+1,j)g+nf

(17)

(2)解碼。大路徑解碼也稱為大路徑分割，通過(guò)采用標(biāo)簽管理方式對(duì)各節(jié)點(diǎn)進(jìn)行標(biāo)記，然后根據(jù)標(biāo)記信息將大路徑上的客戶分別劃入不同的車輛配送路徑中，從而得到各車的配送方案(也稱作子路徑)。大路徑分割思想最先由Beasley[18]提出并應(yīng)用于求解車輛路徑問(wèn)題的先路徑后叢聚啟發(fā)式算法中，后被Prins[17]拓展用于求解VRP問(wèn)題的遺傳算法中。Duhamel等[19]將大路徑分割方法分為廣度優(yōu)先搜索和深度優(yōu)先搜索兩種，其中深度優(yōu)先搜索以其搜索速度快被廣泛用于VRP問(wèn)題的元啟發(fā)方法中[17,19-20]。

根據(jù)VRPTWSPD問(wèn)題的客戶雙重需求特性以及相關(guān)約束條件，包括車輛的最大載重量約束、客戶要求服務(wù)的時(shí)間窗約束，對(duì)文獻(xiàn)[20]的深度優(yōu)先搜索方法進(jìn)行修改，使其適用于VRPTWSPD問(wèn)題的大路徑分割。該方法分為兩階段：第一階段構(gòu)造有向無(wú)圈圖并給每個(gè)節(jié)點(diǎn)創(chuàng)建成本和距離標(biāo)簽，確定每個(gè)節(jié)點(diǎn)上成本標(biāo)簽的最小值，推斷各節(jié)點(diǎn)的前繼節(jié)點(diǎn)。第二個(gè)階段根據(jù)最后一個(gè)節(jié)點(diǎn)的前繼節(jié)點(diǎn)信息，逐個(gè)向前提取各節(jié)點(diǎn)的標(biāo)簽信息，根據(jù)最小化總配送成本目標(biāo)產(chǎn)生最優(yōu)路徑方案。

對(duì)大路徑X={0,1,…,N}，若(i,j)為其有向無(wú)圈圖G(X)上的一段可行弧，Pi、Vi和Di分別為節(jié)點(diǎn)i的前繼節(jié)點(diǎn)標(biāo)簽、總配送成本標(biāo)簽與總行駛距離標(biāo)簽，Pj、Vj和Dj分別為節(jié)點(diǎn)j的前繼節(jié)點(diǎn)標(biāo)簽、總配送成本標(biāo)簽與總行駛距離標(biāo)簽，則存在以下關(guān)系式：Pj=i，Vj=Vi+zij,Dj=Di+DX(i+1,j)。以圖1為例，設(shè)車輛最大裝載量Q=12，單車指派成本f=10，車輛單位距離行駛成本g=1,車輛行駛速度v=2,車輛在每個(gè)節(jié)點(diǎn)的服務(wù)時(shí)間s=10,大路徑X={0,1,2,3,4,5};弧(0,2)表示路徑0-1-2-0，節(jié)點(diǎn)2的前繼節(jié)點(diǎn)標(biāo)簽P2=0，假設(shè)m =n= 1，節(jié)點(diǎn)2的總配送成本標(biāo)簽V2=V0+z02=0+65=65，節(jié)點(diǎn)2的總行駛距離標(biāo)簽D2=D0+DX(1,2)=0+55=55；弧(2,4)表示路徑0-3-4-0,節(jié)點(diǎn)4的前繼節(jié)點(diǎn)標(biāo)簽P4=2，節(jié)點(diǎn)4的總配送成本標(biāo)簽V4=V2+z24=65+105=170，節(jié)點(diǎn)4的總行駛距離標(biāo)簽D4=D2+95=55+95=150。根據(jù)圖1b中的黑色加粗弧可知，當(dāng)V5=V3+z35=100+100=200時(shí)，大路徑X的最優(yōu)分割為0-1-2-3-0、0-4-5-0，從而得到最優(yōu)配送方案如圖1c所示。

(a)直觀圖

(A,B):C[D,E]A:路徑上的總配送裝載量; B:路徑上的總集貨裝載量;C:路徑上的總成本; D:車輛離開(kāi)物流中心的時(shí)間;E:車輛返回物流中心的時(shí)間(b)有向無(wú)圈圖

(c)最優(yōu)方案圖 1　大路徑示例及解碼圖

(3) 解的評(píng)價(jià)。一般情況下，對(duì)目標(biāo)函數(shù)值進(jìn)行比較可以評(píng)價(jià)可行解的優(yōu)劣程度。因此本文選取目標(biāo)函數(shù)值Z作為解的評(píng)價(jià)值。

2.2.2種群初始化

由于初始解質(zhì)量對(duì)粒子群算法求解的速度和質(zhì)量影響較大，本文采用大部分初始種群個(gè)體隨機(jī)生成、部分優(yōu)良個(gè)體采用改進(jìn)節(jié)約法[21]生成得到初始種群。隨機(jī)產(chǎn)生方法遵循以下兩條原則：第一，不允許產(chǎn)生相同的路徑，若隨機(jī)產(chǎn)生的路徑與已存在的初始種群中的粒子完全相同，則在一定代數(shù)內(nèi)重新產(chǎn)生直至不相同為止；第二，隨機(jī)產(chǎn)生的路徑與已產(chǎn)生粒子的目標(biāo)值之差應(yīng)不小于某一數(shù)值Δ(通常Δ=2[17])。

改進(jìn)節(jié)約法是在Clark和Wright的經(jīng)典C-W節(jié)約法基礎(chǔ)上，綜合考慮車輛總行駛距離、時(shí)間窗、同時(shí)取送貨以及車輛容量限制等約束因素，重新定義節(jié)約值的算法。改進(jìn)的節(jié)約值計(jì)算公式為[21]

(18)

(1)建立一條只包含物流中心0的大路徑X。

(2)將所有客戶按時(shí)間窗下限進(jìn)行升序排列，命名為剩余客戶群。

(3)取出第一個(gè)客戶(即具有最小時(shí)間下限的客戶)作為當(dāng)前客戶，將當(dāng)前客戶插入大路徑X；同時(shí)將當(dāng)前客戶從剩余客戶群中去除，得到新的剩余客戶群。

(4)按式(18)計(jì)算當(dāng)前客戶與所有剩余客戶的新節(jié)約值，選取與當(dāng)前客戶具有最大新節(jié)約值的客戶插入X；更新剩余客戶群，如果剩余客戶群不為空，轉(zhuǎn)步驟(3)，否則輸出大路徑X。

2.2.3位置更新準(zhǔn)則

本文采用離散PSO策略實(shí)現(xiàn)個(gè)體粒子的位置更新。每次迭代時(shí)隨機(jī)生成變異概率u1、個(gè)體交叉概率u2和全局交叉概率u3。根據(jù)式(15)，當(dāng)u1≤w時(shí)進(jìn)行自身變異操作，否則不變異；當(dāng)u2≤c1時(shí)與個(gè)體極值進(jìn)行交叉操作，否則不交叉；當(dāng)u3≤c2時(shí)與全局極值進(jìn)行交叉操作，否則不交叉。

變異操作采用兩點(diǎn)插入式變異。任意選擇待變異粒子中的兩個(gè)位置(第一個(gè)位置除外)，將粒子中所選兩個(gè)位置之間的所有元素按原順序取出，作為變異粒子的前段，然后依次按原順序插入第一個(gè)位置前的所有元素、所選擇兩個(gè)位置上的元素、第二個(gè)位置之后的所有元素，便得到變異后的粒子序列。具體變異過(guò)程如圖2所示。

交叉操作采用PTL兩點(diǎn)交叉[15]。由于個(gè)體粒子可能與個(gè)體極值或全局極值的位置相同，PTL兩點(diǎn)交叉可以使相同序列交叉后得到不同的新序列。以個(gè)體粒子與個(gè)體極值交叉為例，PTL兩點(diǎn)交叉步驟為：任意選擇待交叉?zhèn)€體粒子中的兩個(gè)元素(第一個(gè)元素除外)，交叉時(shí)首先將個(gè)體極值中的對(duì)應(yīng)兩個(gè)元素按原順序取出，作為交叉粒子的前段，然后從個(gè)體極值中依次選擇其他元素放置在其后，形成新的交叉粒子。具體交叉過(guò)程如圖3所示。

圖 2　粒子變異操作

圖 3　粒子交叉操作

2.2.4局域搜索

本文以車輛路徑問(wèn)題中常用的六種鄰域機(jī)制為基礎(chǔ)，設(shè)計(jì)一種變鄰域下降搜索程序作為局域搜索方法，用于位置更新后個(gè)體粒子的深度搜索，尋求以較快的速度在更大搜索空間內(nèi)優(yōu)化個(gè)體搜索質(zhì)量，并據(jù)此作為個(gè)體極值及全局極值的選擇依據(jù)。這六種鄰域機(jī)制為：

(1)路徑間部分交叉。對(duì)任意兩條子路徑，選擇不同的位置將每條子路徑分為前后兩部分，將后面兩部分進(jìn)行交換得到兩條新的子路徑。對(duì)所有子路徑、所有可行的位置進(jìn)行分段交叉，選擇令總配送成本最小的交叉結(jié)果作為新的個(gè)體。

(2)路徑間兩點(diǎn)交換。分別選擇兩條子路徑上的一個(gè)元素，從原路徑上刪除后，插入到另一條子路徑中。插入前，首先確定距離當(dāng)前待插入元素最近的k個(gè)客戶，判斷另一條子路徑中是否至少存在k個(gè)客戶中的一個(gè)客戶，如果存在則選擇插入后新路徑總配送成本最小的位置，否則不插入。

(3)路徑間單點(diǎn)轉(zhuǎn)移。對(duì)任意兩條子路徑，選擇一條路徑上的一個(gè)元素并刪除后，將其插入到另一條子路徑中。對(duì)所有插入位置，選擇令插入后新路徑總成本最小的位置。

(4)路徑內(nèi)部分逆轉(zhuǎn)，即為2-OPT操作。對(duì)任意一條子路徑選擇兩個(gè)位置，通過(guò)對(duì)兩個(gè)位置之間部分執(zhí)行逆轉(zhuǎn)產(chǎn)生新的子路徑。對(duì)所有可行的位置對(duì)，選擇令操作后新路徑總成本最小的位置對(duì)。

(5)路徑內(nèi)兩點(diǎn)交換。對(duì)任意一條子路徑選擇兩個(gè)位置并相互交換形成新的子路徑。對(duì)所有可行的位置對(duì)，選擇令操作后新路徑總成本最小的位置對(duì)。

(6)路徑逆轉(zhuǎn)。對(duì)任意一條子路徑，將原序列從后向前顛倒順序。該操作并不影響總的送貨量與總的取貨量，但可能降低車輛在不同客戶點(diǎn)的最大裝載量使其滿足車容量，或者改變車輛到達(dá)客戶的時(shí)間使其滿足客戶時(shí)間窗要求，從而為后續(xù)迭代過(guò)程中的新客戶插入提供機(jī)會(huì)。

上述鄰域機(jī)制中，前三種為路徑間操作，后三種為路徑內(nèi)操作。由于路徑間操作使得個(gè)體變異幅度較大，路徑內(nèi)操作的變異幅度較小，因此本文以有效變異為前提設(shè)計(jì)一種變鄰域下降搜索程序，基本搜索思想為：首先按上述鄰域機(jī)制順序執(zhí)行鄰域搜索，如果搜索得到更好的目標(biāo)值，則對(duì)該鄰域進(jìn)行路徑內(nèi)深度搜索，否則繼續(xù)按上述順序進(jìn)行下一個(gè)鄰域機(jī)制搜索。詳細(xì)搜索步驟如下：

(1)設(shè)定搜索對(duì)象。設(shè)定搜索對(duì)象為大路徑X及其配送路徑集合R。

(2)按上述六種順序初始化鄰域機(jī)制編號(hào)，初始令o=1。

(3)對(duì)集合R，設(shè)當(dāng)前域?yàn)閔，如果o≤6，采用第o個(gè)鄰域機(jī)制尋找到當(dāng)前域h的最好鄰域h′,轉(zhuǎn)步驟(4)；否則，轉(zhuǎn)步驟(5)。

(4)如果尋找到的鄰域目標(biāo)值比當(dāng)前目標(biāo)值低，即f(h′)

(5)輸出新的配送路徑集合R和大路徑X。

由于客戶變動(dòng)會(huì)影響車輛在路徑不同節(jié)點(diǎn)的最大裝載量及到達(dá)時(shí)間的變化，從而使得新路徑成為不可行路徑，因此每一次鄰域操作時(shí)都必須對(duì)路徑進(jìn)行可行性檢查，即對(duì)各客戶點(diǎn)的最大裝載量及客戶時(shí)間窗、車輛返回物流中心的時(shí)間窗進(jìn)行可行性判斷。為保障鄰域搜索的有效性，只有滿足可行性檢查的鄰域操作及相應(yīng)更新才被接受。

2.2.5粒子“極值”更新方法

隨著迭代次數(shù)的增加，種群多樣性快速下降使得粒子過(guò)早收斂而陷入局部極值。解決該問(wèn)題的常用辦法是采用模擬退火思想概率接受劣解，或者引入變異機(jī)制對(duì)停滯粒子進(jìn)行變異。對(duì)粒子個(gè)體極值采用模擬退火思想接受劣解，接受準(zhǔn)則為：計(jì)算粒子迭代后和迭代前解的變化量ΔE，若ΔE≤0，接受新值；若exp(-ΔE/T)>rand(0,1)，也接受新值；否則拒絕。其中，T表示退火溫度，rand(0,1)為0 ～ 1之間的隨機(jī)數(shù)。

若全局極值在若干代內(nèi)未改進(jìn)，則認(rèn)為種群陷入局部最優(yōu)位置。全局極值更新方法為：以一定比例選取種群中目標(biāo)值最低的粒子進(jìn)行兩點(diǎn)換位變異操作，若變異后粒子目標(biāo)值小于全局極值，則更新全局極值，否則不更新。

2.2.6算法步驟

混合離散粒子群算法的具體步驟如下：

(1)初始化種群參數(shù)S、變異概率w、交叉概率c1和c2、局域搜索概率pL、最大迭代次數(shù)Imax、全局極值連續(xù)未更新最大次數(shù)Mg。

(3)判斷是否滿足終止條件。如果Ng>Mg且t>Imax則滿足終止條件，轉(zhuǎn)步驟(5);否則不滿足終止條件，轉(zhuǎn)步驟(4)。

(5)輸出全局極值粒子X(jué)g、全局極值Cg以及最優(yōu)配送方案。

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

為驗(yàn)證算法尋優(yōu)性能，選取2個(gè)算例進(jìn)行尋優(yōu)測(cè)試。算法采用MATLABR2009b編程語(yǔ)言實(shí)現(xiàn)。微機(jī)運(yùn)行環(huán)境為：CPUi5-2520，主頻 2.5GHz，內(nèi)存4G。

3.1算例選取及實(shí)驗(yàn)參數(shù)設(shè)置

選取文獻(xiàn)[10]的算例2作為本文的算例1，用于驗(yàn)證模型(1)中m= 0，n = 1的情況。該算例按一定規(guī)律生成客戶規(guī)模為40的VRPTWSPD問(wèn)題相關(guān)數(shù)據(jù)，以車輛最大行駛距離作為物流中心的限制條件，要求有效安排行車路線使得車輛總行駛距離最短。

文獻(xiàn)[11]的VRPTWSPD算例基于Solomon經(jīng)典的帶時(shí)間窗VRP算例集，但未給出客戶送貨量與取貨量的取值方法，故無(wú)法直接作為參考算例。RC1問(wèn)題的客戶部分叢聚部分分散、客戶時(shí)間窗較窄，車輛行程較短、需求的車輛數(shù)量較多，是Solomon算例集中最復(fù)雜的一種情況。因此，本文分別選擇算例RC101、RC104、RC107的前10、25和50個(gè)客戶的基礎(chǔ)數(shù)據(jù)，產(chǎn)生9組新的VRPTWSPD算例集作為本文的算例2；9組新算例依次命名為RCdp10101、RCdp25101、RCdp50101、RCdp10104、RCdp25104、Cdp50104、RCdp10107、RCdp25107、RCdp50107。算例中基礎(chǔ)數(shù)據(jù)保持不變，客戶送貨量di及取貨量pi數(shù)據(jù)按如下規(guī)則生成：設(shè)原算例中客戶i需求量為Gi，客戶i的坐標(biāo)為(xi,yi)，令ri=min(xi/yi,yi/xi)，則di=Giri，pi=Gi(1-ri)。此外,由于總配送成本最小化目標(biāo)通過(guò)使用車輛數(shù)最少和車輛行駛距離最短兩個(gè)子目標(biāo)實(shí)現(xiàn)，因此本例設(shè)車輛指派成本為一個(gè)很大的正整數(shù)，車輛單位距離行駛成本g = 1。算例2用于測(cè)試算法對(duì)模型(1)的求解精度，同時(shí)也用于分析種群初始化方法及局域搜索對(duì)算法性能的影響。

通過(guò)測(cè)試，參數(shù)設(shè)置為：種群S = 20，局域搜索概率pL=0.3，變異概率w = 0.4，交叉概率c1=c2=0.6;初始化種群參數(shù)α的取值范圍為[1.5, 3.5]，β的取值范圍為[0.1, 0.5]，γ的取值范圍為[0.5, 1.0]，λ的取值范圍為[0.5, 1.5]；粒子極值更新溫度參數(shù)T=30，q = 0.98。對(duì)算例1，設(shè)置最大迭代次數(shù)Imax= 500，全局極值連續(xù)未更新最大次數(shù)Mg= 100；對(duì)算例2，設(shè)置最大迭代次數(shù)Imax= 1500，全局極值連續(xù)未更新最大次數(shù)Mg= 200。

3.2仿真結(jié)果分析

3.2.1算例1分析

表 1　算例1分析結(jié)果

3.2.2算例2分析

以本文新產(chǎn)生的算例2為基礎(chǔ)數(shù)據(jù)，采用文獻(xiàn)[11]的聯(lián)合進(jìn)化遺傳算法(GA)以及本文算法分別進(jìn)行仿真計(jì)算，9組算例的計(jì)算結(jié)果對(duì)比分析如表2所示。表中加粗字體表示計(jì)算得到的最優(yōu)值?？梢?jiàn)，GA算法在客戶數(shù)為10、25的算例條件下，計(jì)算速度較快，且在RCdp25101算例中得到了好的決策結(jié)果，即使用車輛數(shù)為5、行駛距離為507.56km。本文算法在客戶數(shù)為50的算例條件下，具有更好的近似最優(yōu)解，如在RCdp50101及RCdp50107算例中，盡管行駛距離比GA算法大一些，但使用車輛數(shù)較之少1輛。由于車輛指派成本為一個(gè)很大的正整數(shù)，因此車輛數(shù)目的減少可以大大降低總配送成本。由此可以推論，本文算法在求解VRPTWSPD問(wèn)題時(shí)具有更好的尋優(yōu)能力。

表2　算例2計(jì)算結(jié)果比較

為了進(jìn)一步分析種群初始化方法及局域搜索對(duì)算法性能的影響，選取RCdp25101作為對(duì)比分析對(duì)象，以迭代500次為上限，獨(dú)立運(yùn)算10次選取最優(yōu)近似解進(jìn)行分析。圖4給出了采用2.2.2節(jié)的種群初始化方法(INITIAL)與采用另一種初始化種群方法(NO_INITIAL)，以任意產(chǎn)生I條大路徑序列方式對(duì)種群進(jìn)行初始化的算法收斂性對(duì)比?？梢?jiàn)，在INITIAL情況下初始行駛距離較NO_INITIAL情況下初始行駛距離要小很多，收斂速度更快，最優(yōu)行駛距離更小。這說(shuō)明初始化種群方法對(duì)本文算法求解VRPTWSPD問(wèn)題的性能具有較大影響，良好的種群初始化方法能促使其收斂加快并保持良好的尋優(yōu)能力。

圖4　INITIAL與NO_INITIAL收斂性對(duì)比

圖5　LOCAL與NO_LOCAL情況下收斂性對(duì)比

圖5給出了采用2.2.4節(jié)的局域搜索方法(LOCAL)與不采用局域搜索方法(NO_LOCAL)時(shí)的對(duì)比情況。由圖5可見(jiàn)，在LOCAL情況下粒子收斂速度較快，迭代次數(shù)少且最小行駛距離更短。這說(shuō)明本文提出的局域搜索在粒子群算法求解VRPTWSPD問(wèn)題時(shí)，能大大減少迭代次數(shù)，縮短計(jì)算時(shí)間,有效避免陷入局部最優(yōu)。

4結(jié)語(yǔ)

帶時(shí)間窗裝卸一體化車輛路徑問(wèn)題是一類應(yīng)用廣泛的復(fù)雜車輛路徑問(wèn)題，因其決策目標(biāo)、決策因素和限制條件較多等特征需要高求解性能的啟發(fā)式方法或元啟發(fā)算法。針對(duì)帶時(shí)間窗裝卸一體化車輛路徑問(wèn)題，建立了隱含兩個(gè)子目標(biāo)的混合整數(shù)規(guī)劃模型，提出了求解帶時(shí)間窗裝卸一體化車輛路徑問(wèn)題的混合離散粒子群算法。該算法采用基于C-W的改進(jìn)啟發(fā)式方法產(chǎn)生初始種群，在一定概率下對(duì)粒子進(jìn)行局域搜索，并采用模擬退火思想接受粒子個(gè)體極值劣解。針對(duì)不同總目標(biāo)，分別基于兩個(gè)算例進(jìn)行仿真分析。仿真結(jié)果表明，無(wú)論是單純以總行駛距離為目標(biāo)的算例1問(wèn)題，還是以總配送成本為總目標(biāo)、以車輛數(shù)最少和總行駛距離最短為子目標(biāo)的算例2問(wèn)題，本文提出的混合離散粒子群算法都能以較快的收斂速度找到近似最優(yōu)解，且尋優(yōu)性能好于已有的改進(jìn)差分進(jìn)化算法和聯(lián)合進(jìn)化遺傳算法。由此可見(jiàn)，本文所提算法對(duì)于具有不同時(shí)間約束服務(wù)的物流配送和取貨優(yōu)化問(wèn)題具有重要的指導(dǎo)意義，同時(shí)對(duì)于離散型組合優(yōu)化問(wèn)題的進(jìn)一步研究也具有一定的理論參考價(jià)值。

參考文獻(xiàn)：

[1]BerbegliaG,CordeauJF,GribkovskaiaI,etal.StaticPickupandDeliveryProblems:aClassificationSchemeandSurvey[J].TOP,2007,15(1):1-31.

[2]郎茂祥. 物流配送車輛調(diào)度問(wèn)題的模型和算法研究[D]. 北京：北方交通大學(xué), 2002.

[3]MinH.TheMultipleVehicleRoutingProblemwithSimultaneousDeliveryandPick-upPoints[J].TransportationResearchPartAGeneral, 1989, 23(5): 377-386.

[4]DethloffJ.VehicleRoutingandReverseLogistics:theVehicleRoutingProblemwithSimultaneousDeliveryandPick-up[J].OrSpectrum, 2001, 23(1): 79-96.

[5]BianchessiN,RighiniG.HeuristicAlgorithmsfortheVehicleRoutingProblemwithSimultaneousPick-upandDelivery[J].Computers&OperationsResearch,2007,34:578-594.

[6]李雪, 聶蘭順, 齊文艷,等. 基于近似動(dòng)態(tài)規(guī)劃的動(dòng)態(tài)車輛調(diào)度算法[J].中國(guó)機(jī)械工程,2015,26(5):682-688.

LiXue,NieLanshun,QiWenyan,etal.AnAlgorithmofDynamicVehicleSchedulingProblemBasedonApproximateDynamicProgramming[J].ChinaMechanicalEngineering, 2015, 26(5):682-688.

[7]AiTJ,KachitvichyanukulV.AParticleSwarmOptimizationfortheVehicleRoutingProblemwithSimultaneousPickupandDelivery[J].Computers&OperationsResearch,2009,36:1693-1702.

[8]GajpalY,AbadP.AnAntColonySystem(ACS)forVehicleRoutingProblemwithSimultaneousDeliveryandPickup[J].Computers&OperationsResearch, 2009,36:3215- 3223.

[9]AngelelliE,MansiniR.ABranch-and-priceAlgorithmforaSimultaneousPick-upandDeliveryProblem[C]//LectureNotesinEconomicsandMathematicalSystems.USA:Springer, 2002: 249-267.

[10]LaiMingyong,CaoErbao.AnImprovedDifferentialEvolutionAlgorithmforVehicleRoutingProblemwithSimultaneousPickupsandDeliveriesandTimeWindows[J].EngineeringApplicationsofArtificialIntelligence, 2010, 23:188-195.

[11]WangHF,ChenYY.AGeneticAlgorithmfortheSimultaneousDeliveryandPickupProblemswithTimeWindow[J].Computers&IndustrialEngineering, 2012, 62: 84-95.

[12]王超, 穆東. 基于模擬退火算法求解VRPSPDTW問(wèn)題[J]. 系統(tǒng)仿真學(xué)報(bào), 2014,11(6):2618-2623.

WangChao,MuDong.SolvingVRPSPDTWProblemUsingSimulatedAnnealingAlgorithm[J].JournalofSystemSimulation, 2014, 11(6):2618-2623.

[13]BoubahriL,AddoucheSA,MhamediAE.Multi-antColoniesAlgorithmsfortheVRPSPDTW[C]// 2011InternationalConferenceonCommunications,ComputingandControlApplications(CCCA).NewYork:IEEE,2011: 1-6.[14]邱晗光, 張旭梅. 基于改進(jìn)粒子群算法的開(kāi)放式定位-運(yùn)輸路線問(wèn)題研究[J]. 中國(guó)機(jī)械工程, 2006, 17(22): 2359-2361.

QiuHanguang,ZhangXumei.ResearchonOpenLocationRoutingProblemBasedonImprovedParticleSwarmOptimizationAlgorithm[J].ChinaMechanicalEngineering, 2006, 17(22): 2359-2361.

[15]PanQK,TasgetirenMF,LiangYC.ADiscreteParticleSwarmOptimizationAlgorithmfortheNo-waitFlowshopSchedulingProblem[J].Computers&OperationsResearch, 2008, 35: 2807-2839.

[16]郭文忠, 陳國(guó)龍, 陳振. 離散粒子群優(yōu)化算法綜述[J]. 福州大學(xué)學(xué)報(bào)(自然科學(xué)版), 2011, 39(5): 631-638.

GuoWenzhong，ChenGuolong，ChenZhen.SurveyonDiscreteParticleSwarmOptimizationalgorithm[J].JournalofFuzhouUniversity(NaturalScienceEdition), 2011, 39(5): 631-638.

[17]PrinsC.ASimpleandEffectiveEvolutionaryAlgorithmfortheVehicleRoutingProblem[J].Computers&OperationsResearch, 2004, 31: 1985-2002.

[18]BeasleyJE.Route-firstCluster-secondMethodsforVehicleRouting[J].Omega, 1983, 11:403-408.

[19]DuhamelC,LacommeP,ProdhonC.AHybridEvolutionaryLocalSearchwithDepthFirstSearchSplitProcedurefortheHeterogeneousVehicleRoutingProblems[J].EngineeringApplicationsofArtificialIntelligence, 2012, 25: 345-358.

[20]DuhamelC,LacommeP,ProdhonC.EfficientFrameworksforGreedySplitandNewDepthFirstSearchSplitProceduresforRoutingProblems[J].Computers&OperationsResearch, 2011, 38: 723-739.

[21]莊英群. 應(yīng)用禁忌搜索法于混合送收貨之車輛途程問(wèn)題[D] .臺(tái)中:逢甲大學(xué), 2003.

(編輯王艷麗)

AHybridDiscreteParticleSwarmOptimizationAlgorithmforVehicleRoutingProblemwithTimeWindowsandSimultaneousPickupandDelivery

ZhouRongShenWeileiLiuMingzhouZhaoHan

HefeiUniversityofTechnology,Hefei, 230009

Abstract：Considering the relative importance of dispatching cost of vehicles and travelling cost of routes, a mixed integer mathematical formulation of the vehicle routing problem with time windows and simultaneous pickup and delivery (VRPTWSPD) was established to make the total delivery cost, the number of vehicles and the travel cost minimize simultaneously. A hybrid discrete particle swarm optimization algorithm was proposed for solving VRPTWSPD. Solutions of algorithm were represented by an intuitive fragment-free giant tour of a permutation of all customers, and were decoded and evaluated by the revised depth first search split procedure. A variable neighborhood descent search procedure was carried out under a certain probability for individuals at each iteration, so that individuals could update with depth search in multi-neighborhood and with bread search in global exploration. The simulated annealing idea and mutating a selective portion of worst individuals were applied to improve the stagnation of the search. The feasibility and effectiveness of the proposed algorithm were verified by two instances with different goals.

Key words：vehicle routing problem with time window; simultaneous pickup and delivery; discrete particle swarm optimization; variable neighborhood descent search

收稿日期：2015-04-28

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(71071046)

中圖分類號(hào)：TP3

DOI：10.3969/j.issn.1004-132X.2016.04.013

作者簡(jiǎn)介：周蓉， 女，1977年生。合肥工業(yè)大學(xué)機(jī)械與汽車工程學(xué)院講師。主要研究方向?yàn)橘Y源調(diào)度、物流系統(tǒng)優(yōu)化。發(fā)表論文10余篇。沈維蕾，女，1969年生。合肥工業(yè)大學(xué)機(jī)械與汽車工程學(xué)院副教授。劉明周，男，1968年生。合肥工業(yè)大學(xué)機(jī)械與汽車工程學(xué)院教授、博士研究生導(dǎo)師。趙韓，男，1957年生。合肥工業(yè)大學(xué)機(jī)械與汽車工程學(xué)院教授、博士研究生導(dǎo)師。