基于蟻群算法的動態(tài)車輛調(diào)度問題的研究.pdf

1、車輛調(diào)度問題涉及的行業(yè)非常廣泛，高節(jié)奏的生活對運(yùn)輸業(yè)實(shí)時性的要求越來越強(qiáng)烈。如何在靜態(tài)車輛調(diào)度問題的基礎(chǔ)上解決動態(tài)車輛調(diào)度問題并且得出最優(yōu)的調(diào)度結(jié)果，已經(jīng)成為眾多學(xué)者研究的重點(diǎn)和難點(diǎn)。車輛調(diào)度問題屬于NP難問題，以往的求解算法可以分為精確算法和啟發(fā)式算法兩大類:精確算法由于引入了嚴(yán)格的數(shù)學(xué)方法，無法避免指數(shù)爆炸增長，所以只能有效求解小規(guī)模的車輛調(diào)度問題;絕大多數(shù)研究學(xué)者把精力用在構(gòu)造高質(zhì)量的啟發(fā)式算法上。本文通過比較各種啟發(fā)式算法，并選

2、擇改進(jìn)的蟻群算法來解決運(yùn)輸途中有新訂單出現(xiàn)的動態(tài)車輛調(diào)度問題。
　　 本文圍繞基于蟻群算法的動態(tài)車輛調(diào)度這一主題，主要做了以下幾方面的工作:
　　 1.首先簡單的描述了車輛調(diào)度問題，然后研究了動態(tài)車輛調(diào)度問題，比較了靜態(tài)車輛調(diào)度和動態(tài)車輛調(diào)度的區(qū)別，分析了動態(tài)車輛調(diào)度問題中變化信息的處理方法。最后研究了各種針對車輛調(diào)度問題的算法，包括精確算法、啟發(fā)式算法及亞啟發(fā)式算法。
　　 2.比較各類算法并最終選擇蟻群算法，

3、通過一系列的仿真實(shí)驗(yàn)，對蟻群算法參數(shù)的合理選取進(jìn)行了較為深入的研究，提出了最優(yōu)算法參數(shù)組合。較于以前完全憑經(jīng)驗(yàn)和試探來選取參數(shù)，大大提高了效率。同時在三個方面對基本蟻群算法進(jìn)行改進(jìn):(1)揮發(fā)因子由常數(shù)變成變量函數(shù);(2)引入“獎懲”機(jī)制;(3)最大最小蟻群系統(tǒng)。將改進(jìn)后的蟻群算法分別與基本蟻群算法、遺傳算法進(jìn)行實(shí)例分析比較，驗(yàn)證改進(jìn)蟻群算法的有效性。
　　 3.進(jìn)行實(shí)例仿真:運(yùn)用Matlab仿真軟件對旅行商問題、帶時間窗的靜態(tài)

4、車輛調(diào)度問題、理想路況和現(xiàn)實(shí)路況的實(shí)例等進(jìn)行了仿真對比，通過與基本蟻群算法、遺傳算法的仿真對比得出改進(jìn)蟻群算法得到的優(yōu)化結(jié)果更好，證明了改進(jìn)蟻群算法的有效性。
　　 4.分析選擇了現(xiàn)實(shí)生活中較常發(fā)生的一類動態(tài)車輛調(diào)度——在運(yùn)輸途中有新訂單到來，并用改進(jìn)蟻群算法對新到訂單進(jìn)行處理接受還是拒絕，接受新訂單的話如何在送貨途中的基礎(chǔ)上完成新訂單的任務(wù)。
　　 本文有效的完成了對基本蟻群算法的改進(jìn)，并用改進(jìn)蟻群算法使得一類動態(tài)車輛