時變路網下帶混合時間窗的車輛路徑問題

范厚明，孫秀娜，張躍光，任曉雪，田攀俊

大連海事大學 交通運輸工程學院，遼寧 大連 116026

時變路網下帶混合時間窗的車輛路徑問題（vehicle routing problem with mixed time windows under timedependent network，VRPMTWTDN）是綜合考慮多中心聯合配送、混合時間窗及車輛行駛速度隨時間連續變化的VRP（vehicle routing problem）拓展問題。現實中，物流企業的多個配送中心共同為客戶提供配送服務，并根據客戶對貨物送達時間的不同要求，將客戶收貨時間約束分為硬時間窗約束和軟時間窗約束。如京東推出的“京準達”服務、天貓推出的基于門店的“定時送”服務及哈根達斯的哈根速遞等，在客戶下單時能預約精準收貨時間段，企業須在該時間窗內將貨物送到達；未預約精準收貨時間段的客戶允許配送時間存在一定偏差。同時，路網交通流量的時空差異使得配送車輛的行駛速度不斷變化，對貨物的送達時間產生一定影響。因此，時變路網下帶混合時間窗的多中心車輛路徑問題貼近實際配送生產活動，具有重要的理論與應用價值。

VRPMTWTDN 是對多中心車輛路徑問題（multidepot vehicle routing problem，MDVRP）、時間依賴型車輛路徑問題（time-dependent vehicle routing problem，TDVRP）、帶混合時間窗的車輛路徑問題（vehicle routing problem with mixed time windows，VRPMTW）的集成問題，已有很多學者對MDVRP、TDVRP 及VRPMTW展開了研究。

針對MDVRP，范厚明等[1]針對多中心聯合配送模式下集貨需求隨機的同時配集貨VRP建立兩階段優化模型，并改進變鄰域文化基因算法進行求解。Zhang等[2]針對MDVRP，以碳排放量最小為目標建立兩階段優化模型，并設計改進蟻群算法進行求解。Zhen等[3]針對帶有時間窗的多行程MDVRP，以配送時長最小為目標建立優化模型，并設計混合粒子群優化算法和混合遺傳算法進行求解。Li 等[4]針對MDVRP，以收益最大和配送成本、時間及碳排放量最小為目標建立優化模型，并設計改進蟻群優化算法進行求解。

針對TDVRP，范厚明等[5]考慮客戶需求模糊及車輛行駛時間依賴路網速度變化特征，提出時變路網下多車型動態VRP，建立兩階段優化模型，并設計自適應大規模鄰域搜索算法進行求解。Ehmke等[6]考慮車輛行駛速度隨時間變化及車輛行駛速度等對油耗的影響，以碳排放量最小為目標建立優化模型，并設計禁忌搜索算法進行求解。Alinaghian 等[7]考慮車輛行駛速度的時間依賴性及車輛行駛速度、載重量、道路坡度對車輛油耗的影響，以油耗量最小為目標建立TDVRP優化模型，并設計改進高斯螢火蟲算法進行求解。張凱慶等[8]考慮軟時間窗約束和車輛速度隨時間變化情況，建立以平均客戶滿意度最大、配送距離及成本最小為目標的優化模型，并設計兩階段算法進行求解。Maha 等[9]考慮車輛行駛速度在路網中不同路段的差異性，建立帶時間窗的VRP優化模型，并設計禁忌搜索算法進行求解。付朝暉等[10]針對生鮮電商末端配送問題，考慮生鮮農產品送達客戶時的鮮活度及城市路網交通狀況的時變性等因素，以總配送成本最小為目標建立TDVRP 優化模型，并設計改進蟻群算法進行求解。

針對VRPMTW，Wang 等[11]針對冷鏈車輛配送問題，考慮混合時間窗及碳交易政策中的碳價格和交易配額設置對模型求解的影響，以成本最小、碳排放量最小和客戶總滿意度最大為目標建立優化模型，并設計自適應遺傳算法進行求解。Wang 等[12]考慮混合時間窗約束，以配送成本和派遣車輛數最小為目標建立多目標優化模型，并將智能水滴算法與遺傳算法相結合進行求解。王勇等[13]針對VRPMTW，將客戶重要度與時間窗相結合，建立雙層數學模型，并將遺傳算法與禁忌搜索算法相結合進行求解。鄒宗峰等[14]以運輸風險、時間窗懲罰成本、交通狀況、道路能力、運輸時間最優為目標建立VRPMTW優化模型，并設計多目標遺傳算法進行求解。

