基于近代優化算法的生鮮團購配送最優路線模型

摘" 要：該項目以某優選的生鮮團購配送為例，在考慮各項約束的基礎上，以生鮮配送中心點到各個小區的總配送路程最小為宗旨，利用回溯法選優搜索出生鮮配送的中心小區，配送中心選址可有效地降低社區團購的運營成本及物流度等等。然后就小區的生鮮團購配送的路線方面，結合實際，采用模擬退火算法建立模型，求解出生鮮配送的最優路徑。優化后的路線能夠提高配送效率，節省配送費用，節約人力、物力、財力等資源。

關鍵詞：社區團購；配送中心選址；回溯法；模擬退火算法；最優路徑

中圖分類號：TP18" " " " 文獻標志碼：A" " " " " 文章編號：2095-2945（2023）10-0013-04

Abstract： Based on the selected fresh food group purchase and distribution， considering various constraints， aiming at minimizing the total distribution distance from the fresh distribution center to each district， this paper uses the backtracking method to select the central district of fresh distribution. The location of distribution center can effectively reduce the operating cost and logistics of community group purchase and so on. Then， in view of the route of fresh group purchase and distribution in the community， combined with practice， the simulated annealing algorithm is used to establish a model to solve the optimal path of birth fresh distribution. The optimized route can improve distribution efficiency， save distribution costs， and save manpower， material resources， financial resources and other resources.

Keywords： community group purchase; location of delivery center; back tracking method; simulated annealing algorithm; optimal path

伴隨著人們生活水平的不斷提高，人民開始關注食品的質量，對綠色食品的需求也在日益增長，生鮮的市場前景也蒸蒸日上，但是有很多農產品因為各個方面的影響不能及時進行銷售，隨著新興的生鮮電商模式的興起，傳統的生鮮購物方式已經改變。社區團購已經開始逐漸走入到人們的生活之中，用戶可以通過搜索關鍵詞直接找到線上小程序。用戶在小程序里面了解到不同產品的資料，有效地減少了用戶線下購物的時間。社區團購逐漸開始成為人們日常的消費習慣，因此對社區團購的產品要求也越來越高，所以社區團購的便利性在社區中作用越來越重要[1]。隨著社區團購規模的不斷擴大，用戶對于社區團購有了更多的期待。

另外，由于當下國內疫情的影響，使農產品蔬菜、水果等生鮮產品滯銷。但是人們還想要購買新鮮、高質量的產品。基于這個原因，生鮮配送的社區團購開始利用自身的優勢慢慢走進大眾的視野[2]。社區團購由于自身“預售+自提”的形式很大程度減少了人員接觸。在這種情形之下，社區團購迅速發展起來，幾乎遍及每個小區。社區團購確定以生鮮為主要產品，品類豐富，價格比較合理，使大多數的用戶享受到便利快捷的購物體驗。社區的生鮮配送雖然已經逐漸被平臺的用戶所了解，但是在配送路線、物流管理等方面還存在可以優化的空間[3]。

為了解決生鮮平臺配送過程中所出現的各種問題，首先，可以根據社區的位置來設置合理的配送中心，基于每個社區地理位置的不同，選取一個合理的配送路線，優化后的配送方案可以減少人力、物力的消耗，提高生鮮配送平臺的收益。其次，從消費者的角度出發，如果可以在很短的時間拿到自己所需要的商品，這也會吸引更多用戶來使用配送平臺。

1" 點對點配送中心的選擇

1.1" 研究思路

為了更好地完成生鮮配送，首先查詢了許昌市需要配送的各個小區的經緯度坐標，應用已知的地球半徑化弧度制轉化出各個小區間的直線距離。為了可以更快速地完成配送，尋找一個中心點，使得其配送路程最短。假設每個小區所需配送的物資量是相同的，將一個小區去往另外的小區作為一種方法，構建規劃模型并且使用回溯法[4]不斷搜索，求出所有小區到達其他小區的路線，最終尋找到一個小區到其他小區的路程最短，這個小區即為中心點。

在找到配送的中心點之后，為了尋找最優的生鮮配送路線圖減少配送時長，最先通過小區的坐標獲悉小區之間的距離，接著建造相關路徑的線性規劃模型，并且結合模擬退火算法得到途經所有的小區進行生鮮配送時候得到的最佳配送路線。通過最優路線圖結合貨車的速度及在每個小區的停留時長計算出貨車配送生鮮的總時間。

1.2" 基本假設

