新鮮度限制約束下物流配送中心選址-路徑優(yōu)化

劉琳，賈鵬，高犇，趙雪婷

新鮮度限制約束下物流配送中心選址-路徑優(yōu)化

劉琳a，賈鵬b，高犇c，趙雪婷c

（大連海事大學(xué) a.交通運(yùn)輸工程學(xué)院 b.綜合交通運(yùn)輸協(xié)同創(chuàng)新中心 c.航運(yùn)經(jīng)濟(jì)與管理學(xué)院，遼寧 大連 116026）

滿足生鮮產(chǎn)品交付時(shí)較高的新鮮度要求，解決多產(chǎn)品、多車型情景下的配送中心選址-路徑優(yōu)化問(wèn)題。構(gòu)建考慮碳排放成本和滿足客戶對(duì)產(chǎn)品交付最低新鮮度要求的雙層目標(biāo)規(guī)劃模型。上層模型以配送中心固定成本、庫(kù)存管理成本最小化為優(yōu)化目標(biāo)，下層模型以車輛固定成本、運(yùn)輸成本、碳排放成本、懲罰成本最小化為優(yōu)化目標(biāo)，并結(jié)合模型特點(diǎn)，采用兩階段啟發(fā)式算法進(jìn)行求解。采用的兩階段啟發(fā)式算法相對(duì)于遺傳算法的平均成本解改進(jìn)率為1.22%，相對(duì)于K-means聚類求解算法的平均解改進(jìn)率為3.03%；兩階段啟發(fā)式算法相對(duì)于遺傳算法最優(yōu)解運(yùn)算時(shí)間的平均提高率為24.8%，相對(duì)于傳統(tǒng)K-means聚類求解算法的平均提高率為33.0%。經(jīng)算例對(duì)比研究發(fā)現(xiàn)，不同新鮮度要求下對(duì)配送中心的選址以及車輛路徑的安排有顯著影響，企業(yè)可通過(guò)合理規(guī)劃物流網(wǎng)絡(luò)和準(zhǔn)確評(píng)估客戶對(duì)產(chǎn)品的新鮮度要求等手段實(shí)現(xiàn)企業(yè)物流成本的降低。

選址-路徑問(wèn)題；新鮮度約束；物流配送中心；雙層目標(biāo)規(guī)劃模型

近年來(lái)，依托于互聯(lián)網(wǎng)的高速發(fā)展，生鮮電商開(kāi)始進(jìn)入發(fā)展的黃金時(shí)代。結(jié)合生鮮產(chǎn)品容易腐爛、易于變質(zhì)、時(shí)效性要求高等特點(diǎn)，對(duì)其交付的及時(shí)性和交付時(shí)的新鮮度提出了很高的要求。若交付時(shí)產(chǎn)品的質(zhì)量明顯下降，通常將直接被拒收。這就需要一個(gè)完善的物流系統(tǒng)來(lái)支撐，通過(guò)合理的物流系統(tǒng)規(guī)劃來(lái)縮短產(chǎn)品的交付時(shí)間，保障產(chǎn)品的質(zhì)量，同時(shí)又可以降低成本。配送中心選址及車輛路徑規(guī)劃是物流系統(tǒng)2個(gè)重要組成部分，兩者之間既相互獨(dú)立又彼此關(guān)聯(lián)，不能割裂看待，企業(yè)應(yīng)該追求的是整體最優(yōu)而不是局部最優(yōu)。由此可見(jiàn)，應(yīng)對(duì)傳統(tǒng)生鮮產(chǎn)品的單一選址問(wèn)題、單一配送進(jìn)行擴(kuò)展，將兩者綜合考慮，并且引入多種生鮮產(chǎn)品、多種車型，這樣與現(xiàn)實(shí)情況更加貼近。

結(jié)合該類產(chǎn)品特點(diǎn)，為了保障產(chǎn)品交付質(zhì)量，考慮生鮮產(chǎn)品的新鮮度受到很多學(xué)者的關(guān)注。楊曉芳等[1]針對(duì)三級(jí)冷鏈物流網(wǎng)絡(luò)配送中心的選址問(wèn)題進(jìn)行了研究，構(gòu)建了以追求物流成本最小化和客戶滿意度最大化的雙目標(biāo)模型。陳紹洵等[2]為解決生鮮產(chǎn)品終端配送難題，研究了生鮮自提柜選址問(wèn)題，建立了考慮貨損成本的雙層目標(biāo)規(guī)劃模型，并證實(shí)產(chǎn)品的新鮮度對(duì)生鮮自提柜的選址有顯著影響。吳芳蕓等[3]針對(duì)生鮮品小批量、多頻次的配送特點(diǎn)，為了提高車輛的裝載率，降低成本，研究了冷鏈背景下軸幅式物流網(wǎng)絡(luò)，引入運(yùn)輸時(shí)間約束，并設(shè)計(jì)了新鮮度分段函數(shù)，構(gòu)建了以時(shí)效最優(yōu)、成本最低的物流網(wǎng)絡(luò)模型。李善俊等[4]研究了單一配送中心、單一生鮮產(chǎn)品、時(shí)間窗約束條件下的配送路徑規(guī)劃問(wèn)題，構(gòu)建了最小化配送總成本和最大化生鮮品新鮮度的多目標(biāo)優(yōu)化模型。P. Amorim等[5]針對(duì)易腐品車輛路徑問(wèn)題，構(gòu)建了分銷成本最小化、交付產(chǎn)品新鮮度最大化的雙層目標(biāo)規(guī)劃模型。以上都是針對(duì)單一生鮮產(chǎn)品進(jìn)行研究，楊霞等[6]研究了軟時(shí)間窗約束下多種生鮮產(chǎn)品的車輛路徑規(guī)劃問(wèn)題，引入了新鮮度閾值，并利用插點(diǎn)分段的方法衡量曲線上兩客戶點(diǎn)間距離，建立了系統(tǒng)總成本最小化的優(yōu)化模型。張倩等[7]更全面地考慮了多種車型，研究了不確定需求下配送路徑優(yōu)化問(wèn)題，建立了總成本最小化、產(chǎn)品新鮮度最大化、碳排放量最小化的配送路徑多目標(biāo)優(yōu)化模型，促進(jìn)了冷鏈物流的綠色化，實(shí)現(xiàn)了經(jīng)濟(jì)與環(huán)境協(xié)調(diào)發(fā)展。顧瑩等[8]研究了多種產(chǎn)品配送路徑優(yōu)化問(wèn)題，考慮了冷藏車、常溫車等2種車型，構(gòu)建了行駛成本最小化和客戶滿意度最大化的雙目標(biāo)模型。

