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

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

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

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

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

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

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

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

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

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

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

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

(3)每個門店必須被訪問,且只能訪問一次。

1.2 符號說明及參數(shù)

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

其余符號

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

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

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

ei——門店i時間窗的最早達(dá)到時間,i∈N0,其中,e0=en+1表示倉庫的最早工作時間

li——門店i時間窗的最晚到達(dá)時間,i∈N0,其中,l0=ln+1表示倉庫的最晚工作時間

ω——倉庫的處理成本系數(shù)

Q——車輛的最大載容量

決策變量

1.3 模型建立

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

2 兩階段搜索算法

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

2.1 構(gòu)建初始解

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

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

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

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

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

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

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

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

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

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

式中:ra表示路徑r的第a個門店;cra,u+cu,ra+1-cra,ra+1表示將u點(diǎn)插入路徑r第a和第a+1個門店后該條路徑運(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)插入算子,是將一個點(diǎn)插入到其他路徑中;shift是指路徑內(nèi)將一個點(diǎn)插入到其他位置;cross 是指交換兩條路徑的后半段;exchange是指交換兩個點(diǎn),包括路徑間interexchange和路徑內(nèi)intro-exchange兩種情況。本文除了使用這5個操作算子,還使用了兩個擴(kuò)展操作算子和k-opt算子。

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

圖1 λ-inter-exchange

圖2 λ-intro-exchange

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 算法流程

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

圖3 算法流程

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

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

3.1 VRPTW 計(jì)算分析

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

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

式中,Tlv為車輛v總的載重量。

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

式中,pi為每個顧客/門店需求的貨物量。

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

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

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

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

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

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

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

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

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

續(xù)表2

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

4 結(jié)語

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