求解冷鏈物流時間依賴型車輛路徑問題的混合自適應(yīng)大鄰域搜索算法

肖智豪，胡志華，朱琳

（上海海事大學物流研究中心，上海 201306）

0 引言

冷鏈物流配送作為一項特殊的運輸方式近年來備受關(guān)注。一方面是由于冷鏈配送車輛相比普通車輛需額外控制貨艙溫度，此舉會產(chǎn)生更高的能耗和更多的碳排放。據(jù)國際能源署的統(tǒng)計結(jié)果表明，交通運輸行業(yè)的碳排放量占全球總排放量的20%以上，而交通運輸行業(yè)產(chǎn)生的碳排放有70%以上來自于公路運輸［1］。為實現(xiàn)碳中和、碳達峰的總目標方針，節(jié)能減排對冷鏈物流企業(yè)尤為重要。另一方面，由于人們生活水平的提高，對于生鮮食品的需求也日益增加，這要求物流企業(yè)對生鮮進行合理的冷藏運輸，否則會發(fā)生損毀、腐爛等情況。據(jù)聯(lián)合國糧食及農(nóng)業(yè)組織調(diào)查顯示，全球有1/3 的食物消耗都是由于浪費或者損耗造成的，其中50%為生鮮食品［2］。因此，如何在保證客戶滿意度的同時，達到節(jié)能減排和減少貨損的目標是當前冷鏈物流企業(yè)所面臨的巨大挑戰(zhàn)。

目前國內(nèi)外很多學者都致力于冷鏈車輛路徑問題的研究：殷亞等［3］對混合蝙蝠算法的單多點變異設(shè)定選擇機制，提出了一種改進混合蝙蝠算法求解以成本最小、客戶滿意度最大的多目標生鮮配送最優(yōu)路徑選擇模型；方文婷等［4］針對蟻群算法階段初期收斂速度過慢的問題，設(shè)計了一種結(jié)合A*算法和蟻群算法的混合蟻群算法，以求解冷鏈配送路徑問題；Song 等［5］則設(shè)計了一種改進人工魚群算法求解以固定成本和能耗最小為目標的多車型冷鏈車輛路徑問題；為了改變目前冷鏈物流配送過程中成本最小化模型的應(yīng)用現(xiàn)狀，Zhao 等［6］設(shè)計了一種基于多目標啟發(fā)式函數(shù)的改進蟻群算法。

隨著研究的進一步深入，許多學者都將交通時變納入到冷鏈車輛路徑問題的考慮范圍之內(nèi)?？紤]交通時變的車輛路徑問題也被稱為時間依賴型車輛路徑問題（Time-Dependent Vehicle Routing Problem，TDVRP），最早由Malandraki 等［7］提 出，是車輛路徑問題（Vehicle Routing Problem，VRP）的變式，屬于組合優(yōu)化中的NP（Nondeterministic Polynomial）-hard 問題，采用啟發(fā)式算法可以高效求解該類問題。反映交通時變的行駛時間依賴函數(shù)可分為Malandraki 模型［7］和Inchoua 模型［8］：Malandraki 模型考慮將每天的時間劃分為多個小段，每一段的行程時間固定，每個時段內(nèi)的行駛時間按照當前的路況呈階梯式分布；Inchoua 模型用行駛速度代替行程時間，每個時間段內(nèi)的行駛速度呈階梯式分布，通過路徑長度和行駛速度計算行駛時間，從而行駛時間連續(xù)變化?，F(xiàn)有對冷鏈時間依賴型車輛路徑問題的研究中，Osvald 等［9］、白秦洋等［10］、杜琛等［11］考慮了Malandraki 模型；趙志學等［12］、付朝暉等［13］、任騰等［14］考慮了Inchoua 模型。

結(jié)合以上分析可知有關(guān)冷鏈時間依賴型車輛路徑問題的研究已經(jīng)形成了一定的成果，但還存在如下3 個問題：1）反映時變的兩類行駛時間依賴函數(shù)和真實路況之間存在一定誤差，其主要原因在于Malandraki 模型并不滿足先進先出（First-In-First-Out，F(xiàn)IFO）準則，而Inchoua 模型雖然可以滿足FIFO 準則，但由于其行駛速度躍遷變化，和實際情況之間存在較大差異；2）對于車輛行駛過程中油耗量的評估，以往的研究中學者們多采用負載估計法［15］描述載重量和油耗的關(guān)系，但該方法按載重量比例估算油耗，和真實值之間存在一定誤差；3）目前很多學者都考慮采用基于隨機鄰域搜索一類的元啟發(fā)式算法來求解同類型的車輛路徑問題，盡管該類算法的求解速度快，但是搜索隨機性較強，從而導致搜索精確度較低，難以滿足求解現(xiàn)有復(fù)雜路徑優(yōu)化問題的要求。

