模糊需求下的多中心冷鏈配送車輛路徑問(wèn)題

王 祺，肖 青

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

現(xiàn)代社會(huì)中，依靠冷鏈運(yùn)輸?shù)漠a(chǎn)品數(shù)量逐漸增加，配送區(qū)域不斷擴(kuò)大，單配送中心模式難以滿足物流合理配送規(guī)劃。同時(shí)，低碳是如今社會(huì)所倡導(dǎo)的理念，人們對(duì)低排放量要求逐漸變高。而冷鏈產(chǎn)品具有易腐性、時(shí)效性以及客戶點(diǎn)分散等特征，為了保證產(chǎn)品新鮮度，在運(yùn)輸過(guò)程中對(duì)時(shí)間的要求高、車輛排耗量大。因此，在優(yōu)化冷鏈配送模式時(shí)，碳排放在車輛路徑優(yōu)化問(wèn)題中也是不容忽視的[1]。此外，實(shí)際配送中，還存在很多不確定性因素，其中客戶對(duì)冷鏈產(chǎn)品需求的不確定是配送中考慮模糊變量的重要因素之一。所以，對(duì)于冷鏈物流來(lái)說(shuō)，綜合考慮帶時(shí)間窗的多配送中心下模糊需求車輛路徑問(wèn)題研究（multi-depot vehicle routing problem with time windows and fuzzy demands，MDVRPTWFD）具有更廣泛的應(yīng)用價(jià)值。

對(duì)于車輛路徑優(yōu)化的相關(guān)引申問(wèn)題，已經(jīng)有很多學(xué)者展開了深入的研究，并取得很不錯(cuò)的研究成果。其中帶時(shí)間窗的VRP（vehicle routing problem with time windows，VRPTW）最早是由Solomon[2]提出，并且給出不同規(guī)模的經(jīng)典求解算例，他提出的最小成本最鄰近法（nearest neighbor algorithm based on minimum cost，

NNC）在構(gòu)造初始解時(shí)，可高效地產(chǎn)生可行解，加速后期算法的迭代優(yōu)化。李軍濤等[3]考慮模糊時(shí)間窗的VRP問(wèn)題，從冷鏈物流運(yùn)輸角度建立碳排放量、配送成本和客戶滿意度的多目標(biāo)優(yōu)化模型，采用自適應(yīng)災(zāi)變遺傳算法進(jìn)行求解。之后，李軍濤等[4]進(jìn)行VRPTW 問(wèn)題的延伸，考慮交通擁堵和多車型的車輛路徑優(yōu)化，并將碳排放量轉(zhuǎn)化為成本加入到配送成本中。Xu 等[5]研究單配送中心車輛路徑優(yōu)化，以時(shí)變車速下的燃料消耗量和客戶滿意度為目標(biāo)，通過(guò)自適應(yīng)和貪心策略的改進(jìn)非支配排序遺傳算法去求解?？祫P等[6]構(gòu)建了單配送中心下考慮碳排放的生鮮農(nóng)產(chǎn)品運(yùn)輸路徑優(yōu)化模型，并用嵌入2-opt局部搜索算法的改進(jìn)蟻群算法進(jìn)行求解。

對(duì)于多配送中心的車輛路徑問(wèn)題（multi-depot vehicle routing problem，MDVRP），范厚明等[7]研究時(shí)變路網(wǎng)下、混合時(shí)間窗的多配送中心VRPTW 問(wèn)題，并設(shè)計(jì)自適應(yīng)遺傳-大鄰域搜索算法進(jìn)行求解。辜勇等[8]考慮多中心的協(xié)同配送VRPTW 問(wèn)題，并設(shè)計(jì)K-mediods 聚類算法、改進(jìn)的蟻群算法和節(jié)約算法的三階段求解算法進(jìn)行求解。Zhen 等[9]研究了具有時(shí)間窗和發(fā)布日期的多車場(chǎng)多行程車輛路徑問(wèn)題，以總旅行時(shí)間最小化為目標(biāo)，提出了混合粒子群優(yōu)化算法和混合遺傳算法求解。

針對(duì)模糊變量下的車輛路徑問(wèn)題的研究，范厚明等[10]結(jié)合模糊需求和模糊時(shí)間窗，去研究VRP 問(wèn)題，以總行駛距離、車輛數(shù)最少以及客戶滿意度最大為目標(biāo)，并利用混合遺傳算法進(jìn)行求解。王文君[11]考慮交通流，以車輛固定成本和油耗成本為目標(biāo)去分析模糊需求下的多車型VRP 問(wèn)題，通過(guò)突變遺傳算法和可信性理論約束模型去求解。Nasab等[12]研究的是模糊需求選址路徑問(wèn)題，基于模糊可信性理論去建模，并結(jié)合隨機(jī)模擬的混合模擬退火算法進(jìn)行求解。

