張 強(qiáng)，姜慧清，王 穎，劉 馨

（東北石油大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院 黑龍江 大慶 163318）

帶模糊時(shí)間窗的多配送中心車輛路徑問(wèn)題（multi-depot vehicle routing problem with fuzzy time windows, MDVRPFTW）是經(jīng)典車輛路徑問(wèn)題（vehicle routing problem, VRP）的擴(kuò)展問(wèn)題之一，同樣屬于NP-hard 問(wèn)題。MDVRPFTW 主要是指配送中心數(shù)量為多個(gè)，模糊化處理開始服務(wù)時(shí)間窗，加入了客戶最大容忍時(shí)間窗，優(yōu)化目標(biāo)不僅有車輛配送的總成本，還有客戶對(duì)服務(wù)時(shí)間的滿意度。與傳統(tǒng)的車輛路徑問(wèn)題相比，MDVRPFTW 更貼合實(shí)際。隨著物流運(yùn)輸業(yè)的興起，車輛路徑問(wèn)題演化為多種類型，對(duì)于多配送中心車輛路徑問(wèn)題（multi-depot vehicle routing problem, MDVRP），學(xué)者們應(yīng)用不同的群智能算法尋找MDVRP 的近似最優(yōu)解。文獻(xiàn)[1]設(shè)計(jì)了一種改進(jìn)多蟻群算法來(lái)求解帶時(shí)間窗的半開放式MDVRP，引入2-opt 鄰域搜索算法更新可行解并作為初始解。文獻(xiàn)[2]設(shè)計(jì)一種混合遺傳算法，并提出一種自適應(yīng)搜索范圍策略，為求解聯(lián)合MDVRP提供一種新思路。文獻(xiàn)[3]針對(duì)MDVRP的4 個(gè)擴(kuò)展問(wèn)題，設(shè)計(jì)混沌遺傳變鄰域搜索算法、改進(jìn)的蟻群算法、兩階段禁忌搜索算法求解模型。文獻(xiàn)[4]針對(duì)帶軟時(shí)間窗的開放式MDVRP，提出了一種新改進(jìn)的離散螢火蟲算法。文獻(xiàn)[5]針對(duì)問(wèn)題和模型特點(diǎn)，設(shè)計(jì)了基于雙層編碼模式的改進(jìn)遺傳算法求解隨機(jī)需求下帶時(shí)間窗的動(dòng)態(tài)MDVRP。文獻(xiàn)[6]通過(guò)結(jié)合2-opt 局部?jī)?yōu)化算法的自適應(yīng)多態(tài)蟻群算法求解基于車輛共享的MDVRP。文獻(xiàn)[7]根據(jù)MDVRP 的具體特征，模擬狼群捕食行為并設(shè)計(jì)了求解該問(wèn)題的狼群算法。文獻(xiàn)[8]將基本的蟻群優(yōu)化與具有快速全局搜索能力的遺傳算法相結(jié)合，構(gòu)成一種混合自適應(yīng)蟻群優(yōu)化算法解決基于VIP 客戶的MDVRP。文獻(xiàn)[9]通過(guò)對(duì)遺傳算法改進(jìn)求解MDVRPTW，結(jié)果表明改進(jìn)的遺傳算法對(duì)求解此類優(yōu)化問(wèn)題有很大的提高。文獻(xiàn)[10]研究了一個(gè)多車場(chǎng)多配送中心半開放式滿載車輛路徑問(wèn)題，給出了該問(wèn)題的數(shù)學(xué)模型和求解算法。

