多車型冷鏈物流配送車輛的路徑優(yōu)化

孫國(guó)華，屈冉冉

(1.山東財(cái)經(jīng)大學(xué) 管理科學(xué)與工程學(xué)院，山東 濟(jì)南 250014；2.天津大學(xué) 管理與經(jīng)濟(jì)學(xué)部，天津 300072)

一、引言

冷鏈物流是使貨物始終處于規(guī)定低溫環(huán)境下，保持貨物品質(zhì)、減少貨物損耗的一種快速物流模式[1]。近年來，我國(guó)冷鏈物流發(fā)展迅速，2018 年冷鏈物流市場(chǎng)規(guī)模近3 000 億元，預(yù)計(jì)2020 年將達(dá)到4 700 億元，復(fù)合增速達(dá)21.5%[2]。作為冷鏈物流的一個(gè)重要環(huán)節(jié)，冷鏈物流配送被認(rèn)為是物流行業(yè)中的“最后一塊蛋糕”。通過科學(xué)合理的優(yōu)化冷鏈物流配送車輛路徑，可以實(shí)現(xiàn)降低配送成本，保證冷鏈產(chǎn)品質(zhì)量，提高客戶滿意度的目標(biāo)，因此，研究冷鏈物流配送車輛路徑優(yōu)化問題具有十分重要的實(shí)踐價(jià)值。

冷鏈物流配送是近年來的一個(gè)研究熱點(diǎn)，研究主要集中在考慮配送時(shí)間或者客戶滿意度的單車型冷鏈物流配送車輛路徑優(yōu)化問題。Hsu 和Chen[3]針對(duì)不同溫度要求的食品，研究了車隊(duì)規(guī)模與配送調(diào)度優(yōu)化問題。Govindan 等[4]研究了易腐品供應(yīng)鏈網(wǎng)絡(luò)中帶有時(shí)間窗的選址—車輛路徑優(yōu)化問題。Yu 等[5]研究了易腐食品冷鏈配送問題，以成本最低及滿足客戶對(duì)各種食品的預(yù)先質(zhì)量要求為目標(biāo)，對(duì)冷鏈?zhǔn)称返呐渌蛦栴}進(jìn)行了優(yōu)化建模。Zhang 和Chen[6]以最小化運(yùn)輸成本為目標(biāo)，研究了多種不同特性冷凍食品的共同配送問題。Song和Ko[7]針對(duì)易腐食品的城市配送問題，建立了非線性規(guī)劃模型并設(shè)計(jì)了啟發(fā)式算法。吳瑤和馬祖軍[8]對(duì)時(shí)變路網(wǎng)環(huán)境下帶時(shí)間窗的易腐品生產(chǎn)—配送集成調(diào)度問題進(jìn)行了研究，建立了混合整數(shù)規(guī)劃模型，并采用混合遺傳算法進(jìn)行了求解。丁秋雷等[9]建立了鮮活農(nóng)產(chǎn)品冷鏈物流配送的干擾管理模型，并采用混合蟻群算法進(jìn)行求解，生成了使系統(tǒng)擾動(dòng)較小的調(diào)整調(diào)度方案。以上研究通常假設(shè)采用單一車型的車輛提供配送服務(wù)，這與實(shí)際中企業(yè)通常采用多種不同車型的車輛提供配送服務(wù)具有一定的差距。因此，已有研究并不完全適用于解決實(shí)際中的多車型冷鏈物流配送車輛路徑優(yōu)化問題。

目前，有關(guān)多車型混合車輛路徑問題的研究已有很多成果，Brandao[10]運(yùn)用禁忌搜索算法研究了多車型車輛路徑優(yōu)化問題。Penna 等[11]在迭代局部搜索算法中引入了變鄰域下降搜索程序與隨機(jī)鄰域排序，并用于解決多車型車輛路徑優(yōu)化問題。Leung 等[12]運(yùn)用帶有局部搜索的模擬退火方法，求解了裝載空間具有二維裝載約束的多車型車輛路徑優(yōu)化問題。Kopfer 等[13]研究了碳排放量最小的多車型車輛路徑問題，發(fā)現(xiàn)采用混合車型進(jìn)行配送可以極大地降低碳排放量。Dominik 和Michael[14]考慮了電動(dòng)商用車和傳統(tǒng)燃油車共存的多車型車輛路徑優(yōu)化問題。潘雯雯等[15]研究了需求可拆分的多車型車輛路徑優(yōu)化問題，提出了路徑優(yōu)化和路徑改進(jìn)相結(jié)合的兩階段算法，對(duì)建立的混合整數(shù)規(guī)劃模型進(jìn)行了求解。田宇等[16]對(duì)集送貨一體化的多車型車輛路徑問題進(jìn)行了研究，并提出了一種基于多屬性標(biāo)簽的蟻群算法。上述研究主要針對(duì)常溫商品的配送，而生鮮產(chǎn)品的配送具有很強(qiáng)的時(shí)效性，因此上述研究并不完全適用于解決冷鏈物流配送車輛路徑優(yōu)化問題。