通過(guò)分析以往的相關(guān)研究，發(fā)現(xiàn)有以下不足之處：（1）針對(duì)VRP問(wèn)題，大多數(shù)學(xué)者考慮的是單配送中心下的路徑優(yōu)化，在城市區(qū)域間的多需求下，會(huì)導(dǎo)致配送壓力過(guò)大以及車輛調(diào)度失衡，即使有的學(xué)者研究了MDVRP問(wèn)題，但沒(méi)有去考慮其他不確定因素，目標(biāo)函數(shù)通常研究單一。而且有的學(xué)者是將多中心問(wèn)題轉(zhuǎn)化為單配送中心，比如Zhen等[9]，研究MDVRP 問(wèn)題，考慮閉環(huán)的多中心，即匹配到合適的中心后，必須往返都在該中心下，并沒(méi)有很好地體現(xiàn)多配送中心資源共享的特征。（2）對(duì)于考慮冷鏈物流配送，在多配送中心基礎(chǔ)上，對(duì)融入碳排放、冷鏈運(yùn)輸特性以及配送中的不確定信息研究較少。（3）有很多考慮帶時(shí)間窗的模糊變量和多中心的VRP 問(wèn)題，但鮮少將其融入冷鏈運(yùn)輸中，對(duì)冷鏈運(yùn)輸配送成本分析也不夠全面。因此，本文研究在多配送中心冷鏈運(yùn)輸基礎(chǔ)上，對(duì)MDVRPTWFD問(wèn)題展開研究，綜合考慮模糊需求、載重量和時(shí)間窗約束，構(gòu)建以車輛的固定成本、運(yùn)輸成本、制冷成本、時(shí)間懲罰成本和碳排放成本為總配送成本最小和客戶滿意度最大的多目標(biāo)優(yōu)化模型，通過(guò)改進(jìn)的遺傳算法-大規(guī)模鄰域算法和隨機(jī)模擬算法進(jìn)行求解。豐富了不確定性多配送中心下冷鏈配送車輛路徑問(wèn)題的研究理論，為相關(guān)企業(yè)提供理論指導(dǎo)。

1 問(wèn)題分析與模型構(gòu)建

1.1 問(wèn)題描述

MDVRPTWFD 問(wèn)題可以描述為在物流運(yùn)輸網(wǎng)絡(luò)中，由多個(gè)配送中心聯(lián)合對(duì)多個(gè)需求不確定的客戶進(jìn)行配送服務(wù)，并在給定的目標(biāo)下，根據(jù)載重量、時(shí)間窗等約束條件下，合理規(guī)劃車輛配送路線。其中不同配送中心之間的車輛是可以共享的，不要求每輛車只有一條路徑，車輛在完成配送任務(wù)后，以及在中途補(bǔ)貨，均可選擇距其距離最近的配送中心進(jìn)行停靠或裝卸貨，然后繼續(xù)進(jìn)行配送服務(wù)。

本文研究的是冷鏈物流配送的MDVRPTWFD問(wèn)題，可以描述為在某個(gè)配送區(qū)域里，有 ||N個(gè)配送中心，配送中心集合為N={n|n=1,2,…,|N|}，M表示客戶集合，M={m|m=1,2,…,|M|}，K表示車輛集合，K={k|k=1,2,…,|K|}，|K|表示車輛總數(shù)。dij表示客戶點(diǎn)（配送中心）i到客戶點(diǎn)（配送中心）j的距離；C1表示單位車輛使用成本；C2表示單位距離運(yùn)輸費(fèi)用；C3表示單位制冷成本；C4表示到達(dá)客戶點(diǎn)i的開始服務(wù)時(shí)間在[Ei,ei]內(nèi)的早到懲罰成本；C5表示到達(dá)客戶點(diǎn)i的開始服務(wù)時(shí)間在[li,Li]內(nèi)的晚到懲罰成本；Ce表示單位碳排放成本；[ei,li]表示節(jié)點(diǎn)i的最佳的服務(wù)時(shí)間窗；[Ei,Li]表示節(jié)點(diǎn)i的最大容忍服務(wù)時(shí)間窗；tijk表示第k輛車從節(jié)點(diǎn)i到節(jié)點(diǎn)j的運(yùn)輸時(shí)間；Qk1表示車輛k運(yùn)輸行駛產(chǎn)生的熱負(fù)荷；Qk2表示車輛k開關(guān)車門裝卸貨時(shí)所產(chǎn)生的熱負(fù)荷；ti表示節(jié)點(diǎn)i的開始服務(wù)時(shí)間；Cd表示碳排放系數(shù)；P1表示單位距離車輛燃油消耗量。

1.2 模型假設(shè)

為了更好地解決問(wèn)題，在構(gòu)建模型時(shí)，提出以下的假設(shè)：

