基于免疫遺傳算法的物流配送VRP問題研究.pdf

1、物流配送路徑優(yōu)化，即車輛路徑問題(VRP)，是當今物流配送優(yōu)化中關鍵的一環(huán)，也是電子商務活動不可缺少的內容，一直是近二十多年來的研究熱點。運輸路線是否合理直接影響到配送速度、成本和效益。選取恰當的車輛路徑，不僅可以加快對客戶需求的響應速度，提高服務質量，還可以增強客戶對物流環(huán)節(jié)的滿意度，降低服務商運作成本。
　　 本文在認真分析國內外VRP研究的基礎上，建立了一種基于單邊硬時間窗的物流配送路徑優(yōu)化模型(ST-VRP)，提出單邊硬

2、時間窗的車輛路徑問題，即在不違背車輛容量，最大路徑時間等約束條件的前提下，合理規(guī)劃運輸時的車輛路徑安排，以盡可能小的成本滿足客戶對貨物和服務時間的要求。
　　 首先介紹了課題的研究背景、意義及VRP問題的研究現(xiàn)狀，分析了物流配送VRP問題的構成要素及分類，總結和比較了以往解決VRP問題的算法及存在的缺點，最后將遺傳算法(GA)和免疫系統(tǒng)的思想相結合，提出一種免疫遺傳改進算法用以解決ST-VRP問題。該算法依據抗原與抗體的親和度以

3、及抗體之間的親和度進行評價和選擇，通過抗體之間的促進和抑制作用，提高最優(yōu)點附近的搜索效率：通過記憶細胞的作用，有效地減小了陷入局部最優(yōu)點的可能，提高了全局搜索能力。
　　 基于基本免疫遺傳算法(IGA)解決ST-VRP問題的解決方案，提出對基本免疫遺傳算法的三個重要的改進策略：第一，針對以往免疫遺傳算法基于單種群的缺陷，算法一旦達到平衡狀態(tài)則種群不會再有大的變化從而難以尋求全局最優(yōu)，將分布式遺傳算法(DGA)的思想引入到免疫遺傳

4、算法中，提出多種群策略和遷移算子策略，從而有效提高了算法的搜索范圍，防止算法出現(xiàn)“早熟”現(xiàn)象；第二，在新抗體產生的過程中，為了進一步提高選擇算子的選優(yōu)能力，在傳統(tǒng)輪盤賭選擇算子的基礎上提出一種基于排序的多輪輪盤賭選擇算子，在提高了選擇算子的選優(yōu)能力的同時有效地減少了隨機性所產生的誤差；隨后將此算子與最佳個體保存法的思想相結合，進一步提出了無回放的基于排序的多輪輪盤賭選擇算子，達到了既能夠選出最好個體又能夠保證種群多樣性的效果；第三，針對

5、基于信息熵親和力計算方法適用于二進制編碼問題但不適用于實數編碼問題的缺點，以及基于矢量距離的親和力計算方法忽略了VRP問題編碼中弧信息的缺點，提出一種新的基于對等弧的親和力計算方法，該方法針對ST-VRP問題編碼特征能夠更有效地保證種群內抗體的多樣性。
　　 在本文的最后給出了用改進的免疫遺傳算法解決物流配送ST-VRP問題的詳細流程，并應用Java語言編程實現(xiàn)了新算法。通過將新算法的實驗數據與遺傳算法以及基本免疫遺傳算法相比較