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

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

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

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

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

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