基于同時取送貨的多溫共配冷鏈車輛路徑優(yōu)化

胡 衛(wèi)，梁承姬，樊陸彬

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

?

基于同時取送貨的多溫共配冷鏈車輛路徑優(yōu)化

胡 衛(wèi)，梁承姬，樊陸彬

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

為降低成本，提高效率，提出了多溫共配冷鏈車輛路徑優(yōu)化問題。在同時取送貨的基礎(chǔ)上，充分考慮了多溫共配運(yùn)輸過程中的特性以及配送節(jié)點(diǎn)的時間窗約束，構(gòu)建了基于VRPDSP的機(jī)械式冷凍區(qū)隔車多溫共配模型。利用遺傳算法(GA)，設(shè)計了適合于求解問題模型的染色體編碼方式以及遺傳算子。最后對算例進(jìn)行求解，結(jié)果表明多溫層冷鏈配送模式能夠有效解決多溫貨物配送問題，且對比傳統(tǒng)的冷鏈配送模式，總成本降低了45.72%。

取送結(jié)合；多溫共配；車輛路徑問題；遺傳算法；時間窗

0 引 言

車輛路徑問題(vehicle routing problem,VRP)最早由Dantzig和Ramser提出，目前已經(jīng)成為運(yùn)輸配送中的核心問題，其中冷鏈品的車輛路徑規(guī)劃是在該理論基礎(chǔ)上發(fā)展起來的。隨著冷鏈物流業(yè)的高速發(fā)展，冷鏈品的配送優(yōu)化也成為國內(nèi)外學(xué)者所關(guān)注的焦點(diǎn)，不僅構(gòu)建出了冷鏈品配送的數(shù)學(xué)模型，而且運(yùn)用啟發(fā)式優(yōu)化算法對配送路徑進(jìn)行優(yōu)化[1-8]。Gendreau等[9]提出六種啟發(fā)式算法求解帶回程取貨的旅行商問題。郭伏等[10]對傳統(tǒng)的VRPB問題進(jìn)行改進(jìn)，不限制車輛的取送貨順序，避免了貨物的重新排列，設(shè)計了先通過分支定界及遺傳算法確定可行路線，再運(yùn)用整數(shù)規(guī)劃方法求解的算法，對改進(jìn)后的VRPB問題進(jìn)行了研究。陳幼林[11]針對回程取貨的車輛路徑問題，分別研究了有無時間窗的VRPB問題，用遺傳算法和蟻群算法求解。李淑琴等[12]建立帶軟時間窗約束的多車型車輛路徑優(yōu)化模型，設(shè)計了模擬退火算法，進(jìn)行仿真，通過對參數(shù)進(jìn)行敏感性分析，研究不同環(huán)保性能車輛的影響。李露蓉等[13]在路徑規(guī)劃模型中考慮到了交通信息的不確定性，并將基于優(yōu)化蟻群算法的動態(tài)路徑規(guī)劃模型與傳統(tǒng)動態(tài)路徑模型進(jìn)行比較。

上述文獻(xiàn)通過不同的角度對冷鏈配送問題以及VRPB問題進(jìn)行了研究，成果頗豐。但是針對帶同時取送貨的多溫共配車輛路徑問題尚不多見。本文以機(jī)械式冷凍區(qū)隔車輛的總成本最小化為目標(biāo)函數(shù)，建立冷鏈車輛路徑優(yōu)化模型，考慮到客戶節(jié)點(diǎn)對取貨和送貨需求的不同，結(jié)合同時取送貨的車輛路徑基本模型，用遺傳算法進(jìn)行求解，對車輛進(jìn)行調(diào)度優(yōu)化。

在傳統(tǒng)的冷鏈配送模式中，按照溫度通常將貨物分為常溫貨、冷藏貨和冷凍貨，則與之對應(yīng)的配送車輛分別為常溫車、冷藏車和冷凍車，不同溫度的貨物采用相應(yīng)的配送車輛進(jìn)行配送。這種配送模式，造成了車輛的專用性，從而大大降低了車輛的使用效率，同時也增加了成本。機(jī)械式冷凍區(qū)隔車輛無疑滿足了消費(fèi)者多樣化、個性化的配送需求，同時增加了車輛的使用效率，進(jìn)而節(jié)省了配送費(fèi)用。

