肖智豪,胡志華,朱琳
(上海海事大學(xué)物流研究中心,上海 201306)
冷鏈物流配送作為一項(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)一步提高算法的全局搜索能力。
本研究以連續(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ì)受到駕駛員主觀因素的影響而變化。
給定一個(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。
連續(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ì)算公式如下:
本文考慮車輛實(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í)間懲罰成本可表示為:
結(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)表示決策變量的取值范圍。
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。
本文的目標(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ù)。
人工蜂群算法是一種模擬蜜蜂采蜜行為的群智能算法,通過不同蜂種之間的分工合作,以實(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ù)。
本文分別選取文獻(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。
采用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
為進(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)建模型。
為助力實(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é)合理的決策方案。