針對以上3 個問題，本文另考慮了一種連續(xù)型行駛時間依賴函數(shù)，車速在不同時段之間連續(xù)變化，以更加真實地反映城市交通擁堵狀況，同時還采用綜合油耗模型來衡量冷藏車行駛過程中的實時燃油消耗量，以準確反映車輛行駛時間和載重量對于行駛油耗的影響；此外，以總成本最小為目標建立數(shù)學優(yōu)化模型，并為獲得良好的求解效果，本研究從自適應(yīng)大鄰域搜索（Adaptive Large Neighborhood Search，ALNS）的角度出發(fā)對該模型進行求解。ALNS 算法能夠采用不同的算子對可行解進行指導性的破壞和修復(fù)，并在此基礎(chǔ)上增加了對算子作用效果的衡量，使算法能夠選擇好的算子進行搜索，從而獲得良好的局部尋優(yōu)的能力，目前已被廣泛應(yīng)用于車輛路徑問題［16-19］中；但該算法全局搜索的能力較弱，容易陷入局部最優(yōu)。因此將本文設(shè)計的破壞-修復(fù)大鄰域搜索算子融入人工蜂群（Artificial Bee Colony，ABC）算法之中，以進一步提高算法的全局搜索能力。

1 問題定義

1.1 問題描述

本研究以連續(xù)型行駛時間依賴函數(shù)為基礎(chǔ)，綜合考慮車輛行駛油耗成本、制冷成本、貨損成本、碳排放成本等其他成本。問題具體表述為：多輛同類型的冷藏車從同一配送中心出發(fā)，按一定順序向同一城市中不同位置的客戶點提供送貨服務(wù)，在完成配送任務(wù)后返回配送中心。每個客戶具有不同的需求，且不超過冷藏車的最大載貨量。所有車輛最大載貨量相同，且配送車輛的行駛速度受交通擁堵的影響而連續(xù)變化。每個客戶都有時間窗要求，提前或者延遲到達都會產(chǎn)生懲罰費用。另外對問題還做出如下假設(shè)：

1）配送中心的庫存量滿足所有客戶點的需求，且配備足夠多的冷藏車為客戶點提供配送服務(wù)。

2）任意兩個客戶點之間的最短距離是提前計算好的，在配送過程中不會改變，只有車輛行駛速度和行駛時間會受路況影響而改變。

3）車輛行駛速度只受到早晚交通車流量高峰期的影響，不考慮行人、氣候等因素。

4）車輛行駛油耗不會受到駕駛員主觀因素的影響而變化。

1.2 符號定義

給定一個有向完全圖G=(N，A)，N={0，1，…，n}為所有節(jié)點的集合，0 表示冷鏈物流中心，N{0}表示需要服務(wù)的客戶集合，A={(i，j)，i∈N，j∈N，i≠j}表示任意兩節(jié)點之間的最短路徑集合。配送中心一共有K輛冷藏車，k=1，2，…，K。Qmax表示車輛最大裝載重量，車輛從客戶i到客戶j的行駛過程中搭載的貨物重量為Qij。客戶i的需求為qi(i∈N)。dij表示客戶i到客戶j之間的距離。vf表示自由流速度，vc表示擁堵速度，vc∈(0，vf]。tki表示車輛k到達客戶的所需要的時間，表示客戶i期望被服務(wù)的時間窗要求表示客戶i接受服務(wù)的時間，tij表示車輛從顧客i到顧客j的通行時間。zk為0-1 變量，車輛k被使用則zk=1，否則zk=0；yki為0-1 變量，yki=1 表示車輛k服務(wù)客戶i，否則yki=0；xkij為0-1 變量，如果車輛k途徑客戶i到達客戶j，則xkij=1，否則xkij=0。

1.3 車輛行駛時間計算

連續(xù)型時間依賴函數(shù)考慮車輛行駛速度受一天內(nèi)早晚高峰的影響而平滑改變，如圖1 所示。

圖1 接近真實路況的連續(xù)型時間依賴函數(shù)Fig.1 Continuous time dependent function close to real road conditions

將一天的時間分為多個時段，時段集合為H，每一時段h∈H，不同時段間的速度連續(xù)改變，因此可用線性函數(shù)表示每段時間內(nèi)的速度：

其中：Vh(t)表示在時段h中和時間t線性相關(guān)的速度函數(shù)；Vh表示時段h的初始速度；th表示時段h的初始時間；(Vh+1-Vh)/(th+1-th)表示車輛在時段h的加速度，后文簡化為αh表示。

本文還考慮兩級速度函數(shù)［20］以計算經(jīng)歷速度拐點的過渡路段所耗行程時間，并對兩級速度函數(shù)進行改進以更好適應(yīng)連續(xù)型時間依賴函數(shù)。若某一車輛在從客戶i到客戶j的行駛過程中從時段h進入時段h+1，假設(shè)車輛離開上一個客戶點i的時間為x，時段h的終止時間為y。兩個客戶位置間的距離為dij，tij(x，vh)表示車輛在客戶i和客戶j之間的行駛時間。車輛在時段h+1 中行駛的距離為：

考慮車輛均勻變速的理想情況下，通過構(gòu)建一元二次方程求解變速行駛時間，并忽略車輛減速時的折返效應(yīng)，則在時段h+1 中的行駛時間為：

因此tij(x，vh)計算公式如下：

1.4 目標成本分析

本文考慮車輛實際配送過程中所產(chǎn)生的行駛油耗成本、制冷成本、碳排放成本、貨損成本，此外還考慮了固定成本和時間懲罰成本，各項成本分析和計算公式如下。

1.4.1 行駛油耗成本