同時(shí)，越來(lái)越多的學(xué)者意識(shí)到選址和配送是物流系統(tǒng)中2個(gè)重要的模塊，兩者之間既相對(duì)獨(dú)立又彼此關(guān)聯(lián)，不能割裂看待，企業(yè)應(yīng)該追求整體最優(yōu)而不是局部最優(yōu)。在非生鮮產(chǎn)品的背景下，陳松巖等[9]以貨物從供貨商，經(jīng)配送中心，最終到達(dá)客戶的整個(gè)物流活動(dòng)成本最小化為目標(biāo)，確定了供貨商、配送中心的位置及數(shù)量，規(guī)劃配送中心到客戶的最優(yōu)配送路徑。石兆等[10]研究了三級(jí)物流網(wǎng)絡(luò)中配送中心的選址及供應(yīng)商、配送中心車輛行駛線路規(guī)劃問(wèn)題，并在模型中引入了配送中心和客戶服務(wù)時(shí)間窗約束，考慮了多種車型，基于改進(jìn)最小包絡(luò)聚類法和遺傳算法的優(yōu)越性求解模型。羅耀波等[11]更全面考慮了倉(cāng)庫(kù)容積約束，并設(shè)計(jì)了模糊時(shí)間窗，以適應(yīng)顧客彈性預(yù)約服務(wù)時(shí)間偏好，建立了以總費(fèi)用最小化、客戶滿意度最大化的雙目標(biāo)選址-路徑模型，構(gòu)造兩階段模擬退火算法進(jìn)行求解。在生鮮產(chǎn)品背景下，楊海蘭[12]引入了混合時(shí)間窗，構(gòu)建了總成本最小化，客戶滿意度、客戶價(jià)值最大化的冷鏈物流選址-路徑多目標(biāo)規(guī)劃模型。楊曉華等[13]研究了在客戶需求量、退貨量不確定的情況下，考慮了多周期、同時(shí)取送的生鮮產(chǎn)品閉環(huán)物流網(wǎng)絡(luò)問(wèn)題，并基于相同的算例數(shù)據(jù)，驗(yàn)證了多周期物流配送系統(tǒng)比單周期更能均衡多決策安排。李冰等[14]研究了多配送中心、單一車型等條件下，生鮮產(chǎn)品同時(shí)取貨的選址-路徑問(wèn)題，綜合考慮了取、送貨時(shí)間窗及產(chǎn)品損耗，通過(guò)算例分析驗(yàn)證了同步取送相對(duì)于取送分離模式的優(yōu)越性。

選址-路徑問(wèn)題（Location Routing Problem，LRP）是選址定位問(wèn)題（Location Allocation Problem，LAP）和車輛路徑問(wèn)題（Vehicle Rounting Problem，VRP）的組合問(wèn)題，兩者都屬于NP-hard，基于此，考慮時(shí)間窗的選址-路徑問(wèn)題（Location Routing Problemwith Time Windows，LRPTW）更為復(fù)雜。在大部分情況下，利用精確算法來(lái)求解LRPTW問(wèn)題存在困難，一些學(xué)者選擇采用兩階段啟發(fā)式算法進(jìn)行求解[10,15-17]。姬楊蓓蓓等[15]利用兩階段啟發(fā)式算法求解快遞企業(yè)末端配送網(wǎng)絡(luò)規(guī)劃問(wèn)題，第1階段利用K-means進(jìn)行聚類，第2階段利用蟻群進(jìn)行路徑規(guī)劃。當(dāng)前，比較常用的聚類方法都是根據(jù)配送中心到客戶的空間距離來(lái)劃分配送中心負(fù)責(zé)客戶點(diǎn)的范圍。這種方法雖然簡(jiǎn)單但是聚類效果較差，特別是在求解帶時(shí)間窗的選址-路徑問(wèn)題時(shí)?；谝陨媳尘?，于濱等[16]設(shè)計(jì)了聚集度啟發(fā)式分類算法，引入了確定性信息和啟發(fā)式信息，在進(jìn)行客戶分類時(shí)，一方面衡量客戶點(diǎn)空間距離及時(shí)間窗相似性，另一方面考慮了先前分類的經(jīng)驗(yàn)，提高了分類效率。Xuping Wang[17]引入了時(shí)空距離的概念，通過(guò)計(jì)算客戶間的時(shí)空距離，并結(jié)合遺傳算法對(duì)客戶點(diǎn)進(jìn)行聚類，生成初始解。

