考慮交通擁堵的城市物流配送路徑規(guī)劃研究

劉建仁

摘 ?要： 為了解決城市物流配送路徑規(guī)劃過程中存在的一些難題，以獲得更優(yōu)的城市物流配送路徑規(guī)劃結(jié)果，提出考慮交通擁堵的城市物流配送路徑規(guī)劃算法。首先分析城市物流配送路徑規(guī)劃的影響因素，并建立相應(yīng)的約束條件;然后建立城市物流配送路徑規(guī)劃的目標(biāo)函數(shù)，采用蟻群算法找到最優(yōu)城市物流配送路徑規(guī)劃方案;最后在相同實(shí)驗(yàn)環(huán)境下，與其他城市物流配送路徑規(guī)劃算法進(jìn)行對(duì)比測(cè)試。結(jié)果表明，所提算法獲得了十分理想的城市物流配送路徑規(guī)劃方案，降低了城市物流配送成本，具有更高的實(shí)際應(yīng)用價(jià)值。

關(guān)鍵詞： 城市物流; 配送路徑; 目標(biāo)函數(shù); 數(shù)學(xué)模型; 蟻群算法; 規(guī)劃方案; 影響因素分析

中圖分類號(hào)： TN911.1?34; TP391 ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼： A ? ? ? ? ? ? ? ? ? 文章編號(hào)： 1004?373X（2020）23?0116?04

Abstract： In order to cope with the difficulties existing in the process of urban logistics distribution path planning and obtain better results of urban logistics distribution path planning， an urban logistics distribution path planning algorithm considering traffic congestion is proposed. The influence factors of urban logistics distribution path planning are analyzed， and the corresponding constraints are established. And then， the objective function of urban logistics distribution path planning is established. The ant colony algorithm is used to obtain the optimal planning scheme of urban logistics distribution path. In the same experimental environment， the proposed algorithm is compared with logistics distribution path planning algorithms used in other cities. The results show that the proposed algorithm can produce a satisfactory planning scheme of urban logistics distribution path， which reduces the cost of urban logistics distribution. Therefore， it has a higher practical application value.

Keywords： urban logistics; distribution path; objective function; mathematical model; ant colony algorithm; planning scheme; influence factor analysis

0 ?引 ?言

隨著城市規(guī)模的不斷擴(kuò)大，城市常住人口越來越多，城市物流需求量快速增長(zhǎng)，物流行業(yè)在城市經(jīng)濟(jì)發(fā)展過程中具有十分重要的地位[1?3]。配送最優(yōu)路徑規(guī)劃是城市物流管理中的一項(xiàng)關(guān)鍵技術(shù)，城市物流配送路徑規(guī)劃方案不僅可以提高物流企業(yè)核心競(jìng)爭(zhēng)力，而且能夠提高物流企業(yè)經(jīng)濟(jì)效益[4?6]。尋找最優(yōu)城市物流配送路徑，提高物流服務(wù)質(zhì)量具有重要的現(xiàn)實(shí)意義[7]。

根據(jù)配送中心的結(jié)構(gòu)，可以劃分為單中心和多中心兩種城市物流配送路徑優(yōu)化問題，由于城市越來越大，當(dāng)前主要研究多中心的城市物流配送路徑優(yōu)化問題。根據(jù)車輛類型，可以劃分為同質(zhì)車輛和異質(zhì)車輛的城市物流配送路徑優(yōu)化問題[8?10]。城市物流配送路徑規(guī)劃問題與多種因素相關(guān)，建立的數(shù)學(xué)模型十分復(fù)雜，約束條件多。近幾十年以來，國(guó)內(nèi)外學(xué)者對(duì)該問題進(jìn)行了大量的研究，提出了許多城市物流配送路徑規(guī)劃算法[11]。城市物流配送路徑規(guī)劃算法可以劃分為兩類：精確算法和啟發(fā)式算法。精確算法主要有：動(dòng)態(tài)規(guī)劃法、支定界算法，它們主要針對(duì)小規(guī)模的城市物流配送路徑優(yōu)化問題，隨著客戶數(shù)量的增加，求解城市物流配送路徑的時(shí)間呈爆炸性增長(zhǎng)，無法滿足現(xiàn)代城市物流配送路徑發(fā)展要求[12]。啟發(fā)式算法分為傳統(tǒng)啟發(fā)式算法和群智能優(yōu)化算法兩類，其中傳統(tǒng)啟發(fā)式算法主要有：插入算法、最近鄰算法等，它們本質(zhì)上與精確算法相差不大，因此求解城市物流配送路徑效率低;群智能優(yōu)化算法模擬自然界生物一些行為，對(duì)城市物流配送路徑優(yōu)化問題進(jìn)行求解，主要有遺傳算法、人工魚群算法、粒子群算法等[12?14]，它們求解城市物流配送路徑效率更高，可以獲得更優(yōu)的城市物流配送路徑規(guī)劃方案。在實(shí)際中，群智能優(yōu)化算法存在一些不足，如：遺傳算法易過早收斂，難以得到城市物流配送路徑優(yōu)化問題的全局最優(yōu)解;人工魚群算法局部搜索能力差，得到局部最優(yōu)城市物流配送路徑規(guī)劃方案的概率高;粒子群算法存在搜索時(shí)間長(zhǎng)，易出現(xiàn)停滯現(xiàn)象等[15?16]。

