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

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

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

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

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

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