（1）多配送中心模式下的冷藏車輛均為同一車型，車輛的裝載量、制冷性能、碳排放相關(guān)系數(shù)以及單位距離車輛油耗消耗量等相關(guān)信息已知。（2）車輛可在任意中心出發(fā)，完成任務(wù)可選擇回到距離最近的任意中心，不需要回到原配送中心。（3）配送中心和客戶點(diǎn)的位置信息已知，但客戶需求量是不確定的。（4）車輛進(jìn)行配送時(shí)以某個(gè)平均速度進(jìn)行配送。（5）一輛車可被調(diào)度多次，服務(wù)多個(gè)客戶，但每個(gè)客戶只能由一輛車進(jìn)行服務(wù)。（6）對(duì)冷鏈物流運(yùn)輸問(wèn)題，僅考慮制冷成本，不考慮在配送中由于冷鏈產(chǎn)品變質(zhì)等因素產(chǎn)生的貨損成本，這部分貨損體現(xiàn)在時(shí)間懲罰成本和客戶滿意度上。（7）所有配送中心能滿足客戶需求，不存在缺貨情況。（8）對(duì)模糊需求來(lái)說(shuō)，在得到初始計(jì)劃路線和實(shí)際需求后，不考慮在配送途中需要返回配送中心補(bǔ)貨再返回客戶點(diǎn)繼續(xù)服務(wù)后，會(huì)違反其最大容忍時(shí)間窗，只是相應(yīng)的客戶點(diǎn)的開始服務(wù)時(shí)間改變了。

1.3 模糊需求分析

由于配送車輛在未到達(dá)客戶點(diǎn)時(shí)，客戶需求是不確定的，即模糊需求。所以，引入決策者的主觀偏好值和可信性測(cè)度理論，在初始階段，客戶需求被看作是三角模糊數(shù)，即客戶需求qi=(q1i,q2i,q3i)，每輛車有相同的載重量Q，假設(shè)某一輛車已經(jīng)服務(wù)p個(gè)客戶后，由模糊數(shù)學(xué)知識(shí)可知，此時(shí)車輛剩余的載重量Up也是三角模糊數(shù)，即：

根據(jù)可信性理論[13]，對(duì)于客戶點(diǎn)p來(lái)說(shuō)，其下一個(gè)客戶p+1點(diǎn)的需求量小于車輛剩余載重量的可信性為：

式（1）中，Cr為滿足qp+1≤Up條件的可信度，Cr越大，表明車輛剩余的載重量越有可能滿足下一個(gè)客戶點(diǎn)的需求量，則該客戶點(diǎn)被服務(wù)的機(jī)會(huì)越大，故引入主觀偏好值Cr*，它表示決策者對(duì)車輛是否繼續(xù)服務(wù)下一個(gè)客戶點(diǎn)的態(tài)度偏好，從而規(guī)劃出相應(yīng)的初始計(jì)劃路線。當(dāng)Cr*取較小值時(shí)，決策者傾向于充分利用車輛的載重能力，不怕配送失敗的風(fēng)險(xiǎn)；反之，Cr*取較大值時(shí)，決策者希望盡可能地規(guī)避配送失敗的風(fēng)險(xiǎn)，此時(shí)車輛剩余載重量滿足下一個(gè)客戶點(diǎn)的需求量的可能性很大，配送失敗的可能性小。根據(jù)文獻(xiàn)[13]知Cr*∈(0,1]。在車輛服務(wù)客戶的過(guò)程中，當(dāng)Cr≥Cr*時(shí)，該車輛繼續(xù)完成下一個(gè)客戶的配送任務(wù)；當(dāng)Cr≤Cr*時(shí)，該車輛就近返回配送中心?？?，同時(shí)距離該配送失敗的客戶最近的配送中心，開始新派車完成剩余的運(yùn)輸任務(wù)；重復(fù)上述過(guò)程，直至所有客戶都被服務(wù)。

1.4 模型構(gòu)建

1.4.1 總配送成本函數(shù)

（1）車輛的固定成本Z1。其指的是參與配送車輛的基本保養(yǎng)損耗、司機(jī)工資等，與使用的車輛數(shù)目有關(guān)。

（2）車輛運(yùn)輸成本Z2。本研究主要指的是車輛行駛過(guò)程產(chǎn)生的成本，與運(yùn)輸距離呈正相關(guān)。

（3）車輛制冷成本Z3。冷鏈物流配送車輛一般是冷藏車，所以綜合考慮車輛行駛過(guò)程中和裝卸貨開門時(shí)，為了維持車廂內(nèi)的低溫，車廂的制冷系統(tǒng)產(chǎn)生的能耗。制冷能耗與溫差導(dǎo)致的熱負(fù)荷有關(guān)，對(duì)于運(yùn)輸途中，制冷成本與廂體隔熱壁滲入、廂體漏氣以及太陽(yáng)直射傳入車廂體內(nèi)部的熱負(fù)荷有關(guān)；裝卸貨時(shí)，考慮開門時(shí)的廂體隔熱壁和太陽(yáng)直射傳入廂體的熱負(fù)荷，而該部分熱負(fù)荷與車輛配送時(shí)的開門次數(shù)所附加的熱負(fù)荷系數(shù)相關(guān)。根據(jù)文獻(xiàn)[14]得出下列制冷成本計(jì)算公式：

