(3)鄰域解的計算。在得到初始解之后,為保持解的多樣性,采用兩種方法產生鄰域解,(1)使用插入、交換和反向操作算子,由于是按照約束條件產生合法解,因此不同路線之間不再使用交換算子;(2)使用交互向量。交互向量可以使得初始解在不同路線間發生變化,即服務礦區會產生由不同車輛服務的變化效果。假設三個初始解a,b,c,交互向量v=[1,1,1],交互向量的作用之后可能產生的解為a*,b*,c*。交互向量根據礦區需求量和位置角度設計產生。
四、 實驗仿真與分析
本文選取國際標準測試數據進行實驗,數據來源于網站。算法首先根據問題規模設置種群規模及參數,然后根據生產滿足約束條件的初始解,根據交叉向量信息進行采蜜峰的搜索,然后根據共享信息進入了圍觀蜂搜索階段,偵查蜂對搜索到的解進行評價后以一定概率放棄并生成新的解,直至滿足條件為止。混合人工蜂群算法迭代的流程圖如圖(1)所示。
表2為采用國際標準測試案例中E集合中不同規模案例的測試結果。算法中蜂群最小規模設為20,最大規模設為問題規模二倍,迭代步數設為150步,算法迭代次數為10次。采用局部搜索策略時,蟻群搜索機制的參數分別設為ρ=0.1。從表2中可以看出對于,不同規模的的問題,本文提出的算法均得到近似最優解,且車輛平均滿載率較高,除E_n23_3外,各個案例車輛滿載率均在90%左右。表3為對應各個算例的實際路線安排表。圖2為大規模測試用例E-n101-k8各個車輛運行路線圖,圖3為該算例下算法迭代后收斂效果圖,從圖中可以看出,運行距離從930逐漸下降到850,在80步之后逐漸穩定。
五、 結論
通過國際測試用例仿真,驗證了混合人工蜂群算法在求解煤炭物流中CVRP的有效性,可以快速計算出近似最優解,證明了算法的實際應用價值。同時,通過算法設計以及仿真過程可以得出以下結論:
1. 在對煤炭物流中CVRP問題研究基礎上,采用改進的人工蜂群算法對該類問題進行求解,并取得近似最優解的效果,可將算法用于實際煤炭物流路線優化。
2. 根據問題約束特點以及算法自身特點,采用了以“1”作為標記的編碼方式,該編碼方式簡單易懂,迭代方便。
3. 改進人工蜂群算法中,初始解產生按照極角方式,避免非法解參與運算;鄰域解采用交叉向量作為“指引”,避免大范圍的無效搜索;局部搜索采用蟻群搜索機制,增強局部搜索能力。
參考文獻:
1. 汪文生,曾志猛,王娟.多級煤炭物流網絡優化選擇模型的構建與應用.煤炭學報,2011,26(6):1060-1064.
2. WANG Wen-sheng, ZENG Zhi-meng, WANG Juan. Construction and application of multi-level coal logistics network optimization model. JOURNAL OF CHINA COAL SOCIETY,2011,26(6):1060-1064.
3. T.K.Ralphsy, L.Kopmanz, W.R. Pulleyblankx, L.E. Trotter, Jr. On the Capacitated Vehicle Routing Problem. Mathematical Programming,2003,94(2):343-359.
4. G.Clarke, J W Wright.Scheduling of Vehic- les from a Central Depot to a Number of Delivery Points. Operations Research,1964,12(4):568-581.
5. 姜大立,楊西龍,杜文,周賢偉.車輛路徑問題的遺傳算法研究. 系統工程理論與實踐,1996,(6):40-44.
6. 張麗萍, 柴躍廷.車輛路徑問題的改進遺傳算法.系統工程理論與實踐,2002,(8):79-84.
7. 謝秉磊,安實,郭耀煌.隨機車輛路徑問題的多回路優化策略.系統工程理論與實踐,2007,(2):167-171.
8. 袁健,劉晉,盧厚清.隨機需求情形VRP 的退火網絡解法.系統工程理論與實踐,2002,(3):109-113.
9. 張濤,田文馨,張玥杰,劉士新.帶車輛行程約束的VRPSPD問題的改進蟻群算法.系統工程理論與實踐,2008,(1):132-140.
10. 劉志碩, 申金升, 關偉.車輛路徑問題的混合蟻群算法設計與實現. 管理科學學報,2007,10(3):15-21.
11. 李琳,劉士新,唐加福.改進的蟻群算法求解帶時間窗的車輛路徑問題.控制與決策,2010,25(9):1379-1383.
12. 李寧,鄒彤,孫德寶.車輛路徑問題的粒子群算法研究.系統工程學報,2004,19(6):596-600.
13. 王素欣,高利,崔曉光等. 多需求點車輛調度模型及其群體智能混合求解.自動化學報,2008,34(1):102-104.
作者簡介:阮平南,北京工業大學經管學院教授、博士生導師;龐柒,北京工業大學經管學院管理科學與工程專業博士生;關志強,北京工業大學電控學院碩士生。
收稿日期:2013-11-20。
四、 實驗仿真與分析
本文選取國際標準測試數據進行實驗,數據來源于網站。算法首先根據問題規模設置種群規模及參數,然后根據生產滿足約束條件的初始解,根據交叉向量信息進行采蜜峰的搜索,然后根據共享信息進入了圍觀蜂搜索階段,偵查蜂對搜索到的解進行評價后以一定概率放棄并生成新的解,直至滿足條件為止。混合人工蜂群算法迭代的流程圖如圖(1)所示。
表2為采用國際標準測試案例中E集合中不同規模案例的測試結果。算法中蜂群最小規模設為20,最大規模設為問題規模二倍,迭代步數設為150步,算法迭代次數為10次。采用局部搜索策略時,蟻群搜索機制的參數分別設為ρ=0.1。從表2中可以看出對于,不同規模的的問題,本文提出的算法均得到近似最優解,且車輛平均滿載率較高,除E_n23_3外,各個案例車輛滿載率均在90%左右。表3為對應各個算例的實際路線安排表。圖2為大規模測試用例E-n101-k8各個車輛運行路線圖,圖3為該算例下算法迭代后收斂效果圖,從圖中可以看出,運行距離從930逐漸下降到850,在80步之后逐漸穩定。
五、 結論
通過國際測試用例仿真,驗證了混合人工蜂群算法在求解煤炭物流中CVRP的有效性,可以快速計算出近似最優解,證明了算法的實際應用價值。同時,通過算法設計以及仿真過程可以得出以下結論:
1. 在對煤炭物流中CVRP問題研究基礎上,采用改進的人工蜂群算法對該類問題進行求解,并取得近似最優解的效果,可將算法用于實際煤炭物流路線優化。
2. 根據問題約束特點以及算法自身特點,采用了以“1”作為標記的編碼方式,該編碼方式簡單易懂,迭代方便。
3. 改進人工蜂群算法中,初始解產生按照極角方式,避免非法解參與運算;鄰域解采用交叉向量作為“指引”,避免大范圍的無效搜索;局部搜索采用蟻群搜索機制,增強局部搜索能力。
參考文獻:
1. 汪文生,曾志猛,王娟.多級煤炭物流網絡優化選擇模型的構建與應用.煤炭學報,2011,26(6):1060-1064.
2. WANG Wen-sheng, ZENG Zhi-meng, WANG Juan. Construction and application of multi-level coal logistics network optimization model. JOURNAL OF CHINA COAL SOCIETY,2011,26(6):1060-1064.
3. T.K.Ralphsy, L.Kopmanz, W.R. Pulleyblankx, L.E. Trotter, Jr. On the Capacitated Vehicle Routing Problem. Mathematical Programming,2003,94(2):343-359.
4. G.Clarke, J W Wright.Scheduling of Vehic- les from a Central Depot to a Number of Delivery Points. Operations Research,1964,12(4):568-581.
5. 姜大立,楊西龍,杜文,周賢偉.車輛路徑問題的遺傳算法研究. 系統工程理論與實踐,1996,(6):40-44.
6. 張麗萍, 柴躍廷.車輛路徑問題的改進遺傳算法.系統工程理論與實踐,2002,(8):79-84.
7. 謝秉磊,安實,郭耀煌.隨機車輛路徑問題的多回路優化策略.系統工程理論與實踐,2007,(2):167-171.
8. 袁健,劉晉,盧厚清.隨機需求情形VRP 的退火網絡解法.系統工程理論與實踐,2002,(3):109-113.
9. 張濤,田文馨,張玥杰,劉士新.帶車輛行程約束的VRPSPD問題的改進蟻群算法.系統工程理論與實踐,2008,(1):132-140.
10. 劉志碩, 申金升, 關偉.車輛路徑問題的混合蟻群算法設計與實現. 管理科學學報,2007,10(3):15-21.
11. 李琳,劉士新,唐加福.改進的蟻群算法求解帶時間窗的車輛路徑問題.控制與決策,2010,25(9):1379-1383.
12. 李寧,鄒彤,孫德寶.車輛路徑問題的粒子群算法研究.系統工程學報,2004,19(6):596-600.
13. 王素欣,高利,崔曉光等. 多需求點車輛調度模型及其群體智能混合求解.自動化學報,2008,34(1):102-104.
作者簡介:阮平南,北京工業大學經管學院教授、博士生導師;龐柒,北京工業大學經管學院管理科學與工程專業博士生;關志強,北京工業大學電控學院碩士生。
收稿日期:2013-11-20。