大規(guī)模車(chē)輛路徑問(wèn)題的優(yōu)化方法研究.pdf

1、配送環(huán)節(jié)在大規(guī)模的物流網(wǎng)絡(luò)系統(tǒng)中有著重要的地位，根據(jù)國(guó)外權(quán)威數(shù)據(jù)顯示，超過(guò)一半的物流成本來(lái)自于配送環(huán)節(jié)，尤其是在大規(guī)模物流配送網(wǎng)絡(luò)中。而隨著交通線路的日趨復(fù)雜以及更高的客戶響應(yīng)需求，對(duì)科學(xué)規(guī)劃路徑也提出了很高的要求。因此，大規(guī)模車(chē)輛路徑問(wèn)題的優(yōu)化研究成為合理降低物流成本的關(guān)鍵。
　　本文針對(duì)大規(guī)模的車(chē)輛路徑問(wèn)題，考慮客戶的靜態(tài)和動(dòng)態(tài)需求來(lái)研究車(chē)輛路徑問(wèn)題。主要包括兩個(gè)方面：一是在考慮客戶靜態(tài)需求基礎(chǔ)上，根據(jù)是否可以分割配送來(lái)研究車(chē)

2、輛路徑問(wèn)題的優(yōu)化方法，并基于啟發(fā)式方法求解了需求允許分割下的車(chē)輛路徑問(wèn)題；二是考慮客戶隨機(jī)需求的基礎(chǔ)上，應(yīng)用馬爾科夫過(guò)程和啟發(fā)式算法來(lái)給出一對(duì)車(chē)輛實(shí)時(shí)動(dòng)態(tài)路徑規(guī)劃的策略。本文的主要工作內(nèi)容和創(chuàng)新點(diǎn)如下：
　　首先，針對(duì)大規(guī)模配送系統(tǒng)中的客戶需求進(jìn)行客戶聚類子問(wèn)題的研究，以便在每個(gè)聚類集上的車(chē)輛配送問(wèn)題研究。提出了一種新的基于人工免疫系統(tǒng)的聚類算法。為了得到較好地初始解，引入自組織映射方法來(lái)生成初始抗體群；在迭代聚類算法過(guò)程中，設(shè)計(jì)

3、了一系列優(yōu)化和控制進(jìn)化的策略，如聚類滿意度、種群規(guī)模的閾值、學(xué)習(xí)率、聚類監(jiān)測(cè)點(diǎn)和聚類評(píng)價(jià)指標(biāo)等。這些策略可以使得聚類參數(shù)閾值實(shí)現(xiàn)自適應(yīng)量化來(lái)減少用戶的主觀因素影響；并通過(guò)策略的綜合作用，來(lái)同時(shí)得到一種取得局部聚類和全局聚類的方法。最后，仿真實(shí)驗(yàn)和分析比較說(shuō)明了本文方法的有效性。
　　其次，考慮了靜態(tài)客戶需求下的大規(guī)模車(chē)輛路徑問(wèn)題。在前一部分的研究基礎(chǔ)上，提出了一個(gè)基于人工免疫系統(tǒng)(AIS)的啟發(fā)式算法來(lái)求解車(chē)輛路徑問(wèn)題。通過(guò)引入一

4、種新的路徑覆蓋方法，設(shè)計(jì)了一種新的編碼和算法結(jié)構(gòu)。配送路徑通過(guò)先聚類后路徑的方法產(chǎn)生，并通過(guò)網(wǎng)絡(luò)更新機(jī)制來(lái)產(chǎn)生初始抗體，以機(jī)會(huì)均等下的雙向?qū)W習(xí)來(lái)擴(kuò)增抗體。進(jìn)一步，發(fā)展了同心圓建造策略來(lái)識(shí)別不同客戶類，以便形成更多的配送路徑以供選擇；而提出的兩種精英策略(AB)和(R)來(lái)去掉較差的抗體以保持配送路徑庫(kù)中路徑的多樣性。然后，再通過(guò)求解更新后路徑庫(kù)中的集合覆蓋模型，使得VRP解隨著不斷增加的路徑選擇而逐步實(shí)現(xiàn)優(yōu)化過(guò)程。最后，還設(shè)計(jì)了路徑合并策

5、略來(lái)進(jìn)一步增加更優(yōu)的路徑。這樣，最終的VRP最優(yōu)解通過(guò)在最終路徑庫(kù)中選擇成本最優(yōu)的路徑來(lái)得到。仿真實(shí)驗(yàn)分析說(shuō)明了所提算法的有效性。
　　第三，在考慮客戶靜態(tài)需求下，針對(duì)一類客戶需求允許分割的集成裝載問(wèn)題進(jìn)行研究。分析該問(wèn)題的特點(diǎn)，建立了一個(gè)雙層規(guī)劃模型來(lái)進(jìn)行描述。為求解該問(wèn)題，提出了一種雙層的聚類算法，即把客戶需求進(jìn)行子聚類的算法和針對(duì)每個(gè)聚類的客戶需求，再進(jìn)行車(chē)輛配載聚類的算法。算法綜合應(yīng)用了人工免疫系統(tǒng)、啟發(fā)式規(guī)則和偽系統(tǒng)聚類

6、算法等，逐步迭代得出整個(gè)系統(tǒng)的最優(yōu)解。最后，設(shè)計(jì)了仿真數(shù)值實(shí)驗(yàn)，并進(jìn)一步與現(xiàn)有文獻(xiàn)的研究成果進(jìn)行了比較分析，得出了所提算法性能的優(yōu)異性。
　　最后，對(duì)于隨機(jī)客戶需求下的車(chē)輛路徑問(wèn)題，提出了一個(gè)成對(duì)合作重新規(guī)劃路徑的策略問(wèn)題。該策略可以實(shí)現(xiàn)配送的一對(duì)車(chē)輛相互配合，通過(guò)兩者之間觸發(fā)有效的通訊，基于實(shí)時(shí)的客戶需求更新車(chē)輛指派，來(lái)實(shí)現(xiàn)配送中路徑重優(yōu)化的動(dòng)態(tài)規(guī)劃效果。本章提出了一個(gè)雙層馬爾科夫過(guò)程來(lái)描述此策略，同時(shí)設(shè)計(jì)了啟發(fā)式算法來(lái)根據(jù)實(shí)時(shí)