帶時間窗偏好的多行程模糊需求車輛路徑優(yōu)化

張曉楠，范厚明

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

0 引言

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

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

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

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

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

1 問題描述及模型建立

1.1 問題描述

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

1.2 預優(yōu)化模型

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

具體預優(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 實時調整策略

為解決“實時調整階段如何看待計劃路徑中的返回點”的問題，先列舉兩個簡單例子說明。

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

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

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

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

節(jié)點012345需求Q13001230354080220120202530503203020010153042035251008605154030158070

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

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

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

(1)i點不失敗

(19)

(2)i點失敗

(20)

(1)g點不失敗

(21)

(2)g點失敗

(22)

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

(1)i點不失敗

(23)

(2)i點失敗

(24)

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

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

2 種群進化算法

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

2.1 解的編碼

2.2 初始種群

2.3 選擇操作

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

(22)

(23)

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

2.4 全局搜索

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

2.5 局部搜索

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

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

2.6 精英保留策略

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

2.7 終止條件

當迭代次數滿足最大迭代次數MaxN次時，算法終止。

3 算例分析

為驗證模型和算法的有效性，本文采用兩類算例：標準算例驗證種群進化算法的求解性能；隨機算例驗證預優(yōu)化模型和實時調整策略的有效性。

3.1 標準算例

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

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

表3 無時間窗VRP的求解結果比較

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

表4 軟時間窗VRPTW的求解結果比較

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

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

表5 帶時間窗VRPTW的求解結果比較

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

表6 帶時間窗VRPTW的求解結果

注：文獻[22]給出的結果并不滿足客戶15的硬時間窗要求，會超出時間窗0.05。

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

表7 允許等待的硬時間窗VRPTW的求解結果

綜合上述關于現有文獻的VRPTW標準算例測試及比較結果可以看出，本文算法尋優(yōu)能力強，求解精度高，求解時間可接受，是求解VRPTW問題的有效算法。

3.2 MVRPFDTW隨機算例

3.2.1 算例描述

表8 客戶信息表

3.2.2 算例求解

實驗環(huán)境同標準算例相同，實驗參數取Psize=20，|B1|=5，|B2|=5，MAXCount=10，MaxN=20，M=1 000。表9所示為算法求解預優(yōu)化模型的10次實驗結果，平均求解時間為120 s，總成本均值為1 055.47，最大值為1 069.25，最小值為1 052.52，偏差在1.59%以內，較小可以接受，且6次均能找到最優(yōu)解，說明本文算法求解質量好，穩(wěn)定性高，能在可接受時間內找到問題的最優(yōu)解。圖8所示為最優(yōu)計劃路徑圖，圖中共使用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ōu)化結果

續(xù)表9

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

表10 最優(yōu)計劃路徑的實時調整

從表10的詳細的調整路線來看：①該策略下失敗點出現的概率較小，車輛1為3.83%，車輛2為0.5%，車輛3為0.01%；②該策略不完全局限原計劃路徑的返回，能夠有效縮短配送長度，例如車輛1的計劃路線須在拜訪完客戶12后返回配送中心，而實際調整路線卻以83.78%的概率發(fā)生車輛無須在客戶點12返回配送中心補貨的情況。③該策略能柔性選擇合適的返回點，如車輛2出現路徑失敗時，調整方案出現了在失敗點前序點返回的方案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)。綜上認為，本文策略基本實現了設計前制定的兩大原則，策略合理有效。

3.2.3 多行程策略有效性分析

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

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

續(xù)表11

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

表12 偏好值α變動的求解結果(表中結果均為實驗10次的平均結果)

表13 服務水平β變動的求解結果(表中結果均為實驗10次的平均結果)

表14 車輛容量CV變動的求解結果(表中結果均為實驗10次的平均結果)

續(xù)表14

表15 車輛派遣成本FV變動的求解結果(表中結果均為實驗10次的平均結果)

3.2.4 實時調整策略有效性分析

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

表16 不同調整策略的實時調整結果

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

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

表17 不同偏好值α下最優(yōu)計劃路徑的實時調整結果

表18 α=1.0且β=0.6下最優(yōu)計劃路徑的實時調整

4 結束語

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

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