多元宇宙優(yōu)化算法（multi-verse optimizer, MVO）是文獻(xiàn)[11]于2016 年設(shè)計(jì)的一種基于物理學(xué)中多元宇宙理論的群智能優(yōu)化算法。通過(guò)模擬白洞、黑洞和蟲洞之間的相互作用來(lái)完成尋優(yōu)過(guò)程的數(shù)學(xué)建模。由于該算法具有框架簡(jiǎn)單、易于理解、參數(shù)較少、性能穩(wěn)定、搜索效率高等優(yōu)點(diǎn)，受到關(guān)注。但傳統(tǒng)多元宇宙算法是針對(duì)連續(xù)問(wèn)題設(shè)計(jì)的，無(wú)法直接應(yīng)用于離散車輛路徑問(wèn)題。因此，本文提出一種離散多元宇宙算法，重新定義了對(duì)于離散車輛路徑問(wèn)題下的更新策略，尋找更優(yōu)解。

1 問(wèn)題描述及建模

1.1 問(wèn)題描述

模糊時(shí)間窗約束下多中心車輛路徑問(wèn)題可以描述為：擁有多個(gè)配送中心，車輛從配送中心出發(fā)，擁有客戶最大容忍時(shí)間窗，客戶點(diǎn)的需求量已知，需要合理的規(guī)劃路徑使目標(biāo)函數(shù)最優(yōu)。模糊時(shí)間窗約束下多中心車輛路徑問(wèn)題考慮如下假設(shè)：1） 配送中心到客戶節(jié)點(diǎn)距離以及客戶點(diǎn)之間的距離是已知的；2） 配送車輛必須以所屬配送中心為起始點(diǎn)，任務(wù)完成后以所屬配送中心為返回點(diǎn)；3） 每輛車可以對(duì)多個(gè)客戶節(jié)點(diǎn)進(jìn)行服務(wù)，但每個(gè)客戶節(jié)點(diǎn)有且僅有一輛車為其服務(wù)；4） 物流配送中心和客戶節(jié)點(diǎn)之間以及客戶節(jié)點(diǎn)之間都是可以連通的道路；5） 客戶節(jié)點(diǎn)貨物需求量小于配送車輛的最大承載量。6） 配送路徑數(shù)不能大于配送中心配送車輛總數(shù)；7） 配送車輛的到達(dá)時(shí)間不能早于和晚于客戶最大容忍時(shí)間窗。

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

在MDVRPFTW 中，P={1,2,···,p}為配送中心的集合；N={1,2,···,n}為所有客戶節(jié)點(diǎn)的集合；Kp為 配送中心p的車輛數(shù)；Ktotal為 車輛總數(shù)；qi為客戶節(jié)點(diǎn)i的貨物需求量，i∈N；Q為配送車輛的最大容量；c1為單個(gè)配送車輛完成配送任務(wù)的固定費(fèi)用；c2為 單位距離的行駛成本；c3為由于客戶不滿意帶來(lái)的業(yè)務(wù)損失成本；di j為節(jié)點(diǎn)i到 節(jié)點(diǎn)j之間的距離；Si為 開始服務(wù)時(shí)間；Kpm為配送中心p參與配送車輛數(shù)。本文采用的模糊時(shí)間窗[12][EET, ET,LT, ELT]相應(yīng)隸屬函數(shù)圖像如圖1 所示。

圖1 梯形模糊時(shí)間窗隸屬函數(shù)

多配送中心情況下的客戶滿意度函數(shù)[13]可把客戶i對(duì)配送服務(wù)的滿意度定義為其服務(wù)開始時(shí)間的隸屬度函數(shù)：

其中，式（2）表示目標(biāo)函數(shù)是配送總成本的最小化；式（3）表示平均顧客滿意度的最大化；式（4）表示總的優(yōu)化目標(biāo)為配送總成本最小化與客戶不滿意度最小化的和；式（5）表示車輛k的載重量不允許超過(guò)該車輛的額定載重量；式（6）表示每一個(gè)顧客點(diǎn)都被服務(wù)到且只被服務(wù)一次；式（7）表示使用的車輛總數(shù)不超過(guò)配送系統(tǒng)中所擁有的車輛數(shù)；式（8）表示車輛服務(wù)完客戶后，必須返回其所出發(fā)的配送中心；式（9）表示決策變量為0-1 變量。

