混合啟發(fā)式算法求解多配送人員車輛路徑問(wèn)題

蘇欣欣， 王紅衛(wèi)， 秦 虎， 王 愷

(1.青島理工大學(xué) 管理工程學(xué)院,山東 青島 266000; 2.華中科技大學(xué) 管理學(xué)院,湖北 武漢 430074; 3.武漢大學(xué) 經(jīng)濟(jì)與管理學(xué)院,湖北 武漢 430000)

0 引言

帶時(shí)間窗和多配送人員的車輛路徑問(wèn)題(Vehicle Routing Problem with Time Windowsand Multiple Deliverymen, VRPTWMD)是Dantzig和Ramser[1]于1959年提出的車輛路徑問(wèn)題(Vehicle Routing Problem，VRP)的推廣。此問(wèn)題不但適用于貨物要求多個(gè)配送人員合作才能配送的情況，還適用于配送時(shí)間相對(duì)于行程時(shí)間較長(zhǎng)的情況。配送時(shí)間不但與貨物需求量有關(guān)而且與配送人員數(shù)目有關(guān)。因此，如何調(diào)節(jié)每輛車的配送人員數(shù)目和設(shè)計(jì)車輛行駛路線成為本文研究的主要問(wèn)題。

近年來(lái)，學(xué)者們對(duì)VRPTWMD進(jìn)行了一系列的研究。該問(wèn)題由Pureza，Morabito和Reimann[2]在2012年提出，他們指出此類問(wèn)題主要分為兩個(gè)決策問(wèn)題：(1)將顧客進(jìn)行區(qū)域劃分，同一區(qū)域的顧客共享一個(gè)停車場(chǎng)；(2)優(yōu)化路徑，車輛到達(dá)停車場(chǎng)后，配送人員服務(wù)該區(qū)域的全部顧客。該文假設(shè)區(qū)域劃分為已知，并提出禁忌搜索算法和蟻群算法求解該問(wèn)題。2016年, De Grancy和Reimann[3]分別基于蟻群算法和隨機(jī)自適應(yīng)搜索提出了兩種新的啟發(fā)式算法求解VRPTWMD。2018年，Munari和Morabito[4]提出分支定價(jià)割平面算法來(lái)求解該問(wèn)題。2015年，De Grancy[5]首次考慮區(qū)域劃分，解決完整的VRPTWMD，同時(shí)提出通過(guò)路徑的優(yōu)化方案來(lái)引導(dǎo)區(qū)域劃分的自適應(yīng)元啟發(fā)式算法。

對(duì)于啟發(fā)式算法，Luo等[6]提出了適應(yīng)性的彈射池與靈活多變的方法解決團(tuán)隊(duì)定向問(wèn)題。Hu和Lim[7]提出了迭代三分量啟發(fā)式算法求解帶時(shí)間窗的團(tuán)隊(duì)定向問(wèn)題。受以上論文的啟發(fā)，針對(duì)本文的VRPTWMD，我們提出了混合啟發(fā)式算法。通過(guò)與其他算法進(jìn)行比較，驗(yàn)證了該算法具有較強(qiáng)的全局尋優(yōu)能力和較高的搜索效率。

1 多配送人員的車輛路徑問(wèn)題

1.1 問(wèn)題描述

本文考慮的VRPTWMD通過(guò)調(diào)節(jié)每輛車的配送人員數(shù)目和設(shè)計(jì)車輛路線來(lái)滿足顧客對(duì)貨物和時(shí)間窗的要求。假設(shè)區(qū)域劃分為已知，不考慮顧客與停車場(chǎng)的距離，則顧客集合與對(duì)應(yīng)停車場(chǎng)可以看作是一個(gè)顧客。VRPTWMD的描述如下：1)車輛和配送人員從配送中心出發(fā)服務(wù)顧客，并最終返回配送中心；2)每個(gè)顧客最多被訪問(wèn)一次；3)顧客有嚴(yán)格規(guī)定的時(shí)間窗，包括最早開始服務(wù)時(shí)間和最晚完成時(shí)間。顧客的服務(wù)時(shí)間與需求量和配送人員數(shù)目有關(guān)。VRPTWMD的首要目標(biāo)是效益總值最大，次要目標(biāo)是行駛總距離最短。