車輛在運輸過程中會產(chǎn)生燃油消耗，不同載重量會產(chǎn)生不同的油耗。為更好地體現(xiàn)時間對油耗的影響，本文采用綜合油耗模型求解。該模型由Barth 等［21］提出，本文在此基礎(chǔ)之上進一步改進以適應(yīng)連續(xù)型時間依賴函數(shù)。相關(guān)的參數(shù)及其取值參照文獻［20］，如表1 所示。

表1 車輛參數(shù)定義與取值Tab.1 Definition and value of vehicle parameters

載重Q（kg）貨物的冷藏車以恒定車速v（m/s）行駛d（m）距離所產(chǎn)生的油耗量F（L）為：

考慮連續(xù)型時間依賴行駛函數(shù)的油耗計算可分為兩種情況。

第一種是車輛行駛路段中不包含速度函數(shù)的拐點，相應(yīng)油耗計算公式如下：

第二種是包含速度函數(shù)拐點的過渡路段，相應(yīng)油耗計算公式如下：

綜上所述，行駛油耗成本，也即車輛運輸成本C1為：

1.4.2 制冷成本

本文考慮配送中心派發(fā)同類型車輛提供服務(wù)，車廂整體劣化程度及車輛性能參數(shù)均保持一致，且卸貨過程中只打開一次車門，故而制冷成本可近似看作與時間呈正線性相關(guān)。冷藏車一般配備獨立的制冷機組以保證車廂內(nèi)部恒定低溫，而制冷機組在制冷過程中會產(chǎn)生燃油和制冷劑的消耗，因此制冷成本C2包括燃油消耗成本和制冷劑消耗成本。

制冷機組的燃油消耗又可分為運輸時產(chǎn)生的燃油消耗成本和卸貨時產(chǎn)生的燃油消耗成本。令θ1和θ2分別表示運輸過程和卸貨過程中產(chǎn)生的單位熱負荷燃油消耗量，Gt為車輛在行駛過程中產(chǎn)生的單位時間熱負荷。燃油消耗成本的計算公式如下：

同理，制冷劑消耗成本也可分為運輸時產(chǎn)生的制冷劑消耗成本和卸貨時產(chǎn)生的制冷劑消耗成本。令?1和?2分別表示運輸過程和卸貨過程中產(chǎn)生的單位時間制冷劑消耗成本，則制冷劑消耗成本為：

1.4.3 碳排放成本

本文考慮碳稅以衡量碳排放成本。碳稅政策正逐漸成為許多國家激勵減排的有效工具，其是指將二氧化碳排放帶來的環(huán)境成本轉(zhuǎn)化為企業(yè)生產(chǎn)經(jīng)營成本。冷藏車燃油消耗一部分來自發(fā)動機引擎，一部分來自制冷機組。由Barth等［22］可知，車輛的碳排放量和燃油消耗量呈線性正相關(guān)性，因此可以根據(jù)式（8）和式（9）計算車輛行駛過程中的碳排放量，根據(jù)式（11）計算冷藏車制冷所產(chǎn)生的碳排放量。令ω表示每單位體積的油耗所產(chǎn)生的二氧化碳排放量，Pt表示單位體積二氧化碳所需支付的碳稅。故碳稅成本C3的計算公式如下：

1.4.4 貨損成本

冷鏈貨物具有易損、易腐等特性。由于冷藏車制冷機組能夠?qū)囟瓤刂圃谙鄬Π踩姆秶鷥?nèi)以適宜冷藏貨物的存放，因此考慮貨損成本僅與運輸時間和卸貨時間有關(guān)。貨損成本C4主要包括運輸過程中的貨損成本和卸貨過程中產(chǎn)生的貨損成本。Pg為貨物單價，δ1為單位時間運輸貨損率，δ2為單位時間卸貨貨損率。運輸過程中生鮮產(chǎn)品的自然呼吸作用會導致新鮮度下降，從而導致貨損，相應(yīng)的成本計算如式（13）：

卸貨過程中，由于冷藏車車廂門開啟而產(chǎn)生熱交換，也會導致生鮮產(chǎn)品新鮮度下降，相應(yīng)的成本計算式如下：

1.4.5 其他成本

1）固定成本C5。C5為使用冷藏車完成某一路徑上客戶的配送而產(chǎn)生的固有費用，包括車輛的折損費用、維修費用、保養(yǎng)費用、駕駛員薪資等，與參與配送的冷藏車數(shù)量成正比，可以表示為：

其中Fk表示單位車輛所產(chǎn)生的固定成本。

2）時間懲罰成本C6。C6客戶通常要求冷鏈貨物在規(guī)定時間范圍內(nèi)送達，超出該規(guī)定時間范圍送達貨物會降低客戶滿意度，因此本文考慮軟時間窗懲罰成本，提前或者延遲交付貨物都會產(chǎn)生懲罰費用。令μ1和μ2分別表示提前交貨和延遲交貨所產(chǎn)生的單位時間懲罰成本，則時間懲罰成本可表示為：

2 模型構(gòu)建

結(jié)合上述分析，以行駛油耗成本C1、制冷成本C2、碳排放成本C3、貨損成本C4、固定成本C5和時間懲罰成本C6總和最小為目標函數(shù)，如式（17）所示，根據(jù)文獻［23］中的TDVRP模型，構(gòu)建如下車輛路徑優(yōu)化模型：

