多配送中心路徑優化研究

韓茜 苗倩

摘 要針對冷鏈物流配送客戶分布不均勻，導致單一配送中心壓力過大、配送中心之間車輛調度不協調的問題，提出了一種改進的遺傳算法求解多配送中心路徑優化問題的方法。建立了基于K-means聚類算法與遺傳算法相結合的冷鏈物流車輛路徑優化模型。給出基于全局最優的區域劃分與車輛路徑協調優化策略，以實現多配送中心協同配送。最后，通過實例分析證明了該算法及優化策略可以有效地減少運輸成本，提高多配送中心整體的工作效率。

關鍵詞冷鏈物流;多配送中心;區域劃分

中圖分類號： U12 文獻標識碼： A

AbstractAiming at the problem of uneven distribution of cold chain logistics distribution customers，resulting in excessive pressure in a single distribution center and uncoordinated vehicle scheduling between distribution centers，an improved genetic algorithm for solving multi-distribution center path optimization problems is proposed.A cold chain logistics vehicle routing optimization model based on K-means clustering algorithm and genetic algorithm is established.A global optimization based region division and vehicle path coordination optimization strategy is proposed to achieve coordinated distribution of multiple distribution centers. Finally，an example analysis shows that the algorithm and optimization strategy can effectively reduce transportation costs and improve the overall efficiency of multi-distribution centers.

Key WordsCold chain;Multi-distribution center;Regional division

0 引言

隨著現代社會城市規模不斷擴大，電子商務發展迅速，從下單到送貨再到收貨，其中最重要的就是物流配送這一環節[1]。生鮮產品本身所具有的易腐性使得配送成本本身就高于常溫產品，同時也給它的配送質量提出了更高的要求。冷鏈物流配送受到越來越多學者的關注，文獻[2]根據生鮮產品的時效性強的特點，將顧客滿意度用模糊隸屬度函數表示，驗證了模型及算法的有效性。文獻[3]針對顧客的隨機需求，建立了多溫共配路徑優化模型。本文針對冷鏈品的配送問題，考慮企業有多個配送中心，多輛配送車，將K-means算法與改進的遺傳算法相結合，從全局上合理劃分配送區域和配送路徑，以達到降低成本、提高冷鏈品配送質量的目的。

1 問題描述與數學模型

設某城市中有一個總調度中心安排訂單配送，H個配送中心，每個配送中心服務的顧客區域構成一個配送分區，負責給n個客戶點完成配送任務，配送中心擁有的車輛數為Kh，且每個配送中心車輛數相等，車型統一，每輛車的最大載裝為Q。已知客戶i到客戶j的運輸距離為dij以及客戶i的需求qi，要求設計一套合理的調度方案，使所有客戶點的貨物需求都得到滿足，并使總成本最小且滿足以下約束條件：式中gkh表示第h個配送中心的第k輛冷藏車所產生的固定成本;φ為單位行駛里程成本;p為冷鏈產品的單位價值;β1、β2為運輸過程中的產品腐敗率和裝卸過程中的產品腐敗率;Q■■是第h個配送中心的車輛k到達客戶i時車上所運載的剩余貨量。

2 算法設計

遺傳算法的啟發來自達爾文的進化論，它是依照自然選擇和自然進化的原理，模擬生物在自然界中的進化過程所得到的一種優化求解方法[4]。本文利用K-means算法對客戶點進行聚類，將聚類的結果作為遺傳算法中的初始種群，并且使每個個體滿足約束條件，然后利用遺傳算法對路徑進行優化，之后再隨機選擇聚類方案再次進行K-means區域劃分，直到找到最優解。算法流程如下：

步驟1：將配送中心作為起始點，顧客用自然數進行編號，作為遺傳算法的染色體。

步驟2：將自然數列隨機排列形成一條染色體，通過循環隨機生成N條染色體，作為一個初始種群。

步驟3：把初始種群中的每一個個體帶入適應度函數中，求出每個個體的適應度。

步驟4：進行選擇、交叉、變異操作。

步驟5：如果滿足終止條件，則輸出解，否則返回步驟2。

3 算法實驗及結果分析

假設某配送站有3個配送中心，每個配送中心有3輛配送車輛，共有60個客戶分布點，已知客戶需求量且配送車輛的車型規格統一。

對于多配送中心路徑優化問題，如果采用傳統的固定區域劃分方法，就只能求出每個區域的最優解，而不利于求整體最優解。本文在解決問題時采用動態區域劃分的方法，這樣做能夠根據不同顧客點的位置靈活分配配送任務，使結果更加接近于整個配送區域的全局最優解。根據實驗結果分析比較可知：在進行區域動態劃分后，顧客訂單所在的配送區域發生了改變，配送路徑也和原來有很大區別，輛配送的顧客數目也能相對更加均勻一些。從距離上看，基于固定區域劃分的配送距離為989.53km，基于動態區域劃分的配送距離為905.5km，相比原來減少了8.5%，這在一定程度上能降低配送成本。

4 結束語

本文研究中采用動態劃分配送區域的方法，將多個配送中心問題轉化為多個單一配送中心問題，在一定程度上減少了原算法的復雜程度。通過這種方式，根據顧客點所在位置的不同，隨時調整車輛配送區域，為現實應用提供了可行依據。算法實驗結果表明：在動態區域劃分下，車輛的配送距離有所縮短，能夠在一定程度上減少企業的生產成本。將來在研究過程中可以還考慮顧客需求量對路徑規劃的影響，或是還可以把時間窗作為限制條件一并進行優化。

參考文獻

[1]殷脂，葉春明.多配送中心物流配送車輛調度問題的分層算法模型[J].系統管理學報，2014，23（04）：602-606.

[2]邵舉平，曹倩，沈敏燕，孫延安.生鮮農產品配送中帶時窗的VRP模型與算法[J].工業工程與管理，2015，20（01）：122-127，134.

[3]王淑云，孫虹.隨機需求下冷鏈品多溫共配路徑優化研究[J].工業工程與管理，2016，21（02）：49-58.

[4]藍永聯.廣交長運冷鏈物流配送路徑優化研究[D].華南理工大學，2017.