帶時(shí)間窗和調(diào)貨特性的多品類(lèi)取送貨優(yōu)化算法

溫 昆 ,郭 鵬,2 ,裴 霞 ,吳 曉,2

(1.西南交通大學(xué) 機(jī)械工程學(xué)院,成都 610031;2.軌道交通運(yùn)維技術(shù)與裝備四川省重點(diǎn)實(shí)驗(yàn)室,成都 610031)

快時(shí)尚品(譬如女鞋、女裝等)款式更新快且上架展示周期短,需要零售管理方主動(dòng)控制門(mén)店庫(kù)存,盡可能保證門(mén)店銷(xiāo)售需求得到滿(mǎn)足。管理人員基于門(mén)店以往的銷(xiāo)售數(shù)據(jù)對(duì)時(shí)下流行貨品進(jìn)行銷(xiāo)量預(yù)測(cè),估算出每種貨品未來(lái)時(shí)段的銷(xiāo)售量。以此為基礎(chǔ)并結(jié)合每個(gè)門(mén)店現(xiàn)有的庫(kù)存,對(duì)每個(gè)門(mén)店的每種貨品進(jìn)行補(bǔ)貨和調(diào)貨。當(dāng)預(yù)測(cè)的銷(xiāo)量小于現(xiàn)有的存量時(shí),為了防止門(mén)店此類(lèi)貨品積壓,需及時(shí)將多余的貨品運(yùn)走;當(dāng)預(yù)測(cè)的銷(xiāo)量大于現(xiàn)有的存量時(shí),需對(duì)門(mén)店的此類(lèi)貨品進(jìn)行補(bǔ)充。提倡門(mén)店之間貨品互補(bǔ),以降低調(diào)配成本。此外,門(mén)店取送貨服務(wù)時(shí)段存在差異。為保證取送貨的順利進(jìn)行,對(duì)配送車(chē)輛到達(dá)門(mén)店的時(shí)間也有限制。為此,本文提出帶時(shí)間窗和調(diào)貨特性的多品類(lèi)取送貨問(wèn)題(Multi-commodity Pickup and Delivery Problem with Time Window and Transshipment,M-PDPTWT),以幫助快時(shí)尚零售企業(yè)降低成本、提高作業(yè)效率。M-PDPTWT是帶時(shí)間窗車(chē)輛路徑問(wèn)題(Vehicle Routing Problem with Time Windows,VRPTW)更一般的描述。VRPTW 旨在考慮各個(gè)門(mén)店可配送的時(shí)間窗,在滿(mǎn)足倉(cāng)庫(kù)輻射范圍內(nèi)各個(gè)門(mén)店貨品需求和不超過(guò)車(chē)輛最大載容量的前提下,以實(shí)現(xiàn)配送車(chē)輛數(shù)最小化、車(chē)輛行駛距離最短、車(chē)輛裝載均衡等目標(biāo)。

Braekers等[1]對(duì)VRP進(jìn)行了綜述,討論了精確算法與啟發(fā)式算法應(yīng)用情況。針對(duì)VRPTW,精確算法有基于集劃分的分支定價(jià)與切割算法[2]、基于集合覆蓋的列生成算法[3]、改進(jìn)分支切割算法[4]等,啟發(fā)式算法有遺傳算法[5]、大規(guī)模鄰域搜索算法[6]、進(jìn)化學(xué)習(xí)算法[7]、融合禁忌搜索和人工蜂群算法的混合算法[8]、混合蟻群算法[9]以及混合遺傳算法[10]等。VRPTW 作為經(jīng)典的車(chē)輛路徑問(wèn)題,具有時(shí)間窗和車(chē)容量約束,但僅考慮送貨需求。同時(shí),帶有取送貨和時(shí)間窗的車(chē)輛路徑問(wèn)題(Vehicle Routing Problem with Simultaneous Pickup-Delivery and Time Windows,VRPSPDTW)和帶時(shí)間窗的同時(shí)取送貨問(wèn)題(Pickup and Delivery Problem with Time Windows,PDPTW)均考慮了取送貨需求。VRPSPDTW 和PDPTW 都是針對(duì)配送時(shí)間有要求的顧客,在滿(mǎn)足車(chē)載容量、顧客時(shí)間窗以及每個(gè)顧客對(duì)貨物的配送請(qǐng)求,規(guī)劃出車(chē)輛數(shù)最少、運(yùn)輸距離最小以及倉(cāng)庫(kù)處理成本最小等目標(biāo)的運(yùn)輸方案。VRPSPDTW 規(guī)定顧客需求的貨物必須從倉(cāng)庫(kù)運(yùn)輸,顧客不需要的貨物也必須帶回倉(cāng)庫(kù),如快遞員上門(mén)取送包裹。Ko?等[11]對(duì)同時(shí)取送貨問(wèn)題進(jìn)行了綜述,分析了取送貨問(wèn)題的研究趨勢(shì)。模擬退火算法[12]、化學(xué)反應(yīng)優(yōu)化算法[13]、基于學(xué)習(xí)的兩階段搜索算法[14]等被用來(lái)求解VRPSPDTW,且面臨最小化車(chē)輛數(shù)、最小化車(chē)輛行駛距離、最小化運(yùn)營(yíng)成本以及最大化工作效率等目標(biāo)。PDPTW 則是將指定節(jié)點(diǎn)(包括倉(cāng)庫(kù)和顧客)的貨物運(yùn)送到另一指定節(jié)點(diǎn),是一對(duì)一的運(yùn)輸問(wèn)題,如經(jīng)典的電話(huà)叫車(chē)問(wèn)題(Dial A Ride Problem,DARP)。自適應(yīng)大規(guī)模鄰域搜索算法[15]、禁忌搜索算法[16]、基于數(shù)學(xué)規(guī)劃的混合算法[17]、改進(jìn)遺傳算法[18]以及列生成算法與啟發(fā)式規(guī)則相結(jié)合的CGA 混合算法[19]等用于求解不同場(chǎng)景下的PDPTW。

