張曉楠，范厚明

(1.陜西科技大學(xué) 機(jī)電工程學(xué)院，陜西 西安 710021； 2.大連海事大學(xué) 交通運(yùn)輸工程學(xué)院，遼寧 大連 116026)

0 引言

車輛路徑問題(Vehicle Routing Problem, VRP)是運(yùn)籌學(xué)和組合優(yōu)化領(lǐng)域的熱點(diǎn)問題，為了使其更貼近實(shí)際，研究了VRP的各類擴(kuò)展問題[1]。模糊需求車輛路徑問題(VRP with Fuzzy Demands, VRPFD)是在VRP的基礎(chǔ)上考慮客戶需求符合模糊特征且確切需求信息往往在車輛到達(dá)客戶點(diǎn)時(shí)才能獲知的情況，在應(yīng)急物流、郵遞等領(lǐng)域具有應(yīng)用價(jià)值[2]。

兩階段法是求解VRPFD的常用方法，即在客戶需求未明情況下先設(shè)計(jì)一個(gè)預(yù)優(yōu)化方案，當(dāng)車輛按預(yù)優(yōu)化方案逐一到達(dá)客戶并獲知客戶的實(shí)際需求后，可能發(fā)生實(shí)際剩余車載量不足夠服務(wù)該客戶的情況，為避免預(yù)優(yōu)化路徑失敗，對(duì)車輛是否需要返回配送中心補(bǔ)貨進(jìn)行實(shí)時(shí)調(diào)整[3]。相關(guān)研究從兩方面進(jìn)行：①構(gòu)建預(yù)優(yōu)化模型，例如Teodorovic等[4]運(yùn)用模糊推理求解；Luci等[5]運(yùn)用模糊集合求解；張建勇等[6]運(yùn)用模糊可能性理論求解；曹二保等[7]運(yùn)用模糊可信性理論求解；王連峰等[8]為避免可信性理論中置信水平的影響，建立失敗事件的模糊期望值模型。②提出實(shí)時(shí)調(diào)整策略，Teodorovic等[4]提出一種基于失敗點(diǎn)返回的調(diào)整策略，以發(fā)貨為例，定義車輛按計(jì)劃路徑服務(wù)某一客戶j后的實(shí)際剩余車載量為Qj，當(dāng)Qj<0時(shí)標(biāo)記j點(diǎn)成為失敗點(diǎn)，車輛服務(wù)j點(diǎn)后返回配送中心補(bǔ)貨，再回到j(luò)點(diǎn)服務(wù)剩余需求，繼而服務(wù)剩余客戶；實(shí)際上，依據(jù)三角形三邊原理，在失敗點(diǎn)的前序點(diǎn)返回一定比在失敗點(diǎn)返回更優(yōu)，為此Yang等[9]以隨機(jī)需求VRP為例更改Qj<0的判斷，即當(dāng)Qj小于等于下一客戶需求期望值時(shí)，車輛立即返回配送中心補(bǔ)貨，但實(shí)驗(yàn)發(fā)現(xiàn)，該策略雖能降低失敗點(diǎn)出現(xiàn)的概率，卻可能增加不恰當(dāng)?shù)姆祷卮螖?shù)，造成運(yùn)力浪費(fèi)和成本增加；之后，張曉楠等[10]通過平衡失敗點(diǎn)出現(xiàn)概率和車輛返回次數(shù)提出“基于調(diào)整成本期望值”的實(shí)時(shí)調(diào)整策略用于調(diào)整VRPFD。

然而，無論構(gòu)建預(yù)優(yōu)化模型還是提出實(shí)時(shí)調(diào)整策略，現(xiàn)有研究均假設(shè)車輛在預(yù)優(yōu)化階段只能從配送中心出發(fā)一次，完成配送后回到配送中心，不允許中途返回補(bǔ)貨，而在實(shí)時(shí)調(diào)整階段卻允許車輛中途返回補(bǔ)貨后繼續(xù)服務(wù)。若定義車輛從配送中心出發(fā)后回到配送中心為一次行程，即預(yù)優(yōu)化階段的車輛單行程行駛方案可能會(huì)在實(shí)時(shí)調(diào)整階段調(diào)整為多行程行駛方案?，F(xiàn)實(shí)中的很多VRP存在允許車輛多行程行駛的情況，屬于多行程VRP(Multi-trip VRP, MVRP)范疇。目前一些學(xué)者已在靜態(tài)環(huán)境下證明多行程可有效減少車輛數(shù)量，降低發(fā)車成本，提高配送服務(wù)水平[11]。