為了獲得更優(yōu)的城市物流配送路徑規(guī)劃方案，減少城市物流配送成本，本文提出了考慮交通擁堵的城市物流配送路徑規(guī)劃算法。該方法將交通擁堵條件考慮到城市物流配送路徑規(guī)劃數(shù)學(xué)模型構(gòu)建中，并對(duì)蟻群算法進(jìn)行改進(jìn)，用于數(shù)學(xué)模型的求解，采用具體仿真對(duì)比測(cè)試，驗(yàn)證了本文城市物流配送路徑規(guī)劃算法的優(yōu)越性。

1 ?城市物流配送路徑優(yōu)化問題的數(shù)學(xué)模型構(gòu)建

1.1 ?城市物流配送流程

隨著電子商務(wù)的發(fā)展，城市物流得到了迅速的發(fā)展，城市物流配送服務(wù)質(zhì)量成為描述一個(gè)城市綜合實(shí)力的重要指標(biāo)，可以保障整個(gè)城市消費(fèi)和生活品需要，更好地完善城市現(xiàn)代化功能。城市物流配送根據(jù)客戶要求，將貨物在有效時(shí)間內(nèi)發(fā)送到客戶手中。城市物流配送流程如圖1所示。從圖1可以看出，城市物流配送包括許多內(nèi)容，如收集貨物、存儲(chǔ)、車輛貨物裝配、配送路徑規(guī)劃等，其中物流配送路徑規(guī)劃是最為關(guān)鍵的技術(shù)，合理的物流配送路徑可以減少重復(fù)運(yùn)輸，在提高了物流配送效率和企業(yè)經(jīng)濟(jì)效益的同時(shí)，可以有效緩解交通壓力，減少城市污染，因此城市物流配送路徑優(yōu)化問題是當(dāng)今城市物流管理系統(tǒng)中的關(guān)鍵問題。

1.2 ?考慮交通擁堵的城市物流配送路徑優(yōu)化問題數(shù)學(xué)模型

城市物流配送路徑規(guī)劃問題本質(zhì)上是車輛路徑優(yōu)化問題，可以定義為：在配送中心和客戶點(diǎn)已知的條件下，找到一條車輛配送最優(yōu)路徑方案，在規(guī)定的時(shí)間內(nèi)將貨物發(fā)到客戶手中，通常情況下以配送成本最小為目標(biāo)。

1） 設(shè)車輛管理使用成本為[C1]，計(jì)算公式如下：

[C1=k∈Kηkgk+k∈K i∈N j∈N h∈Hzijkhtijkh（μ+ψ）+k∈K j∈Nyjkstj+k∈K j∈Nyjkσjk*（μ+ψ）] ?（1）

式中：[ηk]表示是否使用第[k]輛車，如果使用，其值為1，否則為0;[K]表示配送車輛集合;[gk]表示第[k]輛車的發(fā)車費(fèi)用;[μ]和[ψ]分別表示車輛使用單位時(shí)間和單位人力成本;[yjk]表示第[k]輛車是否為第[j]個(gè)客戶服務(wù)，如果服務(wù)其值為1，否則為0;[stj]表示第[j]個(gè)客戶的卸貨服務(wù)時(shí)間;[tijkh]表示在道路[（i，j）]的路段[h]，第[k]輛車行駛的時(shí)間;[zijkh]表示第[k]輛車是否在道路[（i，j）]的路段[h]上行駛，如果行駛，其值為1，否則為0;[N]表示城市物流網(wǎng)絡(luò)的節(jié)點(diǎn)集合;[σjk]表示第[k]輛車在客戶點(diǎn)[j]的等待時(shí)間。