式（18）表示每位客戶只由一輛冷藏車進行配送；式（19）表示車輛到達某一客戶點后必須從該客戶點離開，以保證路徑的連貫性；式（20）表示每條車輛路徑上總的客戶需求不超過車輛最大容量；式（21）表示每個客戶只能被服務(wù)一次；式（22）表示離開配送中心的冷藏車在完成配送后必須返回配送中心；式（23）表示車輛到達下一個客戶的時間是車輛到達上一個客戶的時間、上一個客戶的服務(wù)時間以及上一個客戶到下一個客戶的車輛行駛時間之和，車輛運行是一個連續(xù)的過程；式（24）是為了消除子回路；式（25）表示決策變量的取值范圍。

3 混合ALNS算法設(shè)計

ALNS 局部尋優(yōu)能力更加精準，有較高的概率探索到更優(yōu)解，但這也導致算法容易陷入局部最優(yōu)，因此本文將自適應(yīng)大鄰域搜索算法融入ABC 算法中，提出了一種自適應(yīng)大鄰域搜索人工蜂群（Adaptive Large Neighborhood Search Artificial Bee Colony，ALNS_ABC）算法，以提高全局尋優(yōu)的能力。另外算法采用自然數(shù)方式進行編碼，并且對應(yīng)的適應(yīng)度值用目標總成本的倒數(shù)進行表示，即fit=1/C。

3.1 大鄰域搜索算子設(shè)計

本文的目標成本主要和通行時間密切相關(guān)，而通行時間又和速度、路程相關(guān)，此外問題的特點還包括客戶的時間窗要求，因此本文所提的大鄰域算子主要圍繞以上4 個特點進行設(shè)計。此外關(guān)聯(lián)度算子、隨機算子、貪婪算子、遺憾準則算子都是通用自適應(yīng)大鄰域搜索算法中高效的搜索算子，也都被本文考慮在內(nèi)。另外在執(zhí)行修復(fù)操作的同時需要保證修復(fù)后的解為可行解，即滿足車輛的容量約束。本文使用了6種破壞（移除）算子和5 種修復(fù)（插入）算子。

3.1.1 破壞算子

1）關(guān)聯(lián)度移除。該方法最初由Shaw［24］在1998 年提出。為適應(yīng)本文研究的問題對該算子做出進一步改進，其基本原理是移除一組相關(guān)聯(lián)的點，客戶i和客戶j之間的關(guān)聯(lián)性由R(i，j)表示，其表達式如下：

其中：φ1、φ2、φ3、φ4分別代表距離、時間窗、需求以及路徑的權(quán)重系數(shù)。R(i，j)越小表示兩節(jié)點間的關(guān)聯(lián)度越高。移除的所有節(jié)點之間要保證關(guān)聯(lián)度盡可能低。如果i和j在同一條路徑上，則φ4=1，否則為0。首先隨機選擇一個點放入被移除點的集合Lr，然后從未移除點集中選一個點j，根據(jù)公式j(luò)=argmin{R(i，j)}選擇Nr個客戶進行移除。通常情況下φ1=6，φ2=5，φ3=4。

2）時間最長移除。該算子的思想是移除對路徑時間影響最大的點，以此減少整條路徑上的通行時間。試探性地移除路徑上的每一個點，并計算移除該點后路徑行程的縮短時間。更新當前路徑，并不斷執(zhí)行移除操作直到Nr個客戶點被移除。

3）時間窗最遠移除。由于本文考慮了時間懲罰成本，因此需要保證車輛抵達時間盡可能靠近客戶時間窗要求。移除車輛抵達客戶的時間離客戶要求的時間窗最遠的客戶點。若車輛抵達時間滿足客戶i的時間窗，Δti=0，否則：

4）最 大速度差移除。該方法由Franceschetti 等［18］在2017 年提出，其基本思想是移除車輛抵達途徑客戶時前后出入速度之差最大的客戶。本文研究考慮平均速度，前一條路徑的速度為vij=dij/tij(x，vh)，后一條路徑的速度為vjl=djl/tjl(x，vh)，前后路徑 速度差為Δvj=vij-vjl。根 據(jù)j=argmax{Δvj}選擇Nr個客戶進行移除。

5）路徑隨機移除。該算子旨在為算法加入隨機因素，以減少陷入局部最優(yōu)的可能性。選擇總成本最大的一條路徑，再隨機選擇該路徑上的一個客戶進行移除，同時更新路徑。不斷執(zhí)行移除操作直到Nr個客戶被移除。

6）最差移除。該算子旨在移除對整條路徑的成本費用影響最大的點，從而直觀地減少總的運輸成本。計算每一個點移除以后和未移除之前的目標函數(shù)差值，選擇差值最大的客戶點進行移除，同時更新路徑。重復(fù)執(zhí)行移除操作直到Nr個客戶被移除。

3.1.2 修復(fù)算子

1）時間窗最近插入。從Lr中隨機取出一個客戶點m，試探性地將其插入到路徑上的某一位置后，卡車到達m的時間為tkm，如果其插入以后的前一個點為i，則tkm=tki++tim。保證m插入到tkm和差值最小所對應(yīng)的位置，即m=argmin{|tkm-|}，重復(fù)上述操作直到Lr為空集。