為使VRPFD更貼近現(xiàn)實(shí)情況，獲取更優(yōu)的配送方案，本文基于前期文獻(xiàn)[10]，開放車輛行程限制，同時(shí)考慮客戶的時(shí)間窗偏好，研究帶時(shí)間窗偏好的多行程模糊需求車輛路徑問題(Multi-trip VRP with Fuzzy Demands considering Time Window preference, MVRPFDTW)，側(cè)重MVRPFDTW的預(yù)優(yōu)化模型構(gòu)建和實(shí)時(shí)調(diào)整策略提出。為簡化管理決策難度，確保司機(jī)對(duì)行駛路線和服務(wù)客戶的熟悉度，這里的實(shí)時(shí)調(diào)整策略同文獻(xiàn)[4,9-10]一樣，假設(shè)車輛不改變計(jì)劃方案安排好的客戶集合和服務(wù)順序。

相對(duì)于VRPFD，MVRPFDTW的求解存在以下難點(diǎn)：①車輛的計(jì)劃路徑可能包含多個(gè)起止于配送中心的單行程，每個(gè)客戶只能由一輛車的一個(gè)行程服務(wù)一次，且在每個(gè)行程開始時(shí)，車輛容量還原，時(shí)間花費(fèi)不還原；②對(duì)于包含多個(gè)行程的計(jì)劃路徑，在實(shí)時(shí)調(diào)整階段，如何看待這些已計(jì)劃好的返回點(diǎn)。③在考慮時(shí)間的前提下，車輛返回配送中心補(bǔ)貨可能同時(shí)導(dǎo)致配送長度增加和客戶到達(dá)時(shí)間延遲，因此實(shí)時(shí)調(diào)整成本不僅包括額外配送成本，還包括時(shí)間延遲成本。

1 問題描述及模型建立

1.1 問題描述

MVRPFDTW是在基本VRPFD基礎(chǔ)上開放車輛行程限制，同時(shí)考慮客戶時(shí)間窗偏好，解決的是確定一個(gè)滿足客戶模糊需求和時(shí)間窗偏好的車輛多行程計(jì)劃路線和實(shí)時(shí)調(diào)整方案，使物流成本最低且客戶總體滿意度最高。開放車輛行程限制可描述為允許車輛多行程行駛，定義車輛從配送中心出發(fā)返回配送中心為一次行程，每輛車僅有一條服務(wù)路線，每條服務(wù)路線可包含多個(gè)起止于配送中心的單行程，每個(gè)客戶只能由一輛車的一個(gè)行程服務(wù)一次?？蛻魰r(shí)間窗偏好可描述為客戶存在期望服務(wù)時(shí)間窗和最大容忍時(shí)間窗，在期望時(shí)間窗內(nèi)被服務(wù)的客戶滿意度為100%，隨著服務(wù)時(shí)間與期望服務(wù)時(shí)間窗差距的增大，客戶滿意度降低，不允許在最大容忍時(shí)間窗外服務(wù)客戶。

1.2 預(yù)優(yōu)化模型

為解決“在每個(gè)行程開始時(shí)，車輛容量還原，時(shí)間花費(fèi)不還原”的問題，模型添加決策變量的行程維度，令車輛容量按單行程核算，客戶到達(dá)時(shí)間按多行程累加計(jì)算。為保證客戶整體滿意度，同時(shí)有利于在后續(xù)實(shí)時(shí)調(diào)整階段核算時(shí)間延遲成本，定義客戶滿意度為到達(dá)時(shí)間隸屬度函數(shù)[12]，并設(shè)置目標(biāo)函數(shù)為最小化物流成本和時(shí)間成本的總和。

具體預(yù)優(yōu)化模型如下：

(1)

s.t.

(2)

?i∈V,?k∈K,?r∈R;

(3)

?k∈K,?r∈R;

(4)

(5)

(6)

(7)

(8)

?k∈K,?r∈R;

(9)

?k∈K,?r∈R;

(10)

(11)

?k∈K,?r∈R1;

(12)

(13)

?i∈V,j∈J,k∈K,r∈R;

(14)

yk∈{0,1},?k∈K;

(15)

(16)

(17)

(18)

1.3 實(shí)時(shí)調(diào)整策略

為解決“實(shí)時(shí)調(diào)整階段如何看待計(jì)劃路徑中的返回點(diǎn)”的問題，先列舉兩個(gè)簡單例子說明。