遺傳算法是一種基于生物自然選擇與遺傳機(jī)理的隨機(jī)搜索算法[14]，最早由Holland[15]提出。遺傳算法是通過對初始種群進(jìn)行選擇、交叉和變異的演化過程，最后達(dá)到最優(yōu)或近似最優(yōu)解。因而，作為一種相對高效的人工智能算法，遺傳算法在解決大規(guī)模VRP問題上具有自身獨(dú)特的優(yōu)勢。

1 模型建立

本文研究了以機(jī)械式冷凍區(qū)隔車總成本作為目標(biāo)函數(shù)，構(gòu)建基于同時取送貨的多溫共配冷鏈車輛路徑優(yōu)化模型。機(jī)械式冷凍車廂區(qū)隔車將車廂通過用絕緣材料分成常溫區(qū)、冷藏區(qū)和冷凍區(qū)三個溫區(qū)，通過制冷機(jī)提供貨物所需的溫度。相比較傳統(tǒng)冷鏈配送模式而言，機(jī)械式冷凍區(qū)隔車實(shí)現(xiàn)了多溫貨物的共同配送，從而降低了成本。

1.1 問題描述

本文所研究的冷鏈車輛配送模型是單一配送中心配送多個客戶，配送中心配送常溫貨、冷藏貨和冷凍貨三種不同溫度的貨物，配送這三種貨物的車輛是機(jī)械式冷凍區(qū)隔車輛，這三種產(chǎn)品除了溫度不同其他參數(shù)都相同。在配送過程中的車輛需要符合如下約束條件,每輛車及各溫層區(qū)必須符合相應(yīng)的容量限制，每個客戶節(jié)點(diǎn)只能受到一次服務(wù)，且每個客戶節(jié)點(diǎn)都有時間窗限制等。根據(jù)這些約束條件，計算最小車輛總成本，并得出最優(yōu)化的車輛行駛路徑。

1.2 模型假設(shè)

假設(shè)每輛車只能從唯一的一個配送中心出發(fā)且只有一條配送線路；每輛車在配送過程中的裝載量不能大于車的容量；車的數(shù)量不限；最大容量已知；配送中心到各客戶節(jié)點(diǎn)的位置和距離已知；每個客戶的取送貨量都已知；每個客戶節(jié)點(diǎn)的時間窗己知；僅對貨物的重量有要求而不考慮尺寸大小及整理時間；機(jī)械式冷凍區(qū)隔車輛中的冷藏區(qū)和冷凍區(qū)能夠滿足低溫貨物對于溫度的需求，且所有車輛的容量相同。

1.3 參數(shù)定義

表1 不同外界溫度對應(yīng)不同的α1

表2 常用的u值

1.4 數(shù)學(xué)模型

帶同時取送貨的多溫共配車輛配送成本包括：運(yùn)輸成本，配送過程中的能源成本，開關(guān)車門所消耗的能源成本，低溫貨物的貨損成本與固定成本。

車輛在配送過程中的運(yùn)輸成本和車輛行駛距離成正比，通常包含有車輛定時養(yǎng)護(hù)費(fèi)用、隨時維修的費(fèi)用、耗油量等成本。則運(yùn)輸成本為：

(1)

在機(jī)械式冷凍區(qū)隔車的運(yùn)輸過程中，消耗的能源成本包含了冷藏區(qū)和冷凍區(qū)。制冷成本主要產(chǎn)生在運(yùn)輸過程中制冷劑的消耗，以及開關(guān)門過程中熱量的散失。在運(yùn)輸過程中，主要影響能源消耗的因素有不同溫層區(qū)的內(nèi)外溫差、冷藏區(qū)和冷凍區(qū)內(nèi)外表面積、制冷劑的價格和單位時間消耗量、傳熱系數(shù)等，運(yùn)輸所消耗的能源公式為：

(2)