2）距離最短插入。從Lr中隨機取出一個客戶點m，將其插入客戶i和客戶j之間，那么總里程增量Δd(i，m，j)=dim+dmj-dij，選擇增量最小的位置進行插入，即m=argmin{Δd(i，m，j)}，重復(fù)上述操作直到Lr為空集。

3）時間最短插入。從Lr中隨機取出一個客戶點m，將其插入客戶i和客戶j之間，那么總時間增量Δt(i，m，j)=t(0，…，i，m，j，…，0) -t(0，…，i，j，…，0)，選擇增量最小的位置進行插入，即m=argmin{Δt(i，m，j)}，重復(fù)上述操作直到Lr為空集。

4）最優(yōu)貪婪插入。選擇對目標函數(shù)值影響最小的位置進行插入。隨機選一個點，判斷該點插入某一位置后該條路徑的總成本增加值，選擇增加值最低所對應(yīng)的位置進行插入，重復(fù)上述操作直到Lr為空集。

5）遺憾準則插入。該算子在最優(yōu)貪婪插入算子的基礎(chǔ)上多考慮了一步，以保證算子的多元性。評估每一個移除點被插入的最優(yōu)位置和次優(yōu)位置，并計算最少的總成本增量和次少的總成本增量之間的差值。所有移除點對應(yīng)該差值進行從大到小的排序，并按照該順序選擇下一個要插入的點，以最優(yōu)貪婪方式進行插入。

3.1.3 自適應(yīng)權(quán)重調(diào)整

每一次搜索過程中，移除和插入算子的選擇都基于輪盤賭規(guī)則，以此增加算子選擇的多樣性。在計算開始時，每一個算子都有相同的權(quán)重和分值，并且初始分值為1。根據(jù)算子的不同表現(xiàn)情況階梯式給分，得分越高表明算子表現(xiàn)越好。每一次計算過程中算子加分情況如下：

1）新解被接受作為下一次鄰域搜索的出發(fā)解，得5 分。

2）新解被接受作為下一次鄰域搜索的出發(fā)解，并作為當前最優(yōu)解，再得5 分。

3）新解未被接受為下一次鄰域搜索的出發(fā)解，且比當前解更差不得分。

根據(jù)每一輪的平均得分來計算當前算子參與輪盤賭選擇的權(quán)重。此外還設(shè)定了一個權(quán)重更新系數(shù)ρ以避免收斂速度過快陷入局部最優(yōu)。算子的權(quán)重按照式（28）更新：

其中：ηa為權(quán)重，sa為累計得分，ua為累計使用次數(shù)。

3.2 自適應(yīng)大鄰域搜索人工蜂群算法

人工蜂群算法是一種模擬蜜蜂采蜜行為的群智能算法，通過不同蜂種之間的分工合作，以實現(xiàn)優(yōu)良的全局探索能力。在ABC 算法中，用蜜源的位置來表示解，用蜜源的花粉數(shù)量表示解的適應(yīng)度值。所有的蜜蜂劃分為雇傭蜂、跟隨蜂、偵察蜂三組。雇傭蜂和跟隨蜂各占蜂群總數(shù)的一半。雇傭蜂負責最初地尋找蜜源并采蜜分享信息，跟隨蜂負責呆在蜂巢里根據(jù)雇傭蜂提供的信息去采蜜，偵察蜂在原有蜜源被拋棄后負責隨機尋找新的蜜源來替換原有的蜜源。本文考慮用大鄰域搜索方式替換ABC 算法中常用的隨機鄰域搜索方式。

3.2.1 初始解構(gòu)造

首先在ALNS_ABC 算法中考慮構(gòu)建出較為良好的初始解以提高求解質(zhì)量。根據(jù)貪婪插入策略進行初始解的構(gòu)造，需要注意的是本文根據(jù)距離最短進行插入，而非時間或者目標值最少時進行插入，以避免算法結(jié)果過早收斂而陷入局部最優(yōu)。具體步驟如下：

步驟1 將所有客戶點放入一個客戶列表Lc中。

步驟2 從Lc中隨機取出一個點放入一條空路徑中并與配送中心相連。

步驟3 隨機從Lc中取出一個點x，試探性地將其插入路徑中的每一個位置，并計算相應(yīng)的距離成本增量，計算公式如下：

其中：g(x)的計算包括兩部分，一部分是實際距離的增量，另一部分是考慮插入的x離配送中心太遠而產(chǎn)生的懲罰費用；r表示懲罰系數(shù)，取一個固定的值0.3?？蛻酎cx在對應(yīng)距離成本增量最低的位置進行插入。

步驟4 更新當前路徑，重復(fù)執(zhí)行步驟3，直到路徑滿足最大容量約束，該條路徑構(gòu)造結(jié)束。

步驟5 重復(fù)步驟2～4，直到客戶列表Lc為空集。

3.2.2 ALNS_ABC算法設(shè)計

算法實現(xiàn)的具體步驟描述如下：