通過梳理以上相關文獻可見，目前還沒有針對VRPMTWTDN 的研究成果，且MDVRP、TDVRP 及VRPMTW的研究還存在以下不足：（1）現有針對TDVRP的研究多以階梯分段函數表示全天道路車輛速度變化情況，未考慮車輛行駛速度的連續變化。（2）現有考慮車輛行駛速度連續變化的研究多假設車輛單位距離的油耗是固定的，鮮有考慮車速、載重量等對油耗的影響。（3）現有關于帶時間窗的車輛路徑問題的文獻，多數單獨考慮軟時間窗或硬時間窗，較少研究VRPMTW。針對以上不足，本文綜合考慮多中心聯合配送，不同客戶對服務時間的需求差異，車輛行駛速度隨時間連續變化以及車速、載重量對油耗的影響，對VRPMTWTDN展開研究。

1 問題分析

1.1 問題描述

由配送區域路網構成完備的有向圖G=(V,E)中，節點集合為V=V0?V1?V2，其中V0={1,2,…,m} 為配送中心集合，V1為未預約精準收貨時間段的客戶集合，V2為預約精準收貨時間段的客戶集合；E={(i,j)|i,j∈V,i≠j}為邊集合，各配送中心間無路徑連接，lij為i、j兩節點之間的距離，tij為車輛在i、j兩節點之間的行駛時間；K為所有配送中心的車輛集合，車型相同，最大載重量為Q,Ki(i∈V0)為各配送中心i(i∈V0)的車輛集合，k為配送車輛集合K中任意一輛車，Sk為車輛k服務的客戶集合，Fijk為車輛k在i、j兩節點之間的燃油消耗量，燃油價格為c1，單位車輛的派遣成本為c2；車輛行駛速度v={v1,v2,…,vl}是連續變化的；車輛k從配送中心i出發的時刻為Tik，到達節點i的時刻為，對客戶i的開始服務時刻為，車輛完成所有配送任務后在各配送中心車輛數守恒原則下就近返回任一配送中心；客戶i的需求量為di，單位貨物裝卸時間為δ,配送中心有統一的工作時間窗[Ts,Tf],[ETi,LTi]為預約精準收貨時間段客戶i(i∈V2)的時間窗，車輛須在該時間窗內為客戶i提供服務[ETi,LTi]為未預約精準收貨時間段客戶i(i∈V1)的期望服務時間窗，[EETi,ELTi](EETi≤ETi≤LTi≤ELTi)為其最大容忍時間窗，車輛須在[EETi,ELTi]內為客戶i提供服務，在[EETi,ETi] 到達的單位懲罰成本為c3,在[LTi,ELTi] 到達的單位懲罰成本為；決策變量xijk表示車輛k是否從點i到達點j，是為1，否為0。

圖1為研究問題的示意圖，配送區域有2 個配送中心、25個客戶，每個配送中心擁有若干車輛。根據現有客戶位置及時間窗進行優化得到圖1所示的5條配送路徑，其中車輛1、車輛3 和車輛5 均返回原配送中心，車輛2和車輛4返回就近的配送中心。

圖1 研究問題的示意圖Fig.1 Schematic diagram of research problem

1.2 速度時間依賴函數的確定

現有對TDVRP 的研究，多以階梯分段函數表示路段的車輛行駛速度，在某一時間節點速度突變，不能很好地刻畫高峰時段配送區域路網對車輛行駛速度的限制，不符合現實中車輛行駛速度連續變化的特點。鑒于此，本文參考文獻[15]，以多項式函數表示車輛行駛速度隨時間的連續變化，如圖2所示。

圖2 車輛速度時間依賴函數Fig.2 Vehicle speed-time dependence function

1.3 車輛油耗計算

