針對帶模糊需求與模糊時間窗的車輛路徑問題,以總行駛距離、車輛使用數(shù)最小化,以及平均客戶滿意度最大化為目標,構(gòu)建基于可信性測度理論的多目標模糊機會約束模型。為提高種群的多樣性,改進了交叉算子,在引入局部優(yōu)化算法及擂臺法則的基礎(chǔ)上,設(shè)計了適合求解多目標車輛路徑問題的混合遺傳算法。通過VRPTW標準算例實驗,表明算法能夠有效地求解帶時間窗的車輛路徑問題,以及模型的合理性,同時顯示了決策者偏好值對決策目標的影響。研究成果可為求解帶模糊需求與時間窗的車輛路徑問題提供一種思路,也可為實際配送路徑規(guī)劃提供指導(dǎo)。 

【文章來源】：系統(tǒng)管理學(xué)報. 2020,29(01)北大核心CSSCICSCD

【文章頁數(shù)】：12 頁

【部分圖文】：

客戶滿意度函數(shù)圖

本文研究的VRPFDFTW屬于NP難題,此類問題的求解通常采用啟發(fā)式算法。遺傳算法(Genetic Algorithm,GA)是一種擁有自適應(yīng)能力的隨機化搜索算法。該算法通過模擬生物進化過程搜索最優(yōu)解,不要求優(yōu)化函數(shù)連續(xù),具有良好的全局尋優(yōu)能力,但存在過早收斂、后期收斂速度較慢等問題。局部搜索算法是一種簡單的貪心搜索算法,該算法每次從當前解的鄰域空間中搜索獲得一個局部最優(yōu)解,經(jīng)過多個鄰域變化,擴大搜索空間,有利于找到高質(zhì)量的滿意解。因此,本文結(jié)合遺傳算法與局部搜索算法的優(yōu)勢,引入擂臺法則(Arena’s Principle,AP)構(gòu)造Pareto非支配集,解決多目標優(yōu)化問題中各目標間的矛盾,設(shè)計混合遺傳算法對建立的模型進行求解,如圖2所示。擂臺法則構(gòu)造非支配解集的基本思路是,在每一輪比較時,首先,任意從當前種群中選出一個染色體解作為擂主(一般為當前種群中的第1個染色體);然后,將擂主與當前種群中的剩余染色體逐一比較判斷,將被支配者(敗者)淘汰出局,支配者(勝者)成為新擂主,并繼續(xù)該輪比較;一輪比較后,最后的擂主個體即為非支配個體。以此類推進行下一輪比較,直到當前種群為空。

2.1 染色體編碼與解碼本文采用自然數(shù)編碼方式構(gòu)造染色體,用0表示配送中心,其他自然數(shù)表示客戶點,染色體的編碼如圖3(a)所示,每條染色體表示客戶的配送服務(wù)順序。圖3(b)所示為對應(yīng)的解碼后的個體,每個個體表示客戶的配送服務(wù)車輛,表示車輛1從配送中心0開始,依次經(jīng)過客戶1、3、9、5返回配送中心0,車輛2從配送中心0開始,經(jīng)過客戶8、2、4、7、6返回配送中心0。

【參考文獻】：
期刊論文
[1]基于模糊時間窗的多中心開放式車輛路徑問題[J]. 楊翔,范厚明,張曉楠,李陽.  計算機集成制造系統(tǒng). 2016(07)
[2]模糊需求車輛路徑優(yōu)化及實時調(diào)整[J]. 張曉楠,范厚明.  上海交通大學(xué)學(xué)報. 2016(01)
[3]求解帶時間窗車輛路徑問題的有效混合PBIL算法[J]. 孟祥虎,胡蓉,錢斌.  系統(tǒng)工程理論與實踐. 2014(10)
[4]基于混合遺傳算法的模糊需求車輛路徑問題[J]. 吳天羿,許繼恒.  解放軍理工大學(xué)學(xué)報(自然科學(xué)版). 2014(05)
[5]基于混合NSGA-Ⅱ的有硬時間窗的多目標車輛路徑問題[J]. 吳天羿,劉建永,許繼恒,翁杰,昝良.  交通運輸系統(tǒng)工程與信息. 2014(02)
[6]帶硬時間窗的戰(zhàn)場物資配送車輛路徑優(yōu)化[J]. 王連鋒,宋建社,王正元,曹繼平.  系統(tǒng)工程與電子技術(shù). 2013(04)
[7]基于模糊時間窗的車輛調(diào)度問題研究[J]. 王旭坪,張凱,胡祥培.  管理工程學(xué)報. 2011(03)
[8]模糊環(huán)境下多出救點應(yīng)急救援車輛路徑與物資運輸優(yōu)化研究[J]. 汪傳旭,鄧先明.  系統(tǒng)管理學(xué)報. 2011(03)
[9]帶模糊預(yù)約時間的車輛路徑問題的多目標禁忌搜索算法[J]. 王君,李波.  計算機集成制造系統(tǒng). 2011(04)
[10]高效求解Pareto最優(yōu)前沿的多目標進化算法[J]. 童晶,趙明旺.  計算機仿真. 2009(06)



本文編號：3622759