步驟1 參數(shù)初始化。確定蜜源的數(shù)量S，蜜源最大開發(fā)次數(shù)limit，最大迭代次數(shù)MaxIter，初始算子權(quán)重ηa集合、權(quán)重慣性因子ρ1，搜索范圍也即移除和插入點個數(shù)Nr。

步驟2 蜂群初始化。根據(jù)初始解構(gòu)造方法生成S組初始蜜源，每個蜜源即為一個初始可行解，每個可行解對應(yīng)一組信息列表，包含了蜜源開發(fā)次數(shù)、各項算子的得分和各項算子的權(quán)重三類信息。

步驟3 雇傭蜂階段。每只雇傭蜂采用輪盤賭方式選擇對蜜源進行大鄰域搜索的破壞-修復(fù)算子，每一次進行大鄰域搜索后按貪心策略對蜜源進行選擇，并且更新被使用算子所對應(yīng)的分值和權(quán)重：如果通過大鄰域搜索找到一個比當前蜜源質(zhì)量更好的新蜜源，則替換原有蜜源，同時對記錄的開發(fā)次數(shù)進行清零；如果沒有找到更好的蜜源，則增加一次開發(fā)次數(shù)。

步驟4 跟隨蜂階段。雇傭蜂向跟隨蜂分享當前蜜源信息。跟隨蜂根據(jù)蜜源的適應(yīng)度值，也即目標總成本的倒數(shù)，采用輪盤賭策略選擇蜜源進行跟蹤開采，以保證質(zhì)量更高的蜜源開采的概率更大。跟隨蜂開采過程與雇傭蜂一樣，通過大鄰域搜索找尋新蜜源，并采用貪心策略對蜜源進行選擇，同時更新開發(fā)次數(shù)以及算子的分數(shù)和權(quán)重。

步驟5 偵察蜂階段。如果一個蜜源達到開發(fā)次數(shù)上限，則拋棄該蜜源，再根據(jù)構(gòu)造初始解的方法搜索一個新的蜜源，并對開發(fā)次數(shù)進行清零；同時需要還原算子所對應(yīng)的分數(shù)和權(quán)重，因為新產(chǎn)生的解已經(jīng)破壞了原有的鄰域搜索結(jié)構(gòu)，沿用之前的算子得分和權(quán)重對算子進行選擇會造成搜索效果的偏差。

步驟6 重復(fù)步驟3～5，直到滿足最大迭代次數(shù)。

4 實驗與分析

4.1 實驗算例與參數(shù)設(shè)置

本文分別選取文獻［4］中的實例數(shù)據(jù)和Solomon 測試數(shù)據(jù)庫中的VRPTW 算例數(shù)據(jù)進行仿真分析。貨車在市區(qū)通行的自由流速度一般為40 km/h，另外本文考慮早高峰時段為6：00～10：00、晚高峰時段為16：00～20：00，早晚高峰的擁堵速度為25 km/h，中午12 時的擁堵速度為30 km/h。冷藏車每天上午8：00 出發(fā)進行配送服務(wù)。為方便研究，以直線距離作為客戶位置間的最短距離，實驗結(jié)果保留兩位小數(shù)。車輛相關(guān)參數(shù)已在表1 中給出；成本相關(guān)參數(shù)參照文獻［4］，如表2 所示。

表2 成本相關(guān)參數(shù)Tab.2 Cost related parameters

本文認為R1、RC1 類數(shù)據(jù)集時間窗較窄，服務(wù)時間較短，更類似于冷鏈配送的情況，因此采用Solomon 測試數(shù)據(jù)庫中的數(shù)據(jù)集R101-R103（隨機分布）以及RC101-RC103（半堆分布）進行測試。此外，由于冷鏈配送呈現(xiàn)“批次多、批量少”的特點，客戶規(guī)模相對較小，因此分別截取前25 和50 個客戶點進行算法測試分析。

本文還另設(shè)計3 種混合ALNS 算法作為比較基準。1）自適應(yīng)大鄰域搜索精英蟻群算法（Adaptive Variable Neighborhood Search Elite Ant Colony，ALNS_EAC），該算法在螞蟻完成周游后加入對精英螞蟻進行自適應(yīng)大鄰域搜索的操作，直到連續(xù)10 次搜索都沒有找到更優(yōu)螞蟻路徑再更新信息素濃度。2）自適應(yīng)大鄰域搜索精英遺傳（Adaptive Large Neighborhood Search Elite Genetic，ALNS_EG）算法，該算法用大鄰域搜索算子代替?zhèn)鹘y(tǒng)遺傳算法的變異算子，并保留較優(yōu)個體。3）自適應(yīng)大鄰域搜索模擬退火（Adaptive Large Neighborhood Search Simulated Annealing，ALNS_SA）算法，該算法根據(jù)Metropolis 準則決定是否接受當前解。

