基于改進模擬退火算法的配送路徑優化研究

錢葉霞 陳子敬

摘 要：“互聯網+”時代背景下，越來越多的企業紛紛入駐生鮮電商行業，生鮮電商的企業盈利和競爭壓力隨之增大，這就要求生鮮企業做好精細化的成本控制策略，實現物流系統的高效運作。在生鮮配送過程中，配送路徑優化是極為重要的一環，所以生鮮電商企業必須做好物流配送路徑的合理規劃，降低配送環節的成本，增加物流總收益。本文以生鮮農產品為研究對象，建立以最短路徑為目標函數的數學模型，利用改進模擬退火算法進行研究，并通過PyCharm軟件進行求解。求解結果表明：本文所建立的車輛路徑優化模型能有效縮短配送線路的總距離，降低配送運輸的整體運營成本，進一步驗證了車輛路徑優化模型和改進算法的有效性和實用性。

關鍵詞：生鮮農產品；配送路線優化；改進模擬退火算法；建模分析

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

中圖分類號：F572 文獻標識碼：A 文章編號：2096-0298（2023）04（b）--04

隨著我國經濟水平的提升，人民群眾對食品的消費觀念已經不再是“民以食為天”，而是逐步轉變成“民以鮮為天”。收入水平的不斷提升和經濟社會的進一步發展，使人們從原來“吃得飽”的需求轉變為“吃得好”，同時在食品質量和安全問題上投入更多的關注，尤其是對配送要求較高的生鮮食品。

2020年6月，國家發改委發布《關于進一步優化發展環境促進生鮮農產品流通的實施意見》，旨在統籌推進生鮮運輸市場和疫情防控，規范市場。2020年6月，農業農村部發布《關于進一步加強農產品倉儲保險冷鏈設施建設工作的通知》，細化農產品生鮮運輸，落實建設生鮮農產品信息平臺。2022年4月，交通運輸部發布《關于加快推進冷鏈物流運輸高質量發展的實施意見》，旨在通過促進冷鏈運輸發展來解決現有的生鮮運輸問題。2020年發布的中央一號紅頭文件《關于抓好“三農”領域重點工作確保如期實現全面小康的意見》明確指出“要推進農產品保鮮冷藏冷凍物流基礎設施建設，增強生鮮農產品的冷藏冷凍物流統一規劃，提升制定標準和布局分類”。由此看來，本文通過優化路徑解決生鮮運輸和配送問題具有一定的現實意義。

如圖1所示，2020年新冠疫情推動生鮮電商加速發展，生鮮電商市場規模不斷擴大。

2021年上半年，中國生鮮電商交易規模約2362.1億元；2021年底，生鮮電商交易規模約達4658.1億元，同比增長27.92%。如圖2所示，隨著生鮮電商的發展及模式的成熟、用戶網購生鮮習慣的養成，生鮮電商行業滲透率逐漸提高，越來越多的企業紛紛進入生鮮電商行業，生鮮電商企業盈利和競爭壓力隨之增大，這就要求生鮮企業做好精細化的成本控制策略，實現物流系統的高效運作。在生鮮配送過程中，配送路徑優化是極為重要的一環，本文聚焦生鮮配送路徑優化問題進行研究。

1 生鮮農產品配送路徑模型建立

1.1 生鮮農產品配送路徑優化問題概述

生鮮農產品配送問題可描述為：某個地區存在若干個生鮮農產品需求點，通過規劃和設計運輸路線，使得該若干個需求點的生鮮農產品需求被滿足，并實現包括運輸、庫存、時間等成本在內的總成本最小。

與傳統路徑優化問題不同的是，生鮮農產品運輸車輛路徑優化問題的運輸貨物類型極易腐爛。一方面，這一因素使其必須利用冷鏈運輸，以保證生鮮農產品在抵達目的地時沒有出現損壞。另一方面，運輸所使用的時間必須在客戶需求的時間窗內，最好是在客戶期望的軟時間窗口內，進而滿足客戶要求。

