車輛路徑問題（Vehicle Routing Problem,VRP）是一種典型的組合優(yōu)化問題,其具有廣泛的應(yīng)用背景。為了應(yīng)對實際的需求,對VRP基本模型進行擴展,并提出有效算法是目前關(guān)于該問題的研究熱點。本文就兩類復(fù)雜的VRP擴展模型展開探索,（1）中心點的擴展,由單一中心擴展為多中心;（2）服務(wù)對象的需求由靜態(tài)擴展為動態(tài)。結(jié)合實際問題,本文先分析了一種生活中復(fù)雜的垃圾收運問題——多回收站垃圾收運問題（Multi-station Refuse Collection Problem,MSRCP）,并將其映射為多中心車輛調(diào)度問題。建立了以最小車輛運輸費用為目標的多回收站垃圾收運問題模型,設(shè)計了一種基于協(xié)同進化（Cooperative Co-evolutionary,CC）作為外部框架的問題求解方法。首先利用本文的聚類算法,對每個垃圾回收站進行垃圾收集點的分配操作,將多回收站的垃圾收運問題分解為多個單回收站的垃圾收運問題。再采用一種混合遺傳算法對每個單回收站進行路徑規(guī)劃處理。最后,以安慶市大觀區(qū)生活垃圾收運為例進行了上述模型及算法的驗證,結(jié)果表明本文所提算法在降低復(fù)雜垃圾收運問題時,具有良... 

【文章來源】：安慶師范大學(xué)安徽省

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

【學(xué)位級別】：碩士

【部分圖文】：

改進規(guī)則二應(yīng)用說明圖

路線，增大了該問題解的搜索范圍，提高了種群的多樣性。具體步驟如圖 3.2 所示：第一步，在初始種群中隨機選擇兩條父代染色體 P1、P2，即兩種對垃圾收集點進行垃圾收集的服務(wù)順序。染色體中單個基因代表單個垃圾收集點，基因片段代表多個有服務(wù)順序的垃圾收集點集合。第二步，在 P1、P2 中隨機選取相同位置的基因片段，分別記為change1 和 change2；第三步，按一定規(guī)律改變 P1、P2 中 change1 和 change2 的位置，再刪去 P1 中與 change2 相同的基因，P2 中與 change1 相同的基因；第三步，按一定規(guī)律將 change2 放入刪除后的 P1 中，將 change1 放入刪除后的 P2 中，交叉操作完成生成子代 C1、C2。

18（4）局部搜索算子設(shè)計傳統(tǒng)的遺傳算法中初始化種群經(jīng)過選擇、交叉產(chǎn)生后代，進入變異操作，但是變異概率低，局部搜索能力差，有早熟收斂的風(fēng)險。本章以一定變異概率對初始化種群的每一條染色體依次進行四種局部搜索，反映到MSRCP問題中，就是依次以不同的方法將一條服務(wù)順序上的垃圾收集點變換位置，找到最合適的收集順序。SingleInsertion（SI）單插入：在一條染色體中，依次將單個基因提取出來，插入到染色體的其他位置，每插入一個位置要記錄解并與原解作比較，如果當(dāng)前解要優(yōu)于原來的解，那么將替換原解。這里考慮解是閉合曲線，為避免重復(fù)，單個基因插入的位置避開首基因的前一個位置和尾基因的后一個位置，如圖3.3左所示。DoubleInsertion（DI）雙插入：在一條染色體中，依次將兩個連續(xù)的基因提取出來，插入到染色體的其他位置，每插入一個位置要記錄解并與原解作比較，如果當(dāng)前解要優(yōu)于原來的解，那么將替換原解。同樣這里考慮解是閉合曲線，為避免重復(fù)，基因插入的位置避開首基因的前一個位置和尾基因的后一個位置，如圖3.3右所示。圖3.3SI算子和DI算子示意圖Swap交換算子：在一條染色體中，依次將每個基因與這條染色體上的其他基因互換位置，每換一個位置要記錄解與原解相比，較優(yōu)則替換原解，如圖3.4所示。圖3.4Swap算子示意圖2-Opt：一條染色體轉(zhuǎn)譯成一個車輛路徑方案，經(jīng)常會出現(xiàn)路徑與路徑之間的交叉，這樣必定會增加行駛距離，所以利用2-Opt方法來消除這個現(xiàn)象，如圖3.5所示。2-Opt


本文編號：3209380