改進蟻群算法對車輛配送二次調度的Matlab實現*

□ 李 沖 □ 錢 靜

江南大學 機械工程學院 江蘇無錫 214122

帶時間窗動態車輛路徑問題 WTVRP（Vehicle RoutingOptimizationProblemwithTimeWindows）是指一定數量的工位點，各自需求不同數量的貨物量，配送中心統一向工位點提供貨物，通過安排一定順序的行駛路線，使工位點在滿足一定約束條件下，實現諸如路徑最短、成本值最小、耗費時間最少等目標。路線安排過程中，根據工位點需求、車輛、運輸網絡等信息是否確定，WTVRP可以分為靜態車輛路徑問題SVRP（StaticVehicleRoutingOptimizationProblem）和動態車輛路徑問題DVRP （DymamicVehicleRouting OptimizationProblem）［1］。 其中 DVRP 又包括了工位點需求 VRP、動態車輛 VRP和動態運輸網絡 VRP［2-4］。本文主要研究帶時間窗的動態車輛VRP。

車輛配送過程中造成動態性主要由于兩個原因：①現有車輛總載荷小于貨物運輸總量，為了完成配送任務，同一輛車在滿足時間窗的條件下可能需要進行多次指派；②配送過程中車輛出現故障，需要重新派出車輛替換故障車輛［5］。此外，當前對蟻群算法的研究，大部分都暗含了現有車輛總載荷大于全部運輸物料重量這個假設，而在實際生產中，工位配送總需求大于現有車輛載重總和的情況常會發生。考慮到運輸成本，通常希望完成任務車輛數盡可能少，因此需考慮對部分車輛進行多次配送指派。

本文通過改進基本蟻群算法［6-8］，解決了對車輛進行多次派遣的問題。在算法實現中，設定先完成任務的車輛即返回原點，判斷其是否滿足其余還未運輸路徑的時間窗來判斷此輛車是否接受第二次任務指派，這可以在保證時間窗的條件下使用較少的車輛數來完成任務，節省下來的車輛可以用來進行突發事件的配送或替代發生故障的車輛。

1 WTVRP數學模型構建

WTVRP問題是在VRP基礎上提出的，一般定義為：已知n個工位點坐標及貨物需求量，要求用m輛汽車在時間窗內從配送中心送達。每輛車的最大載荷確定，且每次配送量不能超過該車的最大載荷。每個工位點每次需求必須且只能由一輛車來滿足［9］。筆者將所有車輛在任務時間內行駛距離最小作為該模型的優化目標，即：

式中：dij表示從工位i到工位j的行駛距離。

針對該數學模型，約束條件為式（2）～（7）：

式中：Xijk為決策變量，表示第k輛車是否從工位i出發開向工位j，如果是，其值為1，否則為0。

式中：yik為決策變量，表示工位i的任務是否由車輛k完成，如果是，其值為1，否則為0。

式中：gi表示工位i的貨物需求量；Qk表示牽引車k最大裝載量。

式 （4）對車輛裝載量進行約束，即每輛車在一條運輸路徑上貨物裝載量總和不能大于該車輛最大載荷。

式（5）確保每個工位的任務由一輛車來完成，且每個工位都得到了服務。

式（6）防止車輛在同一個工位點轉圈。

式中：ti為車輛到達工位i的實際時間；si為對工位i的服務時間；Ei和Li表示到達工位i的最早時間和最晚時間范圍。

式（7）確保車輛到達工位時不超出時間窗范圍。

2 基本蟻群算法的改進

蟻群算法（AntSystem）是一種仿生優化算法，具備了并行自催化以及優良的分布式計算機制，魯棒性較強［10］，該算法最初用來解決旅行商問題 TSP（Traveling SalemanProblem）。而WTVRP的復雜程度要遠高于TSP，兩者有一定相似性又存在許多差別。因此設計蟻群算法來求解VRTWP時，要充分結合WTVRP的具體要求，并借鑒蟻群算法求解TSP的經驗。搜索時間長，易陷入局部最優，這是蟻群算法需要改進的缺點。

WTVRP與TSP的不同之處主要體現在表1所示的3個方面。

表1 WTVRP與TSP蟻群算法求解的差別

2.1 改進基本蟻群算法以實現WTVRP優化

Pij（ij）為模型中t時刻車輛k從工位i到工位j的轉移概率，在滿足裝載量和時間窗前提下，主要由兩方面因素決定：①通往下一城市路徑長度以及路徑上的信息量；②時間窗限制因素，即車輛等待時間較短優先原則和時間窗較小優先原則。因此，t時刻車輛k在工位i對下一個工位j的選擇概率為：