綜上所述，現(xiàn)有針對(duì)生鮮產(chǎn)品的選址-路徑問(wèn)題均以單一車型、單一產(chǎn)品為主，但是現(xiàn)實(shí)情況下，企業(yè)往往具有多種不同載質(zhì)量的車型，以適應(yīng)客戶的不同需求。同一客戶同時(shí)需要多種生鮮產(chǎn)品，與現(xiàn)實(shí)情況更為貼近。以往的生鮮產(chǎn)品的選址路徑都是通過(guò)考慮客戶時(shí)間窗，以及在目標(biāo)函數(shù)中引入貨損成本，追求目標(biāo)函數(shù)最小化，來(lái)提高交付時(shí)產(chǎn)品的新鮮度。由于生鮮產(chǎn)品的特殊性，客戶對(duì)交付時(shí)產(chǎn)品的新鮮度有較高的期望。若交付時(shí)產(chǎn)品的質(zhì)量明顯下降，通常將直接被拒收。由此，將產(chǎn)品交付時(shí)的新鮮度大于客戶要求的最低新鮮度作為一個(gè)必要條件存在于模型中是十分有意義的，文中在考慮客戶時(shí)間窗和交付產(chǎn)品新鮮度的基礎(chǔ)上，建立具有最低新鮮度限制的多種生鮮產(chǎn)品、多種車型的選址-路徑優(yōu)化問(wèn)題的雙層目標(biāo)規(guī)劃模型?；谀Ｐ吞攸c(diǎn)，運(yùn)用兩階段啟發(fā)式算法，在滿足客戶要求的條件下，實(shí)現(xiàn)物流系統(tǒng)總成本的最小化。

1 模型構(gòu)建

1.1 問(wèn)題描述

文中的研究對(duì)象是由多個(gè)備選配送中心和多個(gè)客戶點(diǎn)構(gòu)成的物流系統(tǒng)。每個(gè)配送中心內(nèi)含有多種相同的生鮮產(chǎn)品，分別有1支車隊(duì)負(fù)責(zé)完成客戶的配送任務(wù)，每支車隊(duì)均含有A、B、C等3種車型。每個(gè)客戶點(diǎn)同時(shí)需要多種生鮮產(chǎn)品，每種產(chǎn)品的有效生命周期不同，交付時(shí)每種產(chǎn)品的新鮮度都需滿足客戶最低新鮮度的要求。候選配送中心、客戶點(diǎn)的數(shù)量、客戶點(diǎn)位置、每個(gè)客戶點(diǎn)的需求量、服務(wù)時(shí)間窗等信息均已知。車輛從配送中心始發(fā)，前往各客戶點(diǎn)，等待客戶完成裝卸后繼續(xù)行駛到下一個(gè)客戶點(diǎn)，最終返回配送中心。每輛車最多行駛1條路徑，但是每條路徑上可以有多個(gè)客戶點(diǎn)。在滿足客戶需求量、交付時(shí)間窗、最低新鮮度和車輛承載能力的要求下，確定配送中心的位置及配送路徑，最終實(shí)現(xiàn)總成本的最小化。

1.2 模型假設(shè)

為了求解問(wèn)題，建立了如下基本假設(shè)。

1）每輛車只服務(wù)于1條路徑，每輛車1次可以配送多個(gè)客戶的訂單。

2）每個(gè)客戶只有1個(gè)配送中心和1輛車為其提供服務(wù)。

3）每個(gè)客戶的需求在1次配送中得到滿足。

4）配送中心有多種車型，車輛總數(shù)能完成配 送任務(wù)，任意車型的載質(zhì)量都不小于單個(gè)客戶的需求量。

5）假設(shè)商品從離開(kāi)配送中心那一刻起，新鮮度就開(kāi)始衰減，交付客戶的產(chǎn)品必須滿足最低新鮮度的要求。

6）所有車輛都從配送中心出發(fā)，服務(wù)完路徑上的客戶后再返回配送中心。

1.3 符號(hào)說(shuō)明

1.4 相關(guān)指標(biāo)計(jì)算

1）CO2排放量計(jì)算。根據(jù)文獻(xiàn)[18]計(jì)算燃料消耗量，其可以表示為：

(1)

(2)

2）新鮮度計(jì)算。對(duì)于任意一種易腐品，隨著時(shí)間的推移，產(chǎn)品新鮮度會(huì)不斷衰減。文中采用單調(diào)連續(xù)遞減函數(shù)來(lái)描述產(chǎn)品新鮮度隨時(shí)間的變動(dòng)情況[19]。假設(shè)產(chǎn)品其新鮮程度在離開(kāi)配送中心后就會(huì)衰減，設(shè)產(chǎn)品離開(kāi)配送中心為0時(shí)刻，交付客戶為時(shí)刻，產(chǎn)品的新鮮度可以表示為：

(3)

