多配送中心路徑優(yōu)化研究

韓茜 苗倩

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

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

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

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

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

2 算法設(shè)計(jì)

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

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

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

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

步驟4：進(jìn)行選擇、交叉、變異操作。

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

3 算法實(shí)驗(yàn)及結(jié)果分析

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

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

4 結(jié)束語

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

參考文獻(xiàn)

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

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

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

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