無(wú)論是VRPSPDTW 或PDPTW,配送請(qǐng)求都是針對(duì)一種貨物,貨物的配送和交付也不具有可重復(fù)使用性。而在快時(shí)尚服裝銷(xiāo)售鄰域,需要考慮運(yùn)送的貨物多達(dá)幾十、上百種,甚至上千種,這勢(shì)必增加問(wèn)題的求解難度。文獻(xiàn)[20-21]中針對(duì)多貨品調(diào)配和門(mén)店互補(bǔ)的車(chē)輛路徑問(wèn)題提出了精確與啟發(fā)式求解算法。Li等[20]提出了一種基于強(qiáng)集合劃分模型的分支定價(jià)切割算法。Zhang等[21]提出了一種基于自適應(yīng)內(nèi)存規(guī)劃算法。對(duì)于快時(shí)尚品的配送貨問(wèn)題,欒玉麟等[22]基于頂點(diǎn)拆分策略,設(shè)計(jì)了遺傳算法求解大規(guī)模實(shí)際算例。

上述文獻(xiàn)中,與本文最為相關(guān)的文獻(xiàn)[20-22]未考慮各個(gè)門(mén)店存在不同的取送貨服務(wù)時(shí)間窗,而考慮VRPTW 的文獻(xiàn)則未考慮多品類(lèi)與門(mén)店間相互調(diào)貨的實(shí)際情況。基于此,文本提出以車(chē)輛數(shù)最小化為第一優(yōu)化目標(biāo),最小化轉(zhuǎn)運(yùn)成本(運(yùn)輸成本和倉(cāng)庫(kù)處理成本)為第二優(yōu)化目標(biāo)的M-PDPTWT,構(gòu)建了混合整數(shù)規(guī)劃模型?；趦?yōu)化目標(biāo)設(shè)計(jì)了兩階段搜索算法:第1階段,利用最短路徑搜索規(guī)則構(gòu)建初始解;第2階段,以變鄰域搜索算法為框架。不同搜索時(shí)期用不同的適應(yīng)度函數(shù)進(jìn)行計(jì)算,以增強(qiáng)對(duì)最小化車(chē)輛數(shù)的搜索能力,并定義多種鄰域解屬性和優(yōu)先保留策略。在搜索過(guò)程中不僅接受可行解,還允許接受具有潛在搜索能力的不可行解,以增強(qiáng)算法對(duì)全局解空間的搜索能力。在計(jì)算實(shí)驗(yàn)部分,采用標(biāo)準(zhǔn)算例和基于實(shí)際運(yùn)營(yíng)數(shù)據(jù)生成的算例進(jìn)行了算法性能分析。

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

1.1 問(wèn)題描述與假設(shè)

配送車(chē)輛從倉(cāng)庫(kù)出發(fā),攜帶不超過(guò)車(chē)輛最大載重量Q的多種貨品用以補(bǔ)給缺少貨品的門(mén)店。每個(gè)門(mén)店有規(guī)定的到達(dá)時(shí)間窗,配送車(chē)輛如果早于時(shí)刻ei到達(dá)則必須等待,但不能晚于li到達(dá)。車(chē)輛在達(dá)到某個(gè)門(mén)店后耗費(fèi)停留時(shí)間sei用于裝卸貨品。每個(gè)門(mén)店除了有補(bǔ)貨需求,也須將門(mén)店其他多余貨品取走,避免貨品在門(mén)店長(zhǎng)期積壓。被運(yùn)走的貨品可以用來(lái)補(bǔ)給同一條配送路徑上后續(xù)門(mén)店,也可將其運(yùn)回倉(cāng)庫(kù)。通過(guò)提倡貨品在門(mén)店之間相互調(diào)配的方式,可以降低搭配成本和倉(cāng)庫(kù)對(duì)貨品的處理成本。對(duì)整個(gè)配送網(wǎng)絡(luò)體系的路徑優(yōu)化中,需要考慮的目標(biāo)函數(shù)有兩個(gè):配送車(chē)輛數(shù)最少及在此基礎(chǔ)上配送成本(距離)和倉(cāng)庫(kù)處理成本最小化。