車輛油耗量取決于車輛行駛時間、行駛速度、車型和道路狀況等因素，本文借鑒文獻[16]研究結果，考慮車速、載重量對油耗的影響，建立油耗計算模型。

行駛時間dt內的燃油消耗量dfij為：

式中，U(v(t))是空載車輛的燃油消耗率，單位是L/km。

U(v(t))與空載車速之間的關系為：

式中，α、β、θ和ω由道路和車輛狀況決定。

空載車輛k在路段(i,j)上的燃油消耗量fijk為：

式中，Tl ik為車輛k離開i點時刻，Ta jk為車輛k到達j點時刻。

假設油耗增量與車輛載重增量呈線性關系[21]，載重每增加L，油耗增加s（百分比），則載重量為Qik的車輛k在路段(i,j)上的油耗Fijk為：

2 模型建立

式（1）為目標函數式，第一部分為油耗成本，第二部分為車輛派遣成本，第三部分為時間窗懲罰成本；式（2）表示車輛的載重限制；式（3）表示各客戶點車輛進出平衡，且客戶只能被服務一次；式（4）表示各配送中心出發和返回的車輛數一致，且不超過其最大車輛數；式（5）表示各車輛須在配送中心工作截止時間前返回配送中心；式（6）和式（7）為車輛對客戶i開始服務時刻的約束；式（8）為車輛從節點i出發到達節點j時刻的計算方法，其中M為無窮大值；式（9）為消除子回路約束；式（10）為決策變量屬性。

3 算法設計

本文所提問題考慮多中心聯合配送、混合時間窗及車輛行駛速度連續變化等因素對配送方案制定的影響，屬于NP-hard問題，求解過程復雜，用精確算法求解較為困難，因此考慮采用啟發式方法進行求解。遺傳算法（genetic algorithm，GA）具有快速隨機的全局搜索能力，可同時對搜索空間中的多個可行解進行評估，但搜索具有盲目性，在求解到一定范圍時常做大量無為冗余迭代，使求解效率低；大規模鄰域搜索算法既能保持大規模鄰域的尋優能力，又能克服低效的弱點，從而提高算法的求解能力。本文根據VRPMTWTDN 模型特點，將傳統遺傳算法與大規模鄰域搜索算法相結合，設計自適應遺傳-大鄰域搜索算法（adaptive genetic algorithm with large neighborhood search，AGA-LNS）進行求解。

自適應遺傳-大鄰域搜索算法相比于傳統遺傳算法，通過大規模鄰域搜索提高尋優能力，改進的交叉變異算子對可行解不斷進行優化，且以最優個體持續未改變代數作為迭代停止的判斷依據，避免做大量無為冗余迭代，提高求解效率；相比于傳統鄰域搜索，既能保持大規模鄰域的尋優能力，又能克服低效的弱點，局部最優解的質量更好，但迭代耗時較長。自適應遺傳-大鄰域搜索算法早期尋優主要依靠遺傳算法的全局搜索能力和大鄰域算法的局部搜索能力，通過改進的交叉操作和變異操作可以快速接近全局最優解；后期尋優主要依靠大鄰域搜索算法的局部搜索能力，通過移除-插入操作對當前最優解進行摧毀和重建，有利于算法跳出局部最優解，彌補了遺傳算法后期收斂速度慢，容易造成冗余迭代的缺點。遺傳算法與大鄰域搜索算法相結合可以有效平衡算法的局部尋優能力和全局尋優能力，具有較強的求解性能。

自適應遺傳-大鄰域搜索算法流程如圖3所示。

圖3 AGA-LNS流程圖Fig.3 Flow chart of AGA-LNS

3.1 初始解的構造

初始解的質量很大程度上影響著算法的求解質量和求解效率，若隨機生成初始種群，極易產生大量無效個體，增加收斂代數。為提高可行解的生成概率，采用整數編碼方式，設計“先客戶后中心”的兩階段方法生成初始解。首先進行客戶點分組并確定服務順序，然后確定發車時間和返回的配送中心及到達各節點的具體時刻。此方式可保證生成的初始種群均為可行解，且具有一定隨機性，增加了初始種群的多樣性和有效性，避免過早陷入局部最優。具體步驟如下：

