基于遺傳算法的VRP擴(kuò)展模型求解方法研究
發(fā)布時(shí)間：2021-06-01 01:25
車輛路徑問(wèn)題（Vehicle Routing Problem,VRP）是一種典型的組合優(yōu)化問(wèn)題,其具有廣泛的應(yīng)用背景。為了應(yīng)對(duì)實(shí)際的需求,對(duì)VRP基本模型進(jìn)行擴(kuò)展,并提出有效算法是目前關(guān)于該問(wèn)題的研究熱點(diǎn)。本文就兩類復(fù)雜的VRP擴(kuò)展模型展開(kāi)探索,（1）中心點(diǎn)的擴(kuò)展,由單一中心擴(kuò)展為多中心;（2）服務(wù)對(duì)象的需求由靜態(tài)擴(kuò)展為動(dòng)態(tài)。結(jié)合實(shí)際問(wèn)題,本文先分析了一種生活中復(fù)雜的垃圾收運(yùn)問(wèn)題——多回收站垃圾收運(yùn)問(wèn)題（Multi-station Refuse Collection Problem,MSRCP）,并將其映射為多中心車輛調(diào)度問(wèn)題。建立了以最小車輛運(yùn)輸費(fèi)用為目標(biāo)的多回收站垃圾收運(yùn)問(wèn)題模型,設(shè)計(jì)了一種基于協(xié)同進(jìn)化（Cooperative Co-evolutionary,CC）作為外部框架的問(wèn)題求解方法。首先利用本文的聚類算法,對(duì)每個(gè)垃圾回收站進(jìn)行垃圾收集點(diǎn)的分配操作,將多回收站的垃圾收運(yùn)問(wèn)題分解為多個(gè)單回收站的垃圾收運(yùn)問(wèn)題。再采用一種混合遺傳算法對(duì)每個(gè)單回收站進(jìn)行路徑規(guī)劃處理。最后,以安慶市大觀區(qū)生活垃圾收運(yùn)為例進(jìn)行了上述模型及算法的驗(yàn)證,結(jié)果表明本文所提算法在降低復(fù)雜垃圾收運(yùn)問(wèn)題時(shí),具有良...
【文章來(lái)源】：安慶師范大學(xué)安徽省
【文章頁(yè)數(shù)】：54 頁(yè)
【學(xué)位級(jí)別】：碩士
【部分圖文】：
改進(jìn)規(guī)則二應(yīng)用說(shuō)明圖
路線，增大了該問(wèn)題解的搜索范圍，提高了種群的多樣性。具體步驟如圖 3.2 所示：第一步，在初始種群中隨機(jī)選擇兩條父代染色體 P1、P2，即兩種對(duì)垃圾收集點(diǎn)進(jìn)行垃圾收集的服務(wù)順序。染色體中單個(gè)基因代表單個(gè)垃圾收集點(diǎn)，基因片段代表多個(gè)有服務(wù)順序的垃圾收集點(diǎn)集合。第二步，在 P1、P2 中隨機(jī)選取相同位置的基因片段，分別記為change1 和 change2；第三步，按一定規(guī)律改變 P1、P2 中 change1 和 change2 的位置，再刪去 P1 中與 change2 相同的基因，P2 中與 change1 相同的基因；第三步，按一定規(guī)律將 change2 放入刪除后的 P1 中，將 change1 放入刪除后的 P2 中，交叉操作完成生成子代 C1、C2。
18（4）局部搜索算子設(shè)計(jì)傳統(tǒng)的遺傳算法中初始化種群經(jīng)過(guò)選擇、交叉產(chǎn)生后代，進(jìn)入變異操作，但是變異概率低，局部搜索能力差，有早熟收斂的風(fēng)險(xiǎn)。本章以一定變異概率對(duì)初始化種群的每一條染色體依次進(jìn)行四種局部搜索，反映到MSRCP問(wèn)題中，就是依次以不同的方法將一條服務(wù)順序上的垃圾收集點(diǎn)變換位置，找到最合適的收集順序。SingleInsertion（SI）單插入：在一條染色體中，依次將單個(gè)基因提取出來(lái)，插入到染色體的其他位置，每插入一個(gè)位置要記錄解并與原解作比較，如果當(dāng)前解要優(yōu)于原來(lái)的解，那么將替換原解。這里考慮解是閉合曲線，為避免重復(fù)，單個(gè)基因插入的位置避開(kāi)首基因的前一個(gè)位置和尾基因的后一個(gè)位置，如圖3.3左所示。DoubleInsertion（DI）雙插入：在一條染色體中，依次將兩個(gè)連續(xù)的基因提取出來(lái)，插入到染色體的其他位置，每插入一個(gè)位置要記錄解并與原解作比較，如果當(dāng)前解要優(yōu)于原來(lái)的解，那么將替換原解。同樣這里考慮解是閉合曲線，為避免重復(fù)，基因插入的位置避開(kāi)首基因的前一個(gè)位置和尾基因的后一個(gè)位置，如圖3.3右所示。圖3.3SI算子和DI算子示意圖Swap交換算子：在一條染色體中，依次將每個(gè)基因與這條染色體上的其他基因互換位置，每換一個(gè)位置要記錄解與原解相比，較優(yōu)則替換原解，如圖3.4所示。圖3.4Swap算子示意圖2-Opt：一條染色體轉(zhuǎn)譯成一個(gè)車輛路徑方案，經(jīng)常會(huì)出現(xiàn)路徑與路徑之間的交叉，這樣必定會(huì)增加行駛距離，所以利用2-Opt方法來(lái)消除這個(gè)現(xiàn)象，如圖3.5所示。2-Opt
本文編號(hào)：3209380
【文章來(lái)源】：安慶師范大學(xué)安徽省
【文章頁(yè)數(shù)】：54 頁(yè)
【學(xué)位級(jí)別】：碩士
【部分圖文】：
改進(jìn)規(guī)則二應(yīng)用說(shuō)明圖
路線，增大了該問(wèn)題解的搜索范圍，提高了種群的多樣性。具體步驟如圖 3.2 所示：第一步，在初始種群中隨機(jī)選擇兩條父代染色體 P1、P2，即兩種對(duì)垃圾收集點(diǎn)進(jìn)行垃圾收集的服務(wù)順序。染色體中單個(gè)基因代表單個(gè)垃圾收集點(diǎn)，基因片段代表多個(gè)有服務(wù)順序的垃圾收集點(diǎn)集合。第二步，在 P1、P2 中隨機(jī)選取相同位置的基因片段，分別記為change1 和 change2；第三步，按一定規(guī)律改變 P1、P2 中 change1 和 change2 的位置，再刪去 P1 中與 change2 相同的基因，P2 中與 change1 相同的基因；第三步，按一定規(guī)律將 change2 放入刪除后的 P1 中，將 change1 放入刪除后的 P2 中，交叉操作完成生成子代 C1、C2。
18（4）局部搜索算子設(shè)計(jì)傳統(tǒng)的遺傳算法中初始化種群經(jīng)過(guò)選擇、交叉產(chǎn)生后代，進(jìn)入變異操作，但是變異概率低，局部搜索能力差，有早熟收斂的風(fēng)險(xiǎn)。本章以一定變異概率對(duì)初始化種群的每一條染色體依次進(jìn)行四種局部搜索，反映到MSRCP問(wèn)題中，就是依次以不同的方法將一條服務(wù)順序上的垃圾收集點(diǎn)變換位置，找到最合適的收集順序。SingleInsertion（SI）單插入：在一條染色體中，依次將單個(gè)基因提取出來(lái)，插入到染色體的其他位置，每插入一個(gè)位置要記錄解并與原解作比較，如果當(dāng)前解要優(yōu)于原來(lái)的解，那么將替換原解。這里考慮解是閉合曲線，為避免重復(fù)，單個(gè)基因插入的位置避開(kāi)首基因的前一個(gè)位置和尾基因的后一個(gè)位置，如圖3.3左所示。DoubleInsertion（DI）雙插入：在一條染色體中，依次將兩個(gè)連續(xù)的基因提取出來(lái)，插入到染色體的其他位置，每插入一個(gè)位置要記錄解并與原解作比較，如果當(dāng)前解要優(yōu)于原來(lái)的解，那么將替換原解。同樣這里考慮解是閉合曲線，為避免重復(fù)，基因插入的位置避開(kāi)首基因的前一個(gè)位置和尾基因的后一個(gè)位置，如圖3.3右所示。圖3.3SI算子和DI算子示意圖Swap交換算子：在一條染色體中，依次將每個(gè)基因與這條染色體上的其他基因互換位置，每換一個(gè)位置要記錄解與原解相比，較優(yōu)則替換原解，如圖3.4所示。圖3.4Swap算子示意圖2-Opt：一條染色體轉(zhuǎn)譯成一個(gè)車輛路徑方案，經(jīng)常會(huì)出現(xiàn)路徑與路徑之間的交叉，這樣必定會(huì)增加行駛距離，所以利用2-Opt方法來(lái)消除這個(gè)現(xiàn)象，如圖3.5所示。2-Opt
本文編號(hào)：3209380
本文鏈接：http://sikaile.net/shoufeilunwen/boshibiyelunwen/3209380.html
最近更新
教材專著
