基于蟻群算法求解VRPTW路徑規(guī)劃問(wèn)題研究

魏子秋 孫明哲

摘? 要：目前我國(guó)物流業(yè)迅速發(fā)展，但是同時(shí)伴有某些方面的不足，比如：成本控制不足。文章將聯(lián)系實(shí)際情況，同時(shí)以配送車輛的運(yùn)輸總成本、總行駛距離和碳排放量為目標(biāo)函數(shù)，并充分考慮實(shí)際出現(xiàn)的約束條件，再利用MATLAB軟件運(yùn)行帶有時(shí)間窗的蟻群算法，對(duì)車輛配送路徑進(jìn)行仿真實(shí)驗(yàn)，最后尋找到最優(yōu)配送路徑以滿足目標(biāo)函數(shù)。通過(guò)實(shí)驗(yàn)表明，該數(shù)學(xué)模型和算法可以更好地解決物流配送路徑選擇的問(wèn)題，以達(dá)到降低物流成本、提高物流效率等目的。

關(guān)鍵詞：物流配送;蟻群算法;路徑優(yōu)化

中圖分類號(hào)：U116.2? ? 文獻(xiàn)標(biāo)識(shí)碼：A

Abstract： At present， China's logistics industry is developing rapidly， but it is accompanied by some shortcomings， such as insufficient cost control. In this paper， according to the actual situation， taking the total transportation cost， total driving distance and carbon emissions of distribution vehicles as objective functions， and taking full account of the actual constraints， the MATLAB software is used to run ant colony algorithm with time window to simulate the vehicle distribution path， and finally find the optimal distribution path to meet the objective function. Experiments show that the mathematical model and algorithm can better solve the problem of logistics distribution route selection， so as to reduce logistics costs and improve logistics efficiency.

Key words： logistics distribution; ant colony algorithm; path optimization

0? 引? 言

在1959年，Dantzing和Ramser 在經(jīng)過(guò)實(shí)驗(yàn)和思考后，首次提出配送車輛路徑優(yōu)化問(wèn)題[1]。在物流運(yùn)輸中配送是重要的環(huán)節(jié)，準(zhǔn)確選擇配送車輛路徑能有效縮短運(yùn)輸時(shí)間、降低運(yùn)輸成本、滿足顧客需求等目的。

關(guān)于尋找最優(yōu)配送線路問(wèn)題已經(jīng)成為研究的熱點(diǎn)之一[2]。最初蟻群算法是研究旅行商的問(wèn)題[3]，現(xiàn)在已經(jīng)廣泛應(yīng)用到許多尋找最優(yōu)解的問(wèn)題中。例如：鄭娟毅等利用蟻群算法尋找配送車輛路徑最優(yōu)的問(wèn)題[4]，張銀玲等利用蟻群算法尋找移動(dòng)機(jī)器人的最優(yōu)路徑[5-6]，魯豐玲、白俊強(qiáng)等通過(guò)蟻群算法尋找無(wú)人機(jī)最優(yōu)路徑[7-8]，蟻群算法被應(yīng)用到解決旅游最優(yōu)路線的問(wèn)題中[9-10]，Wang Yong等[11]利用蟻群算法解決VNF布局網(wǎng)絡(luò)問(wèn)題，張肖琳等[12]在綠色環(huán)保角度，對(duì)油耗、污染物排放等因素進(jìn)行約束構(gòu)建路徑優(yōu)化模型，利用蟻群算法找出最優(yōu)路徑?？梢钥闯鱿伻核惴m然可以解決許多實(shí)際問(wèn)題，但還存在不足，于是提出最大最小螞蟻系統(tǒng)[13]以及混合螞蟻系統(tǒng)[14]等方法，都在一定程度上提高了運(yùn)算效率。雖然大多數(shù)文獻(xiàn)已經(jīng)對(duì)路徑優(yōu)化進(jìn)行了充分研究，但本文結(jié)合時(shí)間窗約束建立總成本最小、總行駛距離最短、碳排放量最低的多目標(biāo)優(yōu)化模型，通過(guò)蟻群算法對(duì)設(shè)置的參數(shù)和約束條件進(jìn)行求解，得出最優(yōu)的配送路線。

1? 物流配送路徑模型

