考慮交通情況的疫苗冷鏈物流路徑優(yōu)化

杜茂康，朱容嘉，陳 樹(shù)（重慶郵電大學(xué)，重慶 400065）

0 引言

醫(yī)療是降低死亡率的主要手段。由于疫苗的特殊性，在運(yùn)輸和儲(chǔ)存過(guò)程中面臨各種風(fēng)險(xiǎn)，必須低溫保存才能保證質(zhì)量。車(chē)輛配送在整個(gè)物流系統(tǒng)是非常重要的一個(gè)環(huán)節(jié)，所以如何合理地規(guī)劃配送路線對(duì)于提高車(chē)輛的配送效率及減少配送成本是企業(yè)亟待解決的問(wèn)題[1]。

目前，已有部分國(guó)內(nèi)外學(xué)者針對(duì)冷鏈物流配送路徑的優(yōu)化選擇問(wèn)題進(jìn)行了研究。其中Kumar 等[2]將綠色供應(yīng)鏈概念整合到醫(yī)藥冷鏈物流行業(yè)的發(fā)展中。Yan 等[3]評(píng)估了不同企業(yè)條件對(duì)更好的配送路線規(guī)劃的影響。袁志遠(yuǎn)等[4]構(gòu)建了多種藥品集中配送成本的最優(yōu)模型。丁艷[5]在綜合考慮時(shí)間、成本、風(fēng)險(xiǎn)的前提下，構(gòu)建了多溫共配冷鏈物流車(chē)輛配送路徑優(yōu)化模型。Yang 等[6]綜合研究了醫(yī)藥供應(yīng)鏈的安全方案。周鮮成等、趙志學(xué)等、徐梅等、狄衛(wèi)民等[7-10]在構(gòu)建模型時(shí)，不僅考慮了貨物的損壞成本、制冷成本和車(chē)輛的運(yùn)輸成本，還加入了碳排放成本和懲罰成本為目標(biāo)進(jìn)行配送路徑的優(yōu)化研究，并采用了改進(jìn)后的蟻群算法、遺傳算法和模擬退火算法等進(jìn)行求解計(jì)算。Songyi Wang 等[11]在優(yōu)化求解的同時(shí)引入碳稅政策，分析了碳稅對(duì)配送過(guò)程中的總成本和碳排放量的影響。Bamakan 等[12]將區(qū)塊鏈技術(shù)應(yīng)用到冷鏈物流領(lǐng)域，保障了商品流通的安全性。張浩等[13]總結(jié)了醫(yī)藥冷鏈物流的特征，并用魚(yú)骨分析法研究進(jìn)行分析，提出了多方面改進(jìn)的方法，以減少“斷鏈”帶來(lái)的經(jīng)濟(jì)損失。Mandziuk 等[14]在研究考慮道路擁堵情況路徑優(yōu)化問(wèn)題時(shí)，將靜態(tài)的問(wèn)題轉(zhuǎn)化為動(dòng)態(tài)問(wèn)題即具有時(shí)間不確定性及因素不確定性的配送車(chē)輛的調(diào)度問(wèn)題。賈永基等[15]使用“Wait-and-see”的策略對(duì)動(dòng)態(tài)的需求建模并針對(duì)結(jié)果進(jìn)行求解分析，然后建立混合的靜態(tài)子問(wèn)題的優(yōu)化模型。

本文的研究在此基礎(chǔ)上充分考慮實(shí)際城市交通路網(wǎng)的時(shí)變特性、物流配送活動(dòng)中成本過(guò)高和低碳環(huán)保的前提下，在滿足配送點(diǎn)時(shí)間約束、配送車(chē)輛負(fù)載約束等條件下，合理地規(guī)劃配送路線以達(dá)到減少運(yùn)輸成本、降低二氧化碳排放量和提高顧客滿意度的目的。

1 問(wèn)題描述及模型構(gòu)建

1.1 問(wèn)題描述及假設(shè)

1.1.1 問(wèn)題描述

考慮車(chē)輛的通行環(huán)境對(duì)配送路徑產(chǎn)生的影響，本文基于一個(gè)三級(jí)的物流網(wǎng)絡(luò)，包含疫苗供應(yīng)商、疫苗冷藏庫(kù)（中轉(zhuǎn)站）及各疫苗接種點(diǎn)三個(gè)層次，選取一個(gè)共同的配送中心即疫苗冷藏庫(kù)向多個(gè)疫苗接種點(diǎn)進(jìn)行配送，考慮交通情況及配送需求，實(shí)現(xiàn)以最低的配送成本完成配送任務(wù)。