2 離散多元宇宙算法

2.1 標(biāo)準(zhǔn)多元宇宙算法

多元宇宙算法[14]是2016 年提出的一種新型智能優(yōu)化算法。而MVO 算法主要是模擬多元宇宙的種群在黑洞、白洞和蟲洞共同作用下的運(yùn)動(dòng)行為。與其他算法相比，MVO 算法主要分為探測(cè)和開采兩個(gè)階段。多元宇宙?zhèn)€體的位置由內(nèi)部物體的運(yùn)動(dòng)改變。構(gòu)建數(shù)學(xué)模型時(shí)，一個(gè)宇宙被視為優(yōu)化問(wèn)題的一個(gè)解，每個(gè)宇宙中的物體可作為相應(yīng)解的分量。定義單個(gè)宇宙的膨脹率為候選解的適應(yīng)度值。宇宙膨脹率，即適應(yīng)度的計(jì)算方法在不同問(wèn)題中有不同的定義，在本文MDVRPFTW 中，適應(yīng)度函數(shù)定義為總成本函數(shù)式（4）的倒數(shù)。

初始化宇宙種群U，公式如下：

式中，r1為 [0, 1]范圍內(nèi)隨機(jī)數(shù)；xkj表示通過(guò)輪盤賭選擇出來(lái)的第k個(gè)宇宙的第j個(gè)分量； NI(Ui)表示第i個(gè)宇宙的歸一化膨脹率。白洞/黑洞轉(zhuǎn)移是將物體從高膨脹率的宇宙發(fā)送到低膨脹率的宇宙中。因此在整個(gè)迭代過(guò)程中，宇宙種群的平均膨脹率會(huì)不斷提高。

為了保證宇宙種群的多樣性和改進(jìn)宇宙?zhèn)€體自身膨脹率，宇宙?zhèn)€體會(huì)通過(guò)蟲洞和最優(yōu)宇宙之間進(jìn)行物質(zhì)傳輸，公式如下：

式中，L為最大迭代次數(shù)；l為當(dāng)前迭代次數(shù)；WEPmin= 0.2； WEPmax= 1；p為開發(fā)準(zhǔn)確性，值為6。WEP 在迭代過(guò)程中線性增大，保證了在迭代后期進(jìn)行更多的開采。TDR 在迭代過(guò)程中非線性減小，減小速率先快后慢。這是因?yàn)榈捌谶x出最優(yōu)宇宙的適應(yīng)度不高，需要用更大的移動(dòng)距離來(lái)加快開采速度，而在迭代后期，最優(yōu)宇宙具有較高的適應(yīng)度，所以需要減小移動(dòng)距離來(lái)增加開采的精度。

2.2 多元宇宙算法離散化

標(biāo)準(zhǔn)多元宇宙算法只適用于在連續(xù)的解空間中尋優(yōu)。但VRP 的解空間是離散的，需要將MVO進(jìn)行離散化，使其適用于求解車輛路徑問(wèn)題。

2.2.1 編碼與解碼

應(yīng)用多元宇宙求解MDVRPFTW 時(shí)，每個(gè)宇宙代表了一種配送方案，宇宙中的分量代表節(jié)點(diǎn)的編號(hào)?？蛻酎c(diǎn)、配送中心和車輛等節(jié)點(diǎn)的編號(hào)是離散且唯一的，為了便于理解和表示，用連續(xù)的自然數(shù)對(duì)節(jié)點(diǎn)進(jìn)行編號(hào)。假設(shè)有n個(gè)配送中心，每個(gè)配送中心有ki輛車，客戶數(shù)為m。具體編碼解碼規(guī)則如下：

