時(shí)變路網(wǎng)下城市醫(yī)藥冷鏈路徑優(yōu)化研究

廖道爭(zhēng)?王江?潘宇

摘要：針對(duì)醫(yī)藥冷鏈配送的高成本、嚴(yán)時(shí)效及高客戶要求等挑戰(zhàn)，綜合考慮了時(shí)變車速、載重、客戶時(shí)間窗、滿意度及成本等關(guān)鍵因素，提出了一種城市醫(yī)藥冷鏈路徑優(yōu)化策略。以最小化總成本和最大化客戶滿意度為目標(biāo)，構(gòu)建了時(shí)變路網(wǎng)下的優(yōu)化模型，并運(yùn)用改進(jìn)的單親遺傳算法求解。通過多類型算例驗(yàn)證，該方法顯著降低了配送成本和時(shí)間，提升了準(zhǔn)時(shí)率和時(shí)效性。

關(guān)鍵詞：配送成本；客戶滿意度；時(shí)效性；時(shí)變路網(wǎng)

一、前言

近年來，我國生物制藥行業(yè)得到突飛猛進(jìn)的發(fā)展。2021年，生物醫(yī)藥行業(yè)累計(jì)營收為5918億元，同比增長113.8%[1]，但是醫(yī)藥冷鏈物流配送成本一直居高不下。

解決醫(yī)藥冷鏈物流配送問題的關(guān)鍵在于科學(xué)規(guī)劃配送車輛路徑。申曉寧[2]等以總成本最小和客戶不滿意度最低為目標(biāo)構(gòu)建路徑規(guī)劃模型，采用多目標(biāo)煙花算法對(duì)問題進(jìn)行求解。季琳琳[3]等設(shè)計(jì)了以成本和滿意度為目標(biāo)的運(yùn)輸模型，通過灰度白化權(quán)函數(shù)確定滿意度等級(jí)，并運(yùn)用改進(jìn)遺傳算法求解該模型。

王寧[4]等考慮到不同時(shí)段道路的擁堵問題，采用分段函數(shù)刻畫不同時(shí)段的車輛行駛速度，設(shè)計(jì)不同規(guī)模算例進(jìn)行求解。趙志學(xué)[5]等依據(jù)時(shí)變路網(wǎng)特點(diǎn)，設(shè)計(jì)路段劃分策略來計(jì)算行駛時(shí)間。

二、問題描述與模型建立

本研究針對(duì)城市醫(yī)藥冷鏈配送，在時(shí)變路網(wǎng)下優(yōu)化配送路徑，旨在實(shí)現(xiàn)總成本最小化、客戶滿意度最大化的目標(biāo)。

（一）符號(hào)說明

O、K分別為：配送網(wǎng)絡(luò)所有結(jié)點(diǎn)集合， 配送中心所有車輛集合。

qi、qj、dij分別為：客戶點(diǎn)i、j的醫(yī)藥需求量、客戶點(diǎn)i與客戶點(diǎn)j的距離。

t0k、tika、tikl、tijk分別為：車輛k的出發(fā)時(shí)刻、到達(dá)客戶點(diǎn)i的時(shí)間、離開客戶點(diǎn)i的時(shí)間、在道路（i，j）行駛總時(shí)間。

e1、e2分別為：早到和晚到的懲罰成本。

車輛k從i點(diǎn)行駛到j(luò)點(diǎn)

其他

車輛k負(fù)責(zé)客戶點(diǎn)i的物流配送

其他

（二）相關(guān)因素分析

1.時(shí)變路網(wǎng)行駛時(shí)間計(jì)算

參照安聰琢的研究方法[6]，具體步驟如下：

首先，將客戶時(shí)間窗細(xì)分為多個(gè)時(shí)間段，并利用百度地圖大數(shù)據(jù)平臺(tái)獲取各時(shí)間段的平均速度數(shù)據(jù)。