例1以圖1b中車輛1的可能計(jì)劃路徑為例(如圖3a)，設(shè)車輛容量限制CV=200，各點(diǎn)間距離和實(shí)際需求如表1所示?；谖墨I(xiàn)[4]的調(diào)整結(jié)果為圖3b，路徑長度為135；基于失敗點(diǎn)前序點(diǎn)返回的調(diào)整結(jié)果如圖3c所示，路徑長度為125，優(yōu)于圖3b，原因在于c34+c40>c30必定成立；另外，從圖3d所示的調(diào)整方案來看，路徑長度為115，優(yōu)于圖3c，原因在于該網(wǎng)絡(luò)中c23+c04>c20+c34。綜上認(rèn)為，“在失敗點(diǎn)的前序點(diǎn)返回”的調(diào)整策略優(yōu)于文獻(xiàn)[4]的失敗點(diǎn)調(diào)整策略，但仍未能實(shí)現(xiàn)最優(yōu)調(diào)整，“提前柔性選擇返回點(diǎn)”可能效果更好。

例2以圖1b中車輛2的計(jì)劃路徑為例(如圖4a)，各點(diǎn)間距離和實(shí)際需求如表2所示(列舉S1和S2兩種場景)。S1情況下，若固定計(jì)劃返回點(diǎn)，最優(yōu)

調(diào)整如圖4b所示，路徑長度為110，調(diào)整結(jié)果次于圖4c，路徑長度為104，原因在于c67+c08>c06+c78；S2情況下，若固定計(jì)劃返回點(diǎn)，則最優(yōu)調(diào)整如圖4d所示，路徑長度為110，調(diào)整結(jié)果次于圖4e，路徑長度為66，原因在于c07+c08>c78。綜上認(rèn)為，計(jì)劃的返回點(diǎn)可作為路徑調(diào)整的借鑒，但不應(yīng)完全局限和固定。

表1 各節(jié)點(diǎn)間距及客戶需求

節(jié)點(diǎn)012345需求Q13001230354080220120202530503203020010153042035251008605154030158070

表2 各節(jié)點(diǎn)間距及客戶需求

通過上述分析，本文基于以下兩個(gè)原則：①返回點(diǎn)應(yīng)根據(jù)情況柔性選擇，提前判斷，不一定是路徑失敗了才返回；②雖計(jì)劃路徑可能存在返回，但不應(yīng)完全局限和固定，應(yīng)適當(dāng)調(diào)整，甚至取消。針對(duì)上述原則，本文綜合考慮當(dāng)前實(shí)際剩余車載量和未服務(wù)客戶需求，以調(diào)整成本期望值衡量車輛是否返回補(bǔ)貨，設(shè)計(jì)如下實(shí)時(shí)調(diào)整策略：

以發(fā)貨為例，設(shè)車輛按計(jì)劃路徑服務(wù)某一客戶j后的實(shí)際剩余車載量為Qj，當(dāng)Qj>0時(shí)，決策者有兩種選擇,即直接服務(wù)下一客戶和返回補(bǔ)貨后再服務(wù)下一客戶。設(shè)車輛未服務(wù)客戶序列為{i,g,h,…}，方案選擇步驟如下：

(1)i點(diǎn)不失敗

(19)

(2)i點(diǎn)失敗

(20)

(1)g點(diǎn)不失敗

(21)

(2)g點(diǎn)失敗

(22)

逐一求解未服務(wù)客戶的成本期望值，則方案一的整體期望為Cost1=E(Fiti)+E(Fitg)+E(Fith)+…。

(1)i點(diǎn)不失敗

(23)

(2)i點(diǎn)失敗

(24)

步驟3比較Cost1和Cost2，選擇調(diào)整成本期望值較小的方案作為車輛在客戶j的策略選擇。

該策略的優(yōu)點(diǎn)是具有全局思想，可避免文獻(xiàn)[4]的盲目性，實(shí)現(xiàn)在不完全局限和固定計(jì)劃返回點(diǎn)的基礎(chǔ)下柔性選擇返回點(diǎn)，避免因某一局部調(diào)整影響整體最優(yōu)；缺點(diǎn)是車輛每到達(dá)一個(gè)節(jié)點(diǎn)都要判斷，耗時(shí)較長。其他特性將在3.2.4中討論。

2 種群進(jìn)化算法

本文求解涉及種群進(jìn)化算法和隨機(jī)模擬算法，種群進(jìn)化算法用以求解預(yù)優(yōu)化模型，隨機(jī)模擬算法用以模擬實(shí)時(shí)場景。由于隨機(jī)模擬算法在很多VRPFD中均有涉及[3]，這里僅介紹種群進(jìn)化算法，算法流程步驟與遺傳算法(Genetic Algorithm, GA)類似，不同的是將選擇、交叉、變異等遺傳操作更改為選擇、全局搜索和局部搜索。

2.1 解的編碼

2.2 初始種群

2.3 選擇操作

