基于改進(jìn)模擬退火算法的配送路徑優(yōu)化研究

錢(qián)葉霞 陳子敬

摘 要：“互聯(lián)網(wǎng)+”時(shí)代背景下，越來(lái)越多的企業(yè)紛紛入駐生鮮電商行業(yè)，生鮮電商的企業(yè)盈利和競(jìng)爭(zhēng)壓力隨之增大，這就要求生鮮企業(yè)做好精細(xì)化的成本控制策略，實(shí)現(xiàn)物流系統(tǒng)的高效運(yùn)作。在生鮮配送過(guò)程中，配送路徑優(yōu)化是極為重要的一環(huán)，所以生鮮電商企業(yè)必須做好物流配送路徑的合理規(guī)劃，降低配送環(huán)節(jié)的成本，增加物流總收益。本文以生鮮農(nóng)產(chǎn)品為研究對(duì)象，建立以最短路徑為目標(biāo)函數(shù)的數(shù)學(xué)模型，利用改進(jìn)模擬退火算法進(jìn)行研究，并通過(guò)PyCharm軟件進(jìn)行求解。求解結(jié)果表明：本文所建立的車(chē)輛路徑優(yōu)化模型能有效縮短配送線路的總距離，降低配送運(yùn)輸?shù)恼w運(yùn)營(yíng)成本，進(jìn)一步驗(yàn)證了車(chē)輛路徑優(yōu)化模型和改進(jìn)算法的有效性和實(shí)用性。

關(guān)鍵詞：生鮮農(nóng)產(chǎn)品；配送路線優(yōu)化；改進(jìn)模擬退火算法；建模分析

本文索引：錢(qián)葉霞，陳子敬.<變量 2>[J].中國(guó)商論，2023（08）：-089.

中圖分類(lèi)號(hào)：F572 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2096-0298（2023）04（b）--04

隨著我國(guó)經(jīng)濟(jì)水平的提升，人民群眾對(duì)食品的消費(fèi)觀念已經(jīng)不再是“民以食為天”，而是逐步轉(zhuǎn)變成“民以鮮為天”。收入水平的不斷提升和經(jīng)濟(jì)社會(huì)的進(jìn)一步發(fā)展，使人們從原來(lái)“吃得飽”的需求轉(zhuǎn)變?yōu)椤俺缘煤谩?，同時(shí)在食品質(zhì)量和安全問(wèn)題上投入更多的關(guān)注，尤其是對(duì)配送要求較高的生鮮食品。

2020年6月，國(guó)家發(fā)改委發(fā)布《關(guān)于進(jìn)一步優(yōu)化發(fā)展環(huán)境促進(jìn)生鮮農(nóng)產(chǎn)品流通的實(shí)施意見(jiàn)》，旨在統(tǒng)籌推進(jìn)生鮮運(yùn)輸市場(chǎng)和疫情防控，規(guī)范市場(chǎng)。2020年6月，農(nóng)業(yè)農(nóng)村部發(fā)布《關(guān)于進(jìn)一步加強(qiáng)農(nóng)產(chǎn)品倉(cāng)儲(chǔ)保險(xiǎn)冷鏈設(shè)施建設(shè)工作的通知》，細(xì)化農(nóng)產(chǎn)品生鮮運(yùn)輸，落實(shí)建設(shè)生鮮農(nóng)產(chǎn)品信息平臺(tái)。2022年4月，交通運(yùn)輸部發(fā)布《關(guān)于加快推進(jìn)冷鏈物流運(yùn)輸高質(zhì)量發(fā)展的實(shí)施意見(jiàn)》，旨在通過(guò)促進(jìn)冷鏈運(yùn)輸發(fā)展來(lái)解決現(xiàn)有的生鮮運(yùn)輸問(wèn)題。2020年發(fā)布的中央一號(hào)紅頭文件《關(guān)于抓好“三農(nóng)”領(lǐng)域重點(diǎn)工作確保如期實(shí)現(xiàn)全面小康的意見(jiàn)》明確指出“要推進(jìn)農(nóng)產(chǎn)品保鮮冷藏冷凍物流基礎(chǔ)設(shè)施建設(shè)，增強(qiáng)生鮮農(nóng)產(chǎn)品的冷藏冷凍物流統(tǒng)一規(guī)劃，提升制定標(biāo)準(zhǔn)和布局分類(lèi)”。由此看來(lái)，本文通過(guò)優(yōu)化路徑解決生鮮運(yùn)輸和配送問(wèn)題具有一定的現(xiàn)實(shí)意義。