首先為所有節(jié)點(diǎn)進(jìn)行編號(hào)。配送中心的編號(hào)從0 開始到n-1 結(jié)束。符號(hào)0 即代表第一個(gè)配送中心；配送車輛節(jié)點(diǎn)的編號(hào)從n開始到n+（k0+···+kn-1）-1 結(jié)束。隸屬于第一個(gè)配送中心的車輛的編號(hào)從n開始到n+k0-1 結(jié)束，以此類推；客戶點(diǎn)編號(hào)從n+（k0+···+kn-1）開始到n+（k0+···+kn-1）+m-1 結(jié)束。每個(gè)解中只包含車輛節(jié)點(diǎn)和客戶節(jié)點(diǎn)，即解的長(zhǎng)度由配送車輛總數(shù)和客戶點(diǎn)總數(shù)確定。然后先將配送車輛隨機(jī)排列，再把客戶點(diǎn)隨機(jī)插入形成一個(gè)初始解。配送車i的配送路徑中包含的客戶點(diǎn)為配送車i與 配送車i-1 之間的所有客戶點(diǎn)，并在客戶點(diǎn)兩端加上配送車i所屬的配送中心編號(hào)構(gòu)成完整配送路徑，配送順序即客戶點(diǎn)排列順序。例如有n=2，k=2，k=2，m=7，則初始編碼為：

其中編號(hào)為2,3 的配送車輛屬于0 號(hào)配送中心，編號(hào)為4,5 的配送車輛屬于1 號(hào)配送中心。隨機(jī)順序?yàn)椋?/p>

則所有配送路徑為：{0, 8, 10, 11, 12, 0}, {1, 6,1}, {1, 7, 9, 1}。

通過(guò)配送車輛的編號(hào)可推出所屬的配送中心，配送車輛在解中的位置可推出該配送車的配送路徑，所以目標(biāo)函數(shù)值的計(jì)算不會(huì)受亂序的影響。同時(shí)每一輛配送車輛的配送路徑由一段連續(xù)片段指定，給鄰域搜索策略的設(shè)計(jì)提供了思路。

2.2.2 位置更新策略

1） 白洞/黑洞轉(zhuǎn)移

在標(biāo)準(zhǔn)多元宇宙算法中，對(duì)于Ui的 第j個(gè)分量，如果隨機(jī)數(shù)r1小 于Ui的歸一化膨脹率，則用Uk的 第j個(gè)分量取代Ui的 第j個(gè)分量。但這種更新方式在車輛路徑問(wèn)題中會(huì)使更新后的解不合法，因?yàn)楣?jié)點(diǎn)編號(hào)是唯一的。對(duì)于離散車輛路徑問(wèn)題，在Ui的 第j個(gè)分量更新后，需要與對(duì)應(yīng)的分量進(jìn)行交換，以保證解的合法性，具體操作如下：

在標(biāo)準(zhǔn)多元宇宙中，通過(guò)向最優(yōu)宇宙移動(dòng)來(lái)保持群多樣性和激發(fā)每個(gè)宇宙的膨脹率。但標(biāo)準(zhǔn)多元宇宙中的移動(dòng)距離為實(shí)數(shù)，不適用于車輛路徑問(wèn)題。所以將移動(dòng)距離取整。如果Ui的 第j個(gè)分量更新后的值超出了最大節(jié)點(diǎn)編號(hào)，則將其置為最大節(jié)點(diǎn)編號(hào)。為了保證解的合法性，需要在更新后對(duì)解進(jìn)行調(diào)整。離散后的向最優(yōu)宇宙移動(dòng)公式如下：

2） 向最優(yōu)宇宙移動(dòng)

2.3 改進(jìn)策略

2.3.1 原子操作

首先定義宇宙交換物體的原子操作。無(wú)論是白洞黑洞轉(zhuǎn)移還是向最優(yōu)宇宙移動(dòng)，都是基于原子操作。本文將原子操作分為3 種：交換、插入和反轉(zhuǎn)。

1）交換操作

2.3.3 向最優(yōu)宇宙移動(dòng)重定義

