中等動態度車輛路徑問題的雜交螞蟻算法

與中等動態度有關的VRP在現實中有著廣泛的應用背景。例如長途郵件的快遞業務，動態顧客常常因為他們需要得到優先服務而被插入到某些靜態顧客前面。長途郵件的快遞業務中那些要求在一個小時內將郵件寄走的動態顧客就比在一天之內都可以接受服務的靜態顧客應該得到優先服務。可以把前者看成是需要得到立即服務的動態顧客，而把后者作為可以暫緩的靜態顧客。

相比弱動態度動態車輛路徑問題中等動態度動態車輛路徑問題中動態顧客比例較高通常占到50%左右，對于這類問題，常常采用基于概率信息模型的A—Priori優化方法求解。與以往研究不同的是本文旨在研究在假設條件下如何構建描述中等動態車輛路徑的數學模型，并構造雜交螞蟻算法，進行求解并與Benchmark Problem的基本螞蟻算法的求解結果進行比較，證明算法的可行性。

一、數學模型

中等動態度車輛路徑問題要兼顧并平衡好行駛總距離和減少顧客平均等待時間這兩個目標，由此可建立如下的目標函數:

Objective min 公式(1)

這里， 是總行駛距離，(符號的意義同公式(4-1))。是權值，表示到達顧客v的時間，是顧客v 需求服務的截止時間。

二、雜交螞蟻算法簡介

螞蟻工作方式的本質是:1. 跡越多的路徑，被選中的概率越大，即選擇機制;2. 路徑越短，在上面的跡增長得越快，即跡更新機制;3. 螞蟻之間通過跡進行通信，即協同工作機制。

選擇機制和跡更新機制構成正反饋機制，在蟻群的協同作用下，正反饋過程使得越來越多的螞蟻選擇最短的路徑。本文用螞蟻算法和局部搜索算法相結合(稱為雜交螞蟻算法)解中等動態度車輛路徑問題:

雜交螞蟻算法是結合局部搜索算法的螞蟻算法。下面用TSP為例來解釋雜交螞蟻算法。把TSP表示為一個圖，V表示城市的點集，E是連接城市的邊。算法開始時，把m只螞蟻按一定規則分布在各城市，每只螞蟻的任務是建立一個解，即從各自的起始城市開始完成一個環游。環游是一個城市接著一個城市地進行的，位于城市r的螞蟻k根據某種選擇策略選擇下一個要去的城市s (選擇策略)，選擇原則就是在與城市r連接的所有邊中，邊長越短邊上的跡越多的邊，螞蟻就以越高的概率選中這條邊，當到達下一個城市時，螞蟻就適當減少邊上的跡(局部更新)，從而其它螞蟻以較低概率選擇這條邊，以免得到許多相似的解。當所有螞蟻都建立了各自的解，則以各自的解為起始點，用局部搜索算法(3-OPT)求局部最優解。最后，根據局部最優解的好壞更新其邊上的跡，原則是越短的環游，增加越多的跡(全局更新)。跡更新結束后，開始下一輪迭代。算法概述如下:

Step1:初始化跡;

Step2:下述過程迭代次:

1.每只螞蟻根據選擇策略建立一個新解，同時局部更新跡;

2.以所建立的解為起始點，求局部最優解;

3. 根據局部最優解全局更新跡。

三、中等動態度車輛路徑問題的雜交螞蟻算法

把中等動態度車輛路徑問題(P)表示為一個圖，V是n個點的集合，分別表示解的n個分量，U是L個點的集合，是分量i的最大可能取值，V中的點i與U中的點有邊相連。是邊上的跡。如果V中的點i與U中的點j無邊相連，則，跡矩陣是一個n 行L列矩陣。

算法開始時，所有螞蟻都集中在第1個分量處，每只螞蟻按照選擇策略選擇一條邊，當選擇完一條邊后，馬上更新該邊上的跡，當m只螞蟻都選擇好各自的第一個分量的值后，都集中到第二個分量處，直到選擇完第n個分量的值，從而建立了m個解。以所建立的m個解為起始點進行局部搜索，根據得到的局部最優解計算跡的增量，全局更新跡。全局更新跡后，繼續迭代，直到滿足停止條件，停止條件是最大迭代次數。

1.初始化。由于雜交螞蟻算法利用局部最優解計算跡的增量，因而跡的初始值取為，W是常量，螞蟻總數取。

2.改進的選擇策略。位于i個分量的螞蟻，按下列公式選擇邊 :

