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

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

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

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

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

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

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