該問(wèn)題的一般提法是[15]：已知配送中心的橫、縱坐標(biāo)，所有客戶的橫、縱坐標(biāo)和需求量，車輛必須從配送中心開(kāi)始出發(fā)對(duì)每個(gè)客戶進(jìn)行配送，對(duì)每個(gè)客戶進(jìn)行配送完畢之后再回到配送中心，在車輛額定容量和行駛距離等約束條件下，使得目標(biāo)（如成本最少、路程最短等）達(dá)到最優(yōu)。在實(shí)際情況中，除了成本外還要考慮其他許多因素，車輛路徑優(yōu)化問(wèn)題大多數(shù)都是多目標(biāo)優(yōu)化，求解難度更大，所以研究帶有時(shí)間窗的路徑優(yōu)化問(wèn)題意義重大。

1.1? 問(wèn)題的描述

已知某物流公司的配送中心及客戶的橫、縱坐標(biāo)，同時(shí)由相同屬性（油耗、載重、速度）的車輛從配送中心出發(fā)向各自回路中的客戶進(jìn)行貨物配送，配送完畢之后再回到配送中心，每個(gè)客戶所需的貨物量不超過(guò)車輛運(yùn)載能力，并且每個(gè)需求點(diǎn)只能在配送時(shí)間窗內(nèi)由一輛車配送，每輛車所服務(wù)的客戶需求之和不超過(guò)車輛的載重量。

在實(shí)際情況下，為達(dá)到配送中的總運(yùn)輸成本最低、總行駛距離最短、碳排放量最低等目的而提出的問(wèn)題。

1.2? 建立多目標(biāo)數(shù)學(xué)模型

1.2.1? 參數(shù)和變量

由此建立數(shù)學(xué)模型，用O表示配送中心倉(cāng)庫(kù);有n輛相同的車輛，給每條回路上的I個(gè)客戶提供貨物;用a表示車輛的固定成本;用N表示確定所需的車輛數(shù)目，每輛車的編號(hào)為i，并且只在一條回路上行駛;用a表示車輛在客戶j和k的配送過(guò)程中所產(chǎn)生的運(yùn)輸成本;用b表示客戶點(diǎn)j和配送中心O之間的產(chǎn)品總量;每輛車i的路徑為c;車輛i服務(wù)于客戶j為c;用I=0表示車輛i沒(méi)有可服務(wù)的客戶;用d表示在車輛i的配送回路中，兩個(gè)相鄰客戶所配送需要的路程;用d表示車輛i從第I個(gè)客戶行駛到配送中心O的距離;用d表示客戶j和k之間的距離;用e表示車輛i配送結(jié)束之后回到配送中心所剩下的貨物總量;用L表示車輛i行駛的最遠(yuǎn)路程;用p表示車的碳排放量;用Q表示在車輛i的回路中，客戶j所需要的貨物量;用w表示車輛i的額定載重;用ET表示車輛i分別給客戶j最早的配送時(shí)間;用LT表示車輛i分別給客戶j最晚的配送時(shí)間;用WT表示車輛i從客戶j出發(fā)的時(shí)間;用RT表示車輛i到達(dá)客戶j的時(shí)間;用α和β分別表示硬、軟時(shí)間窗懲罰成本系數(shù);用UT表示車輛i對(duì)客戶j所服務(wù)的時(shí)間;用T表示車輛i從客戶j配送完畢后，再出發(fā)到客戶k所耗費(fèi)的時(shí)間;用v表示車輛在配送過(guò)程中的速度;用S表示所有車輛進(jìn)行配送的總路程;用Z表示所有車輛在配送過(guò)程中的運(yùn)輸總成本;用F表示所有車輛總的碳排放量水平。

為了滿足客戶點(diǎn)j設(shè)置的配送時(shí)間窗，在對(duì)客戶點(diǎn)j進(jìn)行配送時(shí)，配送車輛到達(dá)時(shí)間RT必須滿足下式：ET≤RT≤LT;

配送車輛i在客戶j到k間行駛的時(shí)間：T=d/v;

配送車輛i從客戶j出發(fā)抵達(dá)下一個(gè)客戶點(diǎn)k的時(shí)間：RT=WT+UT+T;

時(shí)間窗懲罰函數(shù)系數(shù)用集合H表示：H=α， β。

1.2.2? 目標(biāo)函數(shù)