接著，根據(jù)配送中心的發(fā)車時(shí)間確定其所屬時(shí)間段的平均速度，并假定在該時(shí)間段內(nèi)車輛以恒定速度行駛。隨后，利用這個(gè)速度計(jì)算客戶點(diǎn)的到達(dá)時(shí)間，并判斷行駛過程是否跨越了不同的時(shí)間段，如果行駛過程處于同一時(shí)間段內(nèi)，就按照該時(shí)間段的恒定速度來計(jì)算行駛時(shí)間，如果行駛過程中跨越了多個(gè)時(shí)間段，則會(huì)根據(jù)每個(gè)時(shí)間段的平均速度來分段計(jì)算行駛時(shí)間。

2.客戶滿意度分析

本研究采用送達(dá)時(shí)間的模糊隸屬度函數(shù)來衡量客戶滿意度，客戶點(diǎn)i的滿意度函數(shù)為：

式（9）表示目標(biāo)函數(shù)，由配送過程中的固定成本、運(yùn)輸成本、制冷成本，以及時(shí)間窗懲罰成本構(gòu)成。式（11）表示配送車輛不得超載。式（12）表示每個(gè)客戶點(diǎn)只有一輛車配送。式（13）表示配送網(wǎng)絡(luò)為閉環(huán)且每輛車只能使用一次。式（14）表示客戶點(diǎn)的時(shí)間窗約束。

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

本文提出基于貪心策略的改進(jìn)型單親遺傳算法，通過對(duì)比適應(yīng)度，篩選并保留最優(yōu)染色體，從而增強(qiáng)局部搜索能力，同時(shí)保持全局搜索能力。

（一）種群初始化策略

采用自然數(shù)編碼隨機(jī)生成初始種群。首先確定種群規(guī)模，生成隨機(jī)客戶點(diǎn)序列，并在隨機(jī)選取的K個(gè)位置插入0表示車輛調(diào)度，然后，在序列首尾加0形成閉環(huán)，若生成的序列滿足約束條件，則保留，否則重復(fù)上述步驟，直至達(dá)到種群規(guī)模。

（二）計(jì)算適應(yīng)度函數(shù)策略

其中，Zx為染色體x的目標(biāo)函數(shù)，Hx為染色體x對(duì)應(yīng)的適應(yīng)度。

（三）變異策略

為了擴(kuò)大解的搜索空間，提高算法求解效率和求解質(zhì)量，改進(jìn)單親遺傳算法增加改變插入點(diǎn)的變異方式，形成基因換位+改變插入點(diǎn)、基因倒位+改變插入點(diǎn)、基因移位+改變插入點(diǎn)三種形式。

（四）基于貪心思想的選擇策略

引入貪心算法，進(jìn)行局部調(diào)整操作，通過此種方法的局部尋優(yōu)，找到局部最優(yōu)。具體操作如下：

1.分別計(jì)算各染色體的適應(yīng)度，并按適應(yīng)度值的大小進(jìn)行降序排列。

2.將適應(yīng)度值大的個(gè)體與上一代最優(yōu)個(gè)體進(jìn)行比較，如果該個(gè)體適應(yīng)度大于上一代，則將變異后個(gè)體代替變異前個(gè)體，否則仍舊保留原最優(yōu)個(gè)體，最后將結(jié)果采用最佳個(gè)體保留策略進(jìn)行保存。

3.每個(gè)染色體通過各自的適應(yīng)度值以及種群適應(yīng)度之和來計(jì)算各自被選擇的概率，計(jì)算方法如下：

（13）

4.計(jì)算染色體累計(jì)概率 qx=∑x∈Npx。

5.生成一個(gè)[0，1]之間的隨機(jī)數(shù)ω，若ω≤q1，則將第一條染色體加入下一代種群中。若qx-1≤ω≤qx，則將第x條染色體加入下一代種群中，循環(huán)操作直到將本代個(gè)體選擇完。

6.將步驟2保存的個(gè)體和步驟5選擇的個(gè)體組合生成新一代種群。

四、算例實(shí)驗(yàn)與結(jié)果分析

（一）實(shí)驗(yàn)設(shè)置

1.本研究選取Solomon算例庫[7]中C102、R202、RC202三個(gè)標(biāo)準(zhǔn)算例作為實(shí)驗(yàn)數(shù)據(jù)，

配送路徑如圖1所示。

2.與靜態(tài)網(wǎng)絡(luò)的實(shí)驗(yàn)對(duì)比