公式(2)

其中:，，依均勻分布在(0，1)內隨機取值， 表示與端點i相連的跡最大的邊的另一端點，依如下概率分布在內隨機取值:

公式(3)

該公式表明，跡最大的邊以高概率0.9被選中，其余的邊以概率0.1參與選擇，而在這些初始解中，的取值范圍是所有可能取值，這樣，按公式(5-3)選擇時，跡最大的邊仍然以很高的概率被選中，造成算法太快收斂到次優解。本文縮小了的取值范圍，使得螞蟻不僅以概率0.9選擇跡最大的邊，而且以概率0.1選擇非最大跡的邊，這樣，在每次迭代時可以建立不同的解，在利用最大跡的同時加大對解空間的探測力度，使算法不會太快收斂。實驗結果表明，改進的算法大大提高了得到最優解的概率。

3.局部更新。當螞蟻k選中邊后，就更新邊上的跡:

公式(4)

其中:是上輪迭代得到的跡矩陣中第i行前i個元素的最小值，這是動態變化的。從公式(5-4)知，更新后的跡是原來的跡與最小跡的凸組合，這使得跡的減小基于可供選擇的條邊上的跡的相對大小。由于公式(5-2)以概率0.9選擇 條可供選擇的邊中跡最大的一條，因而螞蟻常常選中跡最大的邊，第一只螞蟻選中它后，就更新該邊上的跡，使跡的值小了一點;第二只螞蟻選中它后，也是這樣，結果是當跡最大的邊被多次選中后，跡的量減少到 條可供選擇的邊上的跡的值的平均水平，從而螞蟻選中其它邊的概率增加，增加了所建立的解的多樣性。

4. 局部搜索算法。當m只螞蟻都建立好各自的解，分別以這些解為起始點作局部搜索。局部搜索的鄰域定義為，其中是第i個分量為1，其余分量為0的n維向量。鄰域搜索算法如下:

Step 1:任給一初始整點;

Step 2:若是問題的局部極小解，停機;否則，檢查的鄰域，找到一整點，使得。

Step 3:令，轉Step2。

5.全局更新。當所有螞蟻都得到局部最優解，就全局更新所有邊上的跡，公式如下:

公式(5)

其中:是參數，;是邊上的跡的增量，是螞蟻k建立的解做局部搜索后得到的局部最優解的目標函數值。公式(5)表明被越多螞蟻訪問過的邊得到越多的跡的增量，同時所有的邊上的跡都蒸發掉一部分，避免跡的無限增長。

下面具體給出解中等動態度車輛路徑問題的雜交螞蟻算法的描述。

(l) 初始化階段

令;在內隨機產生m個解作為起始點，做局部搜索，求出最小的局部最優解，以及相應的目標函數值;令初始跡;并為每條邊賦初始值;

(2) 迭代

for num=1 toImax do

① for i=1 to n do

Fork=1 to m do

begin

根據公式(5-2)求第i個分量的值

按公式(5-4)更新邊上的跡;

end

② 以得到的m個解為起始點，根據本文給出的局部搜索算法求局部最優解及目標函數值;求出該輪迭代的最小目標函數值then

更新迭代以來的最小目標函數值及解，以及該輪迭代所得到的解;

③ for每條邊根據公式(5-5)計算跡增量

for每條邊，

④ 更新跡矩陣每行的最小值minq(i);

(3)輸出最小目標函數值以及相應的解

四、數值計算結果

我們用http://www.dcs.st-and.ac.uk/ apes/apedata.html[1]中的標準中等動態度車輛路徑問題數據測試了本文提出的雜交螞蟻算法的性能。http://www.dcs.st-and.ac.uk/ apes/apedata.html中的標準中等動態度車輛路徑問題是由TAILLARD (1994)， [2] Christophides (1984) [3]和Fisher (1981)中所提出的標準靜態車輛路徑問題轉化而來的。我們考慮25個顧客和1個倉儲中心的中等動態度車輛路徑問題。在標準問題中，位置數據是隨機產生的。在計算過程中，螞蟻的數目等于當前顧客的數目，一個顧客分配一只螞蟻。計算結果見表1，2。

參考文獻:

[1]http://www.dcs.st-and.ac.uk/ apes/apedata.html

[2]Taillard E. Parallel iterative search methods for vehicle routing problem [J]. Networks， 1994，23(8):661-673

[3]Christophides N， Beasley J. The period routing problem [J]. Networks， 1984， 14: 237-256