啟發(fā)式算法及其在車輛路徑問題中的應用.pdf

1、自然界中存在著一類被稱為NP完全的問題，由于其目標解的搜索涉及解空間的組合爆炸，因此，求解大規(guī)模的NP完全問題已經(jīng)成為當今計算機科學、人工智能等領域的瓶頸任務之一。對于這類問題，分支定界、動態(tài)規(guī)劃等傳統(tǒng)的優(yōu)化方法難以求其精確解，因此通常采用啟發(fā)式算法，目標是在可接受的時間內(nèi)找到問題盡可能好的解。車輛路徑問題是一類NP完全問題。實際生活中的物流配送車輛調(diào)度、公共汽車路線制定、信件和報紙投遞、航空和鐵路時間表安排、廢品收集、校車路線安排等問

2、題都可抽象為車輛路徑問題。因此，研究車輛路徑問題的啟發(fā)式算法有著重要的理論價值和現(xiàn)實意義。 本文研究了啟發(fā)式算法及其在車輛路徑問題中的應用，結(jié)合不同元啟發(fā)式算法搜索策略的優(yōu)勢提出混合啟發(fā)式算法，解決帶容量約束車輛路徑問題、開放式車輛路徑問題、多車型車輛路徑問題和卸裝一體車輛路徑問題。本文工作得到了國家重點基礎研究發(fā)展規(guī)劃（973）項目基金（No．2006CB705500）的資助。 本文取得的主要研究成果如下： （

3、1）針對帶容量約束的車輛路徑問題，提出了一個混合迭代局部搜索算法HILS。該算法設計了一種迭代局部搜索和變鄰域下降的結(jié)合方式，在變鄰域搜索中使用多鄰域算子擴大其搜索范圍的同時，基于“粒鄰域”的思想提出一種受限鄰域，減少了不必要的搜索，提高了搜索效率；設計了一種基于cross-exchange算子的擾動策略。算法HILS結(jié)構(gòu)簡單、易實現(xiàn)，并且具有較好的靈活性。在通用的34個基準測試問題上進行實驗，討論了參數(shù)設置問題和算法各要素對算法性能的

4、影響。實驗結(jié)果表明，算法HILS能夠有效求解帶容量約束的車輛路徑問題，性能和效率與表現(xiàn)最好的其它啟發(fā)式算法相當。 （2）針對開放式車輛路徑問題，提出了一種擴展的混合迭代局部搜索算法eHILS。在利用變鄰域下降搜索優(yōu)化當前解時，通過優(yōu)先接受路徑數(shù)較少的解來滿足開放式車輛路徑問題的多目標優(yōu)化的要求。在通用的16個基準測試問題上的實驗結(jié)果表明，算法eHILS能夠獲得13個問題的已知最好解，并更新了其中3個問題的已知最好解。 （

5、3）針對多車型車輛路徑問題，提出了一種變鄰域搜索算法VNS_FSM。該算法設計了實現(xiàn)抖動過程的鄰域結(jié)構(gòu)組合，并提出了一種新的車型調(diào)整策略。本文在通用的基準測試問題上的實驗驗證了算法的有效性，并給出問題G_07至G_12的正確解。結(jié)果表明，該算法能夠獲得大多數(shù)測試問題的已知最好解。與現(xiàn)有的啟發(fā)式算法相比，該算法性能相當或更優(yōu)，是當前求解多車型車輛路徑問題表現(xiàn)最好的算法之一。 （4）針對卸裝一體車輛路徑問題，基于蟻群優(yōu)化和變鄰域下降

6、，提出了一個混合蟻群優(yōu)化算法HACS?；趯π堆b一體車輛路徑問題可行解性質(zhì)的分析，本文提出了一種可行解生成方式，即先生成問題的弱可行解，繼而轉(zhuǎn)換為強可行解。這種解生成方式的優(yōu)點是構(gòu)造方法簡單，而且能有效避免使用過多的車輛。改進蟻群優(yōu)化算法中解的構(gòu)造方式，提出了一種基于插入的構(gòu)造方法生成弱可行解。利用變鄰域下降對蟻群中構(gòu)造的質(zhì)量最好的解進行優(yōu)化，以加快算法的收斂。55個通用基準測試問題上的仿真實驗結(jié)果表明，該算法能夠獲得52個基準測試問題