以RC202算例為例，靜態(tài)速度選取時(shí)變速度的平均值為：45km/h，對(duì)比靜態(tài)網(wǎng)絡(luò)與時(shí)變網(wǎng)絡(luò)下的結(jié)果如表1所示。

表1顯示，與靜態(tài)路網(wǎng)相比，時(shí)變路網(wǎng)在配送路徑的行駛路程和總成本上分別降低了5.89%和7.79%。盡管行駛時(shí)間增加了35分鐘，但考慮到實(shí)際路況對(duì)車速的影響及車輛難以持續(xù)勻速行駛的情況，這一時(shí)間增加是可接受的。因此，本研究的時(shí)變路網(wǎng)VRP模型較傳統(tǒng)靜態(tài)模型更符合實(shí)際，且在成本和行駛距離上有明顯優(yōu)勢(shì)。

3.不同優(yōu)化算法的結(jié)果分析

為了驗(yàn)證改進(jìn)單親遺傳算法的有效性，在使用RC202算例的情況下，采用標(biāo)準(zhǔn)遺傳算法、單親遺傳算法、改進(jìn)單親遺傳算法作對(duì)比實(shí)驗(yàn)，結(jié)果如表2所示。

表2顯示，改進(jìn)單親遺傳算法在程序運(yùn)行時(shí)間上較單親遺傳算法和遺傳算法分別縮短了13.77秒和856.57 秒，顯著提升了求解速度。盡管在配送總成本和距離上略有增加，分別增長了2.33%、1.08%和8.62%、8.05%，但在配送時(shí)間上卻大幅降低了12.82%和21.77%。這表明改進(jìn)單親遺傳算法以較小的成本和距離代價(jià)，實(shí)現(xiàn)了更高效的配送，充分展現(xiàn)了其優(yōu)越性。

五、結(jié)語

為應(yīng)對(duì)醫(yī)藥冷鏈配送的高成本和時(shí)效性挑戰(zhàn)，本文構(gòu)建了時(shí)變路網(wǎng)下的配送路徑優(yōu)化模型。通過考慮交通、天氣及客戶時(shí)間窗等因素，采用車速預(yù)測(cè)函數(shù)和路段劃分策略計(jì)算行駛時(shí)間。利用基于貪心思想的改進(jìn)單親遺傳算法求解模型，實(shí)驗(yàn)顯示該方法能有效規(guī)劃配送路線，降低成本，提升時(shí)效性，驗(yàn)證了設(shè)計(jì)方案的有效性。

參考文獻(xiàn)

[1]國家發(fā)展改革委舉行新聞發(fā)布會(huì)介紹“十四五”生物經(jīng)濟(jì)發(fā)展規(guī)劃有關(guān)情況[J].中國產(chǎn)經(jīng)，2022（10）：16-23.

[2]申曉寧，游璇，陳慶洲，等.采用雙檔案協(xié)同進(jìn)化離散多目標(biāo)煙花算法的低碳疫苗冷鏈優(yōu)化配送[J].計(jì)算機(jī)工程與科學(xué)，2022，44（12）：2255-2265.

[3]季琳琳，王清威，周豪，等.考慮顧客滿意度的冷鏈水果路徑優(yōu)化[J].浙江大學(xué)學(xué)報(bào)（工學(xué)），2021，55（02）：307-317.

[4]王寧，胡大偉，徐杰，等.基于客戶價(jià)值和滿意度的城市冷鏈物流時(shí)變路徑問題[J].中國公路學(xué)報(bào)，2021，34（09）：297-308.

[5]趙志學(xué)，李夏苗.時(shí)變交通下生鮮配送電動(dòng)車輛路徑優(yōu)化方法[J].交通運(yùn)輸系統(tǒng)工程與信息，2020，20（05）：218-225+239.

[6]安聰琢.時(shí)變路網(wǎng)下醫(yī)藥冷鏈物流配送路徑優(yōu)化研究[D].秦皇島：燕山大學(xué)，2022.

[7]孫靖璐.基于改進(jìn)自適應(yīng)大鄰域搜索算法的帶時(shí)間窗車輛路徑問題研究[D].北京：北京交通大學(xué)，2022.

責(zé)任編輯：王穎振、周航