1.2 構建路徑優化模型

本文所研究車輛路徑優化問題是考慮在單個配送中心的情況下，采用一輛運輸車輛進行配送。配送車輛以配送中心為起點，在由多個前置倉組成的區域內進行配送，每個前置倉的位置和訂單信息都是已知的，配送車輛同時向所有的前置倉提供服務，同時假定配送車輛在所需要的配送訂單內具有完全的載貨能力，提出以下假設：

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

（2）車輛從配送中心出發需要重新回到配送中心；

（3）每個前置倉只需要經過一次；

（4）無視時間窗的配送約束條件；

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

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

（7）在配送的過程中，冷鏈車的車廂內溫度始終保持恒定溫度；

（8）假定問題中的路線是對稱的，一座前置倉到另一前置倉的往返距離是一樣的，即dij=dji。

1.3 參數說明

本文對模型中出現的一些參數與符號在表1中做解釋說明。

1.4 建立優化模型

對于上述求解Rmin的問題，本文設立如下模型：

即目標函數為：

式（1）的含義，即將一條旅行商回路中所有前置倉的長度進行比較，在其中選擇最小路徑后，可得到所求問題的最優化解。式（2）和式（3），代表所求的目標函數為該路徑的最優化方案。

約束條件為：

式（4）表示在所求問題中，路程的成本最小。式（5）、式（6）表示，在所求問題中，每一個前置倉都被服務過且僅被服務過一次。

1.5 模擬退火算法原理

模擬退火算法來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內部粒子隨溫升變為無序狀，內能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態，在常溫時達到基態，內能減為最小。以一定的概率接受新狀態所產生的最優問題解，這是算法的核心內容，借此跳出模型中的局部極值點，繼續計算得到模型中的其他解，進而得到全局最優問題解（見圖3）。

2 算例分析

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

3 改進模擬退火算法優化配送路線過程

3.1 獲取基本數據

在本模型中，以A表示分配中心，以B到Q表示每個門店前置倉節點。本文從百度地圖獲取的各個門店前置倉的位置，通過技術的手段，對地圖進行簡化，所有紅色標記即為門店、前置倉各節點的位置，經Python軟件簡化位置如圖4所示。

對坐標簡化進行一定的處理，在圖中建立坐標系，并且得到門店前置倉坐標點的坐標，得到簡化坐標圖5。

經處理后得到的各個門店前置倉坐標點的坐標如表2所示。

同時，利用在平面直角坐標系中兩點間距離公式，可以計算各個門店前置倉坐標點之間的距離，如表3所示。

3.2 將基礎數據帶入算法模型，求得最優解

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

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

4 結語

首先，本文對目前生鮮市場的不斷擴大做了總結和歸納。其次，對模擬退火算法（SA）和生鮮的相關概念進行探討，并討論了模擬退火算法在生鮮配送路徑優化上使用的可行性，為配送路徑優化提供理論上的依據。以D公司為例，通過探討D公司目前存在的配送問題，確立D公司配送的各個門店前置倉的位置，建立了D公司生鮮配送模型。最后，根據D公司的經營狀況，將實際數據帶入建立的優化模型，并使用Python進行優化運算，得出優化的結果。

參考文獻

傅文淵，凌朝東.布朗運動模擬退火算法[J].計算機學報，2014，37（6）：1301-1308.

田昀，梁海龍.基于模擬退火算法的物流配送路徑優化問題分析[J].交通科技與經濟， 2013，15（5）：85-88.

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

張波，葉家瑋，胡郁蔥.模擬退火算法在路徑優化問題中的應用[J].中國公路學報，2004， 17（1）：3-7.

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

李朝遷，裴建朝.新型模擬退火遺傳算法在路徑優化的應用[J].組合機床與自動化加工技術，2022（3）：22-26.

楊理云.用模擬退火算法求解旅行商問題[J].微電子學與計算機，2007，24（5）：6-12.