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

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

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

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

引言

Vehichle Routing Problem簡稱VRP，一般譯為車輛路徑問題或者車輛調(diào)度問題。最早由學(xué)者Dantzig 和Ramser于1959年提出[1].VRP問題一直受國內(nèi)外學(xué)者的關(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)量和需求量都是模糊的問題，國外學(xué)者Penncherry和Kicnchi采用模糊線性規(guī)劃原則來處理[5]。Teodorovic和Pavkoviv運用Gilett和Miller提出的Sweeping算法[6]來解決模糊顧客需求問題。在國內(nèi)對于FVRP，張建勇和李軍采用Sweeping算法、混合遺傳算法和修正的C-W節(jié)約算法等啟發(fā)式算法進行研究[7]。中南大學(xué)的謝小良運用模糊機會規(guī)劃來實現(xiàn)模糊需求的配送路徑優(yōu)化[8]。

本文在對具有模糊需求車輛路徑問題進行描述分析的基礎(chǔ)上，考慮客戶對配送時間的要求和車輛行駛時間的不確定性，運用模糊數(shù)學(xué)的可能性理論建立以車輛配送總行駛距離最小化為目標(biāo)的約束規(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，求滿足運輸需求的費用最小的車輛行駛路線。本文考慮的目標(biāo)是最小化總行駛距離。

為方便起見，本文需求模糊數(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é)點需求量小于車輛剩余運輸能力的可能性可表示為：

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

模型中，目標(biāo)（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=。當(dāng)螞蟻完成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ù)計行駛距離也逐漸增大，而額外行駛距離卻逐漸減小，但當(dāng)P*≤0.6時，預(yù)計行駛距離增加量小于額外行駛距離減少量，致使隨P*值增大，總行駛距離逐漸漸小；而P*>0.6時，預(yù)計行駛距離的增加量稍稍大于額外行駛距離的減少量，致使隨P*值增大，總行駛距離也緩慢增加。即當(dāng)P*=0.6時，可得最小總行駛距離。因此，在實際模糊車輛調(diào)度中，從行駛距離最小化的角度出發(fā)，決策者主觀偏好值P*應(yīng)選擇在0.6左右。

結(jié)束語

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