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

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

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

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

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