表1 開門附加熱負(fù)荷系數(shù)Table 1 Additional thermal load factor of door opening

R為車輛傳熱系數(shù)，S1為車廂體受太陽(yáng)輻射面積，S1=(30%～40%)S，S為車廂傳熱面積，Tw為車廂外界空氣溫度，Tn為車廂內(nèi)的溫度，Ty為廂體受太陽(yáng)輻射后表面的平均溫度，Ty=Tw+20，t為車廂體每天受太陽(yáng)輻射的時(shí)間，一般為12～14 h；β為漏熱系數(shù)，tijk為第k輛車從節(jié)點(diǎn)i到節(jié)點(diǎn)j的運(yùn)輸時(shí)間，tsi為服務(wù)客戶點(diǎn)i所需時(shí)間。

（4）時(shí)間懲罰成本Z4。在最大可接受范圍內(nèi)，車輛到達(dá)客戶點(diǎn)的開始服務(wù)時(shí)間未在期望時(shí)間窗內(nèi)，會(huì)有相應(yīng)的懲罰成本。

懲罰成本函數(shù)：

則時(shí)間懲罰成本Z4為：

（5）碳排放成本Z5。冷鏈配送的車輛比普通貨車要消耗更多的燃料，進(jìn)一步產(chǎn)生大量的二氧化碳，所以考慮碳排放成本是分析冷鏈配送成本不可缺少的一部分。

則總成本函數(shù)F1為：

1.4.2 客戶滿意度函數(shù)

冷鏈產(chǎn)品配送對(duì)時(shí)間有嚴(yán)格的要求，時(shí)間不僅影響到產(chǎn)品的損耗，從而影響客戶對(duì)產(chǎn)品的滿意程度。

客戶i時(shí)間滿意度函數(shù)f(ti)：

所有客戶對(duì)時(shí)間的整體滿意度函數(shù)F2如下：

1.4.3 目標(biāo)函數(shù)量綱轉(zhuǎn)化

為了方便目標(biāo)函數(shù)標(biāo)準(zhǔn)化轉(zhuǎn)化，把客戶滿意度函數(shù)轉(zhuǎn)化為客戶不滿意度。

采用模糊數(shù)學(xué)方法對(duì)總成本函數(shù)F1和客戶不滿意度去標(biāo)量化。冷鏈物流配送路線的規(guī)劃對(duì)時(shí)間要求非常高，即使配送成本很低，但一旦產(chǎn)品腐爛了，客戶不滿意，那這條路線規(guī)劃就毫無(wú)意義，同時(shí)在日益激烈的市場(chǎng)競(jìng)爭(zhēng)中，較高的客戶滿意度是冷鏈企業(yè)提高自身競(jìng)爭(zhēng)力的關(guān)鍵因素之一[15]。故把配送總成本和客戶滿意度視為同等重要，即賦予相同的權(quán)重，讓決策者更好地根據(jù)自身情況去選擇合適的配送路線，此時(shí)多目標(biāo)函數(shù)問(wèn)題也轉(zhuǎn)化為單目標(biāo)優(yōu)化問(wèn)題，，量綱轉(zhuǎn)化后的總目標(biāo)函數(shù)為：

式（15）中，w1為冷鏈配送總成本的權(quán)重系數(shù)，w2為客戶不滿意度的權(quán)重系數(shù)，w1=w2=0.5。

1.5 約束條件

式（16）表示所使用的每輛車裝載量不超過(guò)車輛最大裝載量的可信性Cr不得小于主觀偏好值；式（17）表示每條路徑的車輛裝載量不得超過(guò)其最大載重量；式（18）表示所有配送中心安排的配送車輛數(shù)不得超過(guò)已有的車輛限制總數(shù)；式（19）表示每個(gè)客戶只能派一輛車服務(wù)；式（20）表示車輛到達(dá)客戶點(diǎn)開始服務(wù)時(shí)間必須在其最大容忍時(shí)間窗內(nèi)；式（21）表示車輛從某個(gè)配送中心出發(fā)，中途補(bǔ)貨或完成任務(wù)?？?，可回到任意中心。

2 算法設(shè)計(jì)

