基于分解和決策空間相似性度量的進(jìn)化多目標(biāo)車輛路徑規(guī)劃算法研究.pdf

1、車輛路徑規(guī)劃問題作為物流管理和交通運(yùn)輸?shù)痊F(xiàn)實問題中重要研究內(nèi)容，吸引了大量學(xué)者對其進(jìn)行研究。它的主要目的就是合理安排車輛行駛路線，降低企業(yè)運(yùn)輸成本。目前，研究學(xué)者提出了許多精確算法、啟發(fā)式算法和元啟發(fā)式算法來求解該問題。然而，大部分現(xiàn)有的方法都是優(yōu)化單個目標(biāo)函數(shù)。在現(xiàn)實中，存在許多與運(yùn)輸成本相關(guān)的優(yōu)化目標(biāo)，如車輛數(shù)，路徑總距離，總等待時間，車輛最長服務(wù)時間等。如果僅優(yōu)化其中一個目標(biāo)，可能導(dǎo)致其它目標(biāo)函數(shù)值變差，所以，不如同時優(yōu)化多個目標(biāo)

2、函數(shù)。因此，我們需要研究多目標(biāo)車輛路徑規(guī)劃問題，以便于決策者根據(jù)自己需要選擇合理的路線解決方案。
　　基于分解的多目標(biāo)進(jìn)化算法（MOEA/D）將一個多目標(biāo)優(yōu)化問題分解成一組單目標(biāo)優(yōu)化子問題并同時優(yōu)化他們。由于MOEA/D的簡易性和突出表現(xiàn)性能，它已經(jīng)得到了廣泛的研究和應(yīng)用。本文將MOEA/D應(yīng)用到求解帶時間窗約束的車輛路徑規(guī)劃問題（VRPTW），同時最小優(yōu)化車輛數(shù)和路徑總距離這兩個沖突的目標(biāo)函數(shù)。受限于車輛數(shù)這一不連續(xù)的目標(biāo)函數(shù)，

3、VRPTW問題的非支配解數(shù)量較少，MOEA/D中原有的切比雪夫選擇方法無法維持進(jìn)化種群的多樣性，因此，我們提出了一種新設(shè)計的選擇算子替換MOEA/D原有的選擇算子。另外，局部搜索算子在多目標(biāo)進(jìn)化算法優(yōu)化中具有重要作用，它可以加快種群的收斂速度，搜索出進(jìn)化過程中遺漏的搜索區(qū)域，因此，我們又將三個啟發(fā)式局部搜索算子引入到MOEA/D，加快算法的搜索效率，最后形成了改進(jìn)的MOEA/D（I-MOEA/D）。我們將I-MOEA/D算法在Solom

4、on100個客戶點(diǎn)的數(shù)據(jù)集上進(jìn)行了仿真實驗，驗證了I-MOEA/D算法的高效性。進(jìn)一步實驗分析了兩個算子（局部搜索算子和新設(shè)計選擇算子）在I-MOEA/D算法中的作用。
　　MOEA/D算法通過子問題的權(quán)向量之間的歐式距離構(gòu)建的子問題鄰域。然而，對于多目標(biāo)VRPTW問題，由于目標(biāo)空間上具有相似目標(biāo)值的兩個解在決策空間上可能相差很大，所以兩個鄰域子問題的最優(yōu)解可能完全不同。因此，我們引入了Jaccard相似系數(shù)概念來測量兩個個體在決