1.2 模型構(gòu)建

模型參數(shù)：

K：配送中心的車輛集合；

V：所有點(diǎn)的集合，包括顧客和配送中心，V={0,1,…,n+1}；

C：顧客的集合，C={1,2,…,n}；

m：車輛關(guān)于人員的最大承載量；

L：車輛可能承載的配送人員數(shù)目的集合，L={1,2,…,m}；

m：配送中心的配送人員總數(shù)目；

Q：車輛關(guān)于貨物的最大承載量；

pi,i∈{0,1,…,n+1}：服務(wù)顧客獲得的效益值，假設(shè)p0=pn+1=0；

ei,i∈{0,1,…,n+1}：顧客的貨物需求量，假設(shè)c0=cn+1=0；

dij,i∈{0,1,…,n},j∈{1,2,…,n+1}：車輛在配送中心或顧客i與配送中心或顧客j之間的行駛時(shí)間，假設(shè)與行駛距離數(shù)值相等；

ai,i∈{0,1,…,n+1}：顧客i可接受服務(wù)的最早時(shí)間；

bi,i∈{0,1,…,n+1}：顧客i可接受完成服務(wù)的最晚時(shí)間；

w1,w2：每個(gè)目標(biāo)函數(shù)的權(quán)重，且w1>w2；

R：一個(gè)無(wú)限大的數(shù)。

決策變量：

此問(wèn)題的具體模型如下:

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

?k∈K,i∈C∪{0},j∈C∪{n+1}

(10)

(11)

(12)

(13)

其中，式(1)最大化兩個(gè)不同目標(biāo)的加權(quán)組合，即總效益值和總距離；式(2)和式(3)確保每條路徑的連續(xù)性；式(4)和式(5)確保每輛車從配送中心出發(fā)并最終返回配送中心；式(6)表示每輛車的載重約束；式(7)表示每輛車與承載的配送人員數(shù)目一一對(duì)應(yīng)；式(8)表示配送人員總數(shù)目的約束；式(9)表示每個(gè)顧客最多被訪問(wèn)一次；式(10)確保子回路消除；式(11)和式(12)確保服務(wù)的開始時(shí)間和完成時(shí)間均在時(shí)間窗內(nèi)；式(13)表示變量屬性。

2 混合啟發(fā)式算法

2.1 算法的主流程設(shè)計(jì)

混合啟發(fā)式算法首先生成L個(gè)初始解，然后將產(chǎn)生的解以路徑為單位分解并放入路徑庫(kù)，通過(guò)重組路徑庫(kù)中的路徑產(chǎn)生新的可行解，最后利用局部搜索算法和模擬退火算法分別產(chǎn)生鄰域解，更新全局最優(yōu)解和路徑庫(kù)。算法流程如圖1所示。

圖1 混合啟發(fā)式算法流程圖

2.2 初始解的生成

采用貪婪法生成初始解。首先所有路徑均為空路徑，每條路徑的配送人員數(shù)目隨機(jī)分配，打亂未被服務(wù)顧客的順序并放入unrouted集合中。按照從前至后的順序把unrouted集合中的顧客嘗試插入到路徑中，若滿足載重和時(shí)間窗的限制則進(jìn)行插入操作，直至所有顧客不能插入到任何路徑中為止，則一個(gè)初始解生成。

2.3 整數(shù)規(guī)劃重組

將路徑庫(kù)中的路徑進(jìn)行重組，需建立如下數(shù)學(xué)模型并定義模型參數(shù)：

qk：路徑k含有顧客的總效益值；

dk：路徑k的長(zhǎng)度；

nk：路徑k使用的配送人員數(shù)目；

S:路徑庫(kù)中含有路徑的總數(shù)目；

我們還需要定義模型決策變量：

則構(gòu)建的數(shù)學(xué)模型如下:

(14)