如圖1所示，2020年新冠疫情推動(dòng)生鮮電商加速發(fā)展，生鮮電商市場(chǎng)規(guī)模不斷擴(kuò)大。

2021年上半年，中國(guó)生鮮電商交易規(guī)模約2362.1億元；2021年底，生鮮電商交易規(guī)模約達(dá)4658.1億元，同比增長(zhǎng)27.92%。如圖2所示，隨著生鮮電商的發(fā)展及模式的成熟、用戶(hù)網(wǎng)購(gòu)生鮮習(xí)慣的養(yǎng)成，生鮮電商行業(yè)滲透率逐漸提高，越來(lái)越多的企業(yè)紛紛進(jìn)入生鮮電商行業(yè)，生鮮電商企業(yè)盈利和競(jìng)爭(zhēng)壓力隨之增大，這就要求生鮮企業(yè)做好精細(xì)化的成本控制策略，實(shí)現(xiàn)物流系統(tǒng)的高效運(yùn)作。在生鮮配送過(guò)程中，配送路徑優(yōu)化是極為重要的一環(huán)，本文聚焦生鮮配送路徑優(yōu)化問(wèn)題進(jìn)行研究。

1 生鮮農(nóng)產(chǎn)品配送路徑模型建立

1.1 生鮮農(nóng)產(chǎn)品配送路徑優(yōu)化問(wèn)題概述

生鮮農(nóng)產(chǎn)品配送問(wèn)題可描述為：某個(gè)地區(qū)存在若干個(gè)生鮮農(nóng)產(chǎn)品需求點(diǎn)，通過(guò)規(guī)劃和設(shè)計(jì)運(yùn)輸路線，使得該若干個(gè)需求點(diǎn)的生鮮農(nóng)產(chǎn)品需求被滿(mǎn)足，并實(shí)現(xiàn)包括運(yùn)輸、庫(kù)存、時(shí)間等成本在內(nèi)的總成本最小。

與傳統(tǒng)路徑優(yōu)化問(wèn)題不同的是，生鮮農(nóng)產(chǎn)品運(yùn)輸車(chē)輛路徑優(yōu)化問(wèn)題的運(yùn)輸貨物類(lèi)型極易腐爛。一方面，這一因素使其必須利用冷鏈運(yùn)輸，以保證生鮮農(nóng)產(chǎn)品在抵達(dá)目的地時(shí)沒(méi)有出現(xiàn)損壞。另一方面，運(yùn)輸所使用的時(shí)間必須在客戶(hù)需求的時(shí)間窗內(nèi)，最好是在客戶(hù)期望的軟時(shí)間窗口內(nèi)，進(jìn)而滿(mǎn)足客戶(hù)要求。

1.2 構(gòu)建路徑優(yōu)化模型

本文所研究車(chē)輛路徑優(yōu)化問(wèn)題是考慮在單個(gè)配送中心的情況下，采用一輛運(yùn)輸車(chē)輛進(jìn)行配送。配送車(chē)輛以配送中心為起點(diǎn)，在由多個(gè)前置倉(cāng)組成的區(qū)域內(nèi)進(jìn)行配送，每個(gè)前置倉(cāng)的位置和訂單信息都是已知的，配送車(chē)輛同時(shí)向所有的前置倉(cāng)提供服務(wù)，同時(shí)假定配送車(chē)輛在所需要的配送訂單內(nèi)具有完全的載貨能力，提出以下假設(shè)：

（1）單一的配送中心，配送由一輛車(chē)完成，假定該車(chē)具有完全載貨能力；

（2）車(chē)輛從配送中心出發(fā)需要重新回到配送中心；

（3）每個(gè)前置倉(cāng)只需要經(jīng)過(guò)一次；

（4）無(wú)視時(shí)間窗的配送約束條件；

（5）配送中心、前置倉(cāng)和訂單需求量為已知條件；

（6）不考慮道路條件和惡劣氣候條件，車(chē)輛在道路上始終保持勻速狀態(tài)行駛；

（7）在配送的過(guò)程中，冷鏈車(chē)的車(chē)廂內(nèi)溫度始終保持恒定溫度；

（8）假定問(wèn)題中的路線是對(duì)稱(chēng)的，一座前置倉(cāng)到另一前置倉(cāng)的往返距離是一樣的，即dij=dji。