階段1 客戶點分組并確定服務順序。

步驟1 隨機派遣一輛車，用虛擬配送中心0表示其出發的配送中心，根據客戶允許的最早開始服務時刻由早到晚對所有未服務的客戶進行排序，并從前n個客戶中隨機選取一個作為新派車輛服務的第一個客戶并將其插入到當前路徑。

步驟2 求出從當前客戶出發到所有未服務客戶的到達時刻并判斷其是否在該客戶時間窗內，從到達時刻在客戶時間窗內的所有客戶集合中選擇開始服務時刻最小的客戶插入到路徑，若所有客戶的到達時刻都早于其時間窗開始時刻，則選擇到達時刻距其時間窗開始時刻最近的客戶插入到當前路徑。重復以上操作，直至車載量、未服務客戶的時間窗或返回配送中心時刻中任一約束不滿足，則新派一輛車。

步驟3 重復步驟1 和步驟2，直至所有客戶的配送任務安排完畢。

階段2 確定車輛出發和返回的配送中心及到達各節點的具體時刻。

步驟4 替換車輛出發和返回的虛擬配送中心0：計算每條路徑首尾客戶距離各配送中心的距離，依次選擇與各路徑首個客戶距離最小的配送中心替換車輛出發的虛擬配送中心0，若所選配送中心無可派遣車輛，則選擇距離次近的配送中心，直至替換完畢；然后依次選擇與各路徑末尾客戶距離最小的配送中心替換車輛返回的虛擬配送中心0，若所選配送中心不滿足車輛守恒，則選擇距離次近的配送中心，直至替換完畢。以各車輛服務的首個客戶的時間窗開始時刻作為其到達該客戶點的時刻，計算車輛從配送中心的出發時刻、到各客戶點的服務時刻及返回配送中心的時刻。

圖4 為染色體編解碼過程示意圖，以10 個客戶（編號為1～10）和2個配送中心（編號為11～12）為例，按照上述步驟生成初始解。首先在染色體起始位置插入車輛起始虛擬配送中心0，再將所有客戶按最早開始服務時刻由早到晚排序，從前5 個客戶中隨機選取客戶3 作為車輛服務的首個客戶，再計算從客戶3到所有未服務客戶的到達時刻，選出最佳后續客戶1 插入到路徑中，按照相同方法選出后續客戶2、5，直至不滿足任一約束時，車輛返回虛擬配送中心0。以此類推，劃分后的路徑如圖4（a）所示，再根據步驟4 所述操作先后確定車輛出發、返回的配送中心替換虛擬配送中心0，得到初始解如圖4（c）所示。

圖4 染色體解碼示意圖Fig.4 Chromosome decoding diagram

3.2 進化操作

進化操作首先進行基于時差插入法的自適應交叉變異，然后通過成對的移除、插入算子將路徑中的客戶按照一定規則移除，再將被移除的客戶按照一定規則插入到路徑。由于每一次交叉、變異操作或插入-移除操作都可能減少染色體中的車輛數，每次進化操作后按照3.1節中步驟4描述的方法重新確定車輛出發和返回的配送中心。

3.2.1 時差插入法

客戶m插入到客戶i和客戶j之間的時間約束條件為：車輛在客戶m的開始服務時刻不晚于客戶m容忍的最晚接受時刻Tm；插入客戶m后，車輛到達客戶j的時刻不晚于客戶j的最晚開始時刻。插入的時間約束如下：

式中，車輛在客戶m的最早完成時刻EFm和最晚開始時刻LSm計算方法如式（12）、（13）所示，其中客戶i為客戶m的前序客戶，客戶j為客戶m的后序客戶。

時差插入法的具體步驟如下：

步驟1 計算所有客戶的最早完成時刻和最晚開始時刻。

步驟2 按照時間約束確定客戶m可插入的位置，并計算假設插入客戶m后各位置的目標增量。

步驟3 選擇目標增量最小的位置插入客戶m，若所有位置均不滿足插入條件，則新派遣一輛車。

步驟4 更新所有客戶的最早完成時刻和最晚開始時刻。

