范厚明，田攀俊，呂迎春，張躍光

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

時變路網(wǎng)下考慮時空距離的同時配集貨車輛路徑問題(Time-Dependent Vehicle Routing Problem with Simultaneous Delivery and Pickup considering Temporal-Spatial Distance，TDVRPSDPTSD)是在道路交通狀況不斷變化的條件下，同時考慮客戶的服務(wù)時間、空間位置、配集貨需求及配送中心的車型不同等因素，對配送車輛行駛路徑進行優(yōu)化的VRP拓展問題?，F(xiàn)實中，如餐飲業(yè)中餐具供應(yīng)商依據(jù)客戶需求派遣多種類型車輛配送清潔餐具的同時也會回收使用過的餐具;快遞業(yè)業(yè)務(wù)員配送到達郵件的同時也會收取寄出郵件等。同時，配送車輛行駛速度受路徑的實時交通狀況影響，高峰時段車輛行駛速度緩慢，非高峰時段則可快速行駛。TDVRPSDPTSD包含了當前VRP研究的兩個熱點問題:時間依賴型車輛路徑問題(Time Dependent Vehicle Routing Problem Vehicle Routing Problem，TDVRP)和同時配集貨車輛路徑問題(Vehicle Routing Problem with Simultaneous Delivery and Pickup，VRPSDP)。已有學(xué)者對這兩個問題展開了研究。針對TDVRP，Sabar等[1]對不同時段道路交通狀況不同的DVRP，建立了以最小總配送成本為目標的DVRP數(shù)學(xué)模型，并提出了一種使用可變參數(shù)的自適應(yīng)進化算法更有效地解決此類DVRP。Liao等[2]考慮車輛在網(wǎng)絡(luò)中行駛時間可能會變化，提出第1階段采用掃頻法進行車輛分配，第2階段根據(jù)實時信息采用禁忌搜索算法對路徑進行改進的兩階段法。張傳琪等[3]考慮配送路網(wǎng)中各路段不同時間段的行駛時間不同，建立以配送成本最小為目標的考慮道路動態(tài)擁擠的多車型車輛路徑優(yōu)化模型，并設(shè)計改進遺傳算法進行求解。Haghani等[4]考慮兩節(jié)點間行駛時間和新增客戶需求的變化，研究了不考慮新需求點和考慮新需求點兩種情況，建立以最小配送時間為目標的路徑優(yōu)化模型，設(shè)計遺傳算法進行求解。段征宇等[5]同時考慮路網(wǎng)交通狀態(tài)的時變性和隨機性，基于最小最大原則建立了考慮硬時間窗的隨機時變車輛路徑優(yōu)化模型，設(shè)計了一種非支配排序蟻群算法進行求解。蔡延光等[6]考慮時變路網(wǎng)環(huán)境以及油耗與載重量的相關(guān)關(guān)系，建立時變路網(wǎng)下的車輛路徑問題優(yōu)化模型，并提出一種自適應(yīng)蟻群算法對其進行求解。葛顯龍等[7]研究了實時交通信息的路徑優(yōu)化問題，建立帶有載重與工作時間約束的開放式污染路徑問題數(shù)學(xué)模型，并設(shè)計改進的自適應(yīng)遺傳算法對其進行求解。吳瑤等[8]考慮實際配送過程中道路交通的時變特性，建立以總成本最小的易腐食品集成生產(chǎn)-配送問題優(yōu)化模型，并設(shè)計混合遺傳算法進行求解。Taniguchi等[9]研究了城市配送中使用先進的智能交通系統(tǒng)，建立了一種考慮車輛行駛時間實時變化的車輛路徑問題求解模型，并使用交通仿真數(shù)據(jù)動態(tài)的更新車輛行駛時間。Mancini[10]考慮重復(fù)性擁堵，提出使用多個函數(shù)關(guān)系式表示道路一天的速度變化情況，并以Torino為例進行了分析。Liu等[11]考慮車輛行駛速度對碳排放的影響，提出了跨時間域的計算方法和一種規(guī)避高峰時段交通擁堵的方法，并針對該問題設(shè)計了改進的蟻群算法進行求解。

