帶限制條件的車輛路徑問題的現(xiàn)代啟發(fā)式算法研究.pdf

1、車輛路徑問題(VRP)是運籌學(xué)、應(yīng)用數(shù)學(xué)和計算機(jī)等領(lǐng)域研究的熱點問題之一,其研究宗旨是設(shè)計合理的車輛行駛路線以達(dá)到降低運輸成本的目的,經(jīng)過五十多年的發(fā)展,已被廣泛應(yīng)用于通訊、生產(chǎn)、國防及生物等領(lǐng)域。車輛路徑問題是組合優(yōu)化中典型的NP-hard問題,當(dāng)問題規(guī)模較大時,求解所需的計算時間會隨問題規(guī)模的增大而成指數(shù)級的增長,將很難得到問題的精確解。由于NP問題求解的復(fù)雜性,目前車輛路徑問題的求解方法主要使用啟發(fā)式算法。
　　本文主要對兩

2、類車輛路徑問題的模型和算法進(jìn)行了研究,主要工作如下:
　　1.針對帶有容量限制的車輛路徑問題,提出了一種混合離散人工蜂群算法。該算法給出了食物源位置的離散編碼方法,利用鄰域搜索生成候選食物源,引入局部搜索來增強(qiáng)開采能力。最后通過數(shù)值實驗,驗證了該算法的性能優(yōu)于其他算法。
　　2.針對帶時間窗的車輛路徑問題,提出了改進(jìn)的螢火蟲算法:設(shè)計了一種離散機(jī)制把個體的連續(xù)編碼形式轉(zhuǎn)化為車輛位置的離散編碼方式,從而使算法能夠求解離散問題;