開關(guān)車門所消耗的能源公式為：

(3)

在實(shí)際配送過程中，低溫貨物發(fā)生貨損的條件分為兩個部分，一為在運(yùn)輸途中的累計時間造成的貨損成本，時間越久貨損越多；二為發(fā)生裝卸活動時，車門的開關(guān)使外部空氣進(jìn)入低溫層區(qū)后溫度上升，導(dǎo)致車內(nèi)冷藏貨物因此而造成的貨損。貨損成本為：

(4)

冷鏈車輛的固定成本是指每一輛冷藏車輛在執(zhí)行每一次配送任務(wù)時所產(chǎn)生的包含有駕駛員工資、車輛與制冷設(shè)備固定損耗等固定支出。假設(shè)配送中心總共擁有冷藏配送車K輛，第k輛配送車輛的固定成本為fk，則總固定成本為：

(5)

綜上，目標(biāo)函數(shù)為：

(6)

約束條件為：

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

ei≤bi≤li, ?i∈N,

(17)

式(6)表示目標(biāo)函數(shù)，運(yùn)輸成本，配送過程中的能源成本，冷藏貨物的貨損成本與固定成本之和；式(7)表示決策變量的整數(shù)限制為0或者1；式(8)表示每個客戶節(jié)點(diǎn)只能被服務(wù)一次，且只能被一輛車來服務(wù)；式(9)表示每輛車的運(yùn)輸路線是以配送中心為起點(diǎn)出發(fā)，最終回到配送中心，且車輛的數(shù)量始終相等；式(10)～式(12)表示機(jī)械式冷凍區(qū)隔車各溫層區(qū)的容量不能小于每條線路中相應(yīng)溫層貨物的送貨需求量；式(13)～式(15)表示機(jī)械式冷凍區(qū)隔車各溫層區(qū)的容量不能小于每條線路中相應(yīng)溫層貨物的取貨需求量；式(16)保證配送中配送流量守恒，最優(yōu)化結(jié)果中行駛路線只有一條；式(17)表示時間窗限制。

2 算法的設(shè)計

針對本文建立數(shù)學(xué)模型，對染色體編碼與解碼、交叉變異算子、適應(yīng)度函數(shù)等要素進(jìn)行設(shè)計。對約束條件的處理分為兩個步驟，在染色體的編碼及解碼環(huán)節(jié)，主要考慮車輛的容量約束進(jìn)行染色體的解碼；在適應(yīng)度評價環(huán)節(jié)，在目標(biāo)函數(shù)的基礎(chǔ)上加入懲罰函數(shù)，對不滿足時間窗約束的解施以較大的懲罰，以此來過濾掉不滿足時間窗約束的解并獲取優(yōu)質(zhì)解。

2.1 編碼與解碼方式

編碼時，生成1～20的自然數(shù)隨機(jī)排列，作為配送車輛遍歷節(jié)點(diǎn)的順序。解碼時，需要根據(jù)單車的容量約束來進(jìn)行。車輛從配送中心出發(fā)，若第1至第i-1個節(jié)點(diǎn)的各溫層貨物需求量之和，都在單車的容量限度內(nèi)，而第1至第i個節(jié)點(diǎn)各溫層貨物需求量之和超過了單車的容量限度，則該車輛的遍歷中止點(diǎn)為第i-1個節(jié)點(diǎn)，配送完畢后返回配送中心。下一車次的遍歷從第i個節(jié)點(diǎn)開始，依次類推，直到遍歷完所有的節(jié)點(diǎn)。解碼的過程一方面給出了滿足容量約束的可行路徑;另一方面確定了對應(yīng)的車輛數(shù)量。

圖1 染色體編碼及解碼方式示意圖

2.2 交叉算子

交叉算子在遺傳算法中起著核心的作用，為選擇操作不斷提供新的個體。它使得算法能夠搜索新的基因空間，從而使得新的群體中的個體具有多樣性。如圖2所示，首先，在父代1中隨機(jī)選擇3個基因位上的基因值，將其復(fù)制到子代相同基因位上；然后去掉父代2中與父代1所選基因值相同的基因；最后將父代2中剩余基因位上的基因按順序依次填入子代1中，如果遇到某一基因位上已經(jīng)存在基因值，則跳過該基因位繼續(xù)填入下一個位置。