1.1.2 問(wèn)題假設(shè)

（1）只有一個(gè)配送中心且配送中心擁有足夠多的車(chē)輛來(lái)滿足客戶的配送需求；（2）一個(gè)客戶只能接受一輛車(chē)的配送服務(wù)，同一輛車(chē)可配送多個(gè)客戶；（3）所有客戶都要被服務(wù)；（4）冷藏車(chē)在完成配送的任務(wù)后立刻返回配送中心；（5）每個(gè)客戶的需求量均小于車(chē)輛的最大載重量；（6）客戶的需求量、各節(jié)點(diǎn)的坐標(biāo)及服務(wù)時(shí)間已知；（7）運(yùn)輸車(chē)輛要在規(guī)定的時(shí)間窗內(nèi)完成配送，否則將會(huì)受到相應(yīng)的懲罰；（8）車(chē)輛在同一時(shí)間段的速度是恒定的，在不同時(shí)間段的速度不同。

1.1.3 模型參數(shù)及決策變量

（1）模型參數(shù)

配送中轉(zhuǎn)站的集合為M=｛m|m=1,2,…,M ｝；需求點(diǎn)的集合為D=｛i|i=1,2,…,N,i≠j ｝；車(chē)輛的集合為K=｛k|k=1,2,…,K ｝；S 表示車(chē)輛的固定成本；t 表示運(yùn)輸周期數(shù)（月）；K 表示運(yùn)輸車(chē)輛總數(shù)；fm表示中轉(zhuǎn)站m 的單位周期內(nèi)單次的租賃費(fèi)用；F 表示單位周期內(nèi)中轉(zhuǎn)站的租賃費(fèi)用結(jié)算次數(shù)；tij表示車(chē)輛從客戶點(diǎn)i 到客戶點(diǎn)j 之間的行駛時(shí)間；tj表示車(chē)輛到達(dá)客戶點(diǎn)j 的時(shí)間點(diǎn)；dij表示客戶點(diǎn)i 到客戶點(diǎn)j 的距離；v0表示配送車(chē)輛實(shí)時(shí)行駛的速度；λ0表示單位距離的運(yùn)輸成本；qij表示客戶點(diǎn)i 到客戶點(diǎn)j的運(yùn)輸量；qj表示客戶點(diǎn)的需求量；Q 表示車(chē)輛的最大載重量；p 表示醫(yī)藥產(chǎn)品的單位成本；C0表示碳稅；D 表示車(chē)輛每公里燃油的消耗量；θ 表示燃油的碳排放系數(shù)；ρ 表示配送醫(yī)用產(chǎn)品時(shí)單位時(shí)間的貨損比例；a1表示早到的等待成本系數(shù)；a2表示晚到的懲罰成本系數(shù)；［hj,ej］表示客戶期望的時(shí)間窗；［Hj,Ej］表示客戶的最大容忍時(shí)間窗。

（2）決策變量

1.2 模型構(gòu)建

本文研究的是一種基于時(shí)變速度的疫苗冷鏈物流車(chē)輛路徑優(yōu)化問(wèn)題，總目標(biāo)函數(shù)為綜合配送的最小總成本，總成本包含車(chē)輛的運(yùn)輸成本、貨物的損壞成本、碳排放成本、配送中心的倉(cāng)儲(chǔ)成本及時(shí)間窗懲罰成本。

1.2.1 運(yùn)輸成本

車(chē)輛的變動(dòng)成本主要包括車(chē)輛使用過(guò)程中所消耗的燃油成本，和車(chē)輛的行駛距離呈正相關(guān)的關(guān)系。固定成本主要包括配送司機(jī)的勞務(wù)費(fèi)用及車(chē)輛的損耗、維修費(fèi)用等成本。

1.2.2 配送中心的（即中轉(zhuǎn)站）倉(cāng)儲(chǔ)成本

配送中心的倉(cāng)儲(chǔ)成本主要是指租賃冷藏庫(kù)所需要花費(fèi)的成本。

1.2.3 碳排放成本

碳排放成本是車(chē)輛在行駛過(guò)程中由于燃油消耗所產(chǎn)生的CO2帶來(lái)的成本。

1.2.4 貨損成本

貨損成本主要是因?yàn)榕渌瓦^(guò)程中長(zhǎng)時(shí)間的累計(jì)而導(dǎo)致的部分商品的損耗所帶來(lái)的成本。

1.2.5 時(shí)間窗懲罰成本

時(shí)間窗懲罰成本是指商品沒(méi)有在規(guī)定的時(shí)間窗內(nèi)送達(dá)，早到或者晚到所產(chǎn)生的懲罰成本。

