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

魏子秋，孫明哲

（河北科技大學(xué) 經(jīng)濟管理學(xué)院，河北 石家莊 050018）

0 引 言

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

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

1 物流配送路徑模型

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

1.1 問題的描述

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

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

1.2 建立多目標數(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 目標函數(shù)

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

目標函數(shù)（1） 表示使車輛在最佳運輸路徑上的運輸總成本最?。ㄇ皟身棡檫\輸成本，后兩項為懲罰成本）；目標函數(shù)（2）表示使車輛對所有客戶完成配送并返回配送中心后，進行配送的總路程最短；目標函數(shù)（3） 表示使車輛的排放量降到最低，以降低環(huán)境污染。

1.2.3 約束條件

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

約束條件（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 年提出蟻群算法（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)建路徑的過程中，用輪盤賭法選擇螞蟻要到達的下一座城市。計算公式如下：

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

2.3 更新信息素

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

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

2.4 判斷迭代是否終止

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

3 仿真實驗

某配送中心（編號0） 有額定載重為1 000kg 的配送車輛6 輛，需在42 天內(nèi)（1 008h） 將貨物派送至19 個客戶點，從0～19 依次對配送中心倉庫和19 個客戶點進行編號，其中配送中心以及各個客戶點之間的橫、縱坐標，客戶的需求量、左時間窗、右時間窗和所對應(yīng)的服務(wù)時間如表1 所示。

表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 所示。

表2 6 次路徑距離計算結(jié)果

得出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。

圖1 最優(yōu)配送路徑圖

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

4 結(jié) 論

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