亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        基于遺傳算法和免疫算法的垃圾清運路徑規(guī)劃
        ——以安陽工學(xué)院為例

        2022-04-15 01:59:58李亞茹
        安陽工學(xué)院學(xué)報 2022年2期
        關(guān)鍵詞:清運中轉(zhuǎn)站遺傳算法

        李 航,劉 然,張 潔,李亞茹

        (安陽工學(xué)院,河南 安陽 455000)

        隨著垃圾分類的力度日益加大,高校為了滿足垃圾收集,在校園內(nèi)投放了大量的垃圾桶,但是垃圾回收車的路徑常為隨機運動,這使得運輸產(chǎn)生了較多的往復(fù),增加了運輸時間和成本,一些研究運用蟻群算法進行路徑優(yōu)化[1-8],一些則采用遺傳算法將之轉(zhuǎn)變?yōu)門SP問題求解[9-15]。實際垃圾收運問題涉及回收中心、車輛裝載、往復(fù)運輸?shù)燃s束條件,因此垃圾收運可以化歸為CVRP問題,垃圾中轉(zhuǎn)站設(shè)置可以化歸為FLP問題,為了更加有效的設(shè)置中轉(zhuǎn)站并調(diào)動垃圾車清運,采用GA算法和IA算法進行優(yōu)化設(shè)計。

        1 垃圾運輸問題提出及其數(shù)學(xué)模型

        安陽工學(xué)院校園內(nèi)現(xiàn)有垃圾回收點77處,垃圾中轉(zhuǎn)站1處,垃圾回收車7輛,每輛垃圾回收車最大載量為400 L,每次全園區(qū)清運總費用約1 150元,在無時間窗限制的情況下,垃圾回收車均以空車狀態(tài)從垃圾中轉(zhuǎn)站出發(fā),遍歷77處垃圾回收點,當(dāng)回收達到最大載量后需要回到中轉(zhuǎn)站卸載而后再投入工作,直至所有垃圾清運完成,其數(shù)學(xué)模型可以描述為:園區(qū)內(nèi)有1處垃圾中轉(zhuǎn)站,中轉(zhuǎn)站有m輛垃圾回收車,記為V={k},k=1,2,……m,每輛垃圾回收車載重為L,站點集合記為P={i},i=1,2,……n,各站點垃圾數(shù)量為Qi,從站點i到j(luò)的路程記為Dij,Cij為收運成本,規(guī)劃收運路線最短,分配垃圾回收車數(shù)量m最少。

        目標函數(shù)如下式所示:

        約束條件如下式所示:

        其中,式(1)表示垃圾回收車行程最短;式(2)表示垃圾回收車數(shù)量使用數(shù)最少;式(3)表示最小清運成本;式(4)表示垃圾回收車不能超載;式(5)、式(6)、式(7)表示垃圾回收車從垃圾中轉(zhuǎn)站0出發(fā),如果某處垃圾站點已經(jīng)被回收則其他垃圾車不再處理,回收完成后所有垃圾回收車最終返回中轉(zhuǎn)站。

        實際案例中垃圾回收點和垃圾中轉(zhuǎn)站散點圖如圖1所示,網(wǎng)格單位為米。

        圖1 垃圾回收點和垃圾中轉(zhuǎn)站散點圖

        2 遺傳算法求解

        2.1 編碼

        對于n個目標點的CVRP問題使用自然數(shù)編碼,即坐標系內(nèi)各點用自然數(shù)(n≥1)標記,本例中中轉(zhuǎn)站數(shù)量為1,編號標記為0,各垃圾回收點從1開始標記,受載重的約束,垃圾回收車ki從0開始收運并累積每個回收點的垃圾數(shù)量,超過最大載量時返回0點,并繼續(xù)遍歷,直到園區(qū)內(nèi)垃圾均回收。

        2.2 種群初始化

        根據(jù)目標點規(guī)模數(shù)量初始化一個種群作為初始解,本例采用隨機生成法,取值50。

        2.3 適應(yīng)度函數(shù)

        將P1|P2|P3|……|Pn|作為一個采用自然數(shù)編碼的染色體,為回收點Pi到Pj的距離,個體適應(yīng)度Fitness可表述為

        即遍歷n個回收點再返回0點路程的倒數(shù),適應(yīng)度函數(shù)的值越大染色體表現(xiàn)越好,反之則越差。

        2.4 遺傳算子

        個體被選中的概率與其適應(yīng)度函數(shù)成正比,數(shù)量為n群體中,個體i被選中遺傳到下一代的概率Si的可表述為式(9),在遺傳算子的基礎(chǔ)上,采用輪盤賭算法確定個體是否被遺傳到下一代。

        2.5 交叉運算

        采用部分映射多點雜交,產(chǎn)生個數(shù)為Nu的隨機數(shù),則父代個體基因串被分成Nu個基因段,A(i)表示父代個體A的第i個基因段,Ai=1……Nu,交叉概率取0.9。

        2.6 變異運算

        采用基本位變異,變異概率設(shè)定為0.05,即種群內(nèi)所有基因的5%進行變異,迭代數(shù)為100。

        遺傳算法初始相關(guān)參數(shù)如表1。

        表1 遺傳算法初始參數(shù)

        2.7 優(yōu)化結(jié)果

        本例中僅存在一個垃圾中轉(zhuǎn)站,5輛垃圾回收車即可完成整個園區(qū)的清運工作,較當(dāng)前設(shè)置可以節(jié)省2輛垃圾回收車,5輛垃圾回收車總路程為5 986.84 m,路徑圖及清運總成本變化趨勢如圖2所示,清運路徑如表2所示,回收成本降到600元左右,降比約48%。

        表2 遺傳算法路徑表

        圖2 中轉(zhuǎn)站數(shù)=1時清運路徑優(yōu)化圖及總成本變化趨勢圖

        分析優(yōu)化結(jié)果可知,路線5僅經(jīng)過了5個回收點,且與多條路徑之間產(chǎn)生交叉點,導(dǎo)致清運線程增加。在該模式下,處于園區(qū)邊緣的回收點垃圾存放量較少,垃圾回收車僅需訪問1次即可完成該點清運,因此Pc=0.9時,模型趨向純粹隨機搜索,遺傳算法結(jié)果的收斂性較差,重新設(shè)置Pc=0.5,Pm=0.01,并增加迭代次數(shù)為200,優(yōu)化清運路線及總成本變化趨勢如圖3所示,5輛垃圾回收車路徑如表3,總路程5 853.33 m,回收成本為595元。

        表3 Pc=0.5、MAXGEN=200路徑表

        圖3 Pc=0.5、MAXGEN=200路徑優(yōu)化路線圖及總成本變化趨勢圖

        3 選址問題的提出及其數(shù)學(xué)模型

        由上述遺傳算法結(jié)果可知,1處垃圾中轉(zhuǎn)站無法保證垃圾回收車就近卸載,實際上延長了清運路線,適當(dāng)增加中轉(zhuǎn)站數(shù)量并求解其位置可以進一步減少清運路線和清運成本。此處選擇使用免疫算法對多基址選取進行模擬優(yōu)化[16-22],在遺傳算法得出5輛垃圾回收車的前提下,其數(shù)學(xué)模型可以描述為:園區(qū)內(nèi)有大于1處的垃圾中轉(zhuǎn)站,記為Hi,所有中轉(zhuǎn)站共有5輛垃圾回收車,記為V={k},k=1,2,……5,每輛垃圾回收車載重為L,垃圾站點集合記為P={i},i=1,2,……n,各站點垃圾數(shù)量為Qi,從垃圾回收站點i到垃圾中轉(zhuǎn)站j的路程記為dij,垃圾中轉(zhuǎn)站距離由其服務(wù)的垃圾回收車的距離上限記為S,到回收點i的清運距離小于S的備選中轉(zhuǎn)站集合記為Mi,垃圾回收站點與垃圾中轉(zhuǎn)站的分配關(guān)系記為Jij,該值為0-1變量,Jij=1表示回收站點與垃圾中轉(zhuǎn)站j匹配,否則Jij=0,點j是否選為垃圾中轉(zhuǎn)站由0-1變量表示,記為hi,hj=1表示選為中轉(zhuǎn)站,否則hj=0,綜上在滿足距離上限的前提下,從所有回收點找出中轉(zhuǎn)站并回收垃圾,目標函數(shù)是各中轉(zhuǎn)站到回收站點的清運量和清運距離的乘積之和最小。

        目標函數(shù)如式(10)所示:

        約束條件如式(11)-式(15)所示:

        式中,式(10)表示垃圾回收站點到垃圾中轉(zhuǎn)站距離乘積之和最??;式(11)表示5輛垃圾回收車只能由一個垃圾中轉(zhuǎn)站發(fā)出;式(12)表示沒有中轉(zhuǎn)站則不會接受垃圾回收車返程卸載;式(13)表示垃圾中轉(zhuǎn)站總數(shù)量;式(14)表示Jij和hj兩個變量;式(15)表示垃圾回收站點與垃圾中轉(zhuǎn)站距離未超過上限值。

        4 免疫算法求解

        4.1 初始化記憶庫

        設(shè)置非空記憶庫,保證初始抗體群從記憶庫中產(chǎn)生,每個選址方案形成一個長度為t的抗體(t表示垃圾中轉(zhuǎn)站數(shù)量),每個抗體表示被選為中轉(zhuǎn)站的序列,本例中t=3,記憶庫容量=20。

        4.2 多樣性評價參數(shù)

        多樣性評價由抗體與抗原間的親和力、抗體與抗體間的親和力、抗體濃度以及繁殖概率得出,本例中采用精英保留策略,每次更新記憶庫均先將與抗原親和度最高的個體存入記憶庫,針對垃圾中轉(zhuǎn)站選址模型,設(shè)定多樣性評價參數(shù)Ps=0.9。

        4.3 免疫操作

        采用輪盤賭算法選擇單點交叉機制以及隨機變異,得交叉概率Pc=0.8,變異概率Pm=0.01,迭代次數(shù)為200,垃圾中轉(zhuǎn)站數(shù)為2。

        免疫算法初始相關(guān)參數(shù)如表4。

        表4 遺傳算法初始參數(shù)

        4.4 優(yōu)化結(jié)果

        將垃圾中轉(zhuǎn)站數(shù)量分別設(shè)定為2個、3個、4個、5個,選址位置及收斂曲線如圖4所示。本例中,當(dāng)垃圾中轉(zhuǎn)站數(shù)量超過3個后,垃圾回收車及中轉(zhuǎn)站利用率迅速降低,因此,綜合評價園區(qū)內(nèi)可設(shè)置垃圾中轉(zhuǎn)站數(shù)量為3,其坐標分別為A[191,261],B[381,323],C[527,65],對應(yīng)垃圾回收點數(shù)量分別為16,48,13。

        圖4 垃圾中轉(zhuǎn)站數(shù)量分別為2、3、4、5時選址位置圖及收斂曲線圖

        以3個垃圾中轉(zhuǎn)站再次進行遺傳算法路徑優(yōu)化,路徑圖和總成本圖如圖5所示,5個垃圾回收車的清運總路徑為5 326.94 m,清運成本約為502元,較“2.7”環(huán)節(jié)計算結(jié)果總路徑進一步減少550 m,清運成本降低約90元,分析變化趨勢圖可以發(fā)現(xiàn)曲線有較大波動但是收斂效果較佳。

        圖5 中轉(zhuǎn)站數(shù)=3時清運路徑圖及總成本變化趨勢圖

        5 結(jié)論

        以安陽工學(xué)院為例研究了垃圾中轉(zhuǎn)站設(shè)置和垃圾清運路線,得出校園內(nèi)站點分布相對集中、中轉(zhuǎn)站數(shù)量相對較少,不同分區(qū)內(nèi)垃圾數(shù)量的差異較大,處于邊緣的垃圾回收站點通常僅需一次訪問,在沒有時間窗限制的條件下,垃圾回收車路徑優(yōu)化主要由交叉概率Pc、變異概率Pm兩個參數(shù)控制,當(dāng)Pc=0.5和Pm=0.01時收斂平穩(wěn)的結(jié)論。

        園區(qū)內(nèi)當(dāng)前僅有一個垃圾中轉(zhuǎn)站,本研究增加了邊緣垃圾中轉(zhuǎn)站的訪問路徑,根據(jù)免疫算法將園區(qū)內(nèi)中轉(zhuǎn)站設(shè)定為3個,可以在現(xiàn)有垃圾回收點不變的情況下,進一步優(yōu)化清運路徑及降低費用。

        猜你喜歡
        清運中轉(zhuǎn)站遺傳算法
        中亞是人類祖先關(guān)鍵“中轉(zhuǎn)站”?
        軍事文摘(2023年2期)2023-02-17 09:20:32
        基于“互聯(lián)網(wǎng)+”的生活垃圾清運智能管理新模式
        高性能半柔性地坪在生活垃圾中轉(zhuǎn)站的應(yīng)用
        上海建材(2021年1期)2021-11-22 08:01:38
        基于二次清運的回收車輛路徑研究*
        基于自適應(yīng)遺傳算法的CSAMT一維反演
        大機清篩路塹地段污土清理方法
        一種基于遺傳算法的聚類分析方法在DNA序列比較中的應(yīng)用
        基于遺傳算法和LS-SVM的財務(wù)危機預(yù)測
        基于改進的遺傳算法的模糊聚類算法
        寧化石壁:客家人的第一中轉(zhuǎn)站
        福建人(2015年11期)2015-02-27 10:23:59
        美腿丝袜在线一区二区| 一性一交一口添一摸视频| 国产成人精品久久综合| 2021久久精品国产99国产精品 | 精品熟女少妇av免费观看| 亚洲国产成人久久一区www妖精| 少妇无码av无码去区钱| 久久精品国产亚洲av高清蜜臀| 日本中文字幕官网亚洲| 亚洲中文字幕日韩综合| 国内精品久久久久久久97牛牛 | 亚洲综合欧美在线一区在线播放 | 亚洲国产av精品一区二| av一区二区三区在线| 日本阿v片在线播放免费| 久久久久久久岛国免费观看| 天天躁日日躁狠狠躁一区| baoyu网址国产最新| 中文字幕综合一区二区三区| 亚洲最大av网站在线观看| 亚洲啪啪综合av一区| 欧美黄色免费看| 视频二区 无码中出| 国产农村妇女毛片精品久久麻豆| 日本高清一道本一区二区| 亚洲av无码专区在线播放| 国产精品久久久久久人妻精品| 国产资源精品一区二区免费| 国产黄色污一区二区三区| 一区二区三区人妻av| 精品国产一区二区三区香蕉| 一本久道久久综合五月丁香| 日本高清一区在线你懂得| 麻豆视频在线播放观看| 天天碰免费上传视频| 日韩在线无| 国产AV高清精品久久| 国产白浆一区二区三区佳柔| 国产成人av在线免播放观看新| 少妇被爽到高潮动态图| 国产av一区二区三区区别|