使用Python3.7 在Anaconda 環(huán)境下編寫算法求解。為保證實驗的公平性，實驗對比分析的各算法編碼方式相同，大鄰域搜索范圍Nr=5，權(quán)重慣性因子ρ1=0.7。ALNS_ABC的參數(shù)設(shè)置為：蜜源數(shù)S為20，雇傭蜂和跟隨蜂的數(shù)量各為10，最大開發(fā)次數(shù)limit為20。ALNS_EAC 的參數(shù)設(shè)置為：螞蟻數(shù)M為20，信息素重要因子α1=1，啟發(fā)式函數(shù)重要因子β1=3，信息素揮發(fā)因子γ1=0.7。ALNS_EG 的參數(shù)設(shè)置為：種群數(shù)為20，交叉率為0.9，變異率等價為鄰域搜索范圍Nr。3 類群智能算法迭代次數(shù)都為100，種群規(guī)模都為20。ALNS_SA 的參數(shù)設(shè)置為：初溫T0為30℃，退火系數(shù)θ為0.96，終止溫度為0.3，同一溫度下的迭代次數(shù)為20。

4.2 仿真分析

采用ALNS_EAC、ALNS_EG、ALNS_SA、ALNS_ABC 四類混合算法和文獻［25］中自適應(yīng)可變鄰域搜索精英蟻群（Adaptive Variable Neighborhood Search Elite Ant Colony，AVNS_EAC）算法（為保證可對比性還同時考慮了精英策略）分別對15 個客戶點的實例數(shù)據(jù)進行10 次隨機模擬仿真實驗，各算法最優(yōu)、平均結(jié)果以及最優(yōu)路徑如表3 所示。

由表3 可知，AVNS_EAC 的求解效果最不理想，相比之下，ALNS_EAC 求解性能更好，這說明自適應(yīng)大鄰域搜索算子比通用的隨機鄰域搜索算子擁有更高的搜索精度，能有效提高求解質(zhì)量。其他四類混合算法都取得了相同的最優(yōu)結(jié)果，且相較于AVNS_EAC 都有較大提升。從平均結(jié)果來看，ALNS_EAC、ALNS_EG、ALNS_SA，ANS_ABC 相較于AVNS_EAC 分別提升了7.1%、6.8%、6.6%、7.4%?？梢钥闯鯝LNS_ABC 算法的提升效果相比之下較為明顯。

表3 實例數(shù)據(jù)仿真結(jié)果Tab.3 Simulation results of data of a case

4.3 算法對比分析

為進一步對比四類混合算法在求解該類問題上的性能，根據(jù)Solomon 測試數(shù)據(jù)庫中的R101-103、RC101-103 客戶數(shù)據(jù)，分別截取前25、50 個客戶點進行實驗分析。數(shù)據(jù)集R101-103 的客戶地理位置是隨機生成的，數(shù)據(jù)集RC101-103的客戶位置呈混合隨機聚類分布。各參數(shù)和實例中保持一致，同時為保證結(jié)果的真實性，數(shù)據(jù)集中客戶的需求和車輛容量擴展為原有的10 倍。

采用ALNS_EAC、ALNS_EG、ALNS_SA、ALNS_ABC 四類混合算法分別對以上所述的12 組數(shù)據(jù)分別進行10 次隨機仿真實驗，并計算所有結(jié)果的平均值，實驗具體計算結(jié)果見表4。通過實例結(jié)果可知AVNS_EAC 的性能低于其他各類混合算法，因此用AVNS_EAC 對12 組數(shù)據(jù)各運行10 次，并將其平均結(jié)果作為對照依據(jù)，測試各算法在此基礎(chǔ)之上的提升效果，以更加直觀地評估四類混合算法的性能，具體結(jié)果如圖2 所示。此外，為證明本文所構(gòu)模型和算法同樣適用于Solomon 測試數(shù)據(jù)庫，分別對R101-50、RC101-50 數(shù)據(jù)組最好結(jié)果所對應(yīng)的車輛運行圖進行模擬，如圖3 所示。

圖2 不同混合算法的提升效果Fig.2 Improvement effect of different hybrid algorithms

圖3 數(shù)據(jù)組R101-50、RC101-50的最優(yōu)車輛運行圖Fig.3 Optimal vehicle routing diagrams of data group R101-50 and RC101-50

表4 算例仿真結(jié)果Tab.4 Numerical example simulation results

從表4 可以看出12 組數(shù)據(jù)下的最好結(jié)果有10 次都是由ALNS_ABC 算法找到，這直接證明該算法在求解中小規(guī)模問題上尋優(yōu)能力最強，能充分發(fā)揮大鄰域搜索算子的作用，獲得更優(yōu)的局部搜索精度。而ALNS_EAC 只有4 次搜索到最好的結(jié)果，ALNS_SA 只有2 次，ALN_EG 只有1 次，說明其余三種算法的搜索精準度相對較低。結(jié)合圖4 對比分析各算法的平均結(jié)果，可以看出，ALNS_ABC 在所有50 個客戶規(guī)模數(shù)據(jù)下的平均結(jié)果表現(xiàn)都是最好的，反觀ALNS_EG 在客戶規(guī)模越大，客戶位置分布越復(fù)雜的情況下，求解效果越不理想。ALNS_EAC 在25 個客戶規(guī)模下的求解效果與ALNS_ABC 相近，而在50 個客戶規(guī)模數(shù)據(jù)的求解上效果稍弱；ALNS_SA 在25 個客戶規(guī)模下的求解效果與ALNS_EG 相近，而在50 個客戶規(guī)模數(shù)據(jù)的求解上與ALNS_EAC 相近。綜合來看，采用ALNS_ABC 進行求解效果會更好。另外，由圖4 可以看出，算法最優(yōu)結(jié)果所對應(yīng)的車輛行程較為理想，進一步說明了本文所構(gòu)建模型和算法的有效性。