1.3 參數(shù)說(shuō)明

本文對(duì)模型中出現(xiàn)的一些參數(shù)與符號(hào)在表1中做解釋說(shuō)明。

1.4 建立優(yōu)化模型

對(duì)于上述求解Rmin的問(wèn)題，本文設(shè)立如下模型：

即目標(biāo)函數(shù)為：

式（1）的含義，即將一條旅行商回路中所有前置倉(cāng)的長(zhǎng)度進(jìn)行比較，在其中選擇最小路徑后，可得到所求問(wèn)題的最優(yōu)化解。式（2）和式（3），代表所求的目標(biāo)函數(shù)為該路徑的最優(yōu)化方案。

約束條件為：

式（4）表示在所求問(wèn)題中，路程的成本最小。式（5）、式（6）表示，在所求問(wèn)題中，每一個(gè)前置倉(cāng)都被服務(wù)過(guò)且僅被服務(wù)過(guò)一次。

1.5 模擬退火算法原理

模擬退火算法來(lái)源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o(wú)序狀，內(nèi)能增大，而徐徐冷卻時(shí)粒子漸趨有序，在每個(gè)溫度都達(dá)到平衡態(tài)，在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小。以一定的概率接受新?tīng)顟B(tài)所產(chǎn)生的最優(yōu)問(wèn)題解，這是算法的核心內(nèi)容，借此跳出模型中的局部極值點(diǎn)，繼續(xù)計(jì)算得到模型中的其他解，進(jìn)而得到全局最優(yōu)問(wèn)題解（見(jiàn)圖3）。

2 算例分析

本文以D公司為例進(jìn)行分析，D公司主要經(jīng)營(yíng)范圍包括水果蔬菜、肉禽蛋奶、糧油調(diào)味、酒水飲料、休閑食品等，需要每天把生鮮農(nóng)產(chǎn)品運(yùn)往各個(gè)門(mén)店前置倉(cāng)，以保證每日門(mén)店前置倉(cāng)生鮮農(nóng)產(chǎn)品的質(zhì)量和數(shù)量。目前，D公司的門(mén)店前置倉(cāng)主要分布在嘉興市的南湖區(qū)和秀洲區(qū)，各個(gè)門(mén)店前置倉(cāng)的位置比較分散。為了保證生鮮農(nóng)產(chǎn)品的質(zhì)量、數(shù)量和時(shí)效性及降低配送成本，D公司需要合理規(guī)劃從配送中心到各個(gè)門(mén)店前置倉(cāng)的配送路線。D公司為節(jié)約成本，只有一輛冷鏈運(yùn)輸車(chē)，目前對(duì)門(mén)店的需求訂單是由信息系統(tǒng)和員工共同分發(fā)的，每天由調(diào)度員通知司機(jī)需要分發(fā)的門(mén)店。然后，在獲得所需運(yùn)輸商店的分布信息后，司機(jī)往往根據(jù)自己的經(jīng)驗(yàn)在運(yùn)輸環(huán)節(jié)以“由近到遠(yuǎn)”的方式進(jìn)行運(yùn)輸。對(duì)于裝卸搬運(yùn)大多使用手推車(chē)、地牛等較為依靠人力的設(shè)備，效率較低。目前D公司的配送類(lèi)型有以下兩種：（1）直接配送，即冷鏈倉(cāng)根據(jù)日常運(yùn)營(yíng)數(shù)據(jù)估算生鮮農(nóng)產(chǎn)品日需求量，與配送中心形成訂單關(guān)系， 配送中心每天定量向門(mén)店提供生鮮農(nóng)產(chǎn)品；（2）供應(yīng)商配送，即冷鏈倉(cāng)直接接收客戶(hù)下單，將生鮮農(nóng)產(chǎn)品配送至門(mén)店，再由客戶(hù)去提貨。

3 改進(jìn)模擬退火算法優(yōu)化配送路線過(guò)程

3.1 獲取基本數(shù)據(jù)

在本模型中，以A表示分配中心，以B到Q表示每個(gè)門(mén)店前置倉(cāng)節(jié)點(diǎn)。本文從百度地圖獲取的各個(gè)門(mén)店前置倉(cāng)的位置，通過(guò)技術(shù)的手段，對(duì)地圖進(jìn)行簡(jiǎn)化，所有紅色標(biāo)記即為門(mén)店、前置倉(cāng)各節(jié)點(diǎn)的位置，經(jīng)Python軟件簡(jiǎn)化位置如圖4所示。