以總成本最小為目標(biāo)函數(shù)的數(shù)學(xué)模型：

上述模型中，式（7）為總成本最小的目標(biāo)函數(shù)；式（8）至式（14）為約束條件；其中約束條件（8）表示車(chē)輛的運(yùn)輸量不超過(guò)車(chē)輛的最大載重量；約束條件（9）表示一個(gè)客戶點(diǎn)只能被一輛車(chē)服務(wù)；約束條件（10）表示配送車(chē)輛到達(dá)客戶點(diǎn)的時(shí)間必須在最大的容忍時(shí)間窗內(nèi)；約束條件（11）表示配送車(chē)輛從配送中心出發(fā)完成配送的任務(wù)后必須要返回到配送中心；約束條件（12）表示一輛車(chē)只能選擇一條配送路線行駛；約束條件（13）表示保證各配送階段時(shí)間的連續(xù)性；約束條件（14）表示配送的路線數(shù)不能大于車(chē)輛數(shù)。

2 算法流程

VRP 問(wèn)題屬于較難的NP 問(wèn)題，而考慮實(shí)際的交通情況并帶有時(shí)間窗的這種情況更為復(fù)雜，所以在求解問(wèn)題上具有較大的難度。傳統(tǒng)的優(yōu)化算法是從單個(gè)的初始解開(kāi)始進(jìn)行迭代來(lái)求得最優(yōu)解，這樣容易陷入局部最優(yōu)的情況。自適應(yīng)遺傳算法是從串集開(kāi)始進(jìn)行搜索，覆蓋面更大，更有利于全局擇優(yōu)。

所以本文使用自適應(yīng)遺傳算法來(lái)求解問(wèn)題，編碼格式為：車(chē)輛部分+路線部分。

步驟1 采用隨機(jī)的方式產(chǎn)生100 個(gè)個(gè)體，并保證這些個(gè)體是有效的解并計(jì)算每個(gè)個(gè)體的適應(yīng)度值，這里選用成本作為適應(yīng)度值。

步驟2 使用保優(yōu)策略。設(shè)保優(yōu)率為10%，將適應(yīng)度值最大的前10%個(gè)個(gè)體直接作為一下代種群中的個(gè)體。

步驟3 進(jìn)行選擇操作。使用輪盤(pán)賭算法，從100 個(gè)個(gè)體中挑選出2 個(gè)個(gè)體，分布表示為X 和Y。

步驟4 對(duì)X 和Y 進(jìn)行交叉。交叉策略為，對(duì)車(chē)輛信息部分采用單點(diǎn)交叉，對(duì)線路信息部分采用雙點(diǎn)交叉，具體描述如下：

單點(diǎn)交叉：假設(shè)X 中使用了x 輛車(chē)，Y 中使用了y 輛車(chē)，且x＞y。隨機(jī)產(chǎn)生一個(gè)0,［ ］y 的值，假設(shè)為r。將車(chē)輛信息中，X和Y 中車(chē)輛信息段中的前r 個(gè)元素保留，將X 和Y 信息段中的前r 個(gè)元素之后信息段進(jìn)行交換。

雙點(diǎn)交叉：隨機(jī)產(chǎn)生兩個(gè)在（0,1 5）區(qū)間的數(shù)，假設(shè)為a 和b，不妨設(shè)a←b。這樣路線被劃分為了3 段，即第1 點(diǎn)到第a-1點(diǎn)，第a 點(diǎn)到第b 點(diǎn)，第b+1 點(diǎn)到第N 點(diǎn)。將個(gè)體X 和Y 中路線部分的第二段（第a 點(diǎn)到第b 點(diǎn)）進(jìn)行交換。

步驟5 對(duì)交叉后的個(gè)體，進(jìn)行變異操作。變異只針對(duì)路線部分進(jìn)行，隨機(jī)選出兩個(gè)點(diǎn)，將它們的位置進(jìn)行交換。

步驟6 保證新產(chǎn)生個(gè)體的有效性。此時(shí)需要根據(jù)編碼規(guī)則，檢查車(chē)輛的裝載量是否能夠保證大于其對(duì)應(yīng)線路中服務(wù)點(diǎn)的需求之和。如果滿足該條件，則不做任何的變化。如果不滿足則需要調(diào)整車(chē)輛所對(duì)應(yīng)的服務(wù)點(diǎn)數(shù)。

步驟7 將步驟3～6 產(chǎn)生的新的個(gè)體加入到下一代的種群中。重復(fù)步驟3～6，持續(xù)產(chǎn)生新的個(gè)體，直到下一代種群中個(gè)體的數(shù)量達(dá)到100 為止。

