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

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

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

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

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

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

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