步驟5 重復上述操作，直至所有待插入客戶全部插入路徑中。

3.2.2 交叉算子和變異算子

交叉變異概率值的設定對解的尋優過程有很大影響，傳統遺傳算法的交叉概率和變異概率根據經驗和主觀判斷設置為定值，若設置較小，則會使個體進化速度較慢，增加算法的求解時間，若設置較大，則容易在算法求解后期破壞優秀個體，使算法陷入局部最優解。為提升算法的性能，參考文獻[17]設置自適應交叉變異概率，相比于常規交叉變異概率，自適應交叉、變異可以根據每次迭代所得新個體的適應度值適應性地調整交叉、變異概率，在進化前期以較大的交叉變異概率加速個體進化，增加解的多樣性，避免過早陷入局部最優，在進化后期交叉變異概率逐漸減小，避免破壞優秀個體。自適應交叉、變異概率計算方法如式（14）、（15）所示。

式中，Pc_max、Pm_max分別是交叉概率區間和變異概率區間的最大值，Pc_min、Pm_min分別是交叉概率區間和變異概率區間的最小值，f為個體適應度值，其大小為目標函數值的倒數，f′為進行交叉父本中最優個體的適應度值，fmax為所有個體適應度值中的最大值，favg為所有個體的平均適應度值。

考慮車輛的服務時刻不能違反硬時間窗客戶的時間要求，若按傳統交叉變異進行操作，則會破壞原有可行解，產生大量不可行解，對此，在交叉算子和變異算子中引入時差插入法，以客戶的時間窗約束作為種群優化的前提條件，保證每次迭代后均生成可行解，提高可行解的生成率，進而提高求解質量。其中交叉操作對兩個父代個體進行部分交換后保留較優解，提高種群多樣性，變異操作可減少個體中子路徑的數量，即減少配送方案中派遣的車輛數，有利于提高求解質量，降低配送成本。

（1）交叉操作：在兩個父代染色體中分別隨機選取一條子路徑并進行交換，再對交換后的染色體進行修復。首先刪除因交換導致重復的客戶，然后在滿足車輛載重等約束的基礎上，通過時差插入法插入因交換路徑導致染色體中缺失的客戶。以圖5為例，將父代染色體a中子路徑11—1—7—4—10—11與b中子路徑11—9—8—10—12 進行交換得到a1 和b1，刪除a1 中重復客戶8、9及b1中重復客戶1、7、4得到a2和b2，再通過時差插入法將a2 中缺失的客戶1、7、4 插入a2 中、將b2 中缺失的客戶8、9插入b2中得到a3、b3。

（2）變異操作：在父代染色體中隨機刪除客戶數最少的子路徑，然后在滿足所有約束的前提下采用時差插入法重新插入刪除的客戶。以圖6 為例，刪除染色體a中包含客戶數最少的一條子路徑13—6—8—12得到a1，再采用時差插入法將客戶節點6、8重新插入得到a2。

3.2.3 移除算子和插入算子

每次迭代時，在交叉變異后引入基于時差插入法的移除算子和插入算子進行種群優化。先通過移除算子刪除當前解中的μ 個客戶，再通過插入算子將刪除的客戶重新插入構造新解。在每次迭代中多次使用移除-插入組合算子對可行解進行摧毀和重建，可以增加解的多樣性，擴大搜索范圍，提高算法的全局尋優能力。移除算子和插入算子如下：

（1）移除算子

①隨機移除算子：隨機移除當前解中的μ 個客戶。

②最遠距離移除算子：計算當前解中所有客戶的距離成本，移除距離成本D(m) 最大的客戶m ，其中m 的前序客戶，j 為m 的后序客戶。具體操作如圖7所示，圖中D1、D2 代表配送中心，其余為客戶點，箭頭上的數值為節點間的距離。

③最遠偏離客戶中心移除算子：移除每輛車服務的客戶集合中與其他所有客戶的中心點距離最遠的客戶，即移除客戶位置偏差D(j)最大的客戶。客戶j 的位置偏差為為客戶j的位置坐標，(X,Y)為一輛車服務的除客戶j 外其他所有客戶的中心點坐標。