在某個(gè)主觀偏好值下，對(duì)于模糊需求，通過(guò)改進(jìn)遺傳-大鄰域搜索算法進(jìn)行求解得到初始計(jì)劃路線，然后根據(jù)隨機(jī)模擬算法得到客戶的實(shí)際需求；在已產(chǎn)生的初始可行路線方案中，根據(jù)載重約束，當(dāng)實(shí)際客戶需求得不到滿足時(shí)導(dǎo)致配送任務(wù)失敗，車輛就近返回配送中心重新裝貨再返回至任務(wù)失敗點(diǎn)繼續(xù)完成剩余任務(wù)，此時(shí)返回失敗點(diǎn)再服務(wù)，該點(diǎn)的開始服務(wù)時(shí)間變了，相應(yīng)的這條路線運(yùn)輸費(fèi)、制冷、懲罰成本以及滿意度都發(fā)生相應(yīng)的改變；最后，根據(jù)調(diào)整好的路線利用改進(jìn)遺傳算法進(jìn)行目標(biāo)函數(shù)分析，從而選擇最優(yōu)的配送路線。

2.1 改進(jìn)的遺傳-大鄰域搜索算法

MDVRPTWFD 問(wèn)題考慮的變量多而復(fù)雜，而傳統(tǒng)的遺傳算法收斂快，使其不能很好地得到最優(yōu)解。后期嵌入大規(guī)模鄰域算法是為了防止優(yōu)化過(guò)程中產(chǎn)生大量不可行解，降低求解效率，又避免了局部最優(yōu)。

2.1.1 染色體編碼

本研究采用實(shí)數(shù)編碼，對(duì)于MDVRPTWFD 問(wèn)題里包含|M|個(gè)客戶，|K|輛車，則定義染色體長(zhǎng)度為|M|+|K|-1，定義編號(hào)1～|M|為客戶點(diǎn)，大于|M|的數(shù)字編號(hào)作為路徑的分割點(diǎn)。例如假設(shè)有8個(gè)客戶，4輛車，編碼形式如圖1（a）；如果添加的分割點(diǎn)不能補(bǔ)齊個(gè)體染色體長(zhǎng)度，則后面繼續(xù)添加大于| |M的數(shù)字來(lái)補(bǔ)齊，如圖1（b）；這樣根據(jù)分割點(diǎn)可以劃分不同的配送路徑，再進(jìn)行路徑首末配送中心的匹配。

圖1 染色體編碼示意Fig.1 Chromosome decoding diagram

對(duì)于圖1（a）可以看出使用了3輛車，配送路徑為1-4-5，7-8-2，3-6；然后根據(jù)已有的配送中心，進(jìn)行路徑首末客戶點(diǎn)距離最小匹配。

2.1.2 初始種群的生成

在生成初始種群之前，先構(gòu)造MDVRPTWFD 問(wèn)題的初始可行解，本文基于最小成本的最鄰近法[2，16]、載重的可信性約束以及時(shí)間限制約束來(lái)構(gòu)造高質(zhì)量的可行解，然后將初始解合并生成初始化種群。采用上述編碼例子圖1（a），構(gòu)造的可行初始解為1-4-5，7-8-2，3-6；將其合并后用9～11 的數(shù)字編號(hào)來(lái)分割，即初始路徑合并后的初始種群為1-4-5-9-7-8-2-10-3-6-11，再對(duì)其進(jìn)行交叉、變異、選擇以及局部搜索操作。

最小成本的最鄰近法（NNC）的步驟如下：

步驟1派出一輛車進(jìn)行配送，關(guān)于起點(diǎn)選擇，文獻(xiàn)[2，16]是從配送中心出發(fā)，本文是在未訪問(wèn)的客戶點(diǎn)中隨機(jī)選擇一個(gè)節(jié)點(diǎn)開始遍歷搜索，該客戶點(diǎn)是滿足時(shí)間窗要求，若不滿足則換一個(gè)客戶點(diǎn)。

步驟2在未訪問(wèn)的客戶點(diǎn)中，選擇滿足約束條件的“距離成本”最小的節(jié)點(diǎn)，來(lái)插入到當(dāng)前車輛路徑中。

步驟3重復(fù)步驟2，若違反載重可信性或時(shí)間約束，把當(dāng)前路線存儲(chǔ)后，新派一輛車，重復(fù)步驟1、2、3的步驟；若所有客戶點(diǎn)被服務(wù)，則結(jié)束。

具體流程如圖2所示。

式中,Aij為客戶i，j的時(shí)間窗接近程度，指的是后一個(gè)節(jié)點(diǎn)的開始服務(wù)時(shí)間與前一個(gè)節(jié)點(diǎn)的完成服務(wù)時(shí)間之差；Uij表示客戶j的時(shí)間緊迫性，指的是客戶點(diǎn)j的最遲服務(wù)時(shí)間與其開始服務(wù)時(shí)間之差；tij為客戶點(diǎn)i到客戶點(diǎn)j的運(yùn)輸時(shí)間；Dij為客戶點(diǎn)i，j之間的距離成本，其大小用來(lái)衡量下一個(gè)客戶點(diǎn)的選擇，α1、α2、α3是大于0的權(quán)重系數(shù)，α1+α2+α3=1。