針對VRPSDP，王旭坪等[12]研究了帶有時間窗的異車型同時集送車輛路徑問題，以配送成本最小化為目標建立模型，并采用考慮時空距離的鄰域搜索算法對其進行求解。范厚明等[13]考慮集貨需求具有隨機性，建立集貨需求隨機的同時配集貨VRP模型，并采用混合變鄰域搜索算法對其進行求解。田宇等[14]研究了異車型同時集送車輛路徑問題，并采用多屬性標簽的蟻群系統(tǒng)算法進行求解。盛虎宜等[15]研究了農(nóng)村電商物流配送問題，以總配送成本最少為目標構(gòu)建基于共同配送策略的集送貨一體化車輛路徑問題數(shù)學(xué)模型，并根據(jù)模型特點設(shè)計一種改進蟻群算法進行求解。范厚明等[16]研究了多中心聯(lián)合配送模式下的VRPSDP，分兩階段構(gòu)建了多中心聯(lián)合配送模式下集貨需求隨機的同時配集貨車輛路徑模型，并采用自適應(yīng)變鄰域文化基因算法對其進行求解。張曉楠等[17]研究了同時配集貨的定位-路線問題，并建立了三維指數(shù)混合整數(shù)規(guī)劃模型，采用變鄰域分散搜索算法對其進行求解。石建力等[18]考慮了同時配集貨過程中行駛時間和服務(wù)時間隨機性的特點，建立了集送貨一體的分批配送模型，并通過改進的迭代局部搜索算法求解該問題。鄧愛明等[19]研究了軟時間窗條件下的VRPSDP，考慮車輛出發(fā)滿載系數(shù)、軟時間要求等因素，并通過改進的模擬退火算法求解該問題。陳妍等[20]研究了多車型條件下的VRPSDP，并以車輛的固定成本和可變配送成本之和最小化為目標建立多車型集配貨一體化車輛路徑優(yōu)化模型，采用模擬退火算法進行求解。Agarwal等[21]針對易腐產(chǎn)品的同時配集貨問題，建立以網(wǎng)絡(luò)實施成本、環(huán)境副作用成本最小化，社會滿意度最大化的多目標模型，并采用多目標元啟發(fā)式算法對其進行求解。Shahnejat等[22]考慮了家庭醫(yī)療行業(yè)的同時配集貨問題，采用模擬退火和禁忌搜索算法求解了家庭健康照顧路徑與調(diào)度問題。Navazi等[23]通過對比車輛同時配集貨、分取送貨和混合取送貨3種策略下的成本，采用自適應(yīng)大鄰域搜索元啟發(fā)式算法求解了該問題，得出了成本最低的配集貨方案。

車輛路徑問題中時間和空間因素影響著配送成本，Qi等[24]首次將這兩種因素相結(jié)合構(gòu)造了時空距離，并分3種情況計算硬時間窗條件下的時空距離。王旭坪等[12]計算了軟時間窗情況下的時空距離，設(shè)計兩階段啟發(fā)式算法進行求解異車型同時集送車輛路徑問題。范厚明等[25]利用時空距離對零售商聚類生成初始解，并設(shè)計了考慮時空距離的自適應(yīng)遺傳算法求解越庫配送模式下的車輛調(diào)度與庫門分配問題。

綜上所述，還存在如下不足:①關(guān)于時變路網(wǎng)下車輛路徑問題的研究，現(xiàn)有研究的道路速度變化多以階躍函數(shù)表示，未考慮車輛行駛速度是連續(xù)變化的;②針對同時配集貨車輛路徑問題的研究大多忽略了實際的道路交通狀況，未考慮車輛行駛速度連續(xù)動態(tài)變化對配送方案的影響;③針對帶有時間窗的VRPSDP的研究，其算法在生成初始解時大多將時間因素和空間因素單獨考慮，導(dǎo)致算法收斂變慢且最優(yōu)解的質(zhì)量較差。針對上述不足，本文以TDVRPSDPTSD為研究對象，在同時配集貨車輛路徑問題基礎(chǔ)上，劃分路網(wǎng)中道路的類型，考慮道路速度連續(xù)變化且不同類型的道路在同一時刻的車輛行駛速度不同，依據(jù)時空距離對客戶進行聚類，以車輛派遣成本、運輸成本、時間窗懲罰成本之和最小化為目標建立優(yōu)化模型，設(shè)計考慮時空距離的混合變鄰域搜索遺傳算法規(guī)劃車輛行駛路徑，為配送中心獲得合理的車輛調(diào)度方案提供理論依據(jù)。