(18)

其中，式(14)表示最大化兩個(gè)不同目標(biāo)(效益總值和總距離)的加權(quán)組合；式(15)表示每個(gè)顧客最多被服務(wù)一次；式(16)表示車輛總數(shù)目的約束；式(17)表示配送人員總數(shù)目的約束；式(18)表示變量屬性。

根據(jù)上述數(shù)學(xué)模型，CPLEX將路徑進(jìn)行重組，并將得到的解記為S1。

2.4 局部搜索算法和模擬退火算法

局部搜索算法首先隨機(jī)選擇兩條路徑，分別增加一位配送人員和減少一位配送人員。隨后進(jìn)行鄰域操作，產(chǎn)生一個(gè)鄰域解。重復(fù)運(yùn)行L次，產(chǎn)生L個(gè)鄰域解。若超過(guò)已定的循環(huán)數(shù)目局部搜索未更新最優(yōu)解，則在下一次循環(huán)前對(duì)初始解進(jìn)行擾動(dòng)。若更新了最優(yōu)解，則也更新初始解。局部搜索算法產(chǎn)生的最優(yōu)解記為S2。

與局部搜索算法不同，若在模擬退火算法中更新了最優(yōu)解，則也更新初始解；否則，以一定的概率接受此解為初始解。模擬退火算法產(chǎn)生的最優(yōu)解記為S3。

局部搜索算法和模擬退火算法采用的鄰域操作有6個(gè)，如圖2所示。

圖2 鄰域操作示例圖

2.5 擾動(dòng)

隨機(jī)刪除顧客，若顧客的效益值大于平均值，以概率ph刪除；否則，以概率pl刪除，其中ph

3 實(shí)驗(yàn)結(jié)果及分析

3.1 算例說(shuō)明與參數(shù)設(shè)置

本文提出的混合啟發(fā)式算法使用Java語(yǔ)言編寫，運(yùn)行環(huán)境采用Intel(R) Core(TM) i7- 4790 CPU @ 3.60GHz(8.00 GB內(nèi)存)，整數(shù)規(guī)劃重組使用CPLEX(Studio1251)進(jìn)行求解。

參考蘇等[8]中對(duì)Solomon標(biāo)準(zhǔn)測(cè)試問(wèn)題[9]修改的過(guò)程，本文也進(jìn)行相同的修改。我們標(biāo)記每個(gè)算例為“P”+“name”，其中P是與原標(biāo)準(zhǔn)測(cè)試算例作區(qū)分，name是原標(biāo)準(zhǔn)測(cè)試算例的名稱。

經(jīng)過(guò)反復(fù)實(shí)驗(yàn)，混合啟發(fā)式算法的參數(shù)設(shè)定如表1，其中itermax表示最大循環(huán)數(shù)目；improveno表示最大未更新循環(huán)數(shù)目。

3.2 與CPLEX對(duì)比實(shí)驗(yàn)

為驗(yàn)證算法的求解精度和運(yùn)算效率，本文使用CPLEX(Studio1251)求解數(shù)學(xué)模型并用于實(shí)驗(yàn)對(duì)比。

表1 參數(shù)設(shè)置

在改造后的標(biāo)準(zhǔn)測(cè)試算例中隨機(jī)選取24個(gè)算例，且每個(gè)算例包含100個(gè)顧客。我們將其延伸為兩個(gè)小規(guī)模算例，分別包括25個(gè)顧客和50個(gè)顧客?；旌蠁l(fā)式算法運(yùn)行每個(gè)算例10次，求解結(jié)果的最大值表示為fbest，平均值表示為favg；CPLEX運(yùn)行每個(gè)算例一次，且限制運(yùn)行時(shí)間為7200s。為了評(píng)價(jià)混合啟發(fā)式算法的性能，我們使用最大值的相對(duì)誤差Gbest和平均值的相對(duì)誤差Gavg用于兩種算法的對(duì)比，表達(dá)式分別如下:

(19)

(20)

其中，BSK表示已知的最優(yōu)解。