2.1.3 適應(yīng)度函數(shù)確定

傳統(tǒng)的適應(yīng)度函數(shù)計(jì)算是按比例計(jì)算的，在優(yōu)化過(guò)程中會(huì)陷入局部最優(yōu)，引用文獻(xiàn)[17]中的適應(yīng)度計(jì)算方法，將其變得具有隨機(jī)性。

F(x)表示個(gè)體x的目標(biāo)函數(shù)值，G(x)表示個(gè)體x的適應(yīng)度值；為了防止式（25）無(wú)意義，同時(shí)也在遺傳操作中更直觀地比較適應(yīng)度值大小，λ取（0，1）之間任意正實(shí)數(shù)[17]。

2.1.4 遺傳操作

（1）改進(jìn)的交叉操作：以構(gòu)造的可行初始解來(lái)初始化種群，生成的是一模一樣的種群個(gè)體，導(dǎo)致傳統(tǒng)的交叉操作不能適用了；所以根據(jù)交叉概率，先通過(guò)一定的改進(jìn)手段使所有種群不同化，再采用部分映射交叉[18]。具體改進(jìn)方法如下：首先在種群里，根據(jù)個(gè)體順序和交叉概率，依次去選擇兩個(gè)父代A、B，然后隨機(jī)生成兩個(gè)交叉點(diǎn)，將父代A 的交叉片段放到父代B 的尾部，父代B的交叉片段放到父代A的首部，刪掉不是交叉片段的重復(fù)基因，這樣就產(chǎn)生了差異化的父代個(gè)體，方便后續(xù)采用部分映射交叉，來(lái)產(chǎn)生新的子代。

（2）變異操作：采用逆序變異，根據(jù)變異概率去確定要變異的個(gè)體，隨機(jī)生成兩個(gè)變異點(diǎn)，將兩點(diǎn)之間的基因逆序生成新的個(gè)體。例如，[2 3 4 8 1 10 7]→[2 1 8 4 3 10 7]。

（3）選擇操作：采用輪盤賭和精英保留策略相結(jié)合的方法進(jìn)行選擇操作，其中精英保留策略是父代種群最優(yōu)值與新種群最優(yōu)值比較，選出當(dāng)前種群的最優(yōu)值；其次用父代種群的最優(yōu)解替換新種群中最差的個(gè)體，再進(jìn)行下一代的遺傳操作。

2.1.5 大規(guī)模鄰域搜索

遺傳算法在逐代優(yōu)化過(guò)程中，初始可行解的基因已經(jīng)被分解，重新解碼的路徑組合，存在大量不可行解，會(huì)導(dǎo)致收斂過(guò)快，陷入局部最優(yōu)，不能得出最好的最優(yōu)值。而大規(guī)模鄰域搜索算法（large neighborhood search，LNS）是對(duì)路徑間鄰域進(jìn)行破壞修復(fù)，簡(jiǎn)單來(lái)說(shuō)就是使用破壞算子在當(dāng)前解中移除若干個(gè)客戶，然后再使用修復(fù)算子將移除的客戶重新插入到被破壞的解中，從而獲得新的可行解。

（1）破壞算子

①載重約束移除算子。對(duì)當(dāng)前路徑的客戶點(diǎn)進(jìn)行逐步檢查，由于當(dāng)前路徑是在模糊需求情況下產(chǎn)生的，則對(duì)路徑中的每個(gè)客戶點(diǎn)進(jìn)行載重約束可信性判斷，然后把該個(gè)體的每條路徑中不滿足可信性約束的客戶點(diǎn)儲(chǔ)存。②時(shí)間窗約束移除算子。在載重約束移除算子的基礎(chǔ)上，還會(huì)存在路徑中某個(gè)點(diǎn)違反其最大容忍時(shí)間窗的情況，把違反的點(diǎn)儲(chǔ)存起來(lái)。

在使用以上兩個(gè)破壞算子后，可能原路徑上的客戶點(diǎn)被全移除了，則需要把路徑中可能為空的路徑刪除。

（2）修復(fù)算子

最優(yōu)距離插入算子：在滿足所有的約束條件基礎(chǔ)上，把每個(gè)移除點(diǎn)依次插入到路徑各個(gè)空隙，再計(jì)算此時(shí)的路線匹配中心后的距離增量，若存在合理的插入點(diǎn)，選出最小距離增量對(duì)應(yīng)的插入點(diǎn)和插入位置，否則新派一輛車。所有移除點(diǎn)選好最優(yōu)的插入位置后，采用最遠(yuǎn)插入啟發(fā)式來(lái)選擇哪個(gè)移除點(diǎn)先插入，然后把插入完成的點(diǎn)刪除，重復(fù)以上所有步驟，直至所有移除點(diǎn)全被插入到路徑中。其中最遠(yuǎn)插入式啟發(fā)式是將移除客戶點(diǎn)中最優(yōu)插入距離增量中最大的選出來(lái)，其對(duì)應(yīng)的移除點(diǎn)先被插入，這樣的做法是為了在插入時(shí)有隨機(jī)性。

