唐瑞雪等

摘 要：針對多種車型，多個供應(yīng)商，具有模糊需求的車輛路徑問題的特點，運用模糊可信性理論，建立了以最短行駛距離和最小車輛使用率為目標(biāo)函數(shù)的數(shù)學(xué)模型，并設(shè)計了求解該模型的一種改進(jìn)蟻群算法。其中基于置信水平構(gòu)造初始解，提高解的可行性；引入可信性來調(diào)整啟發(fā)因子，以加快啟發(fā)式搜索的收斂速度；動態(tài)地調(diào)整揮發(fā)系數(shù)，降低初始階段出現(xiàn)局部收斂的可能，提高尋找最優(yōu)路徑的能力。實驗結(jié)果表明，所提出的模型和算法是可行有效的。

關(guān)鍵詞：模糊需求；車輛路徑問題；蟻群算法；可信性；置信水平；揮發(fā)系數(shù)

中圖分類號：TP18

車輛路徑問題（簡稱VRP）屬于經(jīng)典的復(fù)雜組合優(yōu)化問題，是由Dantzing于1959年首次提出的。在以往的VRP研究中，客戶的地理位置、需求情況等在路徑規(guī)劃前已經(jīng)確定，提出了確定VRP的算法。但是在實際的應(yīng)用中，車輛路徑問題的某些信息可能是模糊的、不確定的，模糊車輛路徑問題（簡稱FVRP）開始出現(xiàn)。D.Teodorovic和G.Pavkovic在模糊推理算法中引入了決策者偏好的概念進(jìn)行求解；張建勇等采用Sweeping算法和混合遺傳算法求解模糊需求下的車輛路徑問題。

1 問題描述及模型

實驗結(jié)果表明，本文算法所得車輛行駛距離和車輛利用率是小于文獻(xiàn)[6]算法所得行駛距離，尤其當(dāng)實例集較大時，本文算法明顯優(yōu)于文獻(xiàn)[6]算法。所以，本文算法用于求解具有模糊需求的車輛路徑問題是可行且有效的。

4 結(jié)語

針對模糊需求的車輛路徑問題，本文建立了具有模糊特征的數(shù)學(xué)模型，并提出了基于模糊可信性的改進(jìn)蟻群算法。算法中通過引入可信性、置信水平來提高運行效率，并考慮了初始化階段僅以需求量來進(jìn)行路徑構(gòu)造可能出現(xiàn)局部收斂的情況。本文對soloman實例進(jìn)行了測試，由實驗結(jié)果可知本文提出的算法可以快速得到車輛行駛距離較短，車輛利用率較低的路徑。

參考文獻(xiàn)：

[1]GIANPAOLO G，F(xiàn)RANCESCA G.Real-time vehicle routing：Solution concepts，algorithms and parallel computing strategies[J].European Journal of Operational Research，2001，151（1）：1-11.

[2]ALAN L E，JUAN C M，MARTIN S.The vehicle routing problem with stochastic demand and duration constraints[J].Transportation Science，2010，44（4）：474-492.

[3]袁慶達(dá)，杜文，周再玲.帶軟時間窗的混合車隊車輛路線問題的模型和算法研究[J].西南交通大學(xué)學(xué)報，2001，36（4）：401-406.

[4]TEODOROVIC D，PAVKOVIC G.The fuzzy set theory approach to the vehicle routing problem when demand at nodes is uncertain[J].Fuzzy Sets and Systems，1996，82（3）：307-317.

[5]張建勇，李軍，郭耀煌.具有模糊預(yù)約時間的VRP混合遺傳算法[J].管理科學(xué)學(xué)報，2005，8（3）：64-71.

[6]張建勇，李軍，郭耀煌.模糊需求信息條件下的實時動態(tài)車輛調(diào)度問題研究[J].管理工程學(xué)報，2004，18（4）：69-72.

作者簡介：唐瑞雪（1987-），女，貴州貴陽人，碩士，研究方向：算法分析；秦永彬（1980-），山東煙臺人，博士，研究方向：可計算性及計算復(fù)雜性。

作者單位：貴州財經(jīng)大學(xué)信息學(xué)院，貴陽 550004；貴州大學(xué)計算機(jī)科學(xué)與信息學(xué)院，貴陽 550025

基金項目：貴州省科學(xué)技術(shù)基金（黔科合J字[2012]2125號）。