（2）插入算子

①貪婪插入算子：在滿足所有約束的基礎上采用時差插入法找出客戶m 的可插入位置，計算插入距離成本C(m)，并將客戶m 插入C(m)最小的位置，其中C(m)=dim+dmj-dij,i 為插入位置的前序客戶，j 為插入位置的后序客戶。

②最好時間插入算子：在滿足所有約束的基礎上采用時差插入法找出客戶m 的可插入位置，并計算其時間偏差量BT(m)，并將客戶m 插入BT(m)最小的位置，其中

3.2.4 迭代終止條件

當最優個體持續未改變的代數達到最優個體持續未改變的最大代數MAXGEN 時停止迭代，輸出結果。

4 算法驗證與算例分析

4.1 算子的選擇

移除和插入算子是成對出現的，為確定不同算子求解的有效性，采用Cordeau 標準算例庫中MDVRPTW（multi-depot vehicle routing problem with time windows）標準算例對交叉、變異算子和6組移除-插入算子進行測試，各算子求解各算例所得結果的平均值如表1 所示。其中Ai(i=1,2,3)表示三種移除算子，Bi(i=1,2)表示兩種插入算子，BKS為標準算例庫中已知最優解，Avg為各算子求解所有算例所得結果的平均值，GAP為Avg與BKS的誤差。由表1 可知，交叉算子的求解性能最好，平均誤差為4.1%，其次為變異算子，平均誤差為4.6%，移除-插入算子組合中，隨機移除算子和貪婪插入算子組合求解性能最好，平均誤差為12.3%，其次是最遠距離移除算子和貪婪插入算子的組合，平均誤差為32.1%。為保證求解質量及求解速度，選取以上兩種移除-插入算子組合應用于算法中進行可行解的摧毀和重建。

表1 算子測試結果Table 1 Test results of operators

4.2 算法驗證

4.2.1 算法測試

目前沒有VRPMTWTDN 的標準算例庫，選擇MDVRPTW測試AGA-LNS的性能。采用MATLAB R2018b進行算法編程，操作系統為Windows10，電腦內存為8 GB，CPU 為Intel i7-7700M，主頻3.60 GHz。設置種群規模NIND為100，MAXGEN為30～50。

選擇Cordeau 標準算例庫中MDVRPTW 的20 個算例測試AGA-LNS，表2給出了禁忌搜索算法（tabu search，TS）[18]、變鄰域搜索算法（variable neighborhood search，VNS）[19]、基于復合鄰域的離散螢火蟲算法（discrete firefly algorithm with compound neighborhoods，DFACN）[20]、混合遺傳算法（hybrid genetic algorithm，HGA）[21]及AGA-LNS 的求解結果。其中N為客戶規模，M為配送中心數，K為配送中心最大車輛數，Q為車輛最大載量，BKS為標準算例庫中已知最優解，C為算法求解的最優值，GAP為算法求得結果與BKS的相對誤差，t為算法運行10 次的平均耗時。由表2 可知，在求解質量方面，AGA-LNS 求得的最優值與BKS的最小誤差為-3.36%，最大誤差為4.39%，當客戶規模增大時，相對誤差有所增大。AGA-LNS的求解結果優于TS和VNS，略差于DFACN和HGA，求解耗時小于HGA。通過對比分析運算結果，可驗證AGA-LNS的有效性。

表2 算法測試結果Table 2 Algorithm test results

4.2.2 交叉變異概率分析

為驗證自適應交叉變異概率相比于常規交叉變異概率的優越性，設置三種交叉概率0.40、0.65、0.90，三種變異概率0.02、0.11、0.20，采用Cordeau標準算例庫中前10 個MDVRPTW 標準算例對九種概率組合進行測試，并與本文自適應交叉變異概率下算例的求解結果進行對比，如表3所示。其中C為運用自適應交叉變異概率求得的最優解，Avg為所有算例最優解的平均值，GAP為Avg與C平均值的相對誤差。由表3 可知，九種交叉變異概率組合中，交叉、變異概率分別為0.65、0.20時求解結果最優，但與自適應交叉變異概率下的求解結果相比仍相差1.20%，可見運用自適應交叉變異概率進行求解相比于常規交叉變異概率更有優越性。

