多車型弧路徑優(yōu)化問題(MVCARP)研究.pdf

1、帶容量限制的弧路徑優(yōu)化問題（CARP）在日常生活中的應(yīng)用是非常普遍的，有效的解決 CARP問題并將其投入實(shí)際的應(yīng)用對于節(jié)約經(jīng)濟(jì)成本，提高社會生產(chǎn)效率有著非常重大的意義。盡管該項(xiàng)研究課題在過去的20多年時(shí)間里在國際上引起了眾多域?qū)＜覍W(xué)者們的重視，并提出了許多富有成效的解決方案，但是總體上看，CARP的研究相對于我們通常所熟悉的VRP的研究仍然顯得還不夠全面，從現(xiàn)有已經(jīng)發(fā)表的一些文獻(xiàn)中搜集到的解決 CARP問題的方法大多數(shù)存在比較大的改進(jìn)空

2、間。而對于應(yīng)用中比較常見的多車型CARP問題（MVCARP），作者還沒有搜集到的非常有成效的解決方案。因此，在本篇論文中作者對CARP和MV-CARP的理論進(jìn)行了深入研究，并提出一種高效的解決 CARP問題及其擴(kuò)展問題MVCARP問題的算法。
　　CARP問題是NP難題，用普通的精確算法很難求得實(shí)用的解，因此有效的解決方法一般都是以啟發(fā)式算法思想為基礎(chǔ)。由于遺傳算法具有良好的全局收斂性，并且在求解組合優(yōu)化問題上有著優(yōu)良的效果，因此

3、作者在本文中將主要以遺傳算法為工具來對CARP問題進(jìn)行研究。本文對CARP問題研究的主要貢獻(xiàn)有如下幾個(gè)方面：
　?、僭趯鹘y(tǒng)CARP問題的數(shù)學(xué)模型進(jìn)行研究和分析的基礎(chǔ)上，補(bǔ)充提出了多車型CARP問題的數(shù)學(xué)模型。
　?、趯ΜF(xiàn)有解決CARP問題的算法中比較流行的Memetic Algorithm算法（MA）進(jìn)行了細(xì)致的研究，分析了MA算法中的幾個(gè)主要算法過程的時(shí)間復(fù)雜度及其對算法執(zhí)行效率的影響，并指出了該算法無力解決多車型CAR

4、P問題的主要原因。
　?、弁ㄟ^將傳統(tǒng)遺傳算法（TGA）與單親遺傳算法（PGA）進(jìn)行結(jié)合，并對遺傳算法的種群結(jié)構(gòu)以及進(jìn)化算子進(jìn)行改進(jìn)設(shè)計(jì)，進(jìn)而提出了一種不但可以有效求解多車型CARP問題，同時(shí)在求解普通單車型CARP問題上也具有更加出色的運(yùn)算速度的混合遺傳算法。
　　④為多車型 CARP問題的研究提供了四組不同規(guī)模的測試數(shù)據(jù)集。在該四組數(shù)據(jù)集上對本文算法在求解多車型 CARP問題時(shí)的有效性進(jìn)行測試，取得了良好的效果。在國際上流