韓茜 苗倩

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

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

中圖分類號： 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 引言

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

1 問題描述與數(shù)學模型

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

2 算法設計

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

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

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

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

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

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

3 算法實驗及結(jié)果分析

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

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

4 結(jié)束語

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

參考文獻

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

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

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

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