建立模型時(shí)假設(shè)如下:

(1)每輛車(chē)載重量相同,行駛速度相同。

(2)貨品裝車(chē)時(shí)不考慮體積的影響。

(3)每個(gè)門(mén)店必須被訪(fǎng)問(wèn),且只能訪(fǎng)問(wèn)一次。

1.2 符號(hào)說(shuō)明及參數(shù)

假設(shè)有n個(gè)門(mén)店,每個(gè)門(mén)店取送貨在同一地點(diǎn)、同一時(shí)段內(nèi)完成。門(mén)店用i表示,倉(cāng)庫(kù)用0 和n+1表示。集合N為所有門(mén)店的集合,包含倉(cāng)庫(kù)的集合N0=N∪{0,n+1}。配送車(chē)輛集合V={1,2,…,h},其中,h為車(chē)場(chǎng)提供的車(chē)數(shù)量。K={1,2,…,m}為貨品種類(lèi)的集合,其中,m為配送貨品的最大種類(lèi)數(shù)目。

其余符號(hào)

cij——從門(mén)店i到門(mén)店j的運(yùn)輸成本,i,j∈N0

tij——從門(mén)店i到門(mén)店j的運(yùn)輸時(shí)間,i,j∈N0

sei——門(mén)店i的服務(wù)時(shí)間,i∈N0,其中,se0=sen+1=0

ei——門(mén)店i時(shí)間窗的最早達(dá)到時(shí)間,i∈N0,其中,e0=en+1表示倉(cāng)庫(kù)的最早工作時(shí)間

li——門(mén)店i時(shí)間窗的最晚到達(dá)時(shí)間,i∈N0,其中,l0=ln+1表示倉(cāng)庫(kù)的最晚工作時(shí)間

ω——倉(cāng)庫(kù)的處理成本系數(shù)

Q——車(chē)輛的最大載容量

決策變量

1.3 模型建立

目標(biāo)函數(shù)式(1)表示最小化車(chē)輛數(shù);式(2)表示最小化運(yùn)輸成本和倉(cāng)庫(kù)處理成本;約束條件式(3)、(4)表示每個(gè)門(mén)店必須訪(fǎng)問(wèn)且只能訪(fǎng)問(wèn)一次;式(5)為車(chē)流量守恒約束,表示第v輛車(chē)在訪(fǎng)問(wèn)p點(diǎn)之后必須從p點(diǎn)離開(kāi);式(6)表示車(chē)輛必須從倉(cāng)庫(kù)0點(diǎn)出發(fā);式(7)表示車(chē)輛必須返回倉(cāng)庫(kù)n+1點(diǎn);式(8)表示到達(dá)門(mén)店i的時(shí)間加上在門(mén)店i的服務(wù)時(shí)間再加上從門(mén)店i到達(dá)門(mén)店j的車(chē)輛行駛時(shí)間不能晚于門(mén)店j的時(shí)間窗最大值;式(9)為時(shí)間窗約束,表示車(chē)輛必須在規(guī)定的時(shí)間窗范圍內(nèi)訪(fǎng)問(wèn)門(mén)店,早于時(shí)間窗的最小值到達(dá)門(mén)店必須等待,不可晚于最晚的到達(dá)時(shí)間;式(10)為車(chē)輛的載重約束,表示車(chē)輛的實(shí)時(shí)載重不能超過(guò)車(chē)輛的最大載重;式(11)表示當(dāng)?shù)趘輛車(chē)從i點(diǎn)到達(dá)j點(diǎn)時(shí),離開(kāi)i點(diǎn)時(shí)每類(lèi)貨品的載重量大于j點(diǎn)對(duì)該種貨品的需求量;式(12)為載重平衡約束,表示當(dāng)?shù)趘輛車(chē)從i點(diǎn)到達(dá)j點(diǎn)時(shí),離開(kāi)i點(diǎn)時(shí)每類(lèi)貨品的載量加上j點(diǎn)的需求量/供應(yīng)量等于離開(kāi)j點(diǎn)時(shí)該類(lèi)貨品的載量;式(13)為載重量守恒約束,表示車(chē)輛從車(chē)場(chǎng)帶走的k類(lèi)貨品加上整條路徑上所有門(mén)店對(duì)該類(lèi)貨品的需求/供應(yīng)之和,等于返回車(chē)場(chǎng)時(shí)車(chē)輛裝載k類(lèi)貨品的載量;式(14)～(16)為變量的取值范圍約束。

2 兩階段搜索算法