結(jié)合輪盤賭策略[6]和參考集更新策略[14]選擇,具體為：首先，采用文獻(xiàn)[14]的參考集更新策略對(duì)當(dāng)前種群構(gòu)建包含精英解集B1(解集規(guī)模|B1|)和多樣性解集B2(解集規(guī)模|B2|)的選擇池；然后，根據(jù)適應(yīng)度，采用輪盤賭策略從選擇池中選擇Psize個(gè)個(gè)體組成新種群。為保證多樣性解能在輪盤賭中被選擇，提高算法逃離局部最優(yōu)的能力，這里對(duì)精英解集和多樣性解集設(shè)計(jì)了如下不同適應(yīng)度計(jì)算方法：

(22)

(23)

式(22)為精英解的適應(yīng)度計(jì)算公式，式(23)為多樣性解的適應(yīng)度計(jì)算公式。式中：f為目標(biāo)函數(shù)，fmax，fmin為精英解集中目標(biāo)函數(shù)的最大值和最小值，系數(shù)α是避免目標(biāo)函數(shù)最大的解的適應(yīng)度為0，這里α=0.5；D為多樣性距離，Dmax，Dmin為多樣性解集中多樣性距離的最大值和最小值，系數(shù)β是避免多樣性距離最小的解適應(yīng)度為0，這里β=0.5。為使目標(biāo)函數(shù)最小解的適應(yīng)度高于多樣性距離最大解的適應(yīng)度，人為賦予多樣性解集的適應(yīng)度一個(gè)權(quán)重系數(shù)r,r=0.6。

2.4 全局搜索

采用單點(diǎn)交叉法更新被選中的新種群。以待交叉解X1和X2為例，隨機(jī)產(chǎn)生交叉點(diǎn)(σ,θ)，σ表示行交叉點(diǎn)，是取值為[1,min(N1,N2)]的隨機(jī)數(shù)，N1和N2為解X1和X2的實(shí)際使用車輛數(shù)；θ表示列交叉點(diǎn)，是取值為[1,min(find(X1(σ,:)～=0,find(X2(σ,:)～=0)]的隨機(jī)數(shù)。交叉方法為：保留X1中(σ,θ)之前的基因位，其余基因按X2的編碼順序刪除已服務(wù)客戶點(diǎn)，再依次復(fù)制到相應(yīng)位置，形成新解Y1；新解Y2類似。交叉后的解可以是不可行解，若屬于不可行解則在目標(biāo)函數(shù)中額外添加罰函數(shù)M。圖6所示為交叉操作的簡單例子。

2.5 局部搜索

針對(duì)全局搜索后的新種群，采用簡化的變鄰域搜索(Simplified Variable Neighborhood Search, SVNS)對(duì)每個(gè)個(gè)體進(jìn)行局部搜索，以提高解的質(zhì)量。SVNS是在VNS變更鄰域結(jié)構(gòu)時(shí)嚴(yán)格按照指定順序變更，不重復(fù)回到最初鄰域結(jié)構(gòu)再次搜索。這里采用弧交換(2-Opt)、客戶交換(1-1 Exchange)、客戶插入(0-1 Exchange)3種鄰域結(jié)構(gòu)，并依次變更。每種鄰域的終止條件為連續(xù)MAXCount次搜索到的最好解不變。流程如圖7所示。

為提高搜索效率，引入鄰域半徑減少策略(Neighborhood Size Reduction Scheme, NERS)[13]改進(jìn)上述結(jié)構(gòu)：每次鄰域操作均先任意選中某一客戶j，令avgj為j與其他所有客戶的距離平均值，meaj為j與配送中心和其他所有客戶的距離平均值，選擇滿足cji

2.6 精英保留策略

用當(dāng)前最好解替代新種群中的最差解，保證算法的收斂性。

2.7 終止條件

當(dāng)?shù)螖?shù)滿足最大迭代次數(shù)MaxN次時(shí)，算法終止。

3 算例分析

為驗(yàn)證模型和算法的有效性，本文采用兩類算例：標(biāo)準(zhǔn)算例驗(yàn)證種群進(jìn)化算法的求解性能；隨機(jī)算例驗(yàn)證預(yù)優(yōu)化模型和實(shí)時(shí)調(diào)整策略的有效性。

3.1 標(biāo)準(zhǔn)算例

因MVRPFDTW屬于VRPTW(vehicle routing problem with time window)的擴(kuò)展，取VRPTW標(biāo)準(zhǔn)算例測試。采用MATLAB 10.0編譯，在雙核奔騰2.9 GHz CPU、4 G內(nèi)存、Window 7 64位操作系統(tǒng)的PC機(jī)上運(yùn)行。