隨后進一步對比算法的收斂性和穩(wěn)定性。ALNS_EAC、ALNS_EG、ALNS_SA 和ALNS_ABC 四類混合算法隨機運行10 次后的收斂時間如表5 所示。此外，用箱型圖觀察四類混合算法在求解50 個客戶點的數(shù)據(jù)組時解的分布情況，如圖4所示，其中加粗線條表示中位數(shù)，盒子的頂端表示上四分位數(shù)，底端表示下四分位數(shù)，豎線表示該組結(jié)果的平均偏差，豎線頂端的橫線表示最大值，底端的橫線表示最小值，空心圓表示異常值。

圖4 數(shù)據(jù)組R101-103-50、RC101-103-50的箱型圖Fig.4 Box-plots of data group R101-103-50 and RC101-103-50

表5 不同算法的時間對比Tab.5 Comparison of time among different algorithms

1）收斂性。由于各算法每次迭代會選擇不同算子進行鄰域搜索，而不同算子計算復(fù)雜度也不同，因此計算的CPU時間有較大差別。結(jié)合表5 進行分析可知，ALNS_SA 收斂速度快，但更容易陷入局部最優(yōu)，相比其他群智能算法“爬山”能力較弱；而ALNS_EG 求解時間長，收斂速度慢，求解效果也不理想。ALNS_ABC 比ALNS_EAC 在求解較小規(guī)模算例時的CPU 時間較長，但收斂速度快，而在求解較大規(guī)模算例時，盡管收斂速度稍慢，但CPU 時間更短。

2）穩(wěn)定性。在圖4 中，AEG1 代表ALNS_EG 求解序號為101 的50 個客戶點數(shù)據(jù)集時所對應(yīng)的箱型分布。綜合來看，ALNS_EG 箱盒最長，求解效果不穩(wěn)定。ALNS_SA 的箱盒箱較長，且有較多異常值出現(xiàn)。ALNS_EAC 在數(shù)據(jù)集R1 類數(shù)據(jù)集中箱盒較長，且存在異常值，求解效果不穩(wěn)定，而在RC1類數(shù)據(jù)集中箱盒較短。ALNS_ABC 在6 類數(shù)據(jù)集中箱盒都較短，且只在1 組數(shù)據(jù)集的求解中出現(xiàn)異常點，尤其是在求解RC1 類數(shù)據(jù)集時，箱盒都非常短，因此可以認為ANLS_ABC在尋優(yōu)過程中具有更強的穩(wěn)定性。

綜合以上分析可知，自適應(yīng)大鄰域搜索算法比隨機鄰域搜索有更強的局部尋優(yōu)能力，考慮在其他元啟發(fā)式算法中加入大鄰域搜索算子能夠提高算法的求解精度，獲取更高的求解質(zhì)量；同時實驗也證明，人工蜂群算法能充分發(fā)揮大鄰域算子的優(yōu)勢，將人工蜂群算法和自適應(yīng)大鄰域搜索算法相結(jié)合效果最佳，能穩(wěn)定且有效地求解本文所構(gòu)建模型。

5 結(jié)語

為助力實現(xiàn)碳中和、碳達峰的總目標方針，綠色、低碳和環(huán)保正逐漸成為當今企業(yè)發(fā)展的核心理念。物流企業(yè)如何在保證自身經(jīng)濟效益的前提下，構(gòu)建綠色供應(yīng)鏈體系，實現(xiàn)物流與生態(tài)的和諧發(fā)展，是當前所面臨的一大挑戰(zhàn)。本文著眼于冷鏈物流配送中高能耗、高排放、易貨損的問題，結(jié)合城市路網(wǎng)中速度連續(xù)動態(tài)變化的情況，在考慮各項配送成本的基礎(chǔ)上構(gòu)建路徑優(yōu)化模型。本文設(shè)計了6 種破壞算子和5 種修復(fù)算子，并將大鄰域搜索算子組合融入ABC 算法，提出了一種ALNS_ABC 算法，以提高全局搜索的能力。最后將所提出的ALNS_ABC 算法和ALNS_EG、ALNS_EAC、ALNS_SA 算法以及已有文獻中的AVNS_EAC 算法進行對比分析。實驗結(jié)果表明自適應(yīng)大鄰域搜索的尋優(yōu)精度高，同時將自適應(yīng)大鄰域搜索算法和人工蜂群算法相結(jié)合能充分發(fā)揮大鄰域搜索算子的優(yōu)勢，獲得更加高效的尋優(yōu)能力。

未來的研究中可以通過地圖軟件獲取實時交通信息，綜合考慮擁堵、天氣、行人等因素，采用人工神經(jīng)網(wǎng)絡(luò)的方式擬合非線性連續(xù)型時間依賴函數(shù)，以更加精準地預(yù)測車速的實時變化。另外，也可以考慮多車型、多配送中心、多溫共配等其他冷鏈運輸情況，為保障企業(yè)經(jīng)濟效益，實現(xiàn)綠色環(huán)保發(fā)展提供更為科學合理的決策方案。