本文提出的兩階段搜索算法(Two-Stage Search Algorithm,TSSA)采用自然數(shù)編碼,“0”表示倉(cāng)庫(kù),“1,2,…,i,…,n”分別表示不同的門(mén)店,單條車(chē)輛路徑序列為“[0,…,i-1,i,i+1,…,0]”。第1階段利用最短路徑插入規(guī)則構(gòu)建初始解,第2階段以變鄰域搜索算法為框架,通過(guò)兩個(gè)不同適應(yīng)度函數(shù)進(jìn)行反復(fù)迭代搜索;定義了多種形式的更優(yōu)解,引入多種鄰域解的評(píng)價(jià)方式,接受各種形式的更優(yōu)解;通過(guò)改進(jìn)的擾動(dòng)機(jī)制,保證算法能夠跳出局部最優(yōu)解的同時(shí),又增強(qiáng)了算法對(duì)解空間的搜索能力。

2.1 構(gòu)建初始解

初始解采用一種近似貪心算法的最短路徑插入規(guī)則,在滿(mǎn)足車(chē)容量和時(shí)間窗約束的前提下,盡可能多地在一條路徑中插入門(mén)店。算法步驟如下:

(1)確定未被插入的門(mén)店集合A(A=N),生成一條車(chē)輛路徑R={[0]};

(2)插入距離倉(cāng)庫(kù)最遠(yuǎn)的門(mén)店i(i∈A)作為空路徑r(r∈R)的第1個(gè)點(diǎn),A=A{i};

(3)將剩余的門(mén)店u(u∈A)依次插入路徑r(r∈R)的每個(gè)位置a(不包括0點(diǎn))前面,計(jì)算每個(gè)門(mén)店u插入路徑r每個(gè)位置a的適應(yīng)度值構(gòu)成集合B1,集合B2記錄了門(mén)店u每一次插入的位置,如果插入之后使得路徑變成不可行解,則設(shè)置該次插入的適應(yīng)度值為無(wú)窮大;

(4)若集合B1中記錄所有適應(yīng)度值均為無(wú)窮大,則表示當(dāng)前所有路徑?jīng)]有可行的插入點(diǎn),新增一條空路徑R=R∪{[0]},當(dāng)前插入路徑r更新為新的空路徑,循環(huán)步驟(2)～(3),否則執(zhí)行步驟(5);

(5)B1中最小數(shù)值對(duì)應(yīng)的門(mén)店即為最佳的插入門(mén)店u*,B2中門(mén)店u*對(duì)應(yīng)的插入位置即為最佳的插入位置a*;

(6)將門(mén)店u*插入到路徑r的位置a*,A=A{u*};

(7)循環(huán)步驟(3)～(6),直到A=φ時(shí)停止循環(huán);

(8)在所有的路徑最后插入0。

集合B1中每個(gè)元素的適應(yīng)度值按下式計(jì)算:

式中:ra表示路徑r的第a個(gè)門(mén)店;cra,u+cu,ra+1-cra,ra+1表示將u點(diǎn)插入路徑r第a和第a+1個(gè)門(mén)店后該條路徑運(yùn)輸成本增加值;frau表示將u點(diǎn)插入當(dāng)前所有路徑的成本增加值與將u點(diǎn)插入一條新的空路徑的成本增加值的差值。

2.2 改進(jìn)變鄰域搜索算法

2.2.1 操作算子 常用的操作算子包括relocate、shift、cross、inter-exchange 以 及intro-exchange。Relocate是路徑間的單點(diǎn)插入算子,是將一個(gè)點(diǎn)插入到其他路徑中;shift是指路徑內(nèi)將一個(gè)點(diǎn)插入到其他位置;cross 是指交換兩條路徑的后半段;exchange是指交換兩個(gè)點(diǎn),包括路徑間interexchange和路徑內(nèi)intro-exchange兩種情況。本文除了使用這5個(gè)操作算子,還使用了兩個(gè)擴(kuò)展操作算子和k-opt算子。

圖1 所示為路徑間的隨機(jī)長(zhǎng)度片段交換算子λ-inter-exchange,對(duì)任意兩條路徑,取路徑上的任意一個(gè)點(diǎn)后面的隨機(jī)長(zhǎng)度片段(片段可以只有一個(gè)點(diǎn),不包括0)進(jìn)行交換。圖2所示為路徑內(nèi)的隨機(jī)片段交換算子λ-intro-exchange,對(duì)長(zhǎng)度大于等于4的路徑,路徑內(nèi)任意兩點(diǎn)將路徑分割為3個(gè)片段,從第2和第3個(gè)片段最左邊開(kāi)始取隨機(jī)長(zhǎng)度的片段(片段可以只有一個(gè)點(diǎn),不包括0)進(jìn)行交換。兩個(gè)操作算子是對(duì)exchange算子的擴(kuò)展,增加了每一次鄰域操作片段的長(zhǎng)度,采用每次隨機(jī)取每條路徑中的某個(gè)片段進(jìn)行交換,擴(kuò)大了鄰域解的搜索空間,在多次迭代之后保證了對(duì)最優(yōu)解的搜索能力。