實(shí)驗(yàn)1采用文獻(xiàn)[15]中的無時(shí)間窗VRP算例進(jìn)行測試，問題規(guī)模為7，可用車輛數(shù)為3，車輛容量為1。設(shè)置算法參數(shù)Psize=10，|B1|=5，|B2|=2，MAXCount=10，MaxN=10，M=200，運(yùn)行結(jié)果與現(xiàn)有文獻(xiàn)比較，如表3所示。結(jié)果表明：本文算法同文獻(xiàn)[15]GA、文獻(xiàn)[16]粒子群優(yōu)化算法(Particle Swarm Optimization, PSO)均能搜索到最優(yōu)解217.81，但本文算法實(shí)驗(yàn)50次的搜索成功率為100%，且平均求解時(shí)間較短。

表3 無時(shí)間窗VRP的求解結(jié)果比較

實(shí)驗(yàn)2采用文獻(xiàn)[15]的軟時(shí)間窗VRPTW算例進(jìn)行測試。問題規(guī)模為8，可用車輛數(shù)為3，車輛容量為8，超出時(shí)間窗的單位懲罰為PE=PL=50。設(shè)置算法參數(shù)Psize=20，|B1|=10，|B2|=5，MAXCount=10，MaxN=20，M=800，運(yùn)行結(jié)果與現(xiàn)有文獻(xiàn)比較，如表4所示。結(jié)果表明：本文算法同文獻(xiàn)[15-18]均能搜索到最優(yōu)解910，但本文算法的搜索成功率為100%，明顯優(yōu)于文獻(xiàn)[15]GA的24%、文獻(xiàn)[16]PSO的46%、文獻(xiàn)[17]改進(jìn)PSO的97.4%、文獻(xiàn)[18]Memetic算法的96%，且求解時(shí)間更短，可見本文算法性能優(yōu)于文獻(xiàn)[15-18]的算法。

表4 軟時(shí)間窗VRPTW的求解結(jié)果比較

注：文獻(xiàn)[19]給出的QACA最優(yōu)解805，未包含時(shí)間懲罰費(fèi)用265。

實(shí)驗(yàn)3采用文獻(xiàn)[20]的帶時(shí)間窗VRPTW算例進(jìn)行測試，包括無時(shí)間窗VRP、軟時(shí)間窗VRPTW和硬時(shí)間窗VRPTW。問題規(guī)模為15，車輛容量為5，車速為1，忽略在送貨點(diǎn)卸貨的時(shí)間。其中，軟時(shí)間窗VRPTW的單位時(shí)間懲罰設(shè)置為a=b=20。設(shè)置算法參數(shù)Psize=20，|B1|=10，|B2|=5，MAXCount=10，MaxN=20，M=400，運(yùn)行結(jié)果與現(xiàn)有文獻(xiàn)比較，如表5所示。結(jié)果表明：本文算法求解無時(shí)間窗VRP的求解結(jié)果為509.86，軟時(shí)間窗VRPTW的求解結(jié)果為539.36，硬時(shí)間窗問題的求解結(jié)果為562.11，結(jié)果均優(yōu)于文獻(xiàn)[20]的禁忌搜索算法及文獻(xiàn)[21]的改進(jìn)蟻群算法，且求解時(shí)間較快，可見本文算法性能優(yōu)于文獻(xiàn)[20-21]的算法。

表5 帶時(shí)間窗VRPTW的求解結(jié)果比較

實(shí)驗(yàn)4采用文獻(xiàn)[22]的硬時(shí)間窗VRPTW算例進(jìn)行測試。問題規(guī)模為20，配送中心和客戶分布在一個(gè)邊長為200 km的正方形地域內(nèi)，配送中心坐標(biāo)為(145，130)，車輛載重量為8 t，平均行駛速度為60 km/h,不考慮卸貨時(shí)間。設(shè)置算法參數(shù)Psize=20，|B1|=10，|B2|=5，MAXCount=10，MaxN=50，M=1 000，運(yùn)行結(jié)果與現(xiàn)有文獻(xiàn)比較，如表6所示。結(jié)果表明：本文算法每次運(yùn)行都能找到問題最優(yōu)解1112.85，較文獻(xiàn)[21]的1 266.01和文獻(xiàn)[23]的1 249.27更優(yōu)，求解時(shí)間也在可接受范圍內(nèi)，可見本文算法性能優(yōu)于文獻(xiàn)[21，23]的算法。

表6 帶時(shí)間窗VRPTW的求解結(jié)果

注：文獻(xiàn)[22]給出的結(jié)果并不滿足客戶15的硬時(shí)間窗要求，會(huì)超出時(shí)間窗0.05。

