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

魏子秋 孫明哲

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

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

中圖分類號：U116.2? ? 文獻標(biāo)識碼：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)過實驗和思考后，首次提出配送車輛路徑優(yōu)化問題[1]。在物流運輸中配送是重要的環(huán)節(jié)，準(zhǔn)確選擇配送車輛路徑能有效縮短運輸時間、降低運輸成本、滿足顧客需求等目的。

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

1? 物流配送路徑模型

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

1.1? 問題的描述

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

在實際情況下，為達到配送中的總運輸成本最低、總行駛距離最短、碳排放量最低等目的而提出的問題。

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

1.2.1? 參數(shù)和變量

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

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

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

配送車輛i從客戶j出發(fā)抵達下一個客戶點k的時間：RT=WT+UT+T;

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

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

由描述的問題和分析可知，在進行物流配送時應(yīng)首先考慮總成本最小，其中包括運輸成本、車輛固定成本、違時懲罰成本;同時又要考慮最優(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）表示使車輛在最佳運輸路徑上的運輸總成本最小（前兩項為運輸成本，后兩項為懲罰成本）;目標(biāo)函數(shù)（2）表示使車輛對所有客戶完成配送并返回配送中心后，進行配送的總路程最短;目標(biāo)函數(shù)（3）表示使車輛的排放量降到最低，以降低環(huán)境污染。

1.2.3? 約束條件

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

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）表示每個子回路中的車輛配送路程不超過所有車輛總配送路程;約束條件（6）表示配送車輛在各自的回路中所服務(wù)的客戶不超過客戶總量;約束條件（7）表示所有需求車輛所服務(wù)的客戶總數(shù)等于實際的客戶總數(shù)，保證所有客戶都能得到服務(wù);約束條件（8）表示每輛車所服務(wù)客戶的集合;約束條件（9）表示每個客戶被有且僅有一輛車所服務(wù);約束條件（10）確保所有運行車輛空車返回配送中心;約束條件（11）表示第i輛車是否參與服務(wù);約束條件（12）表示有進行配送任務(wù)的車輛數(shù)要小于等于總的車輛數(shù);約束條件（13）表示車輛在符合相應(yīng)客戶的時間窗內(nèi)進行配送。

2? 蟻群算法

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

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

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

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

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

p=

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

2.3? 更新信息素

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

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

Δτ=Δτ

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

Δτ=

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

2.4? 判斷迭代是否終止

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

3? 仿真實驗

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

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

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

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

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

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

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

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

配送路線3：0→7→4→0，運輸量為293kg;

配送路線4：0→8→15→16→0，運輸量為455kg。

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

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

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

4? 結(jié)? 論

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

參考文獻：

[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é)報（自然科學(xué)版），2020，37（4）：89-94.

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

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

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

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

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

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

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

[10] 李夢丹. 基于蟻群算法西安旅游路線的優(yōu)化研究[J]. 價值工程，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] 張肖琳，梁力軍，張夢婉. 綠色物流配送路徑優(yōu)化研究——以京東配送為例[J]. 價格月刊，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.