圖1 λ-inter-exchange

圖2 λ-intro-exchange

由Helsgaun[23-24]提出的k-opt算子是一種對(duì)單條路徑尋優(yōu)效果好且效率高的操作算子。k-opt總是在節(jié)點(diǎn)數(shù)較少的情況下進(jìn)行交換,其效率可以相當(dāng)于2.2-opt。k-opt首先使用不同長(zhǎng)度的2-opt優(yōu)化路徑長(zhǎng)度,在2-opt無(wú)法找到更優(yōu)解時(shí)則使用3-opt操作,如果3-opt能找到更優(yōu)解,則回到2-opt繼續(xù)尋找;如果3-opt不能找到更優(yōu)解,就使用4個(gè)節(jié)點(diǎn)的交換來(lái)尋找更優(yōu)解,以此循環(huán)。

2.2.2 適應(yīng)度函數(shù) 由于服務(wù)時(shí)間窗的導(dǎo)入,使得從倉(cāng)庫(kù)/門(mén)店離開(kāi)到達(dá)下一個(gè)門(mén)店/倉(cāng)庫(kù)的時(shí)間以及在門(mén)店開(kāi)始裝卸的作業(yè)時(shí)間存在差異。根據(jù)時(shí)間窗早到等待的規(guī)則,一是車(chē)輛實(shí)際開(kāi)始服務(wù)門(mén)店的時(shí)間,另一是車(chē)輛實(shí)際達(dá)到門(mén)店的時(shí)間,兩者的計(jì)算方式為:

式(18)同式(9),車(chē)輛開(kāi)始服務(wù)門(mén)店的時(shí)間須滿(mǎn)足每個(gè)門(mén)店的時(shí)間窗限制。式(19)中,車(chē)輛v路徑上第a個(gè)門(mén)店的實(shí)際到達(dá)時(shí)間等于路徑上第a-1個(gè)門(mén)店的服務(wù)開(kāi)始時(shí)間加上在該門(mén)店的服務(wù)時(shí)間再加上從該門(mén)店到第a個(gè)門(mén)店的運(yùn)輸時(shí)間,

式(20)計(jì)算了上述兩個(gè)時(shí)間的累積差值。最小化時(shí)間差累計(jì)和能引導(dǎo)算法朝著時(shí)間窗更加緊湊的方向進(jìn)行搜索。

下式給出了算法的第1 個(gè)適應(yīng)度函數(shù),依次為路徑的運(yùn)輸成本、倉(cāng)庫(kù)的處理成本、時(shí)間窗的違背值、載重量的違背值及鄰域解的緊時(shí)間窗引導(dǎo)函數(shù)T,計(jì)算中后面三部分通過(guò)權(quán)重系數(shù)進(jìn)行調(diào)節(jié),

由式(21)可知,對(duì)于鄰域搜索出現(xiàn)的可行解,時(shí)間窗和載重量的違背值都等于0,并不影響轉(zhuǎn)運(yùn)成本;而不可行解中總有其中之一或兩個(gè)違背值都不等于0。因此,在最小化的搜索過(guò)程中,算法總是朝著可行解的方向進(jìn)行搜索。引導(dǎo)函數(shù)T的加入,使得適應(yīng)度函數(shù)值總是大于實(shí)際的轉(zhuǎn)運(yùn)成本,故引導(dǎo)函數(shù)T不能一直存在于適應(yīng)度函數(shù)中。

本算法設(shè)計(jì)通過(guò)適應(yīng)度函數(shù)f1在經(jīng)過(guò)連續(xù)Z次迭代后,就不再用引導(dǎo)函數(shù)進(jìn)行評(píng)價(jià),故算法提出了第2個(gè)適應(yīng)度函數(shù)f2,即

2.2.3 鄰域解評(píng)價(jià)及優(yōu)先保留算子 鄰域搜索中出現(xiàn)的鄰域解分為可行解和不可行解兩種。其中:①當(dāng)鄰域解的解序列中車(chē)輛的實(shí)時(shí)載量超過(guò)車(chē)輛的最大載量;②當(dāng)鄰域解的解序列中存在某個(gè)點(diǎn)的時(shí)間窗違背了該點(diǎn)前后兩點(diǎn)的時(shí)間窗。只要這兩種情況出現(xiàn)一種,就構(gòu)成了不可行解。可行解中出現(xiàn)車(chē)輛數(shù)減少的情況,這種解稱(chēng)為優(yōu)先可行解,記為sol1;可行解中車(chē)輛數(shù)未減少,但是總的距離縮短,這種解稱(chēng)為距離更優(yōu)的可行解,記為sol2。同樣,不可行解出現(xiàn)車(chē)輛數(shù)減少時(shí),稱(chēng)為車(chē)輛數(shù)更優(yōu)的不可行解,記為sol3;不可行解中車(chē)輛數(shù)未減少,總的距離縮短,稱(chēng)為距離更優(yōu)的不可行解,記為sol4。sol1與sol2是算法前進(jìn)的方向,并且車(chē)輛數(shù)減少的sol1是優(yōu)先考慮接受的,但是產(chǎn)生sol3與sol4時(shí)也不能被即刻淘汰,也許基于當(dāng)前不可行解進(jìn)行搜索會(huì)產(chǎn)生sol1與sol2。因此,算法給出了兩種不同情況下的優(yōu)先保留算子:

(1)當(dāng)產(chǎn)生sol1 時(shí),適應(yīng)度函數(shù)為:f1=f1/ξ1,f2=f2/ξ1。

(2)當(dāng)產(chǎn)生sol3 時(shí),適應(yīng)度函數(shù)為:f1=f1/ξ2,f2=f2/ξ2。

其中,ξ1～ξ2 ＞1,?ξ1,ξ2 ∈N*。在尋找最小值的鄰域搜索中,這兩種情況會(huì)被優(yōu)先保留下來(lái),兩者的區(qū)別在于,前者的鄰域解在向下傳遞鄰域解時(shí)會(huì)將空路徑刪除,而后者不能刪除空路徑,除非在接下來(lái)的搜索中出現(xiàn)sol1或者sol2。

2.2.4 擾動(dòng)機(jī)制 傳統(tǒng)VNS算法在每次鄰域搜索結(jié)束后,將鄰域解傳入新的操作算子中,通過(guò)隨機(jī)指定操作節(jié)點(diǎn)的方式,在有限的時(shí)間內(nèi)(通常時(shí)間小于1 s),將搜索過(guò)程中目標(biāo)值最小的可行鄰域解傳入下一個(gè)操作算子進(jìn)行搜索,如果在有限的時(shí)間內(nèi)未找到可行的鄰域解,則將原鄰域解傳入下一個(gè)操作算子進(jìn)行搜索。可見(jiàn),傳統(tǒng)的鄰域搜索在每次鄰域搜索完成后都對(duì)鄰域解進(jìn)行擾動(dòng),并且擾動(dòng)采用隨機(jī)的方式,保證了VNS算法能夠跳出局部最優(yōu)解。然而,由于搜索過(guò)程中擾動(dòng)頻率太高,使得VNS算法對(duì)當(dāng)前鄰域解的搜索不夠徹底,并且擾動(dòng)采用隨機(jī)的方式,擾動(dòng)后的鄰域解已大幅偏離原鄰域解,再一次增大了對(duì)當(dāng)前鄰域解搜索不夠徹底的可能。

在最小化的尋優(yōu)算法中,操作算子在遍歷當(dāng)前所有可能的鄰域解后,找到一個(gè)比當(dāng)前鄰域解更優(yōu)的鄰域解替換當(dāng)前鄰域解并向下傳遞,如果搜索出現(xiàn)的鄰域解沒(méi)有當(dāng)前的鄰域解好,則不做替換。針對(duì)這一特點(diǎn),本算法設(shè)計(jì)在連續(xù)迭代Y次后都未找到優(yōu)化解,則將當(dāng)前鄰域解的目標(biāo)值設(shè)置為無(wú)窮大,在下一次操作算子搜索過(guò)程中,目標(biāo)值為無(wú)窮大的鄰域解很容易就會(huì)被新的鄰域解替換。通過(guò)不斷地尋優(yōu)替換,在操作算子一次完整的搜索之后,又能重新得到一個(gè)質(zhì)量較好的局部最優(yōu)解。

2.3 算法流程

如圖3所示,首先產(chǎn)生一個(gè)可行的初始解,初始化算法參數(shù)并將neibor_obj設(shè)置為無(wú)窮大,然后將初始解傳入第二階段搜索算法。鄰域搜索過(guò)程用8個(gè)操作算子中neibor_num 對(duì)應(yīng)的算子進(jìn)行搜索。對(duì)搜索出現(xiàn)的每一個(gè)鄰域解按照2.2.2和2.2.3節(jié)進(jìn)行計(jì)算和評(píng)價(jià)。如果獲得了優(yōu)化解(sol1 或sol2),則將當(dāng)前鄰域解的目標(biāo)值更新給neibor_obj,同時(shí)將當(dāng)前優(yōu)化解傳遞給全局優(yōu)化解,然后迭代次數(shù)iteration加1,操作算子序號(hào)neibor_num 加1,count_break重置為0;如果本次操作算子搜索沒(méi)有找到優(yōu)化解,而搜索到更優(yōu)的不可行解(sol3 或sol4)時(shí),同樣將當(dāng)前鄰域解的適應(yīng)度函數(shù)值更新給neibor_obj,然 后iteration 加1,neibor_num 加1,count_break也加1;當(dāng)上述4種鄰域解的情況均未出現(xiàn),即說(shuō)明本次鄰域搜索未找到任何更新解,只需將iteration加1,neibor_num 加1,count_break加1。在迭代過(guò)程中,鄰域搜索算子循環(huán)使用。判斷鄰域解是否需要擾動(dòng),如果count_break是參數(shù)Y的整數(shù)倍,則重置鄰域解目標(biāo)值為無(wú)窮大。直到迭代次數(shù)達(dá)到最大迭代次數(shù)或連續(xù)迭代結(jié)果未改善次數(shù)超過(guò)給定閾值,則終止算法,輸出結(jié)果。本文經(jīng)過(guò)計(jì)算后將最大迭代次數(shù)設(shè)置為2 000,連續(xù)迭代結(jié)果未改善次數(shù)閾值設(shè)置為400。