針對(duì)冷鏈物流配送車輛路徑優(yōu)化問題，本文將在考慮多種車型共存的前提下，構(gòu)建整數(shù)規(guī)劃模型，設(shè)計(jì)基于大車優(yōu)先原則和滿載優(yōu)先原則的遺傳算法對(duì)模型進(jìn)行求解，并采用實(shí)驗(yàn)數(shù)據(jù)與仿真實(shí)例驗(yàn)證算法的有效性。

二、模型構(gòu)建

(一) 問題描述

某冷鏈物流公司擁有一個(gè)配送中心和多種車型(載重量和運(yùn)輸成本不同)的車輛，并負(fù)責(zé)向區(qū)域內(nèi)若干客戶配送生鮮產(chǎn)品。配送車輛的最大載重量和配送時(shí)限已知，配送中心和客戶的地理位置、客戶的需求量確定。配送優(yōu)化目標(biāo)為：合理安排車輛配送路徑，在保證滿足車載容量約束、車輛數(shù)約束及車輛行駛時(shí)間約束的前提下，使得總配送費(fèi)用最小。

(二)模型假設(shè)

1.配送中心庫(kù)存量可滿足所有客戶需求；

2.配送中心有K種車型的冷藏車，車輛數(shù)足夠完成配送任務(wù)，且車載容量大于單個(gè)客戶的需求量；

3.車輛從配送中心出發(fā)，完成配送任務(wù)后返回配送中心；

4.由于生鮮產(chǎn)品具有很強(qiáng)的時(shí)效性，車輛必須在規(guī)定時(shí)限內(nèi)完成配送任務(wù)；

5.客戶需求不可分割，每個(gè)客戶需被一輛車服務(wù)，且只能被服務(wù)一次。

(三)模型符號(hào)

1.標(biāo)號(hào)

i，j：節(jié)點(diǎn)標(biāo)號(hào)；

n：客戶的個(gè)數(shù)；

k：表示第k種車型的車輛；

l：表示第k種車型的第l輛車。

2.模型使用參數(shù)

G ＝(V，A，D) ：冷鏈物流配送網(wǎng)絡(luò)；

V ＝{0 }∪Vc：節(jié)點(diǎn)集，其中0 代表配送中心，Vc ＝{1，...，n} 為客戶點(diǎn)集；

A ＝{(i，j)｜i，j∈V，i≠j} ：有向??；

K：車輛類型集；

dij：節(jié)點(diǎn)i到j(luò)的距離，i，j∈V；

Lk ＝{1，2，...，Mk} ：第k種車型的車輛集合，其中Mk為第k種車型的車輛數(shù)；

ck：第k種車型車輛的單位運(yùn)輸成本；

fk：第k種車型車輛的固定成本，主要包括駕駛員的工資成本和車輛折舊成本；

Qk：第k種車型車輛的車載容量；

qi：客戶i的需求量；

tij：節(jié)點(diǎn)i到j(luò)的行駛時(shí)間；

si：客戶i需要的服務(wù)時(shí)間；

T：車輛運(yùn)行時(shí)間上限；

：節(jié)點(diǎn)i在車輛k行駛路徑中的位勢(shì)。

3.決策變量

(四)多車型冷鏈物流配送車輛路徑優(yōu)化模型構(gòu)建

由以上的問題描述和假設(shè)條件，構(gòu)建以運(yùn)輸成本最低為目標(biāo)的冷鏈物流配送車輛路徑優(yōu)化模型，具體如下：

公式(1)為目標(biāo)函數(shù)，表示最小化總配送成本，其中第一部分是可變運(yùn)輸成本，第二部分是車輛的固定成本；式(2)和式(3)保證每個(gè)客戶均被某種車型的某輛車服務(wù)一次；式(4)保證駛?cè)肟蛻鬸與駛出客戶點(diǎn)j的是同一輛車；式(5)保證每種車型的使用數(shù)量不大于該種車型的車輛總數(shù)Mk；式(6)保證每輛車不違反車載容量約束；式(7)保證配送車輛在規(guī)定時(shí)間內(nèi)完成配送任務(wù)；式(8)保證配送路徑中不包含子回路；式(9)定義了變量的取值范圍。

三、算法設(shè)計(jì)

