帶軟時間窗的開放式車輛路徑問題研究.pdf

1、交通運輸營運管理和物流配送管理中都要面對這樣一個共同的問題：如何為其載運工具（汽車、列車、輪船和飛機，以下統(tǒng)稱為車輛）確定行駛路線及其時刻表，才能有效地運送各站點間的旅客和貨物。運籌學(xué)界將此類問題統(tǒng)稱為車輛路徑問題（VRP）。 為了便于對VRP進行系統(tǒng)的研究，運籌學(xué)界將其分為兩大類：閉合式VRP和開放式VRP。當車輛完成運輸任務(wù)后必須返回原出發(fā)點時，稱之為閉合式VRP，一般就簡稱為車輛路徑問題；當不要求車輛完成任務(wù)后返回原出發(fā)點

2、，或者是要求其沿原去程路線返回時，稱之為開放式VRP（OVRP）。 由于OVRP問題是NP-難問題，所以啟發(fā)式算法是目前求解OVRP的主流。本文的重點是研究如何應(yīng)用啟發(fā)式算法求解開放式車輛路徑問題。首先，分析了目前開放式車輛路徑問題的研究現(xiàn)狀及相應(yīng)的求解算法，并在此基礎(chǔ)上簡述了本文重點研究的問題類型--帶軟時間窗的開放式車輛路徑問題（OVRPSTW）。然后，基于經(jīng)典啟發(fā)式算法思想設(shè)計了求解OVRPSTW的最近鄰域搜索算法，構(gòu)造了

3、鄰域的評價函數(shù)并進行了算例測試。其次，基于現(xiàn)代啟發(fā)式算法思想設(shè)計了求解OVRPSTW的遺傳算法，對遺傳算法所必須考慮的關(guān)鍵問題如編碼、繁殖和遺傳算子等進行了分析。最后，對遺傳算法的性能測試和結(jié)果比較分析，分別比較了使用不同選擇算子、不同交叉算子和不同交叉變異概率后遺傳算法的性能，并可從中選取性能較好的排序加最佳個體保留、交叉算子A加單親遺傳算子和自適應(yīng)交叉變異概率等策略；更進一步，用標準測試算例對算法進行測試，并將遺傳算法結(jié)果與文獻中算