圖2 交叉算子示意圖

2.3 變異算子

變異算子是按照一定的變異概率用新的基因值替代舊的基因值，改變了染色體的基因鏈，通過這種對染色體的局部進(jìn)行修改的方式，從而保證種群多樣性。變異算子的作用是幫助輔助進(jìn)化，防止出現(xiàn)早熟現(xiàn)象。如圖3所示，在父代中隨機(jī)選擇兩個基因位上的基因，然后互換這兩個基因位上的基因，得到子代。

圖3 變異算子示意圖

2.4 適應(yīng)度函數(shù)

遺傳算法中，衡量一個個體質(zhì)量優(yōu)劣的標(biāo)準(zhǔn)是適應(yīng)度，它的設(shè)計要結(jié)合求解問題的本身要求來定。一般是以所求問題的目標(biāo)函數(shù)來確定，解的適應(yīng)度函數(shù)值是遺傳操作過程中進(jìn)行選擇操作的主要依據(jù)。本文在目標(biāo)函數(shù)的基礎(chǔ)上加上懲罰函數(shù)，作為適應(yīng)度函數(shù)，并假定染色體適應(yīng)度值越小，被選擇到下一代的概率越大。適應(yīng)度函數(shù)表達(dá)式如式(18)。

(18)

其中，M為懲罰系數(shù)，本文取M=10 000，對于不滿足時間窗約束[ei,bi]的染色體來說，它的適應(yīng)度函數(shù)會很大，因此在選擇操作中，將被舍棄。

3 算例實(shí)驗(yàn)

算例數(shù)據(jù)如表3所示，編號0代表配送中心。編號1～20代表20個配送節(jié)點(diǎn)。整車的最大載貨量為60件，其中常溫貨貨區(qū)、冷藏貨貨區(qū)、冷凍貨貨區(qū)的最大容量都為20。單位車輛啟動成本為fk=150元/次；制冷劑的價格a1=2元/kg；單位運(yùn)輸成本C=2.5元/km；單位貨物價值c=150元/件；單位時間內(nèi)制冷劑的消耗量α1=0.14；傳熱系數(shù)u=0.2；機(jī)械式冷凍車的低溫層區(qū)車廂內(nèi)外面積平均值1.6 m2，且車門面積sv=1 m2；單位貨物在配送過程中的單位時間損耗比例β1=0.001 5，單位貨物在裝卸過程中的單位時間損耗比例β2=0.025；外界常溫溫度為20 ℃，冷藏溫層區(qū)車廂內(nèi)溫度為-18 ℃，冷凍溫層區(qū)車廂內(nèi)溫度為-10 ℃。

基于以上算例，利用遺傳算法進(jìn)行求解。其中，種群規(guī)模設(shè)置為100，最大迭代次數(shù)為200，交叉概率取0.8，變異概率取0.1。經(jīng)過多次運(yùn)行該算法，得到的最優(yōu)解都為3 522.57元，算法的收斂情況如圖4所示。

圖4 算法收斂圖

節(jié)點(diǎn)編號坐標(biāo)常溫貨物冷藏貨物冷凍貨物X軸Y軸送貨量/件取貨量/件送貨量/件取貨量/件送貨量/件取貨量/件裝卸時間/s時間窗/seili03535020014149103110612182351721304010495935545305011101021124552051202010192951530301041912113062530313120101391497205050401212103115810433121209374695560502011979881030603010509324111206541221010768612503530401081251331330254120401169801415102140301056661530520315213223516102041412012778917530205031119911018204052122113152819156011105086270204565322022115667

運(yùn)算得出成本最低的配送方案如表4，該方案需要4輛車。

表4 模型的配送路徑

最優(yōu)配送方案的路線如圖5所示。