車輛路徑問題是經(jīng)典的NP-hard 問題，運(yùn)用精確算法無(wú)法在較短時(shí)間內(nèi)得到最優(yōu)解，因此有必要采用智能算法對(duì)所研究的問題進(jìn)行求解。由于冷鏈物流配送系統(tǒng)存在多種車型，首先需要解決的問題就是車型選擇問題。從減少車輛數(shù)降低車輛固定成本的角度，應(yīng)該優(yōu)先使用大車；從提高車輛利用率的角度，應(yīng)該優(yōu)先考慮車輛滿載。因此，本文提出了大車優(yōu)先和滿載優(yōu)先兩種原則，并與遺傳算法相結(jié)合對(duì)所研究的問題進(jìn)行了求解。

大車優(yōu)先原則：在安排車輛時(shí)，依據(jù)車載容量的大小，優(yōu)先給車載容量大的車輛分配任務(wù)，在所有大車均被分配配送任務(wù)后，再考慮給車載容量小的車輛分配任務(wù)。這樣做的好處是可以減少配送車輛數(shù)，降低車輛固定成本，容易實(shí)現(xiàn)配送的規(guī)模經(jīng)濟(jì)。

滿載優(yōu)先原則：在安排車輛時(shí)，依據(jù)客戶累積需求量的大小，優(yōu)先將相應(yīng)的客戶分配給滿載率高的車型。這樣做的好處是提高了車輛利用率，減少了車輛的空駛距離。

(一)編碼與解碼

采用基于客戶直接排序的自然數(shù)編碼方式編碼，將配送中心設(shè)定為編號(hào)0，各個(gè)客戶按照1，2，…，n進(jìn)行編號(hào)，自然數(shù)的排列順序表示車輛訪問客戶的順序。popsize ＝N表示種群中有N個(gè)個(gè)體。

基于大車優(yōu)先的解碼機(jī)制：針對(duì)每一個(gè)后代，在不違反車輛行駛時(shí)間的前提下，依據(jù)排序?qū)蛻舻男枨罅窟M(jìn)行累加，優(yōu)先考慮是否違反未安排任務(wù)的大車的車載容量限制，如果不違反，則將客戶分配給相應(yīng)的大車服務(wù)，否則，重新累加，并將客戶安排給車載容量小的車輛服務(wù)。重復(fù)該步驟，直至所有的客戶都被納入車輛路徑中。

基于滿載優(yōu)先的解碼機(jī)制：針對(duì)每一個(gè)后代，在不違反車輛行駛時(shí)間的前提下，依據(jù)排序?qū)蛻舻男枨罅窟M(jìn)行累加，優(yōu)先考慮是否達(dá)到某種車型車輛車載容量的P比例(P∈[0.95，1])，如果該車型有車輛未被安排配送任務(wù)，則停止累加，并將客戶分配給相應(yīng)的車輛服務(wù)；否則，繼續(xù)累加；重復(fù)該步驟，直至所有客戶被納入車輛路徑中。

(二)適應(yīng)度函數(shù)設(shè)計(jì)

由于多車型冷鏈物流配送車輛路徑優(yōu)化問題以總配送費(fèi)用最小為目標(biāo)函數(shù)，因此取fitness ＝為適應(yīng)度函數(shù)，利用其評(píng)價(jià)個(gè)體的好壞。適用度越高，說明總配送費(fèi)用越小，對(duì)應(yīng)的個(gè)體越好。

(三)遺傳算子的設(shè)計(jì)

1.選擇算子

采用適應(yīng)度比例方法對(duì)個(gè)體進(jìn)行選擇，淘汰率為Ps。淘汰適應(yīng)度較小的個(gè)體，適應(yīng)度較高的個(gè)體則直接復(fù)制到下一代，這樣可以減少算法的操作個(gè)數(shù)，提高總體的運(yùn)算速度。

2.交叉算子

采用部分匹配交叉策略PMX 完成交叉操作。

(1)根據(jù)均勻隨機(jī)分布產(chǎn)生兩個(gè)基因交叉點(diǎn)，定義這兩點(diǎn)之間區(qū)域?yàn)橐黄ヅ鋮^(qū)域，如A＝3 4 6 ｜8 1 2 ｜9 7 5，B ＝2 7 1 ｜9 5 3 ｜6 4 8。

(2)使用位置交換操作交換兩個(gè)父串的匹配區(qū)域，得到：A1＝3 4 6 ｜9 5 3 ｜9 7 5，B1＝2 7 1 ｜8 1 2 ｜6 4 8。