其中{8, 10, 11, 12}是編號(hào)為3 的配送車的配送路徑。

2.4 算法步驟

1） 初始化多元宇宙種群，初始化 WEPmin、WEPmax、 開發(fā)精度p、 最大迭代次數(shù)M axIter、當(dāng)前迭代次數(shù)C urIter等參數(shù)；

2） 計(jì)算每個(gè)宇宙?zhèn)€體的適應(yīng)度，宇宙?zhèn)€體歸一化膨脹率 NI(U)，用輪盤賭機(jī)制選擇一個(gè)宇宙?zhèn)€體Uk；

7） 如果達(dá)到最大迭代次數(shù)，輸出最優(yōu)解，算法結(jié)束；否則，返回步驟2）。

3 實(shí)驗(yàn)與分析

本文使用Solomon 數(shù)據(jù)集[15]對(duì)標(biāo)準(zhǔn)多元宇宙算法（MVO）、鯨魚算法（whale optimization algorithm,WOA）[16]、海鷗算法（seagull optimization algorithm,SOA）[17]、粒子群算法（particle swarm optimization,PSO）[18]、飛 蛾 撲 火 算 法（moth-flame optimization,MFO）[19]、灰 狼 優(yōu) 化 算 法（grey wolf optimization,GWO）[20]以及本文提出的離散多元宇宙算法（discrete multi-verse optimizer, DMVO）進(jìn)行了對(duì)比實(shí)驗(yàn)。由于Solomon 標(biāo)準(zhǔn)數(shù)據(jù)集的時(shí)間窗為硬時(shí)間窗且只有一個(gè)配送中心，所以對(duì)Solomon 數(shù)據(jù)集進(jìn)行了擴(kuò)展。配送中心數(shù)目增加至3，另新增了左、右容忍時(shí)間窗。考慮到顧客對(duì)于不同貨物的期望服務(wù)時(shí)間窗不同，其最大容忍程度也不盡相同，設(shè)置顧客可提前接受服務(wù)的時(shí)間窗 [EETi,ETi)和顧客可延遲接受服務(wù)的時(shí)間窗 (LTi,ELTi]分別為顧客期望接受服務(wù)的時(shí)間窗 [ ETi,LTi]的一半，能更加客觀地描述實(shí)際顧客的等待情況。容忍時(shí)間窗按如下公式得出：

式中，EET 為左容忍時(shí)間窗；ELT 為右容忍時(shí)間窗；ET 為左時(shí)間窗；LT 為右時(shí)間窗。

實(shí)驗(yàn)中的最大迭代次數(shù)為2 000，種群數(shù)量為300。表1 為各個(gè)算法在Solomon 數(shù)據(jù)集上的總成本對(duì)比結(jié)果?？偝杀緸楣潭ǔ杀?、距離成本與時(shí)間懲罰成本之和。為了避免不同初始化對(duì)算法造成的影響，隨機(jī)生成了10 組初始種群，取10 組數(shù)據(jù)的平均值作為對(duì)比結(jié)果。

表1 實(shí)驗(yàn)結(jié)果

通過(guò)表1 結(jié)果可以看出，改進(jìn)后的離散多元宇宙算法在求解帶模糊時(shí)間窗的多配送中心車輛路徑問(wèn)題時(shí)，與MVO 相比結(jié)果更優(yōu)。而MVO 總成本普遍優(yōu)于PSO、SOA、WOA、GWO 和MFO 算法。為了直觀地展示迭代過(guò)程中成本的變化情況，下面以Solomon 數(shù)據(jù)集中的C101、C102、R205、R207、RC202、RC208 為例，展示總成本和用戶滿意度在迭代過(guò)程中的變化曲線圖。

通過(guò)圖2～圖13 可以看出，總成本和客戶滿意度隨著迭代次數(shù)的增加都在不斷得到優(yōu)化。由于在迭代過(guò)程中要綜合考慮成本與客戶滿意度，導(dǎo)致圖像曲線出現(xiàn)波動(dòng)。但隨著迭代次數(shù)的增加，結(jié)果達(dá)到平衡，整體損失趨于收斂。