由描述的問(wèn)題和分析可知，在進(jìn)行物流配送時(shí)應(yīng)首先考慮總成本最小，其中包括運(yùn)輸成本、車輛固定成本、違時(shí)懲罰成本;同時(shí)又要考慮最優(yōu)路徑的選擇和碳排放量最低，從而得到多目標(biāo)函數(shù)：

minZ=a×sign

I+a×N+max

ET

-RT， 0+max

RT

-LT， 0? ? ? ?（1）

minS=

d+d×sign

I? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（2）

minF=p×d×sign

I? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （3）

目標(biāo)函數(shù)（1）表示使車輛在最佳運(yùn)輸路徑上的運(yùn)輸總成本最小（前兩項(xiàng)為運(yùn)輸成本，后兩項(xiàng)為懲罰成本）;目標(biāo)函數(shù)（2）表示使車輛對(duì)所有客戶完成配送并返回配送中心后，進(jìn)行配送的總路程最短;目標(biāo)函數(shù)（3）表示使車輛的排放量降到最低，以降低環(huán)境污染。

1.2.3? 約束條件

對(duì)上述目標(biāo)函數(shù)進(jìn)行約束：

Q≤w? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （4）

d+d×sign

I≤L? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（5）

0≤I≤m? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （6）

I=m? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（7）

C=

C

|C∈V

，V

，…，

V， j=1，2，…，

I? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （8）

C∩C=φ， ?≠j? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （9）

e=0， ?∈m? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（10）

sign

I=

（11）

N≤n? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （12）

RT∈

ET，

LT? ? i∈N， j∈m? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （13）

約束條件（4）表示為車輛的容量條件，每輛車所裝載的貨物在小于等于額定載重量的情況下，滿足相應(yīng)回路中客戶的總需求;約束條件（5）表示每個(gè)子回路中的車輛配送路程不超過(guò)所有車輛總配送路程;約束條件（6）表示配送車輛在各自的回路中所服務(wù)的客戶不超過(guò)客戶總量;約束條件（7）表示所有需求車輛所服務(wù)的客戶總數(shù)等于實(shí)際的客戶總數(shù)，保證所有客戶都能得到服務(wù);約束條件（8）表示每輛車所服務(wù)客戶的集合;約束條件（9）表示每個(gè)客戶被有且僅有一輛車所服務(wù);約束條件（10）確保所有運(yùn)行車輛空車返回配送中心;約束條件（11）表示第i輛車是否參與服務(wù);約束條件（12）表示有進(jìn)行配送任務(wù)的車輛數(shù)要小于等于總的車輛數(shù);約束條件（13）表示車輛在符合相應(yīng)客戶的時(shí)間窗內(nèi)進(jìn)行配送。

2? 蟻群算法

Marco Dorigo通過(guò)對(duì)螞蟻群體覓食的研究，隨后在1992年提出蟻群算法[16]（Ant Colony Optimization， ACO），它是一種模擬仿真尋找最優(yōu)路徑的算法，該算法具體是模仿螞蟻在尋找食物過(guò)程中分泌一種特殊的可隨著時(shí)間的推移而揮發(fā)的信息素來(lái)引導(dǎo)其他螞蟻選擇此路徑的行為，經(jīng)過(guò)一段時(shí)間后尋找到最優(yōu)路徑的目的。

2.1? 參數(shù)設(shè)置

蟻群算法中有最基本的6個(gè)參數(shù)：用m表示螞蟻的總數(shù);用Q表示螞蟻一次循環(huán)釋放信息素的總量;用t表示在運(yùn)算過(guò)程中最大的迭代次數(shù);用α表示信息素因子;用β表示啟發(fā)函數(shù)因子;用ρ表示信息素?fù)]發(fā)因子。

2.2? 構(gòu)建行動(dòng)路徑

在構(gòu)建路徑的過(guò)程中，用輪盤(pán)賭法選擇螞蟻要到達(dá)的下一座城市。計(jì)算公式如下：

p=