2） 設(shè)車輛運(yùn)行成本為[C2]，其計(jì)算公式為：

[C2=gf×k∈K i∈N j∈N h∈Hzijkhvijkhtijkhfijkh] （2）

式中：[gf]表示單位油耗費(fèi)用;[fijkh]表示第[k]輛車行駛在路段[h]上的油耗率;[vijkh]表示第[k]輛車在路段[h]上的行駛速度。

3） 在城市物流配送過程中，由于交通擁擠，配送車輛有時(shí)不能在規(guī)定的時(shí)間段將貨物發(fā)送到客戶手中，那么要進(jìn)行一定的懲罰，設(shè)時(shí)間懲罰成本為[C3]，其計(jì)算公式為：

2.3 ?城市物流配送路徑規(guī)劃算法的工作步驟

1） 對(duì)城市物流配送路徑規(guī)劃問題進(jìn)行分析，并設(shè)定相應(yīng)的約束條件。

2） 以城市物流配送成本最低為目標(biāo)，建立城市物流配送路徑的數(shù)學(xué)模型。

3） 設(shè)置蟻群算法的參數(shù)，如最大迭代次數(shù)NCmax、螞蟻的數(shù)量[m]等。

4） 初始化蟻群，每一只螞蟻均布置于城市物流配送中心，并對(duì)每一條路徑上的信息素量進(jìn)行初始化。

5） [NC]=1。

6） 計(jì)算每一只螞蟻下一個(gè)節(jié)點(diǎn)的轉(zhuǎn)移概率，并根據(jù)轉(zhuǎn)移概率爬行相應(yīng)的節(jié)點(diǎn)。

7） 對(duì)路徑上的信息素進(jìn)行更新。

8） [NC=NC+1]。

9） 如果滿足條件[NC]≥[NC]max，那么由最優(yōu)路徑得到城市物流配送路徑規(guī)劃方案，否則，返回步驟6）繼續(xù)進(jìn)行搜索。

綜上可知，考慮交通擁堵的城市物流配送路徑規(guī)劃算法的工作流程如圖2所示。

3 ?城市物流配送路徑規(guī)劃算法的仿真實(shí)驗(yàn)

3.1 ?實(shí)驗(yàn)環(huán)境

為了測(cè)試考慮交通擁堵的城市物流配送路徑規(guī)劃算法的性能，選擇粒子群算法的城市物流配送路徑規(guī)劃算法進(jìn)行對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)環(huán)境如表1所示。兩種算法的最大迭代次數(shù)均為500，種群的數(shù)量為20。

采用5個(gè)城市物流配送路徑規(guī)劃問題作為實(shí)驗(yàn)對(duì)象，它們的配送中心以及客戶點(diǎn)的數(shù)量如表2所示。

3.2 ?找到最優(yōu)路徑規(guī)劃方案的迭代次數(shù)對(duì)比

兩種算法找到城市物流配送路徑規(guī)劃方案的迭代次數(shù)如圖3所示。從圖3可以看出，相對(duì)于對(duì)比算法，本文算法找到城市物流配送路徑規(guī)劃方案的迭代次數(shù)明顯減少，這表明本文算法找到城市物流配送路徑規(guī)劃問題的效率更高，可以滿足城市物流配送向大規(guī)模方向發(fā)展的要求。

3.3 ?找到最優(yōu)路徑規(guī)劃方案的成功率對(duì)比

每一個(gè)問題進(jìn)行100次仿真實(shí)驗(yàn)，統(tǒng)計(jì)兩種算法找到城市物流配送路徑規(guī)劃方案的成功率，具體如圖4所示。從圖4可以看出，相對(duì)于對(duì)比算法，本文算法找到城市物流配送路徑規(guī)劃方案的成功率大幅度增加，說明本文設(shè)計(jì)的城市物流配送路徑規(guī)劃算法具有十分明顯的優(yōu)越性，這主要是考慮了交通擁堵，并對(duì)蟻群算法進(jìn)行了改進(jìn)。

3.4 ?城市物流配送成本對(duì)比

對(duì)于5個(gè)城市物流配送路徑規(guī)劃問題，兩種方法的配送成本如圖5所示。從圖5可以看出，本文算法的城市物流配送成本有所減少，可以提高城市物流配送企業(yè)的利潤(rùn)。

