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

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

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