圖3 算法流程

3 算法驗(yàn)證及結(jié)果分析

TSSA 算法由Python 語(yǔ)言實(shí)現(xiàn),運(yùn)行環(huán)境為Intel(R)Core i3-8100@3.60 GHz CPU 及12 GB內(nèi)存的個(gè)人電腦,模型求解采用Gurobi優(yōu)化器,設(shè)置每個(gè)算例的最大計(jì)算時(shí)間為3 600 s。

3.1 VRPTW 計(jì)算分析

本算法設(shè)計(jì)針對(duì)M-PDPTWT,M-PDPTWT作為VRPTW 變體,在貨品的取送方式上更為復(fù)雜,但因其具有同樣的時(shí)間窗屬性,使得針對(duì)MPDPTWT 的兩階段搜索算法在修改適應(yīng)度函數(shù)和取送貨約束后,算法同樣適用于VRPTW。

算法中的兩個(gè)適應(yīng)度函數(shù)修改如下式所示,兩個(gè)適應(yīng)度函數(shù)中依次為運(yùn)輸成本、時(shí)間窗違背值、載重量違背值以及引導(dǎo)函數(shù),

式中,Tlv為車(chē)輛v總的載重量。

鄰域解中可能會(huì)出現(xiàn)Tlv＞Q的情況,即

式中,pi為每個(gè)顧客/門(mén)店需求的貨物量。

2.2.4 節(jié)中的參數(shù)Z用以界定兩個(gè)適應(yīng)度函數(shù),其取值會(huì)影響算法的收斂速度和可行解的求解質(zhì)量。表1給出了不同取值的Z所求得的算例結(jié)果,其中3個(gè)數(shù)據(jù)依次表示車(chē)輛數(shù)/距離/求解時(shí)間。

當(dāng)Z=0時(shí),表示算法沒(méi)有用適應(yīng)度函數(shù)f1(或f3)進(jìn)行評(píng)價(jià)。由表1 結(jié)果可見(jiàn),當(dāng)Z=0 時(shí),算法將以最快的速度收斂,但是不論是在車(chē)輛數(shù)的優(yōu)化還是距離的優(yōu)化上,求解結(jié)果都不如加入?yún)?shù)Z的求解結(jié)果好,證明了本算法設(shè)計(jì)先用f1(或f3)進(jìn)行評(píng)價(jià)再用f2(或f4)進(jìn)行評(píng)價(jià)的搜索方式是有效的。當(dāng)Z=10時(shí),算法的綜合性能保持得最好,在求解質(zhì)量和求解速度上都能找到一個(gè)平衡,故算法采用Z=10作為最優(yōu)參數(shù)。

表1 參數(shù)Z 的調(diào)試(100個(gè)門(mén)店部分?jǐn)?shù)據(jù))

附表1給出了TSSA 算法求解100 個(gè)門(mén)店的算例結(jié)果,同時(shí)給出了算例的最優(yōu)解和近年發(fā)表的一些啟發(fā)式算法的求解結(jié)果。計(jì)算結(jié)果表明,在大多數(shù)算例中,TSSA 算法都能找到最優(yōu)的求解路徑。

附表1 Solomon算例結(jié)果對(duì)比(100個(gè)顧客)

3.2 M-PDPTWT計(jì)算分析

采用某女鞋企業(yè)的銷(xiāo)售數(shù)據(jù)進(jìn)行算例設(shè)計(jì),公司提供了近兩年某城市包括倉(cāng)庫(kù)中心在內(nèi)的31個(gè)門(mén)店的銷(xiāo)售數(shù)據(jù),數(shù)據(jù)包括4個(gè)季節(jié)中不同品類(lèi)的女鞋樣式18種。算例按照每個(gè)月每種鞋的平均銷(xiāo)量作為該種鞋下一周的預(yù)期銷(xiāo)售量,低于平均值就需要補(bǔ)貨,高于平均值就需要運(yùn)走貨品。同時(shí),為了應(yīng)對(duì)未來(lái)城市規(guī)模的擴(kuò)張,將門(mén)店的數(shù)量增加到50個(gè),增加的門(mén)店位置在已有門(mén)店組成的地理位置網(wǎng)絡(luò)上隨機(jī)取點(diǎn),新增門(mén)店的銷(xiāo)售數(shù)據(jù)也通過(guò)隨機(jī)的方式產(chǎn)生。因此,采用門(mén)店數(shù)S={5,12,18,30,50},貨品數(shù)目C={2,3,6,10}組成18組,每組4個(gè)共計(jì)72個(gè)算例進(jìn)行算例測(cè)試。其中,算例時(shí)間窗為8:00～20:00,共計(jì)720 min,每個(gè)門(mén)店的時(shí)間窗按照間隔大于30 min(服務(wù)時(shí)間為30 min)進(jìn)行隨機(jī)生成。