實(shí)驗(yàn)5采用Solomon標(biāo)準(zhǔn)算例[24](http://www.sintef.no/Projectweb/TOP/VRPTW/solomon-benchmark/)進(jìn)行測試。該算例集屬于允許等待的硬時(shí)間窗VRPTW問題，共計(jì)56個(gè)算例，涉及的問題規(guī)模均為100，包括客戶點(diǎn)隨機(jī)分布(R類)、群集分布(C類)和群集-隨機(jī)分布(RC類)3個(gè)類別，且1類算例為緊時(shí)間窗約束、2類算例為松時(shí)間窗約束，車輛數(shù)最大均為25，車輛容量為200或1 000。這里取每類問題的第一個(gè)和最后一個(gè)算例求解，設(shè)置算法參數(shù)Psize=30～60，|B1|=10～30，|B2|=5～10，MAXCount=10，MaxN=100，M=400～1 500，不同算例的具體取值不同。運(yùn)行結(jié)果與現(xiàn)有文獻(xiàn)比較，如表7所示。結(jié)果表明：本文算法在7個(gè)算例中均能找到優(yōu)于文獻(xiàn)[21,25-27]的解，且平均誤差為1.50%，低于文獻(xiàn)[21]的10.19%、文獻(xiàn)[25]的7.59%、文獻(xiàn)[26]的1.79%和文獻(xiàn)[27]的3.22%。另外，本文算法的最大誤差為6.05%，誤差較小，可以接受，求解時(shí)間亦可以接受。可見，本文算法性能優(yōu)于文獻(xiàn)[21,25-27]的算法。

表7 允許等待的硬時(shí)間窗VRPTW的求解結(jié)果

綜合上述關(guān)于現(xiàn)有文獻(xiàn)的VRPTW標(biāo)準(zhǔn)算例測試及比較結(jié)果可以看出，本文算法尋優(yōu)能力強(qiáng)，求解精度高，求解時(shí)間可接受，是求解VRPTW問題的有效算法。

3.2 MVRPFDTW隨機(jī)算例

3.2.1 算例描述

表8 客戶信息表

3.2.2 算例求解

實(shí)驗(yàn)環(huán)境同標(biāo)準(zhǔn)算例相同，實(shí)驗(yàn)參數(shù)取Psize=20，|B1|=5，|B2|=5，MAXCount=10，MaxN=20，M=1 000。表9所示為算法求解預(yù)優(yōu)化模型的10次實(shí)驗(yàn)結(jié)果，平均求解時(shí)間為120 s，總成本均值為1 055.47，最大值為1 069.25，最小值為1 052.52，偏差在1.59%以內(nèi)，較小可以接受，且6次均能找到最優(yōu)解，說明本文算法求解質(zhì)量好，穩(wěn)定性高，能在可接受時(shí)間內(nèi)找到問題的最優(yōu)解。圖8所示為最優(yōu)計(jì)劃路徑圖，圖中共使用3輛車，車輛路徑為0-3-9-19-11-8-12-0-18-0、0-10-13-16-6-15-5-2-0和0-1-17-14-4-7-20-0。

表9 算例的10次預(yù)優(yōu)化結(jié)果

續(xù)表9

表10所示為最優(yōu)計(jì)劃路徑可能的調(diào)整路徑(以10 000次模擬的可能場景為例)，調(diào)整之后的配送成本實(shí)際耗費(fèi)1 063.54，調(diào)整成本為11.02。

表10 最優(yōu)計(jì)劃路徑的實(shí)時(shí)調(diào)整

從表10的詳細(xì)的調(diào)整路線來看：①該策略下失敗點(diǎn)出現(xiàn)的概率較小，車輛1為3.83%，車輛2為0.5%，車輛3為0.01%；②該策略不完全局限原計(jì)劃路徑的返回，能夠有效縮短配送長度，例如車輛1的計(jì)劃路線須在拜訪完客戶12后返回配送中心，而實(shí)際調(diào)整路線卻以83.78%的概率發(fā)生車輛無須在客戶點(diǎn)12返回配送中心補(bǔ)貨的情況。③該策略能柔性選擇合適的返回點(diǎn)，如車輛2出現(xiàn)路徑失敗時(shí)，調(diào)整方案出現(xiàn)了在失敗點(diǎn)前序點(diǎn)返回的方案0-10-13-16-6-15-5-0-2-0(配送成本777.17)，甚至找到在拜訪完客戶13即返回配送中心的更優(yōu)方案0-10-13-0-16-6-15-5-2-0(配送成本636.39)。綜上認(rèn)為，本文策略基本實(shí)現(xiàn)了設(shè)計(jì)前制定的兩大原則，策略合理有效。

3.2.3 多行程策略有效性分析

表11比較了允許/不允許車輛多行程的最優(yōu)計(jì)劃路徑，結(jié)果顯示：允許車輛多行程雖增加了時(shí)間成本，卻降低了車輛數(shù)和配送成本，總計(jì)劃成本更低。結(jié)合表10，允許車輛多行程的計(jì)劃路徑經(jīng)調(diào)整后的平均實(shí)際成本為1 063.54，低于不允許車輛多行程的計(jì)劃成本1 134.59，可見多行程策略在預(yù)優(yōu)化階段意義顯著。

表11 有無多行程策略的方案比較

續(xù)表11

為便于實(shí)際應(yīng)用，進(jìn)一步分析多行程策略的適用特性，表12～表15分別給出了偏好值α、服務(wù)水平β、車輛容量CV和派遣成本FV變動(dòng)的求解結(jié)果，可見：隨著偏好值α的增加(如α≥0.6)，最優(yōu)路徑方案出現(xiàn)車輛返程，因此多行程策略在偏好值較高(風(fēng)險(xiǎn)喜好程度較低)的VRP中意義顯著；隨著β的增加(如β≥0.8)，最優(yōu)路徑方案均未出現(xiàn)車輛返程，因此多行程策略在高服務(wù)水平(強(qiáng)時(shí)間窗約束)的VRP中意義較弱，而在低服務(wù)水平(弱時(shí)間窗約束)的VRP中意義顯著；隨著車輛容量的增加，最優(yōu)路徑方案中的車輛返程次數(shù)逐漸減少，因此多行程策略在有車輛容量限制的問題中適用于車輛容量約束較強(qiáng)的問題，如現(xiàn)實(shí)中的外賣配送服務(wù)；在車輛派遣費(fèi)用不高的情況下，車輛返程的意義不大，這是因?yàn)楫?dāng)車輛派遣費(fèi)用較少時(shí)，重新派遣一輛車服務(wù)客戶所增加的費(fèi)用不高，且不會(huì)因車輛返程造成后續(xù)客戶的時(shí)間費(fèi)用增加，因此多行程策略適用于車輛派遣費(fèi)用較高的VRP，如撒雪車、廢棄物回收車等專業(yè)車輛派遣，或車輛可用數(shù)量受限的配送。綜上可知，當(dāng)實(shí)際VRP中存在風(fēng)險(xiǎn)喜好程度較低、時(shí)間窗約束弱或車輛容量約束強(qiáng)，以及車輛派遣成本較高等特征時(shí)，多行程策略意義顯著，可有效提高配送效率。