步驟8 重復(fù)步驟7，持續(xù)產(chǎn)生子代，當(dāng)達(dá)到800 代時(shí)結(jié)束。將800 代時(shí)，種群中適應(yīng)度值最大的個(gè)體即為問(wèn)題的解。若有多個(gè)個(gè)體適應(yīng)度值最大，則一起輸出，作為多個(gè)可供選擇的方案。

3 算例分析

3.1 初始數(shù)據(jù)

以重慶某醫(yī)藥冷鏈配送中心為例，使用冷藏車(chē)向20 個(gè)客戶點(diǎn)進(jìn)行配送，配送的產(chǎn)品為冷鏈藥品中的新冠疫苗。令各客戶點(diǎn)的位置在以配送中心為圓心半徑為25km 的圓內(nèi)隨機(jī)生成，配送中心即疫苗冷藏庫(kù)的坐標(biāo)點(diǎn)為（20km，10km）。考慮實(shí)際情況適當(dāng)?shù)貙?duì)各疫苗接種點(diǎn)的需求及服務(wù)時(shí)間做假設(shè)，并且在一定區(qū)間內(nèi)隨機(jī)生成各疫苗接種點(diǎn)的需求量及服務(wù)時(shí)間；在6:00—13:00 內(nèi)隨機(jī)生成各疫苗接種點(diǎn)的時(shí)間窗；考慮擁堵情況，不同時(shí)區(qū)下車(chē)輛的行駛速度不同，假設(shè)車(chē)輛暢通時(shí)的速度為40km/h。具體數(shù)據(jù)如表1、表2 所示，不同時(shí)區(qū)下車(chē)輛的平均速度如圖1 所示。

圖1 不同時(shí)區(qū)下車(chē)輛的平均速度

表1 客戶點(diǎn)的信息表

表2 模型的相關(guān)參數(shù)表

算法的參數(shù)設(shè)置為：種群規(guī)模NP=100，最大迭代次數(shù)maxgen=800，最大交叉概率Pcmax=0.95，最小交叉概率Pcmin=0.6，最大變異概率Pmmax=0.2，最小變異概率Pmmin=0.1，精英比例Pe=0.1。

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

用MATLAB 軟件對(duì)算例進(jìn)行多次運(yùn)算，結(jié)果如圖2、圖3 和表3 所示。

從表3 的車(chē)輛到達(dá)各客戶點(diǎn)的時(shí)間可知，在考慮交通情況下，只有車(chē)輛7 進(jìn)入了早高峰的最擁堵時(shí)段，并且車(chē)輛7 服務(wù)的客戶數(shù)最多，達(dá)到了6 個(gè)，同時(shí)也滿足了時(shí)間窗及確保了適應(yīng)度最小的要求；在不考慮交通情況下，車(chē)輛2、3、4、6 均進(jìn)入了早高峰最擁堵的時(shí)段。從圖2、圖3 和表3 的車(chē)輛行駛路徑和配送總成本可知，不考慮交通情況下的最優(yōu)路徑有6 條且配送總成本為22 375.26 元，考慮交通情況下的最優(yōu)路徑有7 條且配送總成本為19 709.93 元，相比于不考慮交通情況總成本降低了11.91%。兩者都是以總成本最小化為目標(biāo)，但是不考慮交通情況下的配送成本比考慮交通情況下的配送成本更高，前者是在理想的狀態(tài)下建模，后者則把實(shí)際的配送情況考慮進(jìn)去。說(shuō)明本文提出的方法能夠在一定程度上合理地避免擁堵情況，能夠提高車(chē)輛的配送效率、減少車(chē)輛的配送成本。

表3 運(yùn)行結(jié)果

圖2 未考慮交通情況

圖3 考慮交通情況

4 結(jié)論

本文研究考慮實(shí)時(shí)路況的疫苗冷鏈物流路徑優(yōu)化問(wèn)題，綜合考慮了運(yùn)輸成本、配送中心的倉(cāng)儲(chǔ)成本、碳排放成本、貨損成本、時(shí)間窗懲罰成本，構(gòu)建了優(yōu)化模型，用自適應(yīng)遺傳算法進(jìn)行求解，結(jié)果表明本文構(gòu)建的模型能夠在一定程度上避免擁堵并且降低配送成本，可為物流企業(yè)提供參考。本文的單位貨損比例取值為固定值0.01，后續(xù)可考慮不同藥品的單位時(shí)間貨損比例的差異，做進(jìn)一步研究。