表2中S為除去中心倉(cāng)庫(kù)外門(mén)店的數(shù)量,C為貨品的數(shù)量,NO 為算例序號(hào),每組4個(gè)。每組算例在兩階段搜索算法中計(jì)算10次,Best-TSSA 為10次計(jì)算中最好的值,Aver-TSSA 為10次計(jì)算的平均值,Gurobi為通過(guò)Gurobi優(yōu)化器求得的精確解,每一欄都包括車(chē)輛數(shù)(Veh)、距離(Dis)和計(jì)算時(shí)間(Time)。最后一欄為兩階段搜索算法的最好結(jié)果與Gurobi結(jié)果的差值。在用Gurobi優(yōu)化器求解模型時(shí),對(duì)兩個(gè)目標(biāo)函數(shù)設(shè)置不同的優(yōu)先級(jí)順序,具體的設(shè)計(jì)參數(shù)為:priorityobj1=0.9,priorityobj2=0.1。

表2 M-PDPTWT算例計(jì)算結(jié)果

續(xù)表2

由表2 計(jì)算結(jié)果可以看出,Gurobi在規(guī)定時(shí)間3 600 s內(nèi)計(jì)算出精確解的22個(gè)算例中,TSSA算法都能求解到相同的結(jié)果,證明了TSSA 算法的準(zhǔn)確性和數(shù)學(xué)模型的正確性。另外,有19個(gè)算例Gurobi能夠找到與TSSA 算法相同的車(chē)輛數(shù),但是在規(guī)定的時(shí)間內(nèi)無(wú)法求解到距離的最優(yōu)值;在剩下的31 個(gè)算例中,Gurobi無(wú)法找到與TSSA算法相同的車(chē)輛數(shù)和相同的距離值。在時(shí)間方面,Gurobi除了在小規(guī)模算例上(5個(gè)門(mén)店)花費(fèi)的時(shí)間優(yōu)于TSSA 算法,其余算例的計(jì)算時(shí)間都長(zhǎng)于TSSA 算法。TSSA 算法的平均計(jì)算時(shí)間隨著算例規(guī)模的增長(zhǎng)成比例增長(zhǎng),均保持在合理的計(jì)算時(shí)間范圍內(nèi)。

4 結(jié)語(yǔ)

本文針對(duì)某快時(shí)尚品調(diào)配貨品的實(shí)際問(wèn)題,結(jié)合問(wèn)題特性,將其歸類(lèi)為帶時(shí)間窗和調(diào)貨特性的多品類(lèi)取送貨問(wèn)題(M-PDPTWT)。以最小化車(chē)輛數(shù)為第一優(yōu)化目標(biāo),最小化配送成本為第二優(yōu)化目標(biāo),建立了完整的混合整數(shù)規(guī)劃模型。針對(duì)局部鄰域搜索算法很容易陷入局部最優(yōu)解這一缺點(diǎn),提出了利用不同的適應(yīng)度函數(shù)和不同的鄰域解評(píng)價(jià)對(duì)鄰域解進(jìn)行定量和定性的處理方式,在利于減少車(chē)輛數(shù)的第2階段和利于減少總距離的第3階段反復(fù)交替迭代中,實(shí)現(xiàn)了對(duì)最優(yōu)解的最大可能的尋找。將兩階段搜索算法用于求解Solomon算例的結(jié)果表明,兩階段搜索算法能求解到大部分與最優(yōu)解相同的最優(yōu)解。最后,根據(jù)企業(yè)提供的銷(xiāo)售數(shù)據(jù)設(shè)計(jì)了用于求解M-PDPTWT 問(wèn)題的測(cè)試算例,通過(guò)兩階段搜索算法與Gurobi求解的精確解對(duì)比發(fā)現(xiàn),兩階段搜索算法在小規(guī)模算例上都能找到與精確解相同的最優(yōu)解,在無(wú)法求解出精確解的較大規(guī)模算例上,兩階段搜索算法也能在較短時(shí)間求解出滿(mǎn)意的結(jié)果。因此,本文設(shè)計(jì)的兩階段搜索算法能夠滿(mǎn)足快時(shí)尚品企業(yè)對(duì)城市各個(gè)網(wǎng)點(diǎn)的調(diào)配需求,為企業(yè)提供滿(mǎn)足條件且運(yùn)輸成本最低的車(chē)輛行駛路徑。