對(duì)坐標(biāo)簡(jiǎn)化進(jìn)行一定的處理，在圖中建立坐標(biāo)系，并且得到門(mén)店前置倉(cāng)坐標(biāo)點(diǎn)的坐標(biāo)，得到簡(jiǎn)化坐標(biāo)圖5。

經(jīng)處理后得到的各個(gè)門(mén)店前置倉(cāng)坐標(biāo)點(diǎn)的坐標(biāo)如表2所示。

同時(shí)，利用在平面直角坐標(biāo)系中兩點(diǎn)間距離公式，可以計(jì)算各個(gè)門(mén)店前置倉(cāng)坐標(biāo)點(diǎn)之間的距離，如表3所示。

3.2 將基礎(chǔ)數(shù)據(jù)帶入算法模型，求得最優(yōu)解

根據(jù)以上參數(shù)和變量，對(duì)所設(shè)計(jì)的配送路經(jīng)進(jìn)行模擬退火算法（SA）利用Python在Jupyter notebook中進(jìn)行了設(shè)計(jì)和編程。算法求解優(yōu)化前初始種群隨機(jī)路徑軌跡如圖6所示，此時(shí)初始種群中的一個(gè)路徑方案為：A-D-M-P-H-E-C-N-L-Q-B-I-F-G-O-J-K-A，總距離為158km，此時(shí)路線十分復(fù)雜，并不是最優(yōu)解，存在優(yōu)化空間。因此，引入模擬退火算法，求解最短路徑。

優(yōu)化后的路徑如圖7所示，優(yōu)化后總路線長(zhǎng)60km，優(yōu)化路線為A-Q-P-O-N-M-L-I-H-K-J-G-F-E-D-C-B-A，較原配送路線長(zhǎng)度158km共節(jié)約里程98km，節(jié)約的里程非常直觀，生成的路徑方案可為D公司的物流配送路徑選擇提供依據(jù)。

4 結(jié)語(yǔ)

首先，本文對(duì)目前生鮮市場(chǎng)的不斷擴(kuò)大做了總結(jié)和歸納。其次，對(duì)模擬退火算法（SA）和生鮮的相關(guān)概念進(jìn)行探討，并討論了模擬退火算法在生鮮配送路徑優(yōu)化上使用的可行性，為配送路徑優(yōu)化提供理論上的依據(jù)。以D公司為例，通過(guò)探討D公司目前存在的配送問(wèn)題，確立D公司配送的各個(gè)門(mén)店前置倉(cāng)的位置，建立了D公司生鮮配送模型。最后，根據(jù)D公司的經(jīng)營(yíng)狀況，將實(shí)際數(shù)據(jù)帶入建立的優(yōu)化模型，并使用Python進(jìn)行優(yōu)化運(yùn)算，得出優(yōu)化的結(jié)果。

參考文獻(xiàn)

傅文淵，凌朝東.布朗運(yùn)動(dòng)模擬退火算法[J].計(jì)算機(jī)學(xué)報(bào)，2014，37（6）：1301-1308.

田昀，梁海龍.基于模擬退火算法的物流配送路徑優(yōu)化問(wèn)題分析[J].交通科技與經(jīng)濟(jì)， 2013，15（5）：85-88.

胡治鋒，陳冬方，李慶奎，等.基于模擬退火蟻群算法的揀貨路徑規(guī)劃[J].電子設(shè)計(jì)工程， 2021，29（24）：10-14.

張波，葉家瑋，胡郁蔥.模擬退火算法在路徑優(yōu)化問(wèn)題中的應(yīng)用[J].中國(guó)公路學(xué)報(bào)，2004， 17（1）：3-7.

陳科勝，鮮思東，郭鵬.求解旅行商問(wèn)題的自適應(yīng)升溫模擬退火算法[J].控制理論與應(yīng)用， 2021，38（2）：8-13.

李朝遷，裴建朝.新型模擬退火遺傳算法在路徑優(yōu)化的應(yīng)用[J].組合機(jī)床與自動(dòng)化加工技術(shù)，2022（3）：22-26.

楊理云.用模擬退火算法求解旅行商問(wèn)題[J].微電子學(xué)與計(jì)算機(jī)，2007，24（5）：6-12.