最優(yōu)配送方案的甘特圖如圖6所示，矩形方框上面的編號代表配送節(jié)點(diǎn)的編號，0代表配送中心。從圖6中可以得出每個節(jié)點(diǎn)的車輛到達(dá)時間、停留時間和離開時間，以及每輛車完成配送任務(wù)返回配送中心的時間。該方案能夠使配送車輛在客戶節(jié)點(diǎn)的時間窗約束內(nèi)進(jìn)行配送，且每輛車的配送完成時間符合配送中心的時間窗約束。

圖5 最優(yōu)車輛路徑安排方案示意圖

圖6 最優(yōu)配送方案甘特圖

傳統(tǒng)的冷鏈配送模式下，配送三種溫層貨物類型則需要三種車型來實(shí)現(xiàn)?；谖闹兴憷?，對20個客戶節(jié)點(diǎn)的貨物需求進(jìn)行配送，在滿足時間窗約束及車輛容量約束的前提下，需要常溫車2輛，冷藏車2輛，冷凍車2輛，總成本為6 489.88元。而多溫層冷鏈共配模式下使用的機(jī)械式冷凍區(qū)隔車，一種車型能同時配送三種溫層貨物，完成上述20個客戶節(jié)點(diǎn)的配送任務(wù)，需要的車輛數(shù)目為4，總成本為3 522.57元，相較傳統(tǒng)冷鏈配送模式，總成本降低了45.72%。具體的成本對比，如表5所示：

表5 多溫層冷鏈共配模式與傳統(tǒng)冷鏈配送模式的對比

同時，為了驗(yàn)證該遺傳算法的有效性，在Matlab環(huán)境下加載YALMIP優(yōu)化工具箱，調(diào)用Cplex對算例模型重新求解，求得最終的成本目標(biāo)函數(shù)值為3 475.75，運(yùn)算時間為212.11 s。如表6所示，本文遺傳算法(GA)獲得的近似最優(yōu)解與Cplex求得的較為精確的解相比，相差不大，而且求解速度上有明顯的優(yōu)勢，這說明了上文中遺傳算法的設(shè)計是有效的。

表6 兩種算法的比較

4 結(jié) 論

將冷鏈車廂分隔成常溫區(qū)、冷藏區(qū)和冷凍區(qū)的多溫層冷鏈配送模式大大提高了多溫貨物冷鏈配送能力。本文以同時取送貨的車輛路徑問題為基礎(chǔ)，充分考慮了冷鏈貨物運(yùn)輸過程中的特性，構(gòu)造了包含運(yùn)輸成本、配送過程中的制冷成本、貨損成本，以及車輛固定成本的目標(biāo)函數(shù)。并且根據(jù)客戶節(jié)點(diǎn)對貨物溫度、和送取貨需求量的不同，配備含有不同溫區(qū)的機(jī)械式冷凍區(qū)隔車輛，利用遺傳算法對算例進(jìn)行求解，得到了最優(yōu)的配送方案，該方案的車輛數(shù)量為4，最終的配送成本為3 522.57元，對比傳統(tǒng)冷鏈配送模式，無論是車輛數(shù)量上還是配送成本上都有很大的優(yōu)勢。這也表明了多溫層冷鏈配送模式能夠有效解決同時取送貨的多溫貨物配送問題，而且是一種低成本的冷鏈配送模式。最后，利用Cplex對算例重新編寫代碼并求解，進(jìn)一步驗(yàn)證了本文算法的有效性。

[1] HU X,WANG Z,HUANG M, et al.A computer-enabled solution procedure for food wholesalers’ distribution in cities with a circular transportation infrastructure[J]. Computers & Operations Research,2009,36(7):2001-2209.

[2] CHENG C, WANG K.Solving a vehicle routing problem with time windows by a decomposition technique and a genetic algorithm[J]. Export Systems with Applications,2009,36(5):7758-7763.

[3] AMORIM P,BELO-FILHO M A F,TOLEDO F M B, et al.Lot sizing versus batching in the production and distribution planning of perishable goods[J]. International Journal of Production Economics,2013,146(1):208-218.