(3)對(duì)于A1和B1兩個(gè)子串中匹配區(qū)域以外出現(xiàn)的重復(fù)節(jié)點(diǎn)，依據(jù)匹配區(qū)域內(nèi)位置映射關(guān)系進(jìn)行逐一交換。對(duì)A1匹配區(qū)域以外的9、5、3 分別以8、1、2 替換得：A2＝2 4 6 ｜9 5 3 ｜8 7 1，同理，B2＝3 7 5 ｜8 1 2 ｜6 4 9。

3.變異算子

個(gè)體采用對(duì)調(diào)變異策略，通過在個(gè)體中隨機(jī)選取兩個(gè)變異點(diǎn)，將兩點(diǎn)的基因值進(jìn)行交換，其中個(gè)體變異的概率為Pm。

(四)終止準(zhǔn)則

采用進(jìn)化代數(shù)gen ＝T作為循環(huán)迭代終止的條件，如果gen ＞T則算法結(jié)束，輸出適應(yīng)度值最高的解，否則，重復(fù)上述過程。

(五)算法步驟

遺傳算法步驟如圖1 所示：

圖1 遺傳算法步驟

四、實(shí)驗(yàn)仿真

(一)數(shù)值實(shí)驗(yàn)

為了驗(yàn)證算法的有效性，通過隨機(jī)生成的算例進(jìn)行了實(shí)驗(yàn)仿真，在Intel(R)Core(TM)i5-6200U 2.30GHZ CPU，4GB RAM 和64 位Windows 7 操作系統(tǒng)的機(jī)器上，針對(duì)規(guī)模為5～9 的冷鏈物流配送車輛路徑優(yōu)化問題，隨機(jī)生成客戶及配送中心的距離矩陣，并采用本文設(shè)計(jì)的算法各運(yùn)行了10 次。

在數(shù)值算例中，配送中心有兩種車型，其固定成本分別為f1和f2。其中，遺傳算法參數(shù)設(shè)置為：popsize ＝150，gen＝500，Ps＝0.2，Pm＝0.3。

仿真結(jié)果由表1 和表2 所示，其中表1 給出了每種算法的平均計(jì)算時(shí)間，表2 給出了每種算法同精確算法相比的平均相對(duì)誤差(相對(duì)誤差＝絕對(duì)誤差/最優(yōu)值×100%)。

表1 算法的平均計(jì)算時(shí)間 單位：秒

表2 平均相對(duì)誤差

由表1 可以看出，隨著節(jié)點(diǎn)規(guī)模的增大，精確算法所需的計(jì)算時(shí)間急劇增加，當(dāng)節(jié)點(diǎn)數(shù)為9 時(shí)，精確算法的計(jì)算時(shí)間已經(jīng)超過30 分鐘，而C-W 節(jié)約算法與遺傳算法都可以在較短時(shí)間內(nèi)求得較優(yōu)解。由表2 可以看出，不論是基于大車優(yōu)先還是滿載優(yōu)先的原則，遺傳算法求解的解整體優(yōu)于C-W 節(jié)約算法求解的解。進(jìn)一步分析發(fā)現(xiàn)，基于大車優(yōu)先原則與基于滿載優(yōu)先原則在不同情形下各具優(yōu)勢(shì)。當(dāng)不同車型的車輛固定成本相差較小時(shí)，基于大車優(yōu)先原則的算法求出的結(jié)果平均相對(duì)誤差較小，即大車優(yōu)先原則較優(yōu)；當(dāng)不同車型的車輛固定成本相差較大時(shí)，基于滿載優(yōu)先原則的算法求得的結(jié)果相對(duì)誤差較小，即滿載優(yōu)先原則較優(yōu)。說明大車優(yōu)先原則適用于不同車型車輛固定成本相差較小的情形，滿載優(yōu)先原則適用于不同車型車輛固定成本相差較大的情形。

(二)H 物流公司仿真實(shí)例

為了進(jìn)一步驗(yàn)證算法的有效性，利用本文設(shè)計(jì)的算法對(duì)H 冷鏈物流公司的實(shí)際問題進(jìn)行了求解。

1.基本數(shù)據(jù)

H 冷鏈物流公司是位于B 市的一家第三方冷鏈物流公司，占地約5 600 平方米，主要為市內(nèi)的37 家便利店提供冷鏈物流配送服務(wù)。目前，公司自有4.2 米與3.5 米兩種車型的廂式冷藏貨車負(fù)責(zé)配送，兩種車型在市區(qū)內(nèi)平均運(yùn)行速度均為30 千米/小時(shí)；車輛晚上11 點(diǎn)出發(fā)開始執(zhí)行配送任務(wù)，次日凌晨7 點(diǎn)完成配送任務(wù)返回配送中心。