表12 偏好值α變動(dòng)的求解結(jié)果(表中結(jié)果均為實(shí)驗(yàn)10次的平均結(jié)果)

表13 服務(wù)水平β變動(dòng)的求解結(jié)果(表中結(jié)果均為實(shí)驗(yàn)10次的平均結(jié)果)

表14 車輛容量CV變動(dòng)的求解結(jié)果(表中結(jié)果均為實(shí)驗(yàn)10次的平均結(jié)果)

續(xù)表14

表15 車輛派遣成本FV變動(dòng)的求解結(jié)果(表中結(jié)果均為實(shí)驗(yàn)10次的平均結(jié)果)

3.2.4 實(shí)時(shí)調(diào)整策略有效性分析

表16所示為本文實(shí)時(shí)調(diào)整策略與文獻(xiàn)[4](策略1)和文獻(xiàn)[9](策略2)的調(diào)整結(jié)果對(duì)比。結(jié)果顯示：①本文調(diào)整策略的失敗點(diǎn)出現(xiàn)概率相對(duì)于策略1和策略2有所減少(如表中加粗部分)，可見在“避免失敗點(diǎn)出現(xiàn)”方面，本文策略優(yōu)于策略1和策略2；②在策略1和策略2中，車輛1均以約95%的概率出現(xiàn)調(diào)整0-3-9-19-11-8-12-0-18-0，本文策略將該路徑出現(xiàn)概率降低至12.08%，出現(xiàn)約83%的更優(yōu)調(diào)整0-3-9-19-11-8-12-18-0，取消了計(jì)劃路徑中的返回(如表中下劃線部分)，因此，在“不應(yīng)完全局限和固定計(jì)劃返回點(diǎn)”方面，本文策略表現(xiàn)良好；③在策略1中，車輛2路徑失敗的調(diào)整路徑為0-10-13-16-6-15-5-2-0-2-0，導(dǎo)致實(shí)際配送成本為859.53，策略2能對(duì)部分失敗路徑進(jìn)行失敗點(diǎn)前序點(diǎn)返回的調(diào)整，即0-10-13-16-6-15-5-0-2-0，實(shí)際配送成本為777.16，而本文策略又對(duì)部分失敗路徑進(jìn)行更為合適的提前調(diào)整，如0-10-13-0-16-6-15-5-2-0，實(shí)際配送成本為636.39(如表中雙下劃線部分)，因此在“提前柔性選擇合適的返回點(diǎn)”方面，本文策略優(yōu)于策略1和策略2。綜上說明，相對(duì)于策略1和策略2，本文策略更能實(shí)現(xiàn)“避免失敗點(diǎn)出現(xiàn)、避免不必要返回和柔性選擇合適返回點(diǎn)”的原則。