式中：用i表示起點(diǎn)，j表示終點(diǎn);ηt=1/d表示i和j之間距離的倒數(shù)，ηt是啟發(fā)函數(shù);用τt表示在時(shí)間t時(shí)刻，起點(diǎn)i到終點(diǎn)j之間所包含的信息素濃度大小;用allowed表示螞蟻k還沒(méi)有到達(dá)過(guò)剩下城市的集合;此路徑上的信息素濃度大小由兩地距離長(zhǎng)短控制，兩地距離越短，信息素濃度越大，選擇此路徑的幾率就會(huì)越大，反之，距離越遠(yuǎn)濃度越小;從公式可以看出信息素因子α決定信息素濃度，啟發(fā)函數(shù)因子β決定轉(zhuǎn)移期望對(duì)螞蟻k從i到j(luò)可能性的貢獻(xiàn)程度。

2.3? 更新信息素

螞蟻釋放的信息素具有隨著時(shí)間揮發(fā)的特性。因此，在每一次迭代完成后，都要將螞蟻所帶來(lái)的相關(guān)信息和信息素濃度進(jìn)行更新，規(guī)則為：

τt+1=τt×1-ρ+Δτ， 0<ρ<1

Δτ=Δτ

式中：1-ρ表示信息素殘留系數(shù);Δτ表示迭代過(guò)程中，路徑ij上信息素增量;Δτ表示第k只螞蟻在本次迭代中留在ij上的信息素量，如下式：

Δτ=

式中：L表示螞蟻k所經(jīng)過(guò)的所有路徑之和。

2.4? 判斷迭代是否終止

是否達(dá)到迭代次數(shù)可以判斷仿真實(shí)驗(yàn)是否終止。一次迭代就是指m只螞蟻都走完所有的路徑，即存在m個(gè)搜索路徑。在所有的路徑中選擇最短的路徑，做出這一次迭代的可視化結(jié)果，更新信息素;然后將新的最短路徑與上一次的最短路徑進(jìn)行對(duì)比，同時(shí)增加1次迭代次數(shù);最后計(jì)算當(dāng)前迭代次數(shù)與最開(kāi)始設(shè)置的迭代次數(shù)相差多少次，若正好相等則停止迭代，否則進(jìn)行下一次迭代。

3? 仿真實(shí)驗(yàn)

某配送中心（編號(hào)0）有額定載重為1 000kg的配送車輛6輛，需在42天內(nèi)（1 008h）將貨物派送至19個(gè)客戶點(diǎn)，從0

～19依次對(duì)配送中心倉(cāng)庫(kù)和19個(gè)客戶點(diǎn)進(jìn)行編號(hào)，其中配送中心以及各個(gè)客戶點(diǎn)之間的橫、縱坐標(biāo)，客戶的需求量、左時(shí)間窗、右時(shí)間窗和所對(duì)應(yīng)的服務(wù)時(shí)間如表1所示。

將表1中的數(shù)據(jù)換成矩陣形式后，導(dǎo)入到MATLAB中，并且對(duì)算法中的參數(shù)進(jìn)行多輪假設(shè)，得出最優(yōu)的參數(shù)數(shù)值為：螞蟻總數(shù)量m=35，釋放信息素常量Q=100，運(yùn)算最大迭代次數(shù)t=100，信息素因子α=1，啟發(fā)函數(shù)因子β=3，信息素?fù)]發(fā)因子ρ

=0.4，等待時(shí)間重要程度因子γ=2，時(shí)間窗跨度重要程度因子δ=3。

對(duì)參數(shù)設(shè)置完畢后，將表1中數(shù)據(jù)與參數(shù)值同時(shí)輸入到程序中，經(jīng)過(guò)100次仿真實(shí)驗(yàn)，得到6種結(jié)果，其中798.4072km為最優(yōu)路徑，計(jì)算過(guò)程如表2所示。

得出4條車輛最優(yōu)配送回路路線：

配送路線1：0→5→13→19→10→14→12→2→0，運(yùn)輸量為835kg;

配送路線2：0→17→18→3→11→9→6→1→0，運(yùn)輸量為1 000kg;

配送路線3：0→7→4→0，運(yùn)輸量為293kg;

配送路線4：0→8→15→16→0，運(yùn)輸量為455kg。

4條配送回路路線如圖1所示：

圖1為MATLAB運(yùn)行出的相對(duì)最優(yōu)配送路徑，藍(lán)點(diǎn)為車輛配送中心，藍(lán)色線為配送路線1，紅色線為配送路線2，綠色線為配送路線3，橙色線為配送路線4。