配送中心和客戶的位置如圖2 所示(其中H 處為H 物流公司位置，其他標(biāo)記為便利店位置)。

圖2 配送中心和客戶位置分布

車輛信息如表3 所示。

表3 車輛信息

配送中心編號(hào)為0，其位置經(jīng)緯度為(116.354 667，39.817 295)。部分客戶的位置、訂單需求量、服務(wù)時(shí)間等信息如表4 所示(客戶從1 開始編號(hào))。

表4 部分客戶數(shù)據(jù)

2.車輛路徑優(yōu)化方案

基于上述數(shù)據(jù)，采用本文設(shè)計(jì)的算法進(jìn)行了求解，具體配送路線如圖3～圖6 所示，不同配送方案的總費(fèi)用如表5 所示。

從圖3～圖6 可以看出，基于大車優(yōu)先的C-W 節(jié)約算法得到的配送方案共使用6 輛A 型冷藏車進(jìn)行配送服務(wù)，基于滿載優(yōu)先的C-W 節(jié)約算法得到的調(diào)度方案共使用7 輛車進(jìn)行配送，其中4 輛A 型車，3 輛B 型車?；诖筌噧?yōu)先的遺傳算法在第476 代求得最優(yōu)解，求得的方案需要5 輛A 型車；滿載優(yōu)先的遺傳算法在第486 代求得最優(yōu)解，求得的方案需要7 輛車進(jìn)行配送，其中3 條路線由A 型車配送，4 條路線由B 型車配送。不難看出，基于大車優(yōu)先原則的C-W 節(jié)約算法和遺傳算法求得的配送方案分別比基于滿載優(yōu)先原則的C-W 節(jié)約算法及遺傳算法需要的車輛更少且費(fèi)用較少。對(duì)比四個(gè)方案的運(yùn)輸費(fèi)用可以看到，不論是基于大車優(yōu)先還是滿載優(yōu)先的原則，遺傳算法求解的解整體優(yōu)于C-W 節(jié)約算法求解的解。因此，針對(duì)這個(gè)實(shí)例，遺傳算法求得的配送方案結(jié)果更優(yōu)。

圖3 基于大車優(yōu)先的C-W 節(jié)約算法生成的配送線路

圖4 基于滿載優(yōu)先的C-W 節(jié)約算法生成的配送線路

圖5 基于大車優(yōu)先的遺傳算法生成的配送線路

圖6 基于滿載優(yōu)先的C-W 節(jié)約算法生成的配送線路

表5 總運(yùn)輸費(fèi)用 單位：元

五、結(jié)論

本文針對(duì)冷鏈物流配送系統(tǒng)中存在多種車型的情形，構(gòu)建了整數(shù)規(guī)劃模型研究了冷鏈物流配送車輛路徑優(yōu)化問題。由于車輛路徑問題為經(jīng)典的NP-Hard 問題，精確算法無(wú)法在短時(shí)間內(nèi)得到最優(yōu)解，因此設(shè)計(jì)了基于大車優(yōu)先原則和滿載優(yōu)先原則的遺傳算法對(duì)所研究的問題進(jìn)行求解。為了驗(yàn)證算法的有效性，采用實(shí)驗(yàn)數(shù)據(jù)與仿真實(shí)例對(duì)算法的有效性進(jìn)行了驗(yàn)證，并與精確算法和基于大車優(yōu)先與滿載優(yōu)先的C-W 節(jié)約算法進(jìn)行了比較。研究發(fā)現(xiàn)：基于兩種原則的遺傳算法均可以在較短時(shí)間內(nèi)得到可行解，而且相對(duì)C-W 節(jié)約算法，可行解的相對(duì)誤差更??；當(dāng)不同車型車輛固定成本相差較小時(shí)，基于大車優(yōu)先原則的遺傳算法所得配送方案更優(yōu)，當(dāng)不同車型車輛固定成本相差較大時(shí)，基于滿載優(yōu)先原則的遺傳算法所得配送方案更優(yōu)。最后，將提出的算法應(yīng)用于H 冷鏈物流公司的實(shí)際配送中，發(fā)現(xiàn)基于大車優(yōu)先原則和滿載優(yōu)先原則的遺傳算法求得的配送方案比相應(yīng)的C-W 節(jié)約算法求得的方案更優(yōu)，進(jìn)一步驗(yàn)證了提出的遺傳算法的有效性。

本文研究的冷鏈物流配送車輛路徑優(yōu)化問題只考慮了配送時(shí)間限制，在今后的研究中將進(jìn)一步考慮制冷成本、貨損成本等因素對(duì)車輛路徑的影響。