當(dāng)產(chǎn)品送達(dá)時(shí)，若產(chǎn)品新鮮程度明顯下降，客戶會(huì)直接拒收這批產(chǎn)品，因此交付時(shí)必須要滿足客戶的最低新鮮度的要求，即：。

1.5 雙層規(guī)劃模型

1）上層模型。

(4)

S.t(5)

(6)

(7)

上層目標(biāo)函數(shù)式（4）表示最小化配送中心的固定成本和倉(cāng)庫(kù)管理成本，式（5）表示配送中心的開(kāi)設(shè)數(shù)量不能超過(guò)最大開(kāi)設(shè)數(shù)量，式（6）表示決策變量的取值范圍，式（7）表示每個(gè)客戶總需求量為各種產(chǎn)品需求量之和。

2）下層模型。

(8)

S.t(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

(23)

(24)

(25)

(26)

2 求解算法

文中運(yùn)用兩階段啟發(fā)式算法[16,20]，第1階段利用聚集度的啟發(fā)式算法，對(duì)客戶點(diǎn)進(jìn)行聚類，初步確定每個(gè)客戶點(diǎn)對(duì)應(yīng)為其提供服務(wù)的配送中心，從而實(shí)現(xiàn)多中心選址-路徑問(wèn)題向多個(gè)單中心路徑問(wèn)題的轉(zhuǎn)換，降低了問(wèn)題難度；第2階段利用改進(jìn)蟻群算法規(guī)劃相應(yīng)的配送路線。具體算法流程見(jiàn)圖1。

首先，確定倉(cāng)庫(kù)的位置和數(shù)量以及所有客戶點(diǎn)的分類，具體步驟如下所述。

其次，完成所有客戶點(diǎn)的初始劃分后，利用蟻群算法，規(guī)劃每個(gè)被選配送中心服務(wù)客戶點(diǎn)的配送路線，以單獨(dú)一個(gè)配送中心為例，具體步驟如下所述。

Step1：螞蟻從配送中心出發(fā)，計(jì)算可行集內(nèi)客戶點(diǎn)被訪問(wèn)的概率，根據(jù)輪盤賭選擇法得到下一個(gè)要訪問(wèn)的客戶點(diǎn)，并分配可獲得的車輛。

圖1 算法流程

Step2：依次確定該條路線后續(xù)訪問(wèn)的客戶點(diǎn)，并滿足車輛的容量、距離限制、交付最低新鮮度限制，否則，轉(zhuǎn)至Step3。

Step3：重新開(kāi)啟其他新的路線，直到完成其服務(wù)范圍內(nèi)所有點(diǎn)的配送。

Step5：在不改變所選配送中心及客戶點(diǎn)劃分的條件下，將每次得到的新的下層目標(biāo)函數(shù)值與原最優(yōu)值進(jìn)行對(duì)比，若新函數(shù)值小于原，則更換，并重新開(kāi)始下一次路徑優(yōu)化，直到超出允許最大迭代次數(shù)。

再次，保持配送中心開(kāi)設(shè)數(shù)量不變，產(chǎn)生新的選址方案，重新計(jì)算上層成本。如果得到的成本小于則跳轉(zhuǎn)到第2部分；否則將配送中心開(kāi)設(shè)數(shù)量降低1個(gè)，在減少配送中心的數(shù)量的同時(shí)必須滿足配送中心的容量約束。如果最后找不到滿足容量約束的配送中心方案，則結(jié)束算法。

2.1 聚集度的啟發(fā)算法進(jìn)行客戶聚類

廣泛使用的客戶聚類方法根據(jù)客戶與配送中心的距離進(jìn)行分類，但是在面臨帶有時(shí)間窗的問(wèn)題時(shí)，這種方法會(huì)產(chǎn)生的解質(zhì)量不高。由此，文中在對(duì)客戶進(jìn)行聚類時(shí)，引入了2種信息。

(27)

(28)

(29)

(30)

(31)

2.2 蟻群算法進(jìn)行路徑規(guī)劃

蟻群算法（ACO）本質(zhì)上是一個(gè)基于信息正反饋原理的智能算法，并且具備較強(qiáng)的魯棒性、良好的分布式計(jì)算機(jī)制等優(yōu)勢(shì)。蟻群算法常用來(lái)解決單配送中心車輛調(diào)度問(wèn)題，并取得了較好的成效。文中首先利用基于聚集度的啟發(fā)式算法，將多配送中心選址路徑問(wèn)題轉(zhuǎn)化為多個(gè)單配送中心車輛調(diào)度問(wèn)題，從而應(yīng)用蟻群算法進(jìn)行車輛路徑的安排。文中按照以下4個(gè)方面設(shè)計(jì)算法，從而確定配送路徑。

1）方案構(gòu)造。從某配送中心出發(fā)，途經(jīng)服務(wù)范圍內(nèi)所有的客戶點(diǎn)，最終返回此配送中心，此路線即構(gòu)成一個(gè)方案。同時(shí)每個(gè)客戶有且僅被服務(wù)1次，滿足每個(gè)客戶的時(shí)間窗要求，交付時(shí)每個(gè)客戶每種產(chǎn)品的新鮮度必須大于最低新鮮度，每輛車載重不能超過(guò)最大承載能力。基于車輛行駛路徑的順序進(jìn)行編碼。例如從配送中心1出發(fā)，先后經(jīng)過(guò)客戶點(diǎn)10、12、20、15，最后返回配送中心1，該路線的編碼為1-10-12-20-15-1。

2）轉(zhuǎn)移規(guī)則。螞蟻從配送中心出發(fā)，根據(jù)式（32）得到每個(gè)客戶點(diǎn)被訪問(wèn)的概率，根據(jù)輪盤賭選擇法得到下一個(gè)要訪問(wèn)的客戶點(diǎn)；然后計(jì)算，如果訪問(wèn)這個(gè)客戶點(diǎn)，是否會(huì)超出車輛的各種最大限制約束和新鮮度約束限制，如果滿足，則將該客戶點(diǎn)加入路徑中；否則，該車路徑結(jié)束，下一輛車?yán)^續(xù)從配送中心出發(fā)。節(jié)點(diǎn)選擇節(jié)點(diǎn)作為下一個(gè)配送點(diǎn)的概率的計(jì)算見(jiàn)式（32）。