表3 不同交叉變異概率下算例求解結果Table 3 Example results under different crossover and mutation probability

4.3 算例分析

VRPMTWTDN問題復雜，沒有通用的算例集，設計兩個算例并用AGA-LNS求解其配送方案。

4.3.1 算例1

假設在配送路網中有4 個配送中心和48 個客戶，配送中心坐標分別為（4.163，13.559）、（21.387，17.105）、（-36.118，49.097）、（-31.201，0.235），隨機生成48 個客戶坐標并將其作為客戶節點，其中橫坐標與縱坐標分別在[-75，50]和[-30，100]范圍內隨機生成，客戶需求量在[0.015，0.375]內隨機生成，客戶時間窗在[05：00，17：00]內隨機生成。每個配送中心的工作時間窗均為[05：00，17：00]，最大車輛數均為4，車輛載重量為3 t，單位車輛的派遣成本為500元，油耗成本c1=5.5 元/升，早到單位懲罰成本c3=30 元/h，晚到單位懲罰成本c4=60 元/h，每噸貨物裝卸時間為0.5 h，交叉概率Pc、變異概率Pm的取值區間分別為[0.4，0.9]、[0.02，0.2]。根據文獻[20]相關研究，參數α、β、θ和ω設為30、100、1 和-5。配送中心根據各車輛第一個待服務客戶的時間窗合理安排出發時間，確保其在首個待服務客戶的時間窗內到達。用AGA-LNS求解得到如表4所示的配送方案，其中YC代表油耗成本，TC代表時間窗懲罰成本，ZC代表配送方案總成本。

表4 算例1配送方案Table 4 Distribution scheme of Example 1

4.3.2 算例2

假設在配送路網中有4個配送中心和96個客戶，配送中心坐標分別為（6.229，10.590）、（32.663，44.730）、（48.807，49.792）、（33.179，-4.968），隨機生成96 個客戶坐標并將其作為客戶節點，其中橫、縱坐標分別在[-40，87]和[-42，80]范圍內隨機生成，客戶需求量在[0.015，0.375]內隨機生成，客戶時間窗在[05：00，17：00]內隨機生成，其他參數設置與算例1相同，用AGA-LNS求解得到如表5所示的配送方案。

表5 算例2配送方案Table 5 Distribution scheme of Example 2

4.3.3 實驗結果分析

選用不同客戶規模的算例（4.3.1、4.3.2 小節中的算例及MDVRPTW 標準算例pr03、pr04）對AGA-LNS 進行算法分析及敏感性分析，未給出的其他參數與算例1設置相同。

（1）算法分析

為驗證AGA-LNS 的有效性，采用自適應遺傳算法（AGA）、大鄰域搜索算法（LNS）求解不同客戶規模算例的配送方案，并與AGA-LNS 的求解結果進行對比分析。其中AGA 采用本文設計的交叉變異操作，LNS 選用隨機移除算子和貪婪插入算子組合、最遠距離移除算子和貪婪插入算子組合。表6 給出了3 種算法運行10次的結果，其中C為10次運算結果中的最優解，t為算法平均耗時，GAP1 為AGA-LNS 與AGA、LNS 所求結果的誤差，GAP2 為AGA-LNS 與AGA、LNS 求解耗時的誤差。由表6 可知，AGA-LNS 與AGA、LNS 相比，在求解時長和求解質量上都有顯著優勢，因此AGA-LNS能較好地解決VRPMTWTDN；對比AGA 和AGA-LNS的求解結果可知，客戶規模相同時，AGA-LNS的求解結果相對于AGA 的求解結果均有所改善，平均改善了2.73%，可見在自適應遺傳算法的交叉變異操作后加入大鄰域搜索可改善自適應遺傳算法陷入局部最優解的問題，提高求解質量。

表6 不同算法求解結果對比Table 6 Comparison of solution results of different algorithms

（2）敏感性分析

①混合時間窗比例的影響