[4] SHUKLA M,JHARKHARIA S.Artificial Immune systembased algorithm for vehicle routing problem with time window constraint for the delivery of agri-fresh produce[J]. Journal of Decision Systems,2013,22(3),224-247.

[5] 王海麗,王勇,曾永長.帶時間窗的易腐食品冷藏車配送問題[J]. 工業(yè)工程,2008,11(3)：127-130.

[6] 繆小紅,周新年,林森,等.第三方冷鏈物流配送路線優(yōu)化研究[J]. 運(yùn)籌與管理,2011,20(4):32-38.

[7] 王淑云,趙敏.蓄冷式冷鏈物流多溫共配的動力機(jī)制[J]. 公路交通科技,2012,29(2):144-148.

[8] 石兆,符桌.時變網(wǎng)絡(luò)條件下帶時間窗的視頻冷鏈配送定位—運(yùn)輸路徑優(yōu)化問題[J]. 計算機(jī)應(yīng)用研究,2013,30(1):183-188.

[9] GENDREAU M, HERTZ A, LAPORTE G.Traveling salesman problem with backhauls[J]. Computers and Operations Research,1996,23(2):501-508.

[10]郭伏,龍穎.帶時間窗回程取貨的車輛路徑問題的算法[J]. 東北大學(xué)學(xué)報(自然科學(xué)版),2006,27(5):575-578.

[11]陳幼林.考慮回程的車輛配送模型研究[D]. 上海:同濟(jì)大學(xué),2006.

[12]李淑琴,楊斌,趙磊,等.需求帶時間窗的環(huán)保多車型組合配送路徑優(yōu)化[J]. 廣西大學(xué)學(xué)報(自然科學(xué)版),2012,32(2):388-394.

[13]李露蓉，王蕾,高應(yīng)波,等.基于優(yōu)化蟻群算法的動態(tài)路徑規(guī)劃問題研究[J]. 廣西大學(xué)學(xué)報(自然科學(xué)版),2013,38(2):359-366.

[14](日)玄光男,程潤偉,汪定偉,等譯.遺傳算法與工程設(shè)計[M]. 北京:科學(xué)出版社, 2000.

[15]HOLLAND J H.Adaptations in Natural and Artificial Systems[M]. University of Michigan Press, Ann Arbor, 1976.

(責(zé)任編輯 梁碧芬)

Optimization of multi-temperature joint-delivery based on simultaneous pickup and delivery

HU Wei, LIANG Cheng-ji, FAN Lu-bin

(Logistics Research Center, Shanghai Maritime University, Shanghai 201306,China)

To reduce costs and improve efficiency, the multi-temperature joint-delivery vehicle routing problem is studied. On the basis of simultaneous pickup and delivery, taking full account of the characteristics of multi-temperature joint-delivery and the time window constraint of delivery node, a multi-temperature joint-delivery model based on VRPDSP for mechanical separated freezer compartments vehicle is established. Then a genetic algorithm whose chromosome coding and genetic operators are designed to suit for solving the above model. Finally, the solution results of a given example shows that the multi-temperature layer cold chain distribution pattern can effectively solve the problem, and the total cost is reduced 45.72% compared to the traditional cold chain distribution model.

simultaneous pickup and delivery; multi-temperature joint-delivery; vehicle routing problem; genetic algorithm; time window

2016-04-01；

2016-05-29

國家自然科學(xué)基金資助項(xiàng)目(71471110；71301101；61540045)；上海市重點(diǎn)學(xué)科資助項(xiàng)目(J50604)；陜西省社會科學(xué)基金資助項(xiàng)目(2015D060)

梁承姬(1970—)，女(朝鮮族)，吉林龍井市人，上海海事大學(xué)教授；E-mail：liangcj@shmtu.edu.com。

胡衛(wèi)，梁承姬，樊陸彬.基于同時取送貨的多溫共配冷鏈車輛路徑優(yōu)化[J].廣西大學(xué)學(xué)報(自然科學(xué)版)，2016，41(5)：1576-1584.

10.13624/j.cnki.issn.1001-7445.2016.1576

U491

A

1001-7445(2016)05-1576-09