(32)

3）交叉算子。為了有效控制算法陷入局部收斂，利用交叉算子拓寬解空間的搜索范圍。依據(jù)交叉率從解決方案中隨機(jī)選擇路徑，從被選路徑 中各自隨機(jī)選擇1個(gè)位置進(jìn)行交叉，構(gòu)造新的解決方案。

4）信息素更新。每完成1次循環(huán)后，都需要更新螞蟻?zhàn)哌^(guò)路徑上的信息素含量，計(jì)算見(jiàn)式（33）。

(33)

(34)

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

3.1 基礎(chǔ)數(shù)據(jù)

為驗(yàn)證模型的有效性和正確性，實(shí)驗(yàn)算例如下：某個(gè)供貨商A作為多種生鮮產(chǎn)品的一級(jí)經(jīng)銷商，其供給的產(chǎn)品有穩(wěn)定的銷路，主要負(fù)責(zé)為區(qū)域內(nèi)多個(gè)地區(qū)的24個(gè)二級(jí)經(jīng)銷商供貨，供貨頻率為每月1次，并針對(duì)單個(gè)周期進(jìn)行研究。由于產(chǎn)品的特殊性，對(duì)產(chǎn)品時(shí)效提出了很高的要求，為了縮短交付時(shí)間，保障產(chǎn)品交付時(shí)的新鮮度，供貨商A決定從當(dāng)前8個(gè)候選配送中心中篩選若干建立配送中心，完成產(chǎn)品的周轉(zhuǎn)工作。設(shè)定每個(gè)配送中心的使用壽命為20年，每個(gè)配送中心的容量、建設(shè)成本、月分?jǐn)偝杀?、月單位?kù)存管理費(fèi)用詳見(jiàn)表1。每位客戶對(duì)產(chǎn)品的需求種類數(shù)為2～3，對(duì)每種產(chǎn)品的需求量和服務(wù)時(shí)間窗詳見(jiàn)表2。每個(gè)配送中心均可以提供a、b和c等3種產(chǎn)品，其有效生命周期分別為9、6、4 d，并擁有A、B、C等3種不同車型用來(lái)承擔(dān)相應(yīng)的運(yùn)輸任務(wù)，詳見(jiàn)表3。各路段的長(zhǎng)度為節(jié)點(diǎn)間的歐式距離，車輛在路段上勻速行駛，平均速度=60 km/h，單位時(shí)間車輛的等待成本和懲罰成本分別為=10，=20。燃油轉(zhuǎn)換系數(shù)=2.62，碳排放成本=0.004元/g，配送中心允許開(kāi)設(shè)的最大數(shù)量=6。

表1 配送中心相關(guān)參數(shù)

Tab.1 Relevant parameters of distribution center

表2 客戶需求的相關(guān)參數(shù)

Tab.2 Relevant parameters of customer demand

表3 不同車型相關(guān)參數(shù)

Tab.3 Relevant parameters of different vehicle models

3.2 結(jié)果分析

相關(guān)數(shù)據(jù)[20]設(shè)置如下：種群數(shù)量為100；最大迭代代數(shù)為150；控制參數(shù)=1；=3；信息保留程度=0.95；控制參數(shù)=2000；螞蟻每完成1次循環(huán)產(chǎn)生的信息總量=1500；啟發(fā)式因子=1；=3；交叉概率=0.01；3種產(chǎn)品的最低新鮮度均為0.75。文中在AMD A6-5345M APU with Radeon(tm) HD Graphics 2.20 GHz內(nèi)存為4 GB的電腦上，利用Matlab 2016a軟件運(yùn)行程序，得到相應(yīng)的配送中心選址和運(yùn)輸路徑結(jié)果，運(yùn)行結(jié)果見(jiàn)表4、圖2。

同時(shí)，基于相同數(shù)據(jù)背景對(duì)比分析3種算法的運(yùn)行結(jié)果，分別包括：文中所采用的兩階段啟發(fā)式算法（算法1）和遺傳算法（算法2），以及傳統(tǒng)利用k-means進(jìn)行聚類的兩階段啟發(fā)式算法（算法3），并進(jìn)行了多組實(shí)驗(yàn)，每組設(shè)置不同的值，每組實(shí)驗(yàn)均進(jìn)行15次，得到3種算法的運(yùn)算結(jié)果詳見(jiàn)表5。

