肖智豪，胡志華，朱琳

（上海海事大學(xué)物流研究中心，上海 201306）

0 引言

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

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

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

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

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

1 問題定義

1.1 問題描述

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

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

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

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

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

1.2 符號(hào)定義

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

1.3 車輛行駛時(shí)間計(jì)算

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

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

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

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

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

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

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

1.4 目標(biāo)成本分析

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

1.4.1 行駛油耗成本

車輛在運(yùn)輸過程中會(huì)產(chǎn)生燃油消耗，不同載重量會(huì)產(chǎn)生不同的油耗。為更好地體現(xiàn)時(shí)間對(duì)油耗的影響，本文采用綜合油耗模型求解。該模型由Barth 等［21］提出，本文在此基礎(chǔ)之上進(jìn)一步改進(jìn)以適應(yīng)連續(xù)型時(shí)間依賴函數(shù)。相關(guān)的參數(shù)及其取值參照文獻(xiàn)［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ù)的油耗計(jì)算可分為兩種情況。

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

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

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

1.4.2 制冷成本

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

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

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

1.4.3 碳排放成本

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

1.4.4 貨損成本

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

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

1.4.5 其他成本

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

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

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

2 模型構(gòu)建

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

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

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

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

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

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

3.1.1 破壞算子

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

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

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

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

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

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

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

3.1.2 修復(fù)算子

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2.1 初始解構(gòu)造

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

步驟1 將所有客戶點(diǎn)放入一個(gè)客戶列表Lc中。

步驟2 從Lc中隨機(jī)取出一個(gè)點(diǎn)放入一條空路徑中并與配送中心相連。

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

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

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

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

3.2.2 ALNS_ABC算法設(shè)計(jì)

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

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

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

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

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

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

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

4 實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)算例與參數(shù)設(shè)置

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

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

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

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

使用Python3.7 在Anaconda 環(huán)境下編寫算法求解。為保證實(shí)驗(yàn)的公平性，實(shí)驗(yàn)對(duì)比分析的各算法編碼方式相同，大鄰域搜索范圍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ù)]發(fā)因子γ1=0.7。ALNS_EG 的參數(shù)設(shè)置為：種群數(shù)為20，交叉率為0.9，變異率等價(jià)為鄰域搜索范圍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 四類混合算法和文獻(xiàn)［25］中自適應(yīng)可變鄰域搜索精英蟻群（Adaptive Variable Neighborhood Search Elite Ant Colony，AVNS_EAC）算法（為保證可對(duì)比性還同時(shí)考慮了精英策略）分別對(duì)15 個(gè)客戶點(diǎn)的實(shí)例數(shù)據(jù)進(jìn)行10 次隨機(jī)模擬仿真實(shí)驗(yàn)，各算法最優(yōu)、平均結(jié)果以及最優(yōu)路徑如表3 所示。

由表3 可知，AVNS_EAC 的求解效果最不理想，相比之下，ALNS_EAC 求解性能更好，這說明自適應(yīng)大鄰域搜索算子比通用的隨機(jī)鄰域搜索算子擁有更高的搜索精度，能有效提高求解質(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%。可以看出ALNS_ABC 算法的提升效果相比之下較為明顯。

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

4.3 算法對(duì)比分析

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

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

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

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

隨后進(jìn)一步對(duì)比算法的收斂性和穩(wěn)定性。ALNS_EAC、ALNS_EG、ALNS_SA 和ALNS_ABC 四類混合算法隨機(jī)運(yùn)行10 次后的收斂時(shí)間如表5 所示。此外，用箱型圖觀察四類混合算法在求解50 個(gè)客戶點(diǎn)的數(shù)據(jù)組時(shí)解的分布情況，如圖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 不同算法的時(shí)間對(duì)比Tab.5 Comparison of time among different algorithms

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

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

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

5 結(jié)語

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

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