一種求解多目標(biāo)車輛路徑問題的遺傳算法研究.pdf

1、車輛路徑問題(Vehicle routing problem，VRP)是一個(gè)經(jīng)典的運(yùn)籌學(xué)問題，它是指若干個(gè)客戶各自有著不同的貨物需求，若干個(gè)配送中心向客戶提供貨物，由車隊(duì)負(fù)責(zé)分送貨物，組織適當(dāng)?shù)男熊嚶肪€，目標(biāo)是使得客戶的需求得到滿足，并能在一定的約束下，達(dá)到諸如路程最短、成本最小、耗費(fèi)時(shí)間最少等目的。VRP問題在科學(xué)和工程應(yīng)用領(lǐng)域具有非常廣泛的應(yīng)用，很多實(shí)際的物流運(yùn)輸問題都可以轉(zhuǎn)化成各種VRP問題來進(jìn)行解決。由于VRP已經(jīng)被證明是NP難

2、的，所以對(duì)于大規(guī)模VRP問題往往考慮利用各種智能優(yōu)化算法來進(jìn)行求解。
　　隨著經(jīng)濟(jì)的發(fā)展、科學(xué)技術(shù)的進(jìn)步以及人們需求的日益多元化，越來越多實(shí)際應(yīng)用問題往往需要考慮多個(gè)優(yōu)化目標(biāo)，多目標(biāo)優(yōu)化正在成為近年來運(yùn)籌學(xué)領(lǐng)域一個(gè)研究熱點(diǎn)。需要注意的是目前關(guān)于多目標(biāo)VRP問題的研究文獻(xiàn)并不多，在很多方面尤其是求解算法設(shè)計(jì)方面亟需開展進(jìn)一步深入的研究。
　　本文采納系統(tǒng)工程的思想，利用運(yùn)籌學(xué)、進(jìn)化計(jì)算等領(lǐng)域的相關(guān)研究成果，設(shè)計(jì)和開發(fā)一種能夠有

3、效求解多目標(biāo)VRP問題的遺傳算法(Genetic algorithm，GA)。本文的主要內(nèi)容可以歸納如下幾個(gè)方面:
　　(1)相關(guān)工作綜述部分。主要介紹了VRP問題及求解算法、多目標(biāo)優(yōu)化理論與方法等方面的研究工作。
　　(2)問題建模部分。在給出一般VRP以及帶有時(shí)間窗約束VRP問題數(shù)學(xué)模型的基礎(chǔ)上，建立一個(gè)以最小化配送成本和最大化客戶滿意度為目標(biāo)函數(shù)的多目標(biāo)VRP問題的數(shù)學(xué)模型。
　　(3)算法設(shè)計(jì)部分。研究一般VR

4、P問題的求解算法，考慮到編碼和解碼是求解VRP問題的GA設(shè)計(jì)中所面臨的主要挑戰(zhàn)，對(duì)三種不同編碼方法的有效性進(jìn)行對(duì)比仿真實(shí)驗(yàn)。在上述研究結(jié)論的基礎(chǔ)上，通過結(jié)合一種經(jīng)典多目標(biāo)進(jìn)化算法(MOEA/D)的相關(guān)思想，提出一種能夠求解多目標(biāo)VRP問題的新型多目標(biāo)GA算法。
　　(4)仿真實(shí)驗(yàn)部分。利用一組根據(jù)VRPLIB中標(biāo)準(zhǔn)測(cè)試問題構(gòu)造的多目標(biāo)VRP問題，對(duì)所提出的多目標(biāo)GA算法進(jìn)行仿真實(shí)驗(yàn)以檢驗(yàn)其性能。此外，還在仿真實(shí)驗(yàn)中分析所提出的算法