表4 運(yùn)算結(jié)果

Tab.4 Operation result

圖2 最優(yōu)選址及路徑分配方案

為了進(jìn)一步驗(yàn)證兩階段啟發(fā)式算法對(duì)于求解兩階段問(wèn)題（選址-路徑問(wèn)題）的優(yōu)越性，并結(jié)合文中考慮客戶交付時(shí)間窗的問(wèn)題背景，著重對(duì)算法1和算法2的最優(yōu)方案收斂圖進(jìn)行了對(duì)比，詳見(jiàn)圖3。

表5 各算法運(yùn)行結(jié)果

Tab.5 Results of each algorithm

圖3 算法迭代

如圖3所示，遺傳算法不僅收斂速度慢，而且容易陷入局部最優(yōu)，求解質(zhì)量較差。文中采用的算法在收斂速度和解的質(zhì)量方面都具有一定的優(yōu)越性。

3.3 敏感度分析

為了分析交付時(shí)產(chǎn)品最低新鮮度約束對(duì)結(jié)果的影響，利用上述數(shù)據(jù)進(jìn)行多組實(shí)驗(yàn)，在其他數(shù)據(jù)保持不變的情況下，以新鮮度值等于0.55時(shí)為起點(diǎn)，以相鄰2個(gè)新鮮度值相差0.1為間隔，進(jìn)行敏感度分析，輸出了1組成本折線圖，從而更清晰地了解隨著交付新鮮度的增加，以及總成本、上層成本、下層成本的變化情況，詳見(jiàn)圖4。

圖4 成本隨新鮮度的變化情況

如圖4所示，隨著產(chǎn)品交付時(shí)最低新鮮度這一變量數(shù)值的變化，上層配送中心的選址成本和下層客戶配送路線的成本都呈上升趨勢(shì)，從而導(dǎo)致總體成本增加，進(jìn)一步驗(yàn)證了文中模型和算法的可行性和有效性。

4 結(jié)語(yǔ)

在傳統(tǒng)生鮮品選址-路徑問(wèn)題研究的基礎(chǔ)上，文中進(jìn)行了擴(kuò)展，一方面考慮了多種生鮮產(chǎn)品、多種車型，與現(xiàn)實(shí)情況更為貼近；另一方面，引入了新鮮度計(jì)算模型，并設(shè)計(jì)交付時(shí)產(chǎn)品的新鮮度必須滿足客戶的最低新鮮度要求，從而優(yōu)化了傳統(tǒng)方法的不足。

針對(duì)多種生鮮產(chǎn)品多種車型的選址-路徑優(yōu)化問(wèn)題，文中構(gòu)建了綜合考慮客戶時(shí)間窗和交付產(chǎn)品最低新鮮度約束的雙層目標(biāo)規(guī)劃模型，并以物流系統(tǒng)總成本最小化為優(yōu)化目標(biāo)，其中第1階段目標(biāo)函數(shù)考慮配送中心建設(shè)成本、庫(kù)存管理成本；第2階段目標(biāo)函數(shù)綜合考慮了車輛固定成本、車輛運(yùn)輸成本、碳排放成本、車輛等待成本、車輛懲罰成本等?；谀Ｐ吞攸c(diǎn)，采用兩階段啟發(fā)式算法，第1階段采用聚集度的啟發(fā)式算法，將每個(gè)客戶點(diǎn)分配給相應(yīng)的配送中心，從而將多中心選址-路徑模型轉(zhuǎn)化成多個(gè)單中心選址-路徑模型；第2階段利用改進(jìn)的蟻群算法，確定每個(gè)配送中心客戶集內(nèi)各點(diǎn)的配送順序。

數(shù)值實(shí)驗(yàn)結(jié)果驗(yàn)證了模型的有效性和可行性，得到的主要結(jié)論包括：根據(jù)客戶需求的變化，選擇不同的車型進(jìn)行配送，在滿足客戶需求的前提下，可以實(shí)現(xiàn)車輛固定成本和配送成本最小化，因此企業(yè)可以儲(chǔ)備多種車型以適應(yīng)客戶的不同需求，在一定程度上可以降低配送成本；產(chǎn)品交付時(shí)最低新鮮度要求會(huì)影響配送中心的選擇和車輛路徑的安排，當(dāng)產(chǎn)品交付時(shí)的新鮮度越高時(shí)，總成本也更高。由此可見(jiàn)，企業(yè)需要準(zhǔn)確評(píng)估客戶對(duì)產(chǎn)品的新鮮度要求，在一定程度可以降低物流系統(tǒng)的總成本。后續(xù)研究可以將生鮮產(chǎn)品選址-路徑問(wèn)題進(jìn)行擴(kuò)展，并結(jié)合逆向物流，綜合考慮交通擁堵、天氣情況對(duì)物流系統(tǒng)規(guī)劃的影響。

[1] 楊曉芳, 姚宇, 付強(qiáng). 基于新鮮度的冷鏈物流配送多目標(biāo)優(yōu)化模型[J]. 計(jì)算機(jī)應(yīng)用研究, 2016, 33(4): 1050-1053.

YANG Xiao-fang, YAO Yu, FU Qiang. Multi-Objective Optimization Model of Cold Chain Logistics Distribution Based on Freshness[J]. Application Research of Computers, 2016, 33(4): 1050-1053.