針對(duì)25個(gè)顧客，2輛車，4個(gè)配送人員的小規(guī)模算例，求解結(jié)果如表2所示，加粗的結(jié)果代表混合啟發(fā)式算法取得的最大值與CPLEX的求解結(jié)果相同。從表2中可以看出，24個(gè)算例中只有9個(gè)算例CPLEX可以在7200s內(nèi)得出結(jié)果，其中5個(gè)算例混合啟發(fā)式算法得到的最大值與CPLEX得到的結(jié)果相同，其余算例的相對(duì)誤差可視為0.00%。對(duì)于運(yùn)算時(shí)間，9個(gè)算例中有7個(gè)算例的運(yùn)算時(shí)間均遠(yuǎn)小于CPLEX的運(yùn)算時(shí)間。因此混合啟發(fā)式算法具有準(zhǔn)確性和高效性。

針對(duì)50個(gè)顧客，3輛車，6個(gè)配送人員的小規(guī)模算例，由于篇幅限制我們并沒(méi)有將結(jié)果統(tǒng)計(jì)于表中。CPLEX只有PC106可以在7200s內(nèi)得出結(jié)果，而混合啟發(fā)式算法得到的最大值和平均值與CPLEX得到的結(jié)果相同，且運(yùn)算時(shí)間遠(yuǎn)小于CPLEX的運(yùn)算時(shí)間?；旌蠁l(fā)式算法的平均值相對(duì)誤差只有PR102平均值的相對(duì)誤差為0.07%，其余均為0.00%。因此混合啟發(fā)式算法具有穩(wěn)定性和有效性。

表2 小規(guī)模算例求解結(jié)果(25個(gè)顧客,2輛車,4個(gè)配送人員)

3.3 與已知算法對(duì)比實(shí)驗(yàn)

為了進(jìn)一步說(shuō)明混合啟發(fā)式算法的有效性, 本文與蘇等[8]提出的禁忌搜索算法進(jìn)行比較。針對(duì)24個(gè)標(biāo)準(zhǔn)規(guī)模測(cè)試算例，混合啟發(fā)式算法獨(dú)立運(yùn)行每個(gè)算例10次，且限定運(yùn)行時(shí)間為300s。將結(jié)果統(tǒng)計(jì)在表3，加粗的數(shù)據(jù)代表該算法可以得到更優(yōu)的結(jié)果。

對(duì)比最大值，24個(gè)算例中有7個(gè)算例混合啟發(fā)式算法得到的結(jié)果比禁忌搜索算法得到的結(jié)果好；只有2個(gè)算例混合啟發(fā)式算法得到的最大值比禁忌搜索算法得到的結(jié)果差，且相對(duì)誤差均在2%之內(nèi)。對(duì)比平均值，有13個(gè)算例混合啟發(fā)式算法得到的結(jié)果比禁忌搜索算法得到的結(jié)果好；只有1個(gè)算例混合啟發(fā)式算法得到的結(jié)果比禁忌搜索算法得到的結(jié)果差,且相對(duì)誤差為1.86%。由此說(shuō)明，混合啟發(fā)式算法相對(duì)禁忌搜索算法更穩(wěn)定，更準(zhǔn)確。

表3 標(biāo)準(zhǔn)規(guī)模算例求解結(jié)果(100個(gè)顧客, 5輛車, 9個(gè)配送人員)

4 結(jié)論

根據(jù)現(xiàn)實(shí)生活中的物流配送，本文對(duì)帶時(shí)間窗和多配送人員的車輛路徑問(wèn)題展開研究。該問(wèn)題考慮了配送人員數(shù)目對(duì)服務(wù)時(shí)間的影響，并且要求在時(shí)間窗內(nèi)完成配送的情況。本文提出的混合啟發(fā)式算法主要以整數(shù)規(guī)劃重組、局部搜索算法和模擬退火算法三部分為循環(huán)運(yùn)行。通過(guò)將混合啟發(fā)式算法與其他算法進(jìn)行對(duì)比，證實(shí)了該算法實(shí)用價(jià)值更高，求解效果更好。