①每個小區之間的直線距離作為貨車的行駛距離。②忽略道路擁堵等情況對貨車配送生鮮造成的影響。③貨車在進行配送的時候無事故發生，保持勻速行駛，不受外界因素影響。④假設貨車進行生鮮配送時，貨車裝載的物資滿足小區所需。⑤貨車的平均速度為45 km/h，在每個小區卸貨的時長為0.2 h。

1.3" 配送小區相關數據

現在假設有34個小區需要進行生鮮的配送，其經緯坐標為（ai，bi）。為了得到小區之間的實際距離，假設地球是一個標準的球體，中心原點是地球的核心，構建空間直角坐標系，從而把經維度轉換成空間直角坐標，轉化的公式為

（ai，bi）=（R cosai cosbi，R sinai cosbi，R sinbi）。（1）

若有A和B 2個小區，從而得到2個小區之間的距離，即公式為

d=R arccos 。（2）

通過調查發現，共有34個小區需要進行貨物的配送，現在對34個小區進行順次編號，同時查尋數據得到每一小區的經維度坐標，得出表1。

通過上面的小區之間的地理坐標位置，接著利用距離的轉化公式（1）和（2）分別算出2個小區間的直線距離，見表2。

1.4" 點對點配送中心選址

如果擁有足夠的配送車輛，可以選定一個小區作為配送中心[5]的選址，向其他需要配送的小區進行點對點配送，合理確定配送中心地址可以提高超市配送效率，使配送系統的經濟效益最大化，能夠大幅度地降低運輸成本，便于貨物配送，保證商品到達的及時性，因此確定配送中心的位置對提高物流系統經濟效益具有重要作用。

假設變量dij是第i個小區和第j個小區的距離，選擇變量Zj是0～1的變量，代表是否被選為配送中心

Zj=1，被選成配送中心0，未被選成配送中心。 （3）

又因為在選址的過程之中只需要找1個小區作為配送的中心點

Zj=1，j=1，2，…，n。（4）

故在整個過程之中，貨車的配送物資的最小公里數是

min Zjdijei，（5）

式中：ei是小區i對于生鮮數量的需求。

選定一個小區作為配送中心前往其他小區進行生鮮的配送，假設每個小區所需要配送的生鮮數量都是相同的，對于生鮮配送中心[6]的選址，選擇回溯法用來求解模型的規劃。最終得到選擇茂源金色家園小區作為配送中心，配送的路線長度最短，為179.9 km，以茂源金色國際小區為配送中心的配送路線如圖1所示。

在進行中心小區的選定的時候，不斷進行試探得出每一個小區到其他小區的總距離，如果在試探的過程之中此小區到所有小區的總距離比上一個小區到所有小區總距離長，退回上一步，一直到試探出所有小區到每個小區的總距離，一直到滿足到達所有小區的距離最短。最后求出選擇茂源金色家園小區來進行生鮮的存放、配送的總路線長度是最短的，路線長度為179.9 km，故以茂源金色家園小區為中心的配送路線的配送中心。

2" 用模擬退火算法求最優配送路徑

如果只考慮一臺配送車輛進行該區域生鮮配送，可以選定一條最優配送路徑，向其他需要配送的小區進行單程循環配送，合理規劃配送路線可以大幅度地降低運輸成本，保證商品到達的及時性，因此確定合理規劃路線可以提高配送效率和配送系統經濟效益。

模擬退火算法是開始于某個比較高初溫，隨著不斷降下的溫度參數，不斷尋找符合目標的最優解，最終搜索結果達到全局最優并且跳出搜索[7-8]。模擬退火算法是通過搜索的突跳性最終達到全局最優的優化算法。

模擬退火算法求配送最優路線過程，詳細流程如圖2所示。

1）形成一個全新的遍歷路線M（i+1），算出路線M（i+1）的長L（M（i+1））。

2）如果L（M（i+1））lt;L（M（i）），采納M（i+1）為新的路線，不然以模擬退火的幾率采納M（i+1），接著降溫。

3）反復程序1），2）直至滿意退出要求。

在進行模擬退火的過程之中，首先根據小區隨機生成一個路線圖，接著遍歷所有配送的小區形成一個路線圖，接著求出配送路線的長度，如果在此次中生成的路線長度比初次路線的長度短，就采用此次配送路線，否則就一直生成路線，直到求出途經所有小區的配送最短路線。在配送中心的分析選擇恒大悅龍臺小區，可以使得配送的總路程最短，但是只有一輛貨車進行配送的時候，可以選擇任意一個小區作為配送的中心，只要配送的路線按照最優路徑進行配送都可達到配送的總路程最短。

