基于模糊模擬的遺傳蟻群算法在模糊需求車輛路徑問題上的研究

摘 要：在對模糊車輛路徑問題進行簡單描述的基礎(chǔ)上，通過引入決策者主觀偏好的理念，給出了解決該問題的基本思路，建立了具有模糊特征的車輛路徑問題的模糊機會約束模型，提出了求解該問題的一種基于模糊模擬的遺傳蟻群混合算法。同時，在最小化總行駛距離的目標下，通過隨機模擬方法研究了決策者主觀偏好值的選擇對最終決策目標的影響作用，并給出了其最佳取值范圍。

關(guān)鍵詞:模糊車輛路徑問題；遺傳蟻群混合算法；模糊模擬；決策者偏好

中圖分類號：C93 文獻標志碼：A 文章編號：1673-291X（2012）16-0185-03

引言

Vehichle Routing Problem簡稱VRP，一般譯為車輛路徑問題或者車輛調(diào)度問題。最早由學者Dantzig 和Ramser于1959年提出[1].VRP問題一直受國內(nèi)外學者的關(guān)注，也因此涌現(xiàn)出了大量解決VRP的精確算法以及啟發(fā)式算法、亞啟發(fā)式算法，如遺傳算法[2]、sweeping算法[3]、動態(tài)規(guī)劃法[4]等。對于不確定VRP多集中在能找出統(tǒng)計規(guī)律的的隨機車輛路徑問題（Stochastic Vehicle Routing Problem，SVRP）上，對于沒有確切數(shù)據(jù)又找不出統(tǒng)計規(guī)律的模糊車輛路徑問題（Fuzzy Vehicle Routing Problem，F(xiàn)VRP）研究的更少。此問題是對隨機需求車輛路徑問題（Vehicle Routing Problem with Stochastic Demands，VRPSD）的延伸研究。對于轉(zhuǎn)載轉(zhuǎn)乘問題中的供應(yīng)量和需求量都是模糊的問題，國外學者Penncherry和Kicnchi采用模糊線性規(guī)劃原則來處理[5]。Teodorovic和Pavkoviv運用Gilett和Miller提出的Sweeping算法[6]來解決模糊顧客需求問題。在國內(nèi)對于FVRP，張建勇和李軍采用Sweeping算法、混合遺傳算法和修正的C-W節(jié)約算法等啟發(fā)式算法進行研究[7]。中南大學的謝小良運用模糊機會規(guī)劃來實現(xiàn)模糊需求的配送路徑優(yōu)化[8]。

本文在對具有模糊需求車輛路徑問題進行描述分析的基礎(chǔ)上，考慮客戶對配送時間的要求和車輛行駛時間的不確定性，運用模糊數(shù)學的可能性理論建立以車輛配送總行駛距離最小化為目標的約束規(guī)劃模型，并利用遺傳蟻群混合算法對問題進行求解。

一、問題描述及模型的建立

此類FVRP可描述如下:某一運輸網(wǎng)絡(luò)中有一車場和n個待服務(wù)的節(jié)點（顧客），分別以0和1，2，……，n表示，車輛從車場出發(fā)，服務(wù)一定數(shù)量的節(jié)點后返回車場，已知每輛車運輸能力為C，每個節(jié)點需求量為一模糊數(shù)Di，節(jié)點i與節(jié)點j之間的距離為cij，求滿足運輸需求的費用最小的車輛行駛路線。本文考慮的目標是最小化總行駛距離。

為方便起見，本文需求模糊數(shù)D用三角模糊數(shù)D=（d1，d2，d3）表示（如圖1所示）。其中d1、d3分別表示該模糊數(shù)的左、右

邊界，d2表示隸屬度為1的點。該模糊數(shù)用隸屬度函數(shù)可表示如下:

μD（x）=0 x≤d1且x≥d3（x-d1）/（d2-d1） d1≤x＜d2（x-d2）/（d3-d2） d2≤x＜d3 （1）

根據(jù)可信性理論，下一節(jié)點需求量小于車輛剩余運輸能力的可能性可表示為：

當p值越大時，該車能夠完成下一節(jié)點運輸任務(wù)的可能性就越大。設(shè)p*（p*∈[0，1]）表示決策者（調(diào)度員）是否安排該車繼續(xù)完成下一節(jié)點任務(wù)的P給出的主觀臨界值（或稱為決策者主觀偏好值）。當p≥p*時，該車繼續(xù)完成下一節(jié)點的運輸任務(wù)，若p

模型中，目標（3）表示最小化計劃運行距離；約束（4）表示每輛車的載運量不超過它的能力的可能性不小于主觀給定值P*；約束（5）確保計劃中每個顧客只有一輛車服務(wù)；約束（6）、（7）表示兩變量xijk和yik之間的關(guān)系；約束（8）為支路消去約束；約束（9）與（10）為變量xijk和yik的取值約束。

二、求解FVRPD的基于模糊模擬的遺傳蟻群混合算法