2.2 隨機(jī)模擬算法

步驟1在客戶的模糊需求范圍內(nèi)隨機(jī)生成一個(gè)數(shù)δ并計(jì)算其隸屬度u(δ)，其中將q2i設(shè)置為qi，模糊需求范圍為((1-r)qi,qi,(1+r)qi)，取r=0.2。

步驟2在[0，1]范圍內(nèi)隨機(jī)生成一個(gè)數(shù)δ1。

步驟3若δ1≤u(δ)，則δ作為該客戶的模擬需求量，否則重復(fù)以上步驟，直至滿足要求。

步驟4重復(fù)步驟1～3，使所有客戶模擬得到實(shí)際需求量。

3 算法驗(yàn)證與算例分析

3.1 算法驗(yàn)證

采用MATLAB R2016b進(jìn)行算法編程，操作系統(tǒng)為windows10。不考慮模糊需求，利用本文的算法去解決文獻(xiàn)[19]的算例，文獻(xiàn)[19]是使用MDVRPTW 標(biāo)準(zhǔn)算例pr01，48 個(gè)客戶點(diǎn)，4 個(gè)配送中心；運(yùn)行10 次，取最優(yōu)解與文獻(xiàn)[19]的蟻群算法所得結(jié)果對(duì)比見表2。

表2 與文獻(xiàn)[19]的結(jié)果對(duì)比Table 2 Contrast with result of literature[19]

由表2 可知，在模型相同的條件下，本文算法求出的最優(yōu)解使用的車輛數(shù)是8，比文獻(xiàn)[19]多3 輛，因?yàn)槲墨I(xiàn)[19]考慮在配送時(shí)，車輛可以中途回到配送中心補(bǔ)貨，而本文算法思想是超過(guò)載重約束時(shí)，就返回任意中心，重新派車服務(wù)。但在成本方面，本文算法要優(yōu)于文獻(xiàn)[19]，總配送成本減少7.3%，實(shí)驗(yàn)結(jié)果證明了本文算法設(shè)計(jì)是合理有效的，并且同樣具有很好的尋優(yōu)性能，兩算法求解的最優(yōu)路線對(duì)比具體見表3，其中49～52 表示配送中心，本文算法求解的最優(yōu)路徑如圖3。

圖3 pr01算例的車輛路徑圖Fig.3 Vehicle path map of example pr01

表3 配送路線對(duì)比Table 3 Comparison of distribution route

3.2 算例分析

3.2.1 算例描述

假設(shè)某企業(yè)有3個(gè)貨物充足的物流配送中心，20個(gè)客戶點(diǎn)，其中每個(gè)配送中心有5輛型號(hào)相同的車輛，車輛最大載重量Q為3.5 t，配送中心之間的車輛是共享的，且總的車輛數(shù)最大為15。車輛平均速度v為40 km/h，每輛車的使用成本為300 元/輛，單位距離運(yùn)輸費(fèi)C2為5 元/km，制冷成本C3為11 元/kcal，漏熱系數(shù)β為0.25，車輛傳熱系數(shù)R為0.3 kcal/m2·h·℃，車廂傳熱面積S為35.77 m2，夏季車廂外界空氣溫度Tw為32 ℃，車廂內(nèi)溫度Tn為5 ℃，廂體每天受太陽(yáng)輻射時(shí)間t為13 h，早到懲罰成本C4為6元/h，晚到懲罰成本C5為11元/h，單位碳排放成本Ce為0.2 元/kg，二氧化碳排放系數(shù)Cd為2.65 kg/L，單位距離燃油消耗量P1為0.16 L/km，車輛每天早上6點(diǎn)從配送中心出發(fā)。算法參數(shù)設(shè)置如下：種群大小取100，最大迭代次數(shù)取200，交叉概率Pc=0.7，變異概率Pm=0.3，λ=0.2；經(jīng)多次測(cè)試，最小成本的最鄰近法中α1=0.5，α2=0.3，α3=0.2。配送中心和客戶點(diǎn)的位置是在[-100，100]范圍里隨機(jī)生成的，具體信息見表4，其中編號(hào)1～20為客戶點(diǎn)，21～23節(jié)點(diǎn)表示配送中心。

表4 客戶和配送中心信息表Table 4 Customer and distribution center information sheet

3.2.2 運(yùn)行結(jié)果分析

為了驗(yàn)證多配送中心在冷鏈物流配送中的有效性，將單配送中心與多配送中心配送模式進(jìn)行對(duì)比分析，設(shè)置以上算例中編號(hào)23 為單配送模式的中心，主觀偏好值=0.3，運(yùn)行10次，取最優(yōu)解，兩模式對(duì)比分析情況見表5，而表6和圖4分別為多配送中心模式下的最優(yōu)路線和最優(yōu)路徑示意圖。