對于只有一輛貨車進行生鮮的配送，只用考慮貨車總的生鮮配送的總路線最短，即為生鮮配送的路線達到最優化，當生鮮配送的路線達到最優，此時為配送的路線為最優路徑。貨車在小區卸貨的時間是一定的，只有不斷優化生鮮的配送路線，才可達到生鮮配送的總時間最短。通過模擬退火算法，不斷地進行搜索，不斷生成生鮮配送的路線圖，并且與上一條生鮮配送路線圖對比選出最短的那條路線，一直把所有的路線圖都運行出來，選出最優路徑，直至達到了整個搜索過程的最優解，此時求出來生鮮配送的最優路徑。通過模擬退火算法能夠快速地求出34個小區進行生鮮配送的一條最優路徑。結合算法并且通過小區的坐標，以及matlab得到了一輛貨車在進行生鮮配送時的路程為71.24 km，一輛貨車配送的路線圖，如圖3所示。

在一輛貨車配送的時候將茂源金色家園小區作為配送的起點，即可得到小區配送路線：12-gt;16-gt;15-gt;10-gt;25-gt;26-gt;24-gt;11-gt;7-gt;6-gt;13-gt;17-gt;22-gt;18-gt;14-gt;4-gt;1-gt;2-gt;5-gt;3-gt;23-gt;8-gt;9-gt;27-gt;28-gt;29-gt;32-gt;33-gt;31-gt;34-gt;30-gt;19-gt;21-gt;20。

在進行模擬退火的過程之中，首先根據小區隨機生成一個路線圖，接著遍歷所有配送的小區形成一個路線圖，接著求出配送路線的長度，如果在此次中生成的路線長度比初次路線的長度短，就采用此次配送路線，否則就一直生成路線，直到求出途經所有小區的配送最短路線。最終時間為10.60 h。這個時間為配送的時候貨車回到了配送點，如果只是求配送地區到所有配送小區的時間再減去配送起始點到配送終點的距離，即為配送的長度71.24 km。但是只有一輛貨車進行配送的時候，可以選擇任意一個小區作為配送的中心，只要配送的路線按照最優路徑進行配送都可達到配送的總路程最短。

3" 結論

對于只有一輛貨車進行生鮮的配送，把貨車的生鮮配送路線設成一個閉圈的形式，不管運輸的起點在哪，都可以將配送的落地點作為原點，充分運用閉圈的性質，因而可以減少返程時多余的距離，如果將全程都設置成為配送的路線，有利于配送工作的效益。模型基于模擬退火算法解決最優路線，工作均衡調度，可以應用于個人旅游、旅游商問題、抗災路線巡視及物資運輸等路線問題。模擬退火算法相比其他類型的算法比較簡單、容易操作，可以被許多地方廣泛運用，受到的限制條件相比其他算法少，非常適用于并行運算，可以有效地減少不必要的物資消耗。通過不斷的探索與回溯法求出配送小區的中心點，能夠減少多種資源的浪費，快速地把物品送到所需的地方。

選擇一輛貨車進行配送的時候總時長不到11 h，能夠滿足社區團購第二天提貨的需求，因此進行貨物配送的時候，可以參照此條配送路線開展配送服務。如果配送時間有更短的要求，則需要增加配送車輛和人員，重新分配配送小區，這些問題將在后續的研究過程中繼續討論。

參考文獻：

[1] 李燕瓏，于麗君，韋利娟.新零售背景下的社區團購發展現狀及問題研究[J].對外經貿，2022（3）：71-74.

[2] 李夢夢，房路生.社區團購平臺商業模式解析及發展展望[J].經濟研究導刊，2022（3）：83-86.

[3] 孫清，張韻辰，魏雪純，等.消費者對社區團購滿意度的影響因素及探究[J].現代商業，2022（7）：42-44.

[4] 劉長河.災情巡視最優路線的尋徑算法[J].北京建筑大學學報，2019，35（3）：68-73.

[5] 孫佳寧，馬海龍，張立臣，等.求解0-1背包問題的融合貪心策略的回溯算法[J].計算機技術與發展，2022，32（2）：190-195.

[6] 趙雪婷，賈鵬，高犇，等.新鮮度限制約束下物流配送中心選址-路徑優化[J].包裝工程，2022，43（5）：232-241.

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

[8] 黃凱奇，陳岳坪，張怡坤.自由曲面加工誤差預測——基于模擬退火算法優化的BP神經網絡算法[J].廣西科技大學學報，2022（2）：69-73，82.