式中：τij和ηij分別表示信息素濃度和能見度；α為信息啟式因子；β 為期望啟發式因子；［ej，lj］表示工位 j點的時間窗；tij為由工位i到達工位j所需時間 （到達工位i服務的時刻+工位i服務時間+從工位i到j的行駛時間）；ω1和 ω2表示權重系數，均∈［0，1］，且有 ω1+ω2=1。

在這里ηij與解決TSP問題不同:

式中：ω（j）為在工位j的開始服務時間之前到達所需要的等待時間。

2.1.2 改進信息素更新方式

在基本蟻群算法中，每只螞蟻遍歷的路徑都需要對其進行信息素的更新，這種方式收斂較慢，既拖延了計算時間，同時全局優化性能也不明顯。本文保留了全局最優解，同時為了擴大信息素更新范圍，避免陷入局部最優，選取每次迭代結果中前幾位的“精英螞蟻”進行信息素更新。

針對基本蟻群算法的缺陷，本文采用如下動態的信息素更新方式:

式中：△τgori為全局最優解或迭代最優解的倒數；ρ是信息素揮發系數。

在搜索過程中，先對局部信息素進行更新，當迭代到一定次數n時，整個系統進行一次全局信息素更新。接下來繼續對局部最優信息素進行更新，兩者交叉進行，直至達到算法中規定的最大迭代次數Nmax時停止。這樣可以避免發生早熟現象，同時增加解的多樣性，有效提升了算法性能和解的質量。

隨著搜索次數的增加和信息素的更新，某個可行解上的信息量可能會出現極大值或極小值：極大值會導致搜索早熟，算法陷入局部最優使搜索停滯；極小值則會減緩收斂速度使求解過程延長。因此將每條軌跡上信息素限制在［τmin，τmax］之間，若 τij≤τmin，則 τij=τmin；若 τij≥τmax，則 τij=τmax。

