有補(bǔ)給點(diǎn)及多裝載的容量約束弧路徑問題的算法研究.pdf

1、帶有容量約束的弧路徑問題(Capacitated Arc Routing Problem,CARP)產(chǎn)生于交通運(yùn)輸服務(wù)系統(tǒng)，是弧路徑問題(Arc Routing Problem,ARP)的一種特殊情況，因其可應(yīng)用于如城市垃圾回收、街道清掃、郵件投遞、結(jié)冰路面撒鹽及路面維護(hù)等實(shí)際問題，故近年來得到了廣泛的研究。本文所研究的有補(bǔ)給點(diǎn)及多裝載的容量約束弧路徑問題（Capacitated Arc Routing Problem with Ref

2、ill Points and Multiple loads,CARP-RP-ML），由于考慮具有能多次給服務(wù)車(Service Vehicle,SV)提供原料補(bǔ)給的補(bǔ)給車輛(Refill Vehicle,RV),因此屬于容量約束弧路徑問題的一種推廣形式。該類問題是NP-hard問題，傳統(tǒng)的算法如精確算法，下界法都因自身缺陷而不能很好地解決這類問題，然而遺傳算法作為一種啟發(fā)式算法因其內(nèi)在的自學(xué)習(xí)性、并行性、穩(wěn)定性等強(qiáng)大優(yōu)點(diǎn)已被證明能很好地

3、解決容量約束弧路徑問題。
　　本文以CARP-RP-ML為研究對象，在廣泛查閱國內(nèi)外文獻(xiàn)的基礎(chǔ)上，深入研究該問題的求解方法，提出了求解CARP-RP-ML問題的分割啟發(fā)式算法和遺傳算法，為CARP問題推廣形式的求解提供了借鑒與參考，主要研究工作和成果如下：
　　1．對CARP問題及其推廣形式進(jìn)行了描述，并引入了有補(bǔ)給點(diǎn)的多裝CARP問題(CARP-RP-ML),并給出該問題的數(shù)學(xué)模型，在歸納總結(jié)已有方法的基礎(chǔ)上，設(shè)計(jì)相應(yīng)算法

4、解決該問題。
　　2．本文根據(jù)CARP-RP-ML問題的特性，提出一種分割啟發(fā)式算法來求得兩類車的最短路徑及問題的可行解，其中設(shè)計(jì)的分割算法在滿足容量約束的條件下對隨機(jī)排序的所有需求弧進(jìn)行分割，以所能達(dá)到的補(bǔ)給點(diǎn)為分割點(diǎn)，計(jì)算出兩個(gè)連續(xù)補(bǔ)給點(diǎn)間兩類不同類型的車輛總費(fèi)用，記錄并保存從車場到當(dāng)前補(bǔ)給點(diǎn)的最小費(fèi)用，直到所有需求弧服務(wù)完畢。
　　3．基于分割算法，文章利用遺傳算法極強(qiáng)的魯棒性和內(nèi)在并行機(jī)制等優(yōu)點(diǎn)進(jìn)一步求得問題的近似最