基于蟻群算法的配送路徑優(yōu)化研究

安曉雯 董福貴

隨著信息技術(shù)的進(jìn)步，電子商務(wù)也在迅速發(fā)展，當(dāng)前制約電子商務(wù)發(fā)展的關(guān)鍵問題是物流配送成本過高、配送效率過低。合理的配送路徑可以更好的縮減企業(yè)的成本，提高服務(wù)質(zhì)量，因此對(duì)于電商企業(yè)配送路徑優(yōu)化的研究具有很大的價(jià)值。本文針對(duì)某電商企業(yè)，對(duì)路徑優(yōu)化問題展開了討論。首先建立VRP模型，提出利用蟻群算法對(duì)VRP問題進(jìn)行求解，借助MATLAB軟件進(jìn)行仿真實(shí)驗(yàn)，實(shí)例分析結(jié)果發(fā)現(xiàn)優(yōu)化后的方案縮短了配送路徑，減少了配送成本。

一、引言

信息技術(shù)的日新月異，促使電子商務(wù)迅速崛起，并帶動(dòng)了物流業(yè)快速發(fā)展，但是與此同時(shí)物流配送也成為制約電子商務(wù)發(fā)展的關(guān)鍵因素，因此優(yōu)化配送路線，降低物流成本，提高顧客滿意度是提高企業(yè)競(jìng)爭(zhēng)力的關(guān)鍵。

羅梓瑄等在物流配送路徑優(yōu)化中，以成本最小化和最小碳排放量為目標(biāo)構(gòu)建了多目標(biāo)優(yōu)化模型，利用蟻群算法對(duì)其進(jìn)行求解，他們認(rèn)為蟻群算法能多點(diǎn)同時(shí)搜索獨(dú)立解，具有較強(qiáng)魯棒性。最后通過仿真，計(jì)算出最優(yōu)配送路徑。張曉娜等以果蔬配送路線最優(yōu)、最大化保持果蔬新鮮為目標(biāo)，構(gòu)建路徑優(yōu)化模型，通過蟻群算法求解。吳雨婷等以配送路徑最短、時(shí)間最少、成本最低、客戶滿意度最高為目標(biāo)，構(gòu)建基于蟻群算法的冷鏈物流配送路徑優(yōu)化研究模型。吳競(jìng)鴻先分析了上海某連鎖商店配送中存在的問題，針對(duì)現(xiàn)狀建立了VRP模型。最后借助MATLAB軟件以及真實(shí)數(shù)據(jù)對(duì)模型進(jìn)行了求解，提出配送路徑優(yōu)化方案。汪越等認(rèn)為在配送過程中加入時(shí)間窗限制可以更好的減少配送成本，他在文章中采用路徑長(zhǎng)度和空載率兩個(gè)指標(biāo)對(duì)帶時(shí)窗物流運(yùn)輸車輛路徑進(jìn)行優(yōu)化，結(jié)果表明配送中心車輛調(diào)度效率提高了，為配送中心合理進(jìn)行配送車輛調(diào)度提供借鑒。馬貴平等在傳統(tǒng)蟻群算法基礎(chǔ)上加入運(yùn)輸時(shí)間、成本和道路通暢程度等約束條件，提出改進(jìn)蟻群算法，并和CSAACO算法和ACO算法對(duì)比，結(jié)果顯示改進(jìn)蟻群算法尋優(yōu)能力更強(qiáng)。張肖琳等在構(gòu)建路徑優(yōu)化模型時(shí)考慮到了車輛在配送中對(duì)環(huán)境產(chǎn)生的影響，通過蟻群算法進(jìn)行優(yōu)化求解，結(jié)果證實(shí)了該模型可以達(dá)到路徑最短和對(duì)環(huán)境影響最小的目的。萬國(guó)海建立了以成本最小化為目標(biāo)的電子商務(wù)配送路徑優(yōu)化模型，并在傳統(tǒng)蟻群算法基礎(chǔ)之上做出了改進(jìn)，結(jié)果表明改進(jìn)后的蟻群算法提高了物流配送效率，降低了成本。

本文在查閱資料基礎(chǔ)之上，研究了針對(duì)某電商企業(yè)的路徑優(yōu)化問題。本文首先建立了VRP模型，通過蟻群算法對(duì)模型進(jìn)行求解，實(shí)例分析結(jié)果顯示蟻群算法在配送路線優(yōu)化中的有效性。

二、物流配送路徑優(yōu)化數(shù)學(xué)模型

（一）問題描述

電商企業(yè)配送路徑優(yōu)化可描述為：已知某地區(qū)的客戶數(shù)量、每位客戶的坐標(biāo)和需求量，由配送中心的配送車輛向客戶配送所需量的貨物。車輛從配送中心出發(fā)，每位客戶只能由一輛配送車輛配送，且每個(gè)客戶點(diǎn)只能被訪問一次，最后配送車輛回到配送中心，實(shí)現(xiàn)路徑最短、時(shí)間最少或成本最低等目標(biāo)，同時(shí)還需要滿足一些約束條件：車輛負(fù)載和配送時(shí)間等。