算法初始時，信息素尚未更新，使用式（11)、(12）來確定 τmin和 τmax:

當信息素開始更新后則采用式（13）確定 τmax（t）：

式中：Lgb為通過PFIH算法構造初始可行解得到的可行路徑總長度；σ為精英螞蟻的個數，即每次循環中找出全局最優解的螞蟻個數；τmin（t）不變。

2．2 蟻群算法參數組合選擇

在蟻群算法中參數的選擇直接影響到計算結果。根據具體問題不同，需要對參數進行相應調整，通過實驗分析，下面方法可以快速選擇出最優組合參數。

（1）城市規模/螞蟻數目≈1．5，首先確定螞蟻數。

（2）對取值范圍較大的信息啟發式因子α、期望啟發式因子β、信息素強度Q進行粗調，來得到效果較好的解。

（3）對取值范圍較小的信息素揮發因子ρ進行微調，提升最優解的效果。

重復以上步驟，直至得到理想參數組合。

2．3 車輛行駛狀態的統計

在改進的蟻群算法中，單只螞蟻k構成的可行解即可看作某一車輛的運輸路徑。算法中規定車輛完成運輸任務即刻返回運輸中心，返回運輸中心的車輛在滿足時間窗的條件下可以進行二次運輸指派，即某一車輛完成的運輸路徑可以看作在時間窗約束下，多只螞蟻構成可行解的集合，這里需要對滿足約束條件的可行解進行有效合并。

為了獲取車輛的行駛狀態、所在工位、預計回到運輸中心時間等信息，需要對全部車輛的狀態進行跟蹤，實現實時調度優化。因此需要建立車輛-時間狀態圖，用來查看車輛的狀態。

具體實現過程為：對每輛車進行編號，并建立時間統計表。當第一輛車V1走完第一個子路徑R0后回到原點，將回到原點時間t0記入時間統計表TV1中。接下來繼續檢測其它子路徑的出發時間 t1，t2，t3……如果t1≥t0，那么車輛V1再次出發走路徑R1，完成任務后返回原點，將時間t1記入時間統計表TV1中，將兩條路徑合并到車輛V1的行走路徑表中，并把新路徑的工位記入禁忌表。依次不斷迭代，直到最后一次返回原點的時間無法滿足剩余子路徑出發時間要求時，然后才能派出新的一輛車。依照此模式直到走完所有子路徑后，就可以得到最佳車輛數。

按照上面算法通過Matlab建立車輛—時間狀態模型：縱坐標依次對派遣車輛進行編號，橫坐標時間軸上采用不同顏色來顯示車輛的不同行駛狀態。根據圖表，可以清楚了解到路上行駛的車輛和原點剩余車輛，以方便下一次車輛運送或處理突發事件。

3 算法實現

針對本文中車輛配送二次調度，對蟻群算法改進后，步驟如圖1所示。

4 算例

▲圖1 改進后蟻群算法流程圖

▲圖2 改進前蟻群算法迭代次數與總路程的關系

▲圖3 改進后蟻群算法迭代次數與總路程的關系

選取數據模型見表2，模型中共22個坐標點，其中第一個坐標點為運輸中心，車輛在230s內完成全部運輸任務，貨物量運輸單位為kg。

表2 各工位需求信息

各參數取值為：螞蟻數量m=15；根據以往經驗和多次計算比較，取信息啟發式因子α=0.9；期望啟發式因子β=5；信息素揮發因子ρ=0.1；信息素強度Q=1；車輛載重為150kg，最大迭代次數為100次。

經過計算得到的最佳路徑：Routes=

車輛V1: 1 14 7 22 1 0 0

車輛V2: 1 6 3 1 13 5 1

車輛V3: 1 21 2 1 0 0 0

車輛V4: 1 20 16 17 4 19 1

車輛V5: 1 18 10 11 12 1 0

車輛V6: 1 15 8 9 1 0 0

圖2、圖3分別為改進前、后蟻群算法迭代次數與總路程的關系，圖中橫坐標為迭代次數，縱坐標為里程數。由圖2中可以看出，達到最佳里程數需迭代30次以上，而改進后（圖3）的蟻群算法經過20次迭代即可達到最優值，從而保證了計算的時間限制。

改進后蟻群算法車輛巡回圖如圖4所示，車輛最佳里程數為680.465，改進前為706.538。蟻群算法改進后車輛—時間狀態如圖5所示，圖中白色為車輛在原點停止時間段，黑色為車輛行駛時間段，深灰色為車輛在其它工位等待時間段，淺色為車輛服務時間段。從圖中可以清晰顯示出全部車輛任一時刻的狀態。通過可行解路線進行合并對車輛進行二次指派，車輛2走完了工位6和3后返回原點，重新裝載貨物后對工位13和5進行了貨物運送。

表3 改進前后結果對比

通過表3可以看出，改進后最佳里程數和得到最佳里程的迭代次數都好于改進前，縮短了行駛路程，同時提高了計算效率，并節省了一輛車輛。

5 結束語

本文針對VRPTW，建立了相應的基于時間軸的數學模型。通過改進的蟻群算法，首先排出最優路徑，然后根據時間選擇出可合并路徑，從而得出最佳車輛數。運算時間和最佳里程數均有所優化。完成任務的車輛返回原點重新接受任務，提高了單輛車利用率，使帶動態時間窗的車輛路徑優化更加具有實際應用價值。

▲圖4 改進后蟻群算法車輛巡回路線

▲圖5 改進后蟻群算法車輛-時間狀態圖

［1］ 郎茂祥，胡思繼．車輛路徑問題的禁忌搜索算法研究［J］．管理工程學報，2004，18（1）:81-84．

［2］ 謝秉磊，郭耀煌，郭強．動態車輛路徑問題：現狀與展望［J］．系統工程理論方法應用，2002，11（2）:116-119．

［3］ 王訓斌，陸慧娟，陳五濤．帶時間窗動態車輛路徑問題的改進蟻群算法［J］．工業控制計算機，2009，22（1）：41-43．

［4］ 郝會霞．基于改進蟻群算法的物流配送車輛路徑優化方法的研究［D］．西安：長安大學，2008．

［5］ 郎茂祥．動態車輛配送優化調度問題的模型及其兩階段算法［J］．交通運輸系統工程與信息，2009，9（4）：140-144．

［6］ 汪鵬飛．并行蟻群算法及其應用研究［D］．成都：西南交通大學，2008．

［7］ 劉霞．給予最大最小螞蟻系統的動態車輛路徑問題研究［J］．計算機工程與科學，2013，35（1）:130-137．

［8］ 王俊鴻，修桂華．二次蟻群算法在運輸調度問題中的應用［J］．計算機應用與軟件，2008，25（7）：71-73．

［9］ 陳迎欣．基于改進蟻群算法的車輛路徑優化問題［J］．計算機應用研究，2012，29（6）:2031-2034．

［10］王君，李波，盧志剛．帶時間窗動態車輛路徑問題的優化調度策略［J］．計算機工程，2012，38（13）:137-141．