[2] 陳紹洵, 蘭洪杰. 基于雙層規(guī)劃的生鮮自提柜節(jié)點(diǎn)選址研究[J]. 工業(yè)工程與管理, 2018, 23(6): 57-63.

CHEN Shao-xun, LAN Hong-jie. Location of Fresh Product Self-Collection Cabinet Based on Bi-Level Programming[J]. Industrial Engineering and Management, 2018, 23(6): 57-63.

[3] 吳芳蕓, 朱小林. 基于軸輻式理論的冷鏈物流網(wǎng)絡(luò)優(yōu)化模型[J]. 公路交通科技, 2019, 36(6): 144-150.

WU Fang-yun, ZHU Xiao-lin. Cold Chain Logistics Network Optimization Model Based on Hub-and-Spoke Theory[J]. Journal of Highway and Transportation Research and Development, 2019, 36(6): 144-150.

[4] 李善俊, 陳淮莉. 基于NSGA Ⅱ的帶時(shí)間窗生鮮品配送路徑優(yōu)化[J]. 上海海事大學(xué)學(xué)報(bào), 2020, 41(2): 58-64.

LI Shan-jun, CHEN Huai-li. Optimization of Fresh Food Distribution Route with Time Window Based on NSGA Ⅱ[J]. Journal of Shanghai Maritime University, 2020, 41(2): 58-64.

[5] AMORIM P, ALMADA-LOBO B. The Impact of Food Perishability Issues in the Vehicle Routing Problem[J]. Computers & Industrial Engineering, 2014, 67: 223-233.

[6] 楊霞, 范體軍, 程方正. 多品種生鮮農(nóng)產(chǎn)品的車輛路徑優(yōu)化[J]. 數(shù)學(xué)的實(shí)踐與認(rèn)識(shí), 2019, 49(2): 198-214.

YANG Xia, FAN Ti-jun, CHENG Fang-zheng. Vehicle Routing Optimization of Multi-Variety Fresh Agricultural Products[J]. Mathematics in Practice and Theory, 2019, 49(2): 198-214.

[7] 張倩, 熊英, 何明珂, 等. 不確定需求生鮮電商配送路徑規(guī)劃多目標(biāo)模型[J]. 系統(tǒng)仿真學(xué)報(bào), 2019, 31(8): 1582-1590.

ZHANG Qian, XIONG Ying, HE Ming-ke, et al. Multi-Objective Model of Distribution Route Problem for Fresh Electricity Commerce under Uncertain Demand[J]. Journal of System Simulation, 2019, 31(8): 1582-1590.

[8] 顧瑩, 楊斌. 考慮異質(zhì)車輛和顧客滿意度的冷藏品配送路徑優(yōu)化[J]. 計(jì)算機(jī)應(yīng)用與軟件, 2020, 37(2): 32-38.

GU Ying, YANG Bin. Route Optimization of Refrigerated Products Delivery Considering Heterogeneous Vehicles and Customer Satisfaction[J]. Computer Applications and Software, 2020, 37(2): 32-38.

[9] 陳松巖, 今井昭夫. 物流網(wǎng)絡(luò)選址與路徑優(yōu)化問(wèn)題的模型與啟發(fā)式解法[J]. 交通運(yùn)輸工程學(xué)報(bào), 2006, 6(3): 118-121.

CHEN Song-yan, IMAI Akio. Model and Heuristic Solution for Location Routing Problems of Logistics Network[J]. Journal of Traffic and Transportation Engineering, 2006, 6(3): 118-121.

[10] 石兆, 符卓. 配送選址-多車型運(yùn)輸路徑優(yōu)化問(wèn)題及求解算法[J]. 計(jì)算機(jī)科學(xué), 2015, 42(5): 245-250.

SHI Zhao, FU Zhuo. Distribution Location-Routing Problem of Heterotypic Vehicles and Its Algorithms[J]. Computer Science, 2015, 42(5): 245-250.

[11] 羅耀波, 孫延明. 基于模糊時(shí)間窗的帶容積約束選址路徑問(wèn)題[J]. 系統(tǒng)工程, 2014, 32(1): 19-25.

LUO Yao-bo, SUN Yan-ming. Capacitated Location Routing Problem Based on Fuzzy Time Windows[J]. Systems Engineering, 2014, 32(1): 19-25.

[12] 楊海蘭. 考慮客戶價(jià)值的冷鏈物流多目標(biāo)LRPTW問(wèn)題優(yōu)化研究[D]. 西安: 長(zhǎng)安大學(xué), 2018: 36-54.

YANG Hai-lan. Optimization of Cold Chain Logistics Multi-Objective LRPTW Problem Considering Customer Value[D]. Xi'an: Changan University, 2018: 36-54.

[13] 楊曉華, 郭健全. 模糊環(huán)境下多周期多決策生鮮閉環(huán)物流網(wǎng)絡(luò)[J]. 計(jì)算機(jī)應(yīng)用, 2019, 39(7): 2168-2174.

YANG Xiao-hua, GUO Jian-quan. Multi-Period Multi-Decision Closed-Loop Logistics Network for Fresh Products with Fuzzy Variables[J]. Journal of Computer Applications, 2019, 39(7): 2168-2174.

