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

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

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

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

引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Δτij=Δτkij （13）

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

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

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

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

三、實驗及結果分析

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

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

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

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

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

結束語

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