圖2 C101 總成本迭代圖

圖3 C102 總成本迭代圖

圖4 R205 總成本迭代圖

圖5 R207 總成本迭代圖

圖6 RC202 總成本迭代圖

圖7 RC208 總成本迭代圖

圖8 C101 滿意度迭代圖

圖9 C102 滿意度迭代圖

圖10 R205 滿意度迭代圖

圖11 R207 滿意度迭代圖

圖12 RC202 滿意度迭代圖

圖13 RC208 滿意度迭代圖

DMVO 與MVO 相比，在迭代前期收斂速度略低。這是因?yàn)閷?duì)于求解MDVRPFTW，MVO 算法在向最優(yōu)宇宙移動(dòng)時(shí)，Ui的 第j個(gè)分量有可能變?yōu)槿我环至?。而改進(jìn)后的DMVO 在向最優(yōu)宇宙移動(dòng)時(shí)，分量變化被限定在某個(gè)配送車的配送路徑中，相當(dāng)于在最優(yōu)宇宙的鄰域進(jìn)行搜索。在迭代前

期，隨機(jī)搜索有助于MVO 可以快速跳出局部最優(yōu)，收斂較快。而改進(jìn)后的DMVO 由于前期的最優(yōu)宇宙的適應(yīng)度不高，在其鄰域難以搜索到更優(yōu)解，導(dǎo)致收斂較慢。但隨著迭代進(jìn)行，最優(yōu)宇宙的適應(yīng)度逐漸提高，最優(yōu)宇宙鄰域搜索的優(yōu)勢(shì)逐漸大于隨機(jī)搜索，所以改進(jìn)后的DMVO 具有更強(qiáng)的尋優(yōu)能力。

為了確定不同配送中心數(shù)目和客戶節(jié)點(diǎn)數(shù)對(duì)各個(gè)算法的影響，將Solomon 數(shù)據(jù)集進(jìn)一步擴(kuò)展，生成了一組新數(shù)據(jù)集。新數(shù)據(jù)集的配送中心數(shù)目和客戶節(jié)點(diǎn)數(shù)分別為（3, 50）、（3, 80）、（3, 200）、（1, 100）、（5, 100）、（10, 100）。以C101，C201，R201，R202，RC208 為例，各算法在新數(shù)據(jù)集上的對(duì)比結(jié)果如下。

通過(guò)表2 和表3 可以看出，在不同配送中心數(shù)目和不同客戶節(jié)點(diǎn)數(shù)目的情況下，改進(jìn)后的離散多元宇宙算法的尋優(yōu)能力都優(yōu)于標(biāo)準(zhǔn)MVO、PSO、SOA、WOA、GWO 和MFO 等算法，證明了DMVO在求解MDVRPFTW 問(wèn)題時(shí)具有很好的魯棒性。

表2 不同客戶點(diǎn)實(shí)驗(yàn)結(jié)果

表3 不同配送中心實(shí)驗(yàn)結(jié)果

4 結(jié) 束 語(yǔ)

本文在解決模糊時(shí)間窗約束下的多配送中心車輛路徑問(wèn)題時(shí)，以總成本最低、顧客滿意度最大為多目標(biāo)函數(shù)，構(gòu)建出相應(yīng)的模型。將連續(xù)多元宇宙進(jìn)行了離散化，并改進(jìn)了多元宇宙的更新策略。通過(guò)離散多元宇宙算法來(lái)求解Solomon 數(shù)據(jù)集中部分算例，更具有參考價(jià)值。而對(duì)于車輛路徑問(wèn)題，仍然有很多不確定因素，接下來(lái)將繼續(xù)研究多元宇宙算法在其他車輛路徑問(wèn)題上的應(yīng)用。