在原始的算法中沒(méi)有對(duì)顧客服務(wù)時(shí)間的約束，會(huì)增加懲罰成本并且大幅降低顧客滿意度，此方法將配送車輛在時(shí)間約束下計(jì)算出相對(duì)最優(yōu)的路徑，更好地降低物流成本，提高客戶滿意度等優(yōu)勢(shì)?？梢?jiàn)，帶有時(shí)間窗的蟻群算法更加符合企業(yè)的成本控制和顧客的需求，使該模型的配送效益最高，適用性更強(qiáng)。

4? 結(jié)? 論

如今我國(guó)的物流產(chǎn)業(yè)正在進(jìn)行迅速的發(fā)展，但不可避免會(huì)出現(xiàn)成本控制等問(wèn)題，所以合理規(guī)劃最優(yōu)路徑以降低成本顯得尤為重要。此方法在車輛的行駛距離、物流成本、碳排放量等目標(biāo)基礎(chǔ)上，做了數(shù)學(xué)優(yōu)化模型，并利用MATLAB運(yùn)行帶有時(shí)間窗的蟻群算法尋找車輛的最優(yōu)路徑，達(dá)到車輛行駛距離、運(yùn)輸成本、碳排放量最低的目標(biāo)，此計(jì)算結(jié)果在一定程度上對(duì)實(shí)際情況有參考價(jià)值。

參考文獻(xiàn)：

[1] Dantzig G B， Ramser J H. The truck dispatching problem[J]. Management Science， 1959，6（1）：80-91.

[2] 羅梓瑄，劉學(xué)文. 基于蟻群算法的物流配送路徑優(yōu)化研究[J]. 重慶工商大學(xué)學(xué)報(bào)（自然科學(xué)版），2020，37（4）：89-94.

[3] 李炳宇，蕭蘊(yùn)詩(shī). 基于模式求解旅行商問(wèn)題的蟻群算法[J]. 同濟(jì)大學(xué)學(xué)報(bào)（自然科學(xué)版），2003（11）：1348-1352.

[4] 鄭娟毅，付姣姣，程秀琦. 面向物流車輛路徑規(guī)劃的自適應(yīng)蟻群算法[J]. 計(jì)算機(jī)仿真，2021，38（4）：477-482.

[5] 張銀玲，牛小梅. 蟻群算法在移動(dòng)機(jī)器人路徑規(guī)劃中的仿真研究[J]. 計(jì)算機(jī)仿真，2011，28（6）：231-234.

[6] 張曉玲，羅印升，張寶峰，等. 基于蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃[J]. 激光雜志，2016，37（11）：80-83.

[7] 魯豐玲. 基于蟻群算法的無(wú)人機(jī)艦機(jī)協(xié)同任務(wù)規(guī)劃[J]. 艦船科學(xué)技術(shù)，2019，41（18）：67-69.

[8] 白俊強(qiáng)，柳長(zhǎng)安. 基于蟻群算法的無(wú)人機(jī)航路規(guī)劃[J]. 飛行力學(xué)，2005（2）：35-38.

[9] 萬(wàn)慧云，蔣艷. 基于蟻群算法的5A景點(diǎn)旅游路線規(guī)劃問(wèn)題研究[J]. 軟件導(dǎo)刊，2019，18（4）：141-144.

[10] 李夢(mèng)丹. 基于蟻群算法西安旅游路線的優(yōu)化研究[J]. 價(jià)值工程，2020，39（20）：136-137.

[11]? Wang Yong， Han Zunpu. Ant colony optimization for traveling salesman problem based on parameters optimization[J]. Applied Soft Computing， 2021，107（2）：107439.

[12] 張肖琳，梁力軍，張夢(mèng)婉. 綠色物流配送路徑優(yōu)化研究——以京東配送為例[J]. 價(jià)格月刊，2020（8）：64-69.

[13]? Stutzle T. MAX-MIN ant system[J]. Future Generation Computer Systems， 2000，16（8）：899-914.

[14]? Gambardella L M， Dorigo M. An ant colony system hybridized with a new local search for the ordering problem[J]. Informs Journal of Computing， 2000，12（3）：237-255.

[15]? Solomon M M. Algorithms for the vehicle routing and scheduling problems with time window constraints[J]. Operations Research， 1987，35（2）：254-265.

[16]? Marco Dorigo. Using transputers to increase speed and flexibility of genetics-based machine learning systems[J]. Microprocessing and Microprogramming， 1992，34（1-5）：147-152.