為驗證軟硬時間窗客戶數量的比例變化對配送方案制定的影響，本文針對不同客戶規模，分別設置了6種軟硬時間窗客戶數量比例（軟時間窗客戶數∶硬時間窗客戶數=S∶H）。表7給出了算法運行10次的結果，其中N為客戶規模，C為10次運算結果中的最優解，GAP為不同軟硬時間窗客戶數量比例下10次運算結果的最優解與S∶H=1∶1 時求得最優解的相對誤差。由表7 可知，相同客戶規模下，最優解隨著硬時間窗客戶數量比例的增大而增大，即軟時間窗和硬時間窗客戶總數一定，硬時間窗客戶越多，其最優配送方案總成本越高。

表7 軟硬時間窗客戶不同比例下最優配送方案總成本Table 7 Total cost of optimal distribution scheme under different ratios of customers with hard and soft time windows

②車輛行駛速度的影響

為驗證車輛行駛速度對配送方案制定的影響，本文對不同客戶規模算例在車輛勻速行駛情況下進行求解。表8給出了算法運行10次運算結果，其中N為客戶規模，Case1 代表速度連續變化，Case2 代表速度恒為40 km/h，Case3代表速度恒為50 km/h，Case4代表速度恒為60 km/h，C為10次運算結果中的最優解，GAP為車輛勻速行駛時10次運算結果中的最優解與車速時間依賴時求得最優解的相對誤差。由表8可知，相同客戶規模下，不同行駛速度下求得的最優解與速度時間依賴時求得的最優解具有一定誤差，如客戶規模為48時，誤差分別為1.05%、-0.79%、-1.68%。其中車輛行駛速度為50 km/h時的求解結果與本文設置的速度時間依賴函數下求解結果的誤差最小，車輛行駛速度增大或減小，與本文設置的速度時間依賴函數下求解結果的誤差均增大。綜合分析，在制定配送方案時考慮車輛行駛速度時間依賴性具有重要意義。

表8 不同車速下最優配送方案總成本Table 8 Total cost of optimal distribution scheme under different vehicle speeds

表9給出了速度連續變化時與恒定速度時各自運行10 次的平均求解耗時。其中Case1 代表速度連續變化，Case2代表速度恒為50 km/h，GAP為速度連續變化時算例求解的平均耗時與恒定速度時算例求解的平均耗時的相對誤差。由表9可知，速度連續變化時算例求解平均耗時比速度恒定時算例求解平均耗時平均多63.82%，因此考慮車輛速度連續變化增加了算法實現的時間成本約63.82%，但配送中心通常在配送前一天根據已有訂單制定配送方案，因此速度時間依賴下的算法時間成本是可行的。

表9 不同車速下算例求解耗時Table 9 Example solving time under different vehicle speeds

5 結束語

本文考慮配送路網中車輛速度的連續變化，并按照客戶對配送時間的不同要求對其服務時間窗進行分類，對VRPMTWTDN 進行研究，建立了以配送成本最小化為目標的優化模型，并設計了自適應遺傳-大鄰域搜索算法求解配送方案，并實驗驗證了其有效性，結論如下：

（1）模型中不僅考慮了配送中心間配送資源的共享及混合時間窗，還考慮了車輛速度連續變化及車速、載重量對油耗的影響，雖增加了問題求解難度，但更貼近配送生產活動的實際。

（2）AGA-LNS 引入時差插入法改進交叉、變異算子，并嵌入移除、插入算子。針對4 個不同客戶規模的算例，AGA-LNS 與AGA 和LNS 相比，求解質量平均改進了2.73%和21.27%，求解時長平均縮短了7.63%和2.13%，求解質量高，收斂速度快，因此AGA-LNS 能較好地求解帶混合時間窗約束的車輛路徑問題。

（3）不同混合時間窗比例敏感性分析表明，相同客戶規模下，硬時間窗客戶數量比例越小，配送成本越低；不同車輛行駛速度敏感性分析表明，不同行駛速度對配送計劃的制定及配送成本有較大影響，因此在優化配送方案時所設車輛行駛速度應盡量貼近現實。

未來研究將考慮實時交通信息、電動車配送等因素，使問題更貼近實際，并改進、開發更加有效的求解算法。