[14] 李冰, 黨佳俊. 多配送中心下生鮮農(nóng)產(chǎn)品同步取送選址-路徑優(yōu)化[J]. 智能系統(tǒng)學(xué)報(bào), 2020, 15(1): 50-58.

LI Bing, DANG Jia-jun. Fresh Agricultural Cargoes Location-Routing Optimization with Simultaneous Pickup and Delivery for Multiple Distribution Centers[J]. CAAI Transactions on Intelligent Systems, 2020, 15(1): 50-58.

[15] 姬楊蓓蓓, 儲(chǔ)昊, 成楓. 基于兩階段算法的快遞企業(yè)末端配送網(wǎng)絡(luò)優(yōu)化研究[J]. 系統(tǒng)工程, 2019, 37(2): 100-105.

JI-YANG Bei-bei, CHU Hao, CHENG Feng. Optimization of Delivery Enterprise Delivery Network Based on Two Stage Algorithm[J]. Systems Engineering, 2019, 37(2): 100-105.

[16] 于濱, 靳鵬歡, 楊忠振. 兩階段啟發(fā)式算法求解帶時(shí)間窗的多中心車輛路徑問(wèn)題[J]. 系統(tǒng)工程理論與實(shí)踐, 2012, 32(8): 1793-1800. YU Bin, JIN Peng-huan, YANG Zhong-zhen. Two-Stage Heuristic Algorithm for Multi-Depot Vehicle Routing Problem with Time Windows[J]. Systems Engineering-Theory & Practice, 2012, 32(8): 1793-1800.

[17] WANG Xu-ping, LI Xin-yu. Carbon Reduction in the Location Routing Problem with Heterogeneous Fleet, Simultaneous Pickup-Delivery and Time Windows[J]. Procedia Computer Science, 2017, 112: 1131-1140.

[18] 趙燕偉, 錢振宇, 張景玲, 等. 考慮碳排放的選址-路徑問(wèn)題研究[J]. 浙江工業(yè)大學(xué)學(xué)報(bào), 2018, 46(5): 550-557.

ZHAO Yan-wei, QIAN Zhen-yu, ZHANG Jing-ling, et al. Research on Location Routing Problem Considering Carbon Emissions[J]. Journal of Zhejiang University of Technology, 2018, 46(5): 550-557.

[19] 吳瑤, 馬祖軍, 鄭斌. 有新鮮度限制的易腐品生產(chǎn)-配送協(xié)同調(diào)度[J]. 計(jì)算機(jī)應(yīng)用, 2018, 38(4): 1181-1188.

WU Yao, MA Zu-jun, ZHENG Bin. Integrated Scheduling of Production and Distribution for Perishable Products with Freshness Requirements[J]. Journal of Computer Applications, 2018, 38(4): 1181-1188.

[20] 王道平, 徐展, 楊岑. 基于兩階段啟發(fā)式算法的物流配送選址-路徑問(wèn)題研究[J]. 運(yùn)籌與管理, 2017, 26(4): 70-75.

WANG Dao-ping, XU Zhan, YANG Cen. Study on Location-Routing Problem of Logistics Distribution Based on Two-Stage Heuristic Algorithm[J]. Operations Research and Management Science, 2017, 26(4): 70-75.

Location Routing Optimization of Logistics Distribution Center under Freshness Limitation

LIU Lina, JIA Pengb, GAO Benc, ZHAO Xue-tingc

(a.College of Transportation Engineering b.Collaborative Innovation Center for Transport Studies c.School of Maritime Economics and Management, Dalian Maritime University, Dalian 116026, China)

The work aims to meet the requirements of high freshness when fresh products are delivered, and realize the optimization of location routing of distribution center under the scenario of multiple products and multiple vehicle models. A two-level goal programming model was constructed in view of considering the cost of carbon emission and meeting the customers' requirements for the minimum freshness of product at delivery. The optimization goal of the upper model was to minimize the fixed cost of distribution center and inventory management cost, while the optimization goal of the lower model was to minimize the fixed cost of vehicles, transportation cost, carbon emission cost and punishment cost. Combined with the characteristics of the model, a two-stage heuristic algorithm was used to solve the problem. The average cost improvement rate of the two-stage heuristic algorithm was 1.22% compared with that of genetic algorithm, and 3.03% compared with that of K-means clustering algorithm. The average improvement rate of the two-stage heuristic algorithm was 24.8% compared with that of genetic algorithm, and 33.0% compared with that of traditional K-means clustering algorithm. Through the comparative study of calculation examples, different freshness requirements have a significant impact on the location of distribution centers and the arrangement of vehicle routes. Enterprises can reduce logistics costs by means of reasonable logistics network planning and accurate evaluation of customers' requirements for product freshness.

location routing; freshness limitation; distribution center; two-level programming model

F252.14

A

1001-3563(2022)05-0232-10

10.19554/j.cnki.1001-3563.2022.05.032

2021-03-15

國(guó)家自然科學(xué)基金（72174035，71774018）；遼寧省“興遼英才計(jì)劃”（XLYC2008030）；遼寧省社會(huì)科學(xué)規(guī)劃基金（L21CGL003）

劉琳（1997—），女，碩士，主要研究方向?yàn)槲锪飨到y(tǒng)優(yōu)化設(shè)計(jì)。

賈鵬（1979—），男，博士，大連海事大學(xué)教授，主要研究方向?yàn)楣芾砜茖W(xué)與工程。