從表5 可以看出兩配送模式所派的車輛數(shù)是一樣的，客戶滿意度相差不大，但在配送成本方面，多配送中心模式使運(yùn)輸總成本降低了23.24%，完成運(yùn)輸任務(wù)的總距離減少了28.68%，總目標(biāo)函數(shù)值減少了18.27%；多配送中心能共享資源，大幅度減少車輛往返距離，從而降低配送成本。因此在配送成本和客戶滿意度同等重要情況下，多配送中心配送模式要優(yōu)于單配送中心模式。

其中圖4 的虛線部分表示在考慮模糊需求的情況下，該路徑得知實(shí)際需求后，發(fā)生配送失敗，就近返回中心補(bǔ)貨了，實(shí)線則是沒(méi)有發(fā)生配送失敗情況。

3.2.3 算法對(duì)比分析

以相同的參數(shù)設(shè)置條件，采用普通遺傳算法進(jìn)行多目標(biāo)冷鏈物流模糊機(jī)會(huì)約束模型求解，運(yùn)行10 次，取最優(yōu)解，求解結(jié)果是派遣8 輛車，最優(yōu)配送成本為151 130.62，客戶滿意度為0.949 5。而采用改進(jìn)的遺傳-大規(guī)模鄰域算法求解，使配送成本減少了13.89%，客戶滿意度提高了3.53%。圖5給出了兩算法總目標(biāo)函數(shù)值的迭代圖，可以看出，本研究設(shè)計(jì)的改進(jìn)算法，避免了陷入局部最優(yōu)現(xiàn)象，能更全面更深入尋找最優(yōu)解，而且在保證全局最優(yōu)同時(shí)，加速了收斂速度。

圖5 總目標(biāo)函數(shù)對(duì)比迭代圖Fig.5 Total objective function contrastiteration diagram

4 參數(shù)敏感性分析

表7 不同下的優(yōu)化結(jié)果Table 7 Optimization result of different

表7 不同下的優(yōu)化結(jié)果Table 7 Optimization result of different

表8 在0.5～0.6之間的優(yōu)化結(jié)果Table 8 optimization result between 0.5 and 0.6

表8 在0.5～0.6之間的優(yōu)化結(jié)果Table 8 optimization result between 0.5 and 0.6

（2）漏熱系數(shù)β的大小影響著成本函數(shù)，以上述冷鏈物流的MDVRPTWFD 算例中參數(shù)β=0.25 為基礎(chǔ)，且在其他參數(shù)條件不變情況下，上下波動(dòng)5%、10%，運(yùn)行10次取平均值，見表9。

表9 漏熱系數(shù)β 對(duì)各目標(biāo)值的影響Table 9 Effect of heat leakage coefficient β on each target value

從表9 可知，漏熱系數(shù)的增大，相應(yīng)的總成本增大或減少，因?yàn)榭偝杀局械闹评涑杀居绊懸蛩夭粌H僅只考慮漏熱，相應(yīng)運(yùn)輸時(shí)間、附加熱負(fù)荷等都是要根據(jù)路徑變化所考慮的。所以選擇合適的漏熱系數(shù)對(duì)冷鏈物流路徑規(guī)劃是有必要的。

5 結(jié)束語(yǔ)

本研究針對(duì)冷鏈物流配送情況下，對(duì)MDVRPTWFD問(wèn)題進(jìn)行研究，并設(shè)計(jì)了改進(jìn)遺傳算法-大鄰域搜索算法求解，通過(guò)算法對(duì)比和算例分析來(lái)驗(yàn)證其有效性。結(jié)果表明：（1）考慮到冷鏈配送的特殊性，在配送成本分析方面考慮得很全面，并引入當(dāng)下倡導(dǎo)的碳排放成本，為冷鏈物流路徑規(guī)劃研究提供了新思路。（2）冷鏈物流配送過(guò)程中采用多配送中心模式，在保證客戶高滿意度的同時(shí)，減少了車輛的無(wú)效調(diào)度，降低了配送成本。（3）模型參數(shù)影響著優(yōu)化結(jié)果，尤其在考慮需求不確定時(shí)，討論決策者的主觀偏好值是十分有必要的。（4）本文設(shè)計(jì)的改進(jìn)遺傳算法-大鄰域搜索算法具有良好的尋優(yōu)能力，加速了收斂，尋優(yōu)速度快。

未來(lái)將進(jìn)一步把不斷變化的交通情況所引起的時(shí)變車速考慮進(jìn)去，車速的變化會(huì)導(dǎo)致到達(dá)時(shí)間和油耗的改變，進(jìn)而引起配送成本變化，使研究更貼近實(shí)際。