表16 不同調(diào)整策略的實(shí)時(shí)調(diào)整結(jié)果

注：*表示3種策略中的最優(yōu)調(diào)整。

表17所示為不同偏好值α下的計(jì)劃路徑實(shí)時(shí)調(diào)整結(jié)果，BK為3種策略的實(shí)際成本最小值，偏差為各策略的實(shí)際成本與BK的偏差。結(jié)果顯示：本文策略總體偏差最小，僅為13.16，小于策略1的49.63和策略2的43.53，進(jìn)一步說明本文策略整體上較文獻(xiàn)[4,9]的策略更優(yōu)。詳細(xì)來看，當(dāng)α≥0.8時(shí)，本文策略明顯較優(yōu)，可見本文策略適用于決策者風(fēng)險(xiǎn)喜好程度較低(α≥0.8)的情況，結(jié)合表16，參數(shù)值取ε1:ε2=1較好；當(dāng)決策者風(fēng)險(xiǎn)喜好程度較高(α≤0.7)時(shí)，只需更改本文策略的“不固定計(jì)劃返回”為“固定計(jì)劃返回”，參數(shù)取值ε1:ε2≤1.1均優(yōu)于策略1的求解結(jié)果，其中當(dāng)0≤ε1:ε2≤0.8時(shí)和策略1結(jié)果相近，當(dāng)0.8≤ε1:ε2≤1.1時(shí)優(yōu)于策略1。表18所示為對(duì)表17中負(fù)調(diào)整成本的補(bǔ)充說明。

表17 不同偏好值α下最優(yōu)計(jì)劃路徑的實(shí)時(shí)調(diào)整結(jié)果

表18 α=1.0且β=0.6下最優(yōu)計(jì)劃路徑的實(shí)時(shí)調(diào)整

4 結(jié)束語

本文對(duì)MVRPFDTW的兩階段求解法進(jìn)行了研究。首先，在需求未明的預(yù)優(yōu)化階段，建立了以物流成本和時(shí)間成本總和最小為優(yōu)化目標(biāo)的預(yù)優(yōu)化模型，其中增加決策變量的行程維度，且車輛容量按單行程核算，客戶到達(dá)時(shí)間按多行程累加計(jì)算，另外客戶滿意度定義為到達(dá)時(shí)間隸屬度函數(shù)；其次，在已知實(shí)際需求的實(shí)時(shí)調(diào)整階段，基于“提前柔性選擇返回點(diǎn)”和“不完全局限和固定計(jì)劃返回點(diǎn)”兩個(gè)原則，提出一種基于調(diào)整成本期望值的實(shí)時(shí)調(diào)整策略；最后，設(shè)計(jì)了種群進(jìn)化算法求解預(yù)優(yōu)化模型，采用隨機(jī)模擬算法模擬實(shí)時(shí)場景。算例分析證明：①種群進(jìn)化算法性能表現(xiàn)良好，是求解這類問題的有效算法；②預(yù)優(yōu)化模型能獲得較優(yōu)的計(jì)劃方案，模型合理有效，且多行程策略在風(fēng)險(xiǎn)喜好程度較低、時(shí)間窗約束弱或車輛容量約束強(qiáng)，以及車輛派遣成本較高的VRP問題中效果顯著；③實(shí)時(shí)調(diào)整策略是個(gè)兼顧全局且風(fēng)險(xiǎn)適中的策略，能實(shí)現(xiàn)“避免失敗點(diǎn)出現(xiàn)、避免不必要返回和柔性選擇合適返回點(diǎn)”，策略靈活且合理有效。

未來可考慮進(jìn)一步開放“實(shí)時(shí)調(diào)整階段車輛不改變計(jì)劃方案安排好的客戶集合和服務(wù)順序”的限制，提出調(diào)整效果更好的實(shí)時(shí)調(diào)整策略。