4 ?結(jié) ?語

城市物流配送路徑規(guī)劃問題的約束條件多，當(dāng)前算法的城市物流配送路徑規(guī)劃求解成功率低，為了獲得理想的最優(yōu)路徑規(guī)劃方案，本文提出了考慮交通擁堵的城市物流配送路徑規(guī)劃算法。首先在已有的算法基礎(chǔ)上，引入交通擁堵條件，建立更優(yōu)的城市物流配送路徑規(guī)劃數(shù)學(xué)模型，然后對(duì)傳統(tǒng)蟻群算法進(jìn)行改進(jìn)，最后通過蟻群算法找到了更優(yōu)的城市物流配送路徑規(guī)劃方案，具有十分廣泛的應(yīng)用前景。

參考文獻(xiàn)

[1] 周曉曄，崔瑤，何亮，等.基于地鐵?貨車聯(lián)運(yùn)的物流配送路徑優(yōu)化[J].交通運(yùn)輸系統(tǒng)工程與信息，2020，20（3）：111?117.

[2] 羅慶，周軍.基于混合遺傳算法的農(nóng)產(chǎn)品物流配送路徑優(yōu)化[J].江蘇農(nóng)業(yè)科學(xué)，2017，45（12）：174?177.

[3] 葛顯龍，孔陽.帶有時(shí)間窗的生鮮物流配送路徑優(yōu)化研究[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2016，46（12）：78?87.

[4] 邰曉紅，李璐.改進(jìn)節(jié)約法下的物流配送路徑優(yōu)化問題[J].遼寧工程技術(shù)大學(xué)學(xué)報(bào)（自然科學(xué)版），2016，35（6）：667?672.

[5] 葛顯龍，許茂增，王偉鑫.基于聯(lián)合配送的城市物流配送路徑優(yōu)化[J].控制與決策，2016，31（3）：503?512.

[6] 蘭輝，何琴飛，邊展，等.考慮道路通行狀況的冷鏈物流配送路徑優(yōu)化[J].大連海事大學(xué)學(xué)報(bào)，2015，41（4）：67?74.

[7] 侯玉梅，賈震環(huán)，田歆，等.帶軟時(shí)間窗整車物流配送路徑優(yōu)化研究[J].系統(tǒng)工程學(xué)報(bào)，2015，30（2）：240?250.

[8] 張勇.基于改進(jìn)蟻群算法物流配送路徑優(yōu)化的研究[J].控制工程，2015，22（2）：252?256.

[9] 蔣國(guó)清，潘勇，胡飛躍.兩階段式的物流配送路徑優(yōu)化方法[J].計(jì)算機(jī)工程與應(yīng)用，2015（2）：255?258.

[10] 戴昕.基于反向?qū)W習(xí)策略粒子群的物流配送路徑優(yōu)化研究[J].物流技術(shù)，2014，33（7）：291?294.

[11] 姚臻，張毅.基于物聯(lián)網(wǎng)和低碳雙視角下冷鏈物流配送路徑優(yōu)化研究[J].生態(tài)經(jīng)濟(jì)，2020，36（2）：61?66.

[12] 尚猛，曹峻瑋.基于鯊魚優(yōu)化算法的農(nóng)產(chǎn)品物流配送路徑優(yōu)化[J].揚(yáng)州大學(xué)學(xué)報(bào)（自然科學(xué)版），2019，22（4）：1?5.

[13] 方文婷，艾時(shí)鐘，王晴，等.基于混合蟻群算法的冷鏈物流配送路徑優(yōu)化研究[J].中國(guó)管理科學(xué)，2019，27（11）：107?115.

[14] 王登清.新零售模式下單中心物流配送路徑優(yōu)化研究[J].福州大學(xué)學(xué)報(bào)（自然科學(xué)版），2019，47（5）：695?699.

[15] 劉炎寶，王珂，楊智勇，等.考慮碳排放與新鮮度的冷鏈物流配送路徑優(yōu)化[J].江西師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2019，43（2）：188?195.

[16] 周顯春，楊婷婷，劉小飛，等.基于改進(jìn)蟻群算法的智能物流配送路徑優(yōu)化方法[J].內(nèi)蒙古師范大學(xué)學(xué)報(bào)（自然科學(xué)漢文版），2017，46（6）：888?892.