1.本文針對基本蟻群算法搜索時間長、易陷入局部最優(yōu)的缺點，提出了一種基于模糊模擬的蟻群算法和遺傳算法相融合的混合算法。我們用人工螞蟻代替車輛服務(wù)客戶，記人工螞蟻個數(shù)為 M，則M=i（t），其中Bi（t）表示 t 時刻位于客戶 i的螞蟻個數(shù)。τij（t）表示 t 時刻在 i、j 路徑上的殘留信息量。初始時刻，各條路徑上的信息量相等，設(shè)τij（0）=0 （C 為常數(shù)）。首先，將 M個螞蟻隨機分布在各個客戶上，然后每只螞蟻根據(jù)各條路徑上的信息量選擇下一個要服務(wù)的客戶。在 t 時刻，螞蟻 k 從客戶 i轉(zhuǎn)到客戶的概率為：

Pkij（t）=，j∈allowedk0，其他 （11）

其中，allowedk={0，1，……，n}表示螞蟻k下一步允許選擇的城市，通常每次循環(huán)后將已經(jīng)訪問過的節(jié)點從中刪除；α，β分別表示螞蟻在運動過程中所積累的信息以及啟發(fā)式因子在螞蟻路徑選擇中所起的不同作用；ηij表示由城市i轉(zhuǎn)移到城市j的期望程度，ηij=。當螞蟻完成n次循環(huán)之后，相應(yīng)路徑上的信息素濃度為：

τij（t+1）=（1-ρ）τij（t）+Δτij （12）

其中，ρ為一個取值范圍在 0 到 1 之間的常數(shù)系數(shù)，（1- ρ）表示在時刻 t 到 t+1 之間信息素的揮發(fā)。

Δτij=Δτkij （13）

其中Δτkij為第 k 個螞蟻在時刻 t 到 t+1 之間，在路徑（i，j）上增加的信息素變量。

Δτkij=第k只螞蟻在t和t+1經(jīng)過（i，j）0 否則 （14）

其中Q是一個常量，表示螞蟻完成一次完整的路徑遍歷后，所釋放的信息素總量，LK是第 k 只螞蟻遍歷的路徑總費用。

2.由“失敗”產(chǎn)生的額外行駛距離的估計。對于任一“可行”路徑安排，對其由于“失敗”產(chǎn)生的額外行駛距離的估計用隨機模擬方法產(chǎn)生，其基本步驟如下:（1）對每一顧客，生成估計額外行駛距離用的“實際”需求，該“實際”需求也用模擬方法產(chǎn)生，其步驟是:1）在某顧客的模糊需求數(shù)范圍內(nèi)隨機生成一個數(shù)x并計算其隸屬度；2）生成一個[0，l]范圍內(nèi)的隨機數(shù)a；3）比較a與刀，如果a小于μ，則x為該顧客的實際實現(xiàn)的需求量，否則，重復(fù)以上步驟:4）重復(fù)上述步驟，直至生成所有顧客的模擬“實際”需求量。（2）計算在此“實際”需求條件下，該路徑安排由于“失敗”產(chǎn)生的額外行駛距離；（3）重復(fù)1、2次；（4）計算M次模擬的平均值，以其作為該路徑安排由于可能存在的“失敗”而產(chǎn)生的額外行駛距離的估計值。

三、實驗及結(jié)果分析

實驗中顧客數(shù)為 30，隨機產(chǎn)生顧客的位置，計算任意兩個顧客以及顧客和車場的距離。本文算法參數(shù)設(shè)置如下：

1.蟻群算法中參數(shù)設(shè)置：螞蟻個數(shù) m=15，α=1，β=4，ρ=0.6，Q=10，τij（0）=80，最大迭代次數(shù) ncMax=100。

2.遺傳算法中參數(shù)設(shè)置：種群規(guī)模 popSize=50，迭代次數(shù)為iteraMax=100，交叉率 pc=0.8，變異率 pm=0.2。

基于以上基本設(shè)置，主觀參數(shù)P*在0~1之間變動，P211表1給出了每個設(shè)置下50次運行結(jié)果的均值。

從P211表1中可以看出，隨p*值增大，預(yù)計行駛距離也逐漸增大，而額外行駛距離卻逐漸減小，但當P*≤0.6時，預(yù)計行駛距離增加量小于額外行駛距離減少量，致使隨P*值增大，總行駛距離逐漸漸小；而P*>0.6時，預(yù)計行駛距離的增加量稍稍大于額外行駛距離的減少量，致使隨P*值增大，總行駛距離也緩慢增加。即當P*=0.6時，可得最小總行駛距離。因此，在實際模糊車輛調(diào)度中，從行駛距離最小化的角度出發(fā)，決策者主觀偏好值P*應(yīng)選擇在0.6左右。

結(jié)束語

在傳統(tǒng)車輛路徑問題的基礎(chǔ)上，分析需求信息的不確定性，針對單車輛單車場的車輛路徑問題，建立了基于模糊可信性理論的模糊需求規(guī)劃模型，并提出了求解該問題的一種基于模糊模擬的遺傳蟻群混合算法。并通過實驗驗證了決策者主觀偏好值的選取對決策結(jié)果的影響，得出在最小化總行駛距離的目標下，決策者主觀偏好值應(yīng)選在 0.6 左右。