1 問題描述與模型建立

1.1 問題描述

本文研究的TDVRPSDPTSD可描述為:假設(shè)有完備的有向圖G=(V，E)，有不同類型的道路，每種類型的道路車輛行駛速度v是連續(xù)變化的;節(jié)點集合V=Vc∪{0}，其中，0為配送中心，其工作時間窗為[T s，T f]，Vc為客戶點集合;邊集合E={(i，其中，l ij為節(jié)點i、j之間的距離;配送中心有R種類型車輛，r(r∈R)為車輛類型，K r為r型車輛集合，k r為第k輛r型車，其容量為Q r，單位車輛派遣成本為c r1，單位距離運輸成本為c r2;Q ijkr為車輛k r服務(wù)完客戶i接著要服務(wù)客戶j時的車輛剩余裝載量，Q0jkr為車輛從配送中心出發(fā)時的初始裝載量;客戶點i的配貨量為d i，集貨量為p i，T ikr為車輛k r到達節(jié)點i的時刻，t ikr為車輛k r在節(jié)點i的服務(wù)時間;[ET i，LT i]為客戶i的服務(wù)時間窗，ET i為客戶i的最早可接受服務(wù)時刻，LT i為客戶i的最晚可接受服務(wù)時刻，車輛早于ET i或晚于LT i到達客戶會產(chǎn)生懲罰成本，早到單位時間懲罰成本為c3，晚到單位時間懲罰成本為c4。1個客戶只允許1輛車服務(wù)，且車輛在完成配送和集貨任務(wù)后返回配送中心。決策變量x ijkr表示車輛k r是否從點i到達點j，是為1，否為0。

1.2 速度時間依賴函數(shù)的確定

現(xiàn)有對TDVRP的研究，多以分段函數(shù)形式表示路段的車輛行駛速度，在某一時間節(jié)點速度是突變的。而現(xiàn)實中，車輛行駛速度是連續(xù)變化的，如文獻[26]中提出的車輛速度(v)與時間(t)之間的三角函數(shù)關(guān)系式:v(t)=φsin(γt)+δ(其中，φ、γ和δ與道路路況有關(guān))，本文將1天中道路速度連續(xù)變化情況用多個三角函數(shù)關(guān)系式近似表示。速度(v)與時間(t)之間的三角函數(shù)關(guān)系表達式為:

式中，參數(shù)aβ，bβ，cβ，dβ，β∈{1，2，…，n}與道路狀況有關(guān)。

依據(jù)文獻[27]中的數(shù)據(jù)，可得到車輛行駛速度全天變化趨勢，如圖1所示。

根據(jù)車輛行駛速度變化趨勢，將全天劃分為多個時段，每個時段車輛行駛速度(v)與時間(t)之間的函數(shù)關(guān)系式不同。假設(shè)車輛從節(jié)點i出發(fā)的時刻T i在[Tβ，Tβ+1]內(nèi)，車輛由節(jié)點i行駛至節(jié)點j存在跨時段和不跨時段兩種可能性，若l ij≤配送車輛在[T i，Tβ+1]內(nèi)到達節(jié)點j，無需跨時間段行駛，行駛時間t ij可根據(jù)l ij和[Tβ，Tβ+1]時段的速度函數(shù)關(guān)系式求積分上限得到;若則配送車輛需要跨時間段行駛，假設(shè)配送車輛由節(jié)點i行駛到節(jié)點j需要跨M個時段，在每個時段內(nèi)行駛距離為，行駛時間為車輛行駛的時間可根據(jù)]時段的速度函數(shù)關(guān)系式求積分上限得到。

1.3 建立數(shù)學(xué)模型

基于上述所述，建立如下DVRPSDPTSD模型:

其中，式(2)表示目標函數(shù)，是以車輛派遣成本、車輛運輸成本、時間窗懲罰成本之和最小化為目標;式(3)表示每個客戶只能被車輛服務(wù)一次;式(4)表示車輛的進出平衡約束;式(5)表示車輛被使用時只有一條服務(wù)路徑且車輛完成任務(wù)后必須返回配送中心;式(6)表示車輛訪問客戶p前后的車輛裝載量平衡約束;式(7)表示車輛在服務(wù)客戶j之后的車載容量約束;式(8)表示車輛初始載量;式(9)表示配集貨過程中配送中心使用的車輛不超過其車輛數(shù)量限制;式(10)表示車輛從客戶i到達客戶j的時刻;式(11)表示相同節(jié)點之間沒有通路;式(12)為消除子回路約束;式(13)確保任意車輛返回配送中心的時刻不超過配送中心截止工作時刻;式(14)為模型決策變量屬性。

2 算法設(shè)計

VRP問題屬于經(jīng)典的NP-hard問題，啟發(fā)式算法在求解這類問題時具有明顯的優(yōu)越性。遺傳算法具有魯棒性、并行性高和搜索能力強的特點，但收斂速度慢且容易陷入局部最優(yōu)，不能保證整體最優(yōu)。變鄰域搜索算法采用多個不同的鄰域結(jié)構(gòu)進行系統(tǒng)搜索，具有較強的局部搜索能力。因此，本文結(jié)合遺傳算法和變鄰域搜索算法，并在此基礎(chǔ)上根據(jù)配送中心以及客戶的時空距離進行客戶分組和聚類，從而生成較好的初始種群，設(shè)計了考慮時空距離的混合變鄰域搜索遺傳算法(Hybrid Genetic Algorithm with Variable Neighborhood Search，HGAVNS)，將變鄰域搜索算法應(yīng)用到遺傳算法的局部搜索策略中，以增強算法的尋優(yōu)能力。算法流程如圖2所示。

2.1 客戶聚類以及初始種群生成

將時空距離相近的客戶進行聚類，生成聚類簇，同一聚類簇內(nèi)客戶的時空距離較近，不同聚類簇間的客戶時空距離較遠。聚類方法如下式所示，目的是使每一個聚類簇中其他客戶到該聚類簇中心的時空距離之和G最小，

式中:u為聚類簇的數(shù)目為客戶i、j之間的時空距離，其計算方法參考文獻[12]。

最后，將聚類簇內(nèi)的客戶按其與配送中心的距離進行排序，靈活選擇合適的車型進行路徑的劃分，最終的路徑可在三維圖中形象地刻畫出來(見圖3)?？v坐標表示時間，平面二維坐標表示空間位置，0表示配送中心，A、B、C、D、E表示客戶，圓柱表示時間窗。時空路徑1為:O3→A1→A2→B1→B2→O4，時空路徑2為:O2→C1→C2→D1→D2→E1→E2→O5，其中，車輛到達客戶A和E的時刻早于最早期望時間，產(chǎn)生一定的早到懲罰成本，而到達客戶D的時刻晚于最晚期望時間，相應(yīng)的會產(chǎn)生晚到懲罰成本。

2.2 編碼與解碼

采用整數(shù)編碼的形式，例如有9個客戶，1個配送中心，則數(shù)字1～9表示客戶，對客戶進行隨機全排列，數(shù)字0表示配送中心。解碼時根據(jù)車輛返回配送中心時刻以及容量約束將顧客按照初始排列順序劃分給車輛，當對下一個客戶進行檢驗發(fā)現(xiàn)當前車輛不能滿足要求時，靈活選擇不同容量的車型對該客戶進行服務(wù)。且每輛車服務(wù)的第1個客戶前插入0，即從配送中心出發(fā)。以一個簡單例子進行說明，如圖4所示，假設(shè)客戶的全排列順序為1，5，8，3，4，6，9，2，7，派第1輛車對客戶1進行服務(wù)，當服務(wù)客戶4時不滿足約束，則第1輛車的路徑為0—1—5—8—3—0，選用車型1。以此類推，第2輛車的路徑為0—4—6—0，選用車型2，第3輛車的路徑為0—9—2—7—0，選用車型1。

2.3 適應(yīng)度評價

染色體的適應(yīng)度函數(shù)可以根據(jù)模型中目標函數(shù)式(2)進行構(gòu)造。染色體K的適應(yīng)度函數(shù)為

本文的目標函數(shù)為總配送成本最小化，優(yōu)化的目標就是選擇適應(yīng)度函數(shù)值較大的染色體。其中，z K為染色體K的目標函數(shù)值。

2.4 選擇操作

選擇操作采取輪盤賭與精英保留相結(jié)合的選擇策略。采用輪盤賭的方式，每條染色體被選中的概率與其適應(yīng)度函數(shù)值的大小成正比，即適應(yīng)度函數(shù)值越高的染色體被選中的概率越高;反之，則被選中的概率越低。在選擇操作結(jié)束后，采用精英保留策略，將每一代的最優(yōu)染色體進行保留，即用上一代適應(yīng)度值最優(yōu)的個體替換子代適應(yīng)度值最差的個體。采用輪盤賭和精英保留相結(jié)合的策略，保證種群規(guī)模始終不變且使算法快速收斂。

2.5 進化操作

本文的進化操作選用順序交叉算子。如圖5所示，對父代Pop1進行順序交叉時，從種群中隨機選取父代Pop2，首先分別隨機產(chǎn)生點位i11、i12、i21和i22，父代Pop1的隨機點位i11、i12之間的部分作為子代new Pop1的第1段，子代new Pop1的后續(xù)點位與父代Pop2有關(guān)，即先消除父代Pop2中包含父代隨機點位i11、i12之間的客戶點，在消除過程中，父代Pop2中的客戶點的位置順序不改變，再將消除后的客戶點排列作為子代new Pop1的第2段，組成新子代new Pop1，子代new Pop2同理。

2.6 局部搜索優(yōu)化

(1)鄰域構(gòu)造。首先構(gòu)造l個鄰域結(jié)構(gòu)集合N k={N1，N2，…，N l}，種群中個體x從第1個領(lǐng)域結(jié)構(gòu)N1開始擾動，若在預(yù)設(shè)的鄰域搜索次數(shù)S n內(nèi)仍未找到改進解，則執(zhí)行下一個鄰域結(jié)構(gòu);否則，若在某一鄰域結(jié)構(gòu)內(nèi)獲得改進解x′，則令x=x′，并返回第1個鄰域結(jié)構(gòu)重新開始迭代，直到循環(huán)到最后一個鄰域結(jié)構(gòu)，仍未找到改進解時，搜索終止;當變鄰域搜索循環(huán)次數(shù)達到預(yù)設(shè)值maxS n時，搜索終止，算法進入下一階段。本文采用5種鄰域結(jié)構(gòu)來增強算法的局部搜索能力:

①插入。隨機選擇兩個客戶點i和j，將i插入到客戶j的后面。如圖6(a)所示，隨機選取客戶3和客戶6，將客戶3插入到客戶6的后面。

②交換。隨機選中兩個客戶點i和j，交換兩客戶點的位置。如圖6(b)所示，將客戶3和客戶6的位置交換。

③2-插入。在原方案中隨機選擇連續(xù)的兩個客戶點，將其插入到隨機選擇的客戶點j的后面。如圖6(c)所示，將客戶3、4插入到客戶6后面。

④2-opt。隨機選擇兩客戶點i和j，并將客戶點間的順序進行交換。如圖6(d)所示，保持客戶3的位置不變，客戶4、5、7、6逆序。

⑤or-opt。在原方案中隨機選擇連續(xù)的兩個客戶點，將其逆序插入到隨機選擇的客戶點j的后面。如圖6(e)所示，將客戶3、4逆序插入到客戶6后面。

(2)自適應(yīng)機制與新解接受機制。本文設(shè)計自適應(yīng)鄰域搜索次數(shù)策略和新解接受機制增強算法搜索的廣度和深度，使變鄰域搜索算法能夠跳出局部最優(yōu)。

鄰域搜索次數(shù)對算法的搜索能力具有較大的影響，直接導(dǎo)致了算法性能的優(yōu)劣。在算法迭代過程中，種群所需的擾動強度不同，在迭代初期，鄰域搜索次數(shù)應(yīng)當較小，使種群快速收斂;而隨著種群的不斷迭代，增加鄰域搜索次數(shù)，加強算法的搜索能力。本文的自適應(yīng)鄰域搜索次數(shù)策略如下:

①設(shè)置初始鄰域搜索次數(shù)S n=1，最優(yōu)解連續(xù)未改變的次數(shù)con_num;

②若本次迭代后的種群最優(yōu)解未改進，則令con_num=con_num+1，S n=S n+1;若擾動后的解存在改進，則令con_num=0，S n=1;

③當最優(yōu)解連續(xù)未改變的次數(shù)con_num達到預(yù)設(shè)值stop_num時，算法終止，輸出最優(yōu)解。

為了進一步提升種群的擾動性，擴大搜索空間，借鑒模擬退火算法中解的接受規(guī)則，以一定的概率接受較差解，從而有效避免算法過早地陷入局部最優(yōu)，提升了算法的尋優(yōu)能力，同時也實現(xiàn)種群的多樣性。其中，新解接受概率的計算方法如下式所示:

3 算例分析

為驗證本文算法的有效性，選取客戶規(guī)模不同的同時配集貨算例對本文算法進行測試。算法編程采用MATLAB R2018b，操作系統(tǒng)為Windows 10，內(nèi)存為8 GB，CPU為Intel i7-7700 M，主頻3.60 GHz。算法參數(shù)設(shè)置為:種群規(guī)模Pop size=30～150，最大迭代次數(shù)max gen=800，初始變鄰域搜索次數(shù)S n=1，最大鄰域循環(huán)次數(shù)maxS n=1 000，stop_num=20～50。參數(shù)的設(shè)置值同對應(yīng)算例中客戶點規(guī)模n相關(guān)，當n≤50時，Pop size=30，stop_num=20;當50＜n≤100時，Pop size=100，stop_num=30;當n＞100時，Pop size=150，stop_num=50。

3.1 算法驗證

實驗1為驗證HGAVNS算法對同時配集貨車輛路徑問題的求解性能，通過文獻[30]中提供的算例進行分析，表1給出了改進模擬退火算法(ISA)[19]、協(xié)同粒子群-模擬退火算法(PSO-SA)[28]、自適應(yīng)粒子群算法(SDAPSO)[29]以及本文HGAVNS算法運行10次的計算結(jié)果。其中，改進幅度指本文算法相較于其他算法求解10次的平均值方面的改進幅度，L為車輛總行駛距離(km)，K為派遣車輛數(shù)，t為運行時間(s)。

表1 算例測試結(jié)果

由表1可以看出，在算法求解性能方面，本文10次測試結(jié)果的平均值比ISA算法改進了19.88%，比PSO-SA算法改進了3.98%，比SDAPSO算法改進了2.39%;在求解性能方面，本文的10次計算結(jié)果的標準差比前3種算法都要小，結(jié)果具有較強的穩(wěn)定性，算法也有很好的魯棒性;在求解時間方面，本文HGAVNS算法的求解時間最短。由此可得本文設(shè)計的算法在求解質(zhì)量、求解穩(wěn)定性和求解時間上都優(yōu)于前3種算法。

實驗2為了驗證本文算法對不同規(guī)模算例求解的性能，基于文獻[31]中的14組算例進行測試，客戶規(guī)模為50～199，其中每組算例分為X型和Y型兩類，其中Y型是X型配集貨需求互換后的算例。表2給出了禁忌搜索和變鄰域算法(TS&VN)[32]、禁忌搜索算法(TS)[33]、混合元啟發(fā)式算法(HMA)[34]以及本文HGAVNS算法運行10次的最優(yōu)解，其中，BKS為已知的最優(yōu)解，L為行駛總距離，Dev%為算法求得的最優(yōu)解同已知最優(yōu)解的偏差。圖7給出了本文算法在算例CMT1Y、CMT3X的求解結(jié)果。

由表2可以看出，在14組算例的求解中，本文算法有10組都找到了最優(yōu)解，TS&VN算法求解質(zhì)量最差，平均偏差為10.42%，最大偏差達到29.87%;TS算法求解質(zhì)量一般，平均偏差為3.58%，最大偏差為8.71%，HMA算法求解質(zhì)量較好，平均偏差為0.44%，最大偏差為2.62%。本文求解質(zhì)量最優(yōu)，平均偏差為0.30%，最大偏差為1.53%。由此可得本文算法對不同規(guī)模的算例都表現(xiàn)出良好的尋優(yōu)能力，再次驗證了本文算法的有效性和適用性。

表2 算例對比結(jié)果

實驗3由于現(xiàn)有研究沒有關(guān)于TDVRPSDPTSD的算例，故對文獻[31]中的CMT1X算例進行適當修改以適應(yīng)本文的模型，該算例含有一個配送中心和50個客戶，客戶的配、集貨量由需求分離規(guī)則產(chǎn)生[31]:x i和y i是客戶的坐標，q i為客戶的原始需求，計算每個客戶的比率r i=min{x i/y i;y i/x i}，由d i=q ir i和p i=q i(1-r i)計算得出該客戶的配、集貨量。本文假設(shè)配送中心工作時間窗為[06:00，19:00]，車輛單位時間等待成本為20，單位時間延誤成本為30，單位貨物裝卸的標準時間為10 min。配送中心用于配集貨的不同車型費用參數(shù)如表3所示。

表3 不同車型費用參數(shù)

如圖8所示，該實驗將配送路網(wǎng)中的道路劃分為主干路、次干路以及支路3種類型。其中，紅色表示主干路，其速度為v1，黑色表示次干路，其速度為v2，圖中未畫出的線路表示支路，其速度為v3。3種類型道路的車輛行駛速度v1、v2和v3的全天變化情況如圖9所示。

利用本文設(shè)計的HGAVNS進行求解，得到最優(yōu)的配集貨方案，配集貨路線如圖10所示，具體配送方案如表4所示。由表4可以得出配送中心派出6輛車對這50個客戶進行服務(wù)，其中容量為60、100和120的車各2輛，將其成本相加可得配集貨總成本為3 422.77。

表4 最優(yōu)配集貨方案

3.2 有效性分析

為了驗證本文算法中時空距離的有效性，以實驗3為基礎(chǔ)，在其余條件相同的情況下，將算法是否考慮時空距離的求解結(jié)果進行對比。在不考慮時空距離的條件下，算法求解的最優(yōu)方案如表5所示。配送中心總計派出了7輛車進行配集貨，其總成本為3 654.21。與實驗3的最優(yōu)方案相比，其派出的車輛數(shù)目增加，且總成本增加了231.44。因此，算法中考慮時空距離可使配送中心派遣車輛減少1輛，且最優(yōu)解改進了6.76%，這進一步證明了算法中考慮時空距離的有效性。

表5 不考慮時空距離最優(yōu)配集貨方案

4 結(jié)論

本文針對時變路網(wǎng)下考慮時空距離的同時配集貨車輛路徑問題的研究得出如下結(jié)論:

(1)以配集貨總成本最小化為目標建立綜合考慮客戶服務(wù)時間、空間位置以及配集貨需求的優(yōu)化模型，能夠更加客觀準確地反映真實物流系統(tǒng)的運行情況，所得出的車輛調(diào)度優(yōu)化方案可以有效降低配送中心的運營成本。

(2)設(shè)計的考慮時空距離的HGAVNS算法，通過計算客戶間時空距離對客戶進行時空聚類后生成的初始種群，有效提高了初始解的質(zhì)量，使結(jié)果更優(yōu)。

(3)算法在選擇操作時采取精英保留和輪盤賭相結(jié)合的策略，保證了算法的有效收斂。并且使用進化操作和自適應(yīng)搜索與新解接受機制，改善了局部搜索能力，提高了求解質(zhì)量，求得的結(jié)果具有較好的穩(wěn)定性。通過不同規(guī)模的算例進行測試并與其他文獻相對比，驗證了本文算法的有效性。

(4)建立的TDVRPSDPTSD模型能夠解決現(xiàn)實中道路行駛速度不斷變化，且道路類型多樣的VRPSPD優(yōu)化問題，是對VRPSPD研究的深化與拓展。

本文的研究更加符合現(xiàn)實中的配送問題，研究成果不僅豐富和拓展了同時配集貨VRP的相關(guān)理論，也為物流企業(yè)配送方案的優(yōu)化決策提供了依據(jù)。