多旅行商問題作為經(jīng)典的旅行商問題的一種擴展,通過附加一定的約束條件,可以模擬生活中的很多實際問題,例如物流規(guī)劃、無人機巡檢、任務(wù)調(diào)度等。多旅行商問題已經(jīng)被證明屬于NP-hard問題,精確的方法無法滿足于大規(guī)模問題的求解需求,而啟發(fā)式算法能夠在較短的時間內(nèi)得到質(zhì)量較好的解,這使得研究人員對于此問題求解方法的關(guān)注更傾向于后者。對于多旅行商問題而言,增加的推銷人員數(shù)量并不是為了減少總路程上的花費,而通常是用作平衡推銷員之間的工作量或是減少為每個客戶服務(wù)時間的舉措。大部分已有文獻在討論該問題的時候都從兩個方面出發(fā),其一是通過減少總路程來使得總花費最小,其二是最小化推銷員中的最長路線以平衡推銷員之間的工作量。然而平衡工作負載和減少總路程的長度是兩個相互沖突的目標,因此本文從多目標優(yōu)化的角度對多旅行商問題進行分析和求解。NSGA-Ⅱ是眾多進化多目標優(yōu)化算法中備受歡迎的一種,已經(jīng)被應(yīng)用到很多實際問題之中,并取得了較好的效果。本文基于NSGA-Ⅱ算法框架,通過對遺傳算法中染色體、交叉算子以及變異算子的設(shè)計來求解多旅行商問題,以得到分布性較好、收斂性較強的Pareto前沿�？紤]到現(xiàn)實生活中,多數(shù)優(yōu)化問題...

【文章頁數(shù)】：66 頁

【學位級別】：碩士

【部分圖文】：

圖3.9eil51-3實例交叉對比和berlin52-3實例交叉對比

武漢科技大學碩士學位論文24代次數(shù)設(shè)置為1400，而eil76和rat99兩個實例的迭代次數(shù)則設(shè)置為1800，實驗結(jié)果如下，其中橫坐標軸均表示總路程（距離），縱坐標軸均表示平衡度（平衡度的衡量標準是推銷員中最長行程與最短行程的差），此兩個標準的數(shù)學公式已經(jīng)在第二章給出，在此不做贅....

圖3.10eil76-3實例交叉對比和rat99-3實例交叉對比

武漢科技大學碩士學位論文24代次數(shù)設(shè)置為1400，而eil76和rat99兩個實例的迭代次數(shù)則設(shè)置為1800，實驗結(jié)果如下，其中橫坐標軸均表示總路程（距離），縱坐標軸均表示平衡度（平衡度的衡量標準是推銷員中最長行程與最短行程的差），此兩個標準的數(shù)學公式已經(jīng)在第二章給出，在此不做贅....

圖3.11rat99-3在平衡度200以內(nèi)的結(jié)果對比

武漢科技大學碩士學位論文25圖3.11rat99-3在平衡度200以內(nèi)的結(jié)果對比綜上4個實例的對比測試，在保證算法中其他變量相同的情況下，以同樣的迭代次數(shù)不同的交叉方法進行對比試驗，結(jié)果表明SNX都有著較好的效果，具體表現(xiàn)在良好的收斂性和多樣性上面，上述測試實例中SNX相對于PM....

圖3.14eil51-5實例和berlin52-5實例

武漢科技大學碩士學位論文2612345678937第一部分第二部分12765438926反轉(zhuǎn)順序重新產(chǎn)生00圖3.12變異方式112345678937第一部分第二部分34512678926重新生成12312300圖3.13變異方式2同樣的，對于eil51實例和berlin52實例....

本文編號：3960165