（二）物流配送路徑優(yōu)化模型

1.參數(shù)說明

M={1，2，…，m}表示客戶點(diǎn)集合

n表示配送車輛的數(shù)量

q是配送車輛的最大負(fù)載

c表示配送車輛的固定成本

cij表示配送車輛從客戶點(diǎn)i到客戶點(diǎn)j的運(yùn)輸成本

qi表示客戶點(diǎn)i的需求量

0-1變量

2.數(shù)學(xué)模型

以配送路徑總成本最低作為目標(biāo)函數(shù)：

上式表示每個(gè)客戶點(diǎn)只能由一輛配送車輛進(jìn)行配送

上式表示每輛配送車輛向客戶點(diǎn)配送的時(shí)候載重量不能超過自身最大負(fù)載

上式表示到達(dá)客戶點(diǎn)和離開客戶點(diǎn)的配送車輛有且僅有一輛

（三）蟻群算法的最優(yōu)路徑設(shè)計(jì)

第t時(shí)刻，節(jié)點(diǎn)i上的螞蟻數(shù)量為Bi（t），那么螞蟻數(shù)量為，n是節(jié)點(diǎn)數(shù)，即客戶數(shù)i，j節(jié)點(diǎn)距離為dij。螞蟻沒爬過時(shí)，初始信息素是相同的，τij（0）=C，第t時(shí)刻，節(jié)點(diǎn)i上的螞蟻k向節(jié)點(diǎn)j轉(zhuǎn)移的概率為：

allowedk是螞蟻k選擇的節(jié)點(diǎn)集合，α，β是啟發(fā)因子和期望因子，表示節(jié)點(diǎn)i和j間的信息素和能見度。

蟻群優(yōu)化具有正反饋機(jī)制，路徑越短，信息素越多，螞蟻每爬行一步，信息素就會(huì)進(jìn)行更新。

ρ是信息素?fù)]發(fā)系數(shù)，Δτij是i和j間的信息素增量。

三、實(shí)例分析

（一）測(cè)試環(huán)境

某電商企業(yè)有5輛配送車，車輛最大負(fù)載為4噸，由配送中心向15個(gè)客戶點(diǎn)點(diǎn)進(jìn)行配送，配送中心編號(hào)為0，客戶點(diǎn)編號(hào)從1-15。配送點(diǎn)坐標(biāo)及需求量如表1所示。

表1 配送點(diǎn)坐標(biāo)及需求量

（二）測(cè)試結(jié)果

用MATLAB進(jìn)行仿真實(shí)驗(yàn)時(shí)，設(shè)置最大迭代次數(shù)為100，螞蟻個(gè)數(shù)為30，車輛載重為4噸。測(cè)試結(jié)果如圖1所示，表2是MATLAB求解結(jié)果，路徑變化如圖2所示：

由表2可知通過蟻群算法優(yōu)化之后的最優(yōu)配送路徑方案總共有三條：

路徑1 由配送中心出發(fā)，經(jīng)過1-2-3-4-5-6-8-7，最終回到配送中心，路徑1總配送距離為184.411km，運(yùn)輸量為3.84t。

路徑2 由配送中心出發(fā)，經(jīng)過10-9-12-13-11，最終回到配送中心，路徑2總配送距離為40.216km，運(yùn)輸量為3.76t。

路徑3 從配送中心出發(fā)，經(jīng)過14-15，最終回到配送中心，路徑3總配送距離為50.836，運(yùn)輸量為1.04t。最終某電商企業(yè)的總配送距離為275.463km。

由上圖和表可知，本文某電商企業(yè)的路徑在蟻群算法優(yōu)化之后由之前的336.6km，縮減到后來的275.4629km，減少了61.1371km。路徑縮短，配送效率也提高了，可以看出優(yōu)化效果還是很明顯的。

四、結(jié)語

在物流快速發(fā)展的今天，物流配送的重要性不言而喻。運(yùn)輸成本作為物流成本中重要的一環(huán)，對(duì)企業(yè)的發(fā)展也存在一定的影響。本文首先建立VRP模型，然后通過蟻群算法對(duì)模型進(jìn)行求解，最后針對(duì)某電商企業(yè)進(jìn)行實(shí)例分析，結(jié)果表明蟻群算法可以優(yōu)化配送路線，提高配送效率，且效果較為明顯。我認(rèn)為本文還存在一些不足之處，綠色發(fā)展已經(jīng)成為各國(guó)大力追逐的目標(biāo)，物流運(yùn)輸業(yè)作為一個(gè)不可或缺的行業(yè)理應(yīng)承擔(dān)起推動(dòng)各國(guó)綠色發(fā)展的重任，因此在今后的研究中除了考慮配送路徑和成本，還需要加入對(duì)碳排放量、時(shí)間窗、貨車裝載率等的考慮。

（作者單位：華北電力大學(xué) 經(jīng)濟(jì)與管理學(xué)院）

基金項(xiàng)目：華北電力大學(xué)哲學(xué)社會(huì)科學(xué)繁榮計(jì)劃專項(xiàng)項(xiàng)目（2019FR003）。