全國(guó)大學(xué)生數(shù)學(xué)建模夏令營(yíng)A題垃圾分類(lèi)處理與清運(yùn)

1、垃圾分類(lèi)處理與清運(yùn)方案設(shè)計(jì)1.摘要隨著我國(guó)城市生活質(zhì)量要求的提高及垃圾處理事業(yè)的發(fā)展，垃圾轉(zhuǎn)運(yùn)系統(tǒng)的轉(zhuǎn)運(yùn)效率和投資效益在城市環(huán)衛(wèi)建設(shè)中起著越來(lái)越重要的作用。因此，轉(zhuǎn)運(yùn)系統(tǒng)的合理規(guī)劃及優(yōu)化設(shè)計(jì)，也隨之成為城市環(huán)衛(wèi)規(guī)劃中的一個(gè)重要課題。本文就a題給出的深圳市南山區(qū)垃圾分類(lèi)處理與清運(yùn)方案設(shè)計(jì)的問(wèn)題進(jìn)行研究，展開(kāi)討論，分析和建立數(shù)學(xué)模型，利用編程進(jìn)行求解。對(duì)于問(wèn)題一：從以下兩點(diǎn)進(jìn)行研究。一、垃圾中轉(zhuǎn)站的位置與數(shù)量已定，但廚余垃圾處理中心的位置與數(shù)量不確定。二、為了確定廚余垃圾處理中心的數(shù)量與位置，我們選用集合覆蓋模型求出待選處理中心位置后，再利用整數(shù)規(guī)劃建立整個(gè)垃圾清運(yùn)系統(tǒng)總費(fèi)用現(xiàn)值最小模型，確定最優(yōu)

2、組合。對(duì)于問(wèn)題二：在問(wèn)題一確定垃圾處理中心基礎(chǔ)上求解垃圾清運(yùn)路線問(wèn)題，類(lèi)似于物流線路優(yōu)化問(wèn)題。我們參考周期多車(chē)場(chǎng)車(chē)輛路徑問(wèn)題（periodic mulit-depot vehicle routing problem，periodic mdvrp），因?yàn)関rp問(wèn)題已被證明為np問(wèn)題，通過(guò)普通計(jì)算數(shù)據(jù)量大并很難求出有效解。本文運(yùn)用遺傳模擬退火算法進(jìn)行求解。并利用仿真實(shí)驗(yàn)證明該算法具較好的搜索性能與全局并行性。對(duì)于問(wèn)題三：在問(wèn)題一基礎(chǔ)上，增加一個(gè)更普通條件，即垃圾轉(zhuǎn)運(yùn)站和廚余垃圾處理中心的布局也顯不確定性。由于未知量太多，采用常規(guī)類(lèi)似物流中心選址方法模型進(jìn)行求解已顯得無(wú)能為力。本文采用選址-路徑三層

3、模型（lap），此模型的特點(diǎn)為中轉(zhuǎn)轉(zhuǎn)于處理中心的位置為未知量。并且在模型中選址與路徑看做整體對(duì)待。我們使用遺傳算法對(duì)此模型進(jìn)行求解，通過(guò)迭代計(jì)算便可以得到中轉(zhuǎn)站分布于最佳線路組合。我們通過(guò)實(shí)驗(yàn)仿真求解證明此模型是高效與可行的。關(guān)鍵詞：最優(yōu)組合 集合覆蓋 周期多車(chē)場(chǎng)車(chē)輛 遺傳模擬退火算法 2.問(wèn)題的重述1、 背景近年來(lái)垃圾包圍城市的問(wèn)題越來(lái)越突出，為了解決這一難題，中國(guó)許多大中城市投資興建垃圾填埋場(chǎng)和焚燒場(chǎng)，垃圾處理工藝越來(lái)越先進(jìn)有效，而原有發(fā)展多年的城市環(huán)衛(wèi)清掃體系也保證了垃圾的有效收集，但是中轉(zhuǎn)運(yùn)輸這一環(huán)的發(fā)展滯后卻逐漸成為立即處理系統(tǒng)的瓶頸，隨之產(chǎn)生原有收運(yùn)系統(tǒng)與其不配套的問(wèn)題，如垃圾處理

4、場(chǎng)遠(yuǎn)離市區(qū)；城市垃圾收運(yùn)車(chē)噸位又比較小，不適宜遠(yuǎn)途運(yùn)輸?shù)龋瑸榱私鉀Q這些問(wèn)題，垃圾分類(lèi)處理與清運(yùn)方案設(shè)計(jì)的問(wèn)題得到越來(lái)越多的人的關(guān)注。2.問(wèn)題 對(duì)于第一問(wèn)和第二問(wèn)，垃圾分為;廚余垃圾，可回收垃圾，有害垃圾和其他不可回收垃圾。所有垃圾將由收集汽車(chē)從小區(qū)的垃圾站運(yùn)往附近的垃圾轉(zhuǎn)運(yùn)站，在垃圾轉(zhuǎn)運(yùn)站進(jìn)行分類(lèi)后，由拖車(chē)將有害垃圾和不可回收垃圾運(yùn)往垃圾處理中心，將廚余垃圾運(yùn)往廚余垃圾處理中心，可回收垃圾就在垃圾轉(zhuǎn)運(yùn)站進(jìn)行分類(lèi)再利用，顯然，可回收垃圾和廚余垃圾能產(chǎn)生經(jīng)濟(jì)效益，而不可回收垃圾和有害垃圾不能產(chǎn)生經(jīng)濟(jì)效益。 其中相關(guān)已知條件如下表所示：廚余設(shè)備相關(guān)數(shù)據(jù)類(lèi)別處理能力投資額運(yùn)行成本產(chǎn)物價(jià)格大型廚余設(shè)備2

5、00噸/日4500萬(wàn)元150元/噸1000-1500元/噸小型廚余設(shè)備200-300公斤/日28萬(wàn)元200元/噸1000-1500元/噸四類(lèi)垃圾比例類(lèi)別廚余垃圾可回收垃圾有害垃圾其他不可回收垃圾比例4213可回收垃圾的相關(guān)數(shù)據(jù)類(lèi)別所占比類(lèi)回收價(jià)格紙類(lèi)55%1元/公斤塑料35%2.5元/公斤玻璃6%0.5元/公斤金屬4%2.5元/公斤拖車(chē)：只拖十噸的大型廂，只用于從轉(zhuǎn)運(yùn)站到垃圾中心，每次只拖一個(gè)大型廂，平均每公里耗油25l30l柴油/每公里。柴油單價(jià)：6.39元/升。收集車(chē)輛：只負(fù)責(zé)從小區(qū)的垃圾站到轉(zhuǎn)運(yùn)站運(yùn)輸，60輛2.5噸汽車(chē)，每車(chē)耗油20l35l 70#汽油/百公里。司機(jī)月薪平均3500元。

6、（1）假定現(xiàn)有垃圾轉(zhuǎn)運(yùn)站的規(guī)模與位置不變的條件下，即38個(gè)垃圾轉(zhuǎn)運(yùn)站位置確定接收垃圾能力一定。建立數(shù)學(xué)模型，確定大、小型廚余垃圾設(shè)備分布的最優(yōu)情況以及目前運(yùn)輸條件下的最優(yōu)清運(yùn)路線。（2）在問(wèn)題（1）中，假設(shè)垃圾轉(zhuǎn)運(yùn)站的規(guī)模與位置隨機(jī)，再次建立數(shù)學(xué)模型，確定大、小型廚余垃圾設(shè)備分布的最優(yōu)情況以及目前運(yùn)輸條件下的最優(yōu)清運(yùn)路線。符號(hào)說(shuō)明對(duì)于第一個(gè)問(wèn)題的模型符號(hào)說(shuō)明：，表示有nz座垃圾收集站組成的集合；ck表示篩選出的第k座垃圾中轉(zhuǎn)站的中轉(zhuǎn)能力；xi表示第z座垃圾收；a（k）表示篩選出的第k座垃圾中轉(zhuǎn)站所覆蓋的垃圾收集站的集合；b（i）表示可以覆蓋第z座垃圾收集站的中轉(zhuǎn)站的集合；wk表示是否啟用第k座

7、垃圾中轉(zhuǎn)站；uik表示第i座垃圾中轉(zhuǎn)站是否被第k座垃圾中轉(zhuǎn)站覆蓋；t 為規(guī)劃使用年限，建設(shè)期為t0年；r 為進(jìn)行現(xiàn)值轉(zhuǎn)換的貼現(xiàn)率；cik 為第i座收集站運(yùn)往第k座中轉(zhuǎn)站單位運(yùn)輸量單位距離的費(fèi)用 ；xik為第i座收集站運(yùn)往第k座中轉(zhuǎn)站的口運(yùn)輸垃圾量；lik 為第i座收集站運(yùn)往第k座中轉(zhuǎn)站運(yùn)輸距離(km)；dkj 為第k座中站運(yùn)往第j座處理場(chǎng)單位運(yùn)輸量單位距離的費(fèi)用；ykj 為第k座中轉(zhuǎn)站運(yùn)往第i座處理場(chǎng)口運(yùn)輸垃圾量；skj為第k座中轉(zhuǎn)站運(yùn)往第.j座處理場(chǎng)運(yùn)輸距離為；fk 為規(guī)劃期內(nèi)待建中轉(zhuǎn)站的固定投資；e 為中轉(zhuǎn)站的運(yùn)行成本；qmin為中轉(zhuǎn)站建設(shè)的最小控制規(guī)模；qmax 為中轉(zhuǎn)站建設(shè)的最大控制規(guī)

8、模。對(duì)于第二個(gè)問(wèn)題的模型符號(hào)說(shuō)明： 式為車(chē)次k所收集垃圾的總資源含量；為點(diǎn)i的垃圾資源含量d(f)為各車(chē)次總資源含量的方差，方差越大，說(shuō)明各車(chē)次資源含量具有明顯差別，資源歸類(lèi)更明確為道路網(wǎng)絡(luò)圖所有頂點(diǎn)的集合，n為收集點(diǎn)數(shù)，廚余垃圾處理中心標(biāo)記為0點(diǎn)，垃圾轉(zhuǎn)運(yùn)站標(biāo)記為，t為總車(chē)輛數(shù)。為0-1整型規(guī)劃變量，且=為i到j(luò)的距離，k為規(guī)劃車(chē)次序數(shù)，m為總車(chē)次數(shù)。點(diǎn)i要求的收集時(shí)間，點(diǎn)i開(kāi)始時(shí)間，為點(diǎn)i結(jié)束時(shí)間為提前到達(dá)收集點(diǎn)的懲罰因子為延遲收集完成收集作業(yè)的懲罰因子對(duì)于第三個(gè)問(wèn)題的模型符號(hào)說(shuō)明：hi|i =0,1.m是停車(chē)場(chǎng)和一系列收集點(diǎn)的集合;grlr=1,.r是一系列備選的中轉(zhuǎn)站;lp|p=1,.

9、p對(duì)是一系列備選的處理站;sgh指停車(chē)場(chǎng)，所有的備選中轉(zhuǎn)站和收集點(diǎn)的總和;fp表示在p處建立處理站的固定成本;fr表示在r處建立中轉(zhuǎn)站的固定成本;是從收集點(diǎn)i 到收集點(diǎn)j 的平均單位距離的運(yùn)輸成本;是從中轉(zhuǎn)站r到處理站p的平均單位距離的運(yùn)輸成本是中轉(zhuǎn)站r到處理站p的距離; 是收集點(diǎn)i到收集點(diǎn)j的距離;是收集點(diǎn)i到收集點(diǎn)r的距離;是收集點(diǎn)i到處理站p的距離為收集點(diǎn)1的垃圾量;為收集車(chē)輛容量;為運(yùn)輸車(chē)輛容量;為處理站p的處理容量。 = 模型假設(shè)對(duì)于第一個(gè)問(wèn)題的模型條件假設(shè)：（1）廚余垃圾中心的選址僅考慮經(jīng)濟(jì)效益，不受地域、環(huán)境、政治等條件的限制或影響；（2）假設(shè)所有運(yùn)輸車(chē)輛每天都能正常工作；（3）

10、每天產(chǎn)生的垃圾總量穩(wěn)定；（4）不考慮交通所帶來(lái)的影響（如：堵車(chē)等）；對(duì)于第二個(gè)問(wèn)題的模型條件假設(shè)為： （1）不考慮生活垃圾在經(jīng)過(guò)轉(zhuǎn)運(yùn)站之后的物質(zhì)流變化。 （2）居民每天所產(chǎn)生的垃圾都能運(yùn)往垃圾轉(zhuǎn)運(yùn)站 （3）假設(shè)所有中轉(zhuǎn)站將當(dāng)天的垃圾都能轉(zhuǎn)運(yùn)到垃圾處理中心。 （4）小型垃圾收集車(chē)行駛的速度恒定，不考慮實(shí)際道路交通狀況。對(duì)于第三個(gè)問(wèn)題的模型假設(shè)條件為：（1）設(shè)施的層次為三層，收集點(diǎn)、中轉(zhuǎn)站和處理站，最后選定的處理站數(shù)量是確定的，只選其中一個(gè)，中轉(zhuǎn)站個(gè)數(shù)不確定; (2)廢棄物只能先運(yùn)到中轉(zhuǎn)站，然后由中轉(zhuǎn)站運(yùn)送到處理站，不能直接運(yùn)送到處理站; (3)中轉(zhuǎn)站和處理站一旦選定建成，使用年限為10年，每年按

11、360天算; (4)停車(chē)場(chǎng)的位置是給定的，收集車(chē)從停車(chē)場(chǎng)出發(fā)，到達(dá)中轉(zhuǎn)站清空垃圾后返回停車(chē)場(chǎng)。且停車(chē)場(chǎng)有同種型號(hào)的收集車(chē)輛若干，且載重量一定; (5)運(yùn)輸車(chē)輛從中轉(zhuǎn)站出發(fā)，到達(dá)處理站后路返回中轉(zhuǎn)站。且有同種型號(hào)的運(yùn)輸車(chē)輛若干，且載重量一定;(6)每個(gè)收集點(diǎn)的垃圾產(chǎn)生量是確定的，都小于收集車(chē)輛的裝載量。且在一定時(shí)期內(nèi)垃圾量不變;(7)每輛收集車(chē)為一個(gè)以上的收集點(diǎn)服務(wù);且每輛車(chē)只負(fù)責(zé)一次收集活動(dòng); (8)單位距離的廢棄物的運(yùn)費(fèi)是已知的。這個(gè)費(fèi)用主要包括垃圾車(chē)成本費(fèi)用和人工費(fèi)用。垃圾車(chē)成本費(fèi)用包括最初投資成本的折舊加上其運(yùn)行和維護(hù)成本。且此費(fèi)用在一定時(shí)期內(nèi)不變;(9)各收集點(diǎn)、停車(chē)場(chǎng)、備選中轉(zhuǎn)站和處

12、理站的位置是已知的且服從三角不等，以及費(fèi)用矩陣是對(duì)稱(chēng)的;(10)考慮到進(jìn)行本文所做研究時(shí)尚處于選址規(guī)劃階段，不考慮各設(shè)施(中轉(zhuǎn)站和處理站)的容量約束限制，在進(jìn)行計(jì)算的時(shí)候?yàn)榱朔奖?，處理站的容量取一個(gè)極大值150萬(wàn)噸;中轉(zhuǎn)站的處理容量取20噸/天;(11)道路狀況確定.，不考慮路段擁擠、堵塞或車(chē)輛本身故障情況。問(wèn)題分析這是一個(gè)優(yōu)化問(wèn)題，要解決大、小廚余設(shè)備的最佳分布設(shè)計(jì)和在一定運(yùn)輸條件下的最佳運(yùn)輸路線的規(guī)劃，即所謂的最優(yōu)化組合，要達(dá)到目標(biāo)，一般來(lái)說(shuō)有如下幾個(gè)目標(biāo)是矛盾的，建立廚余垃圾處理中心越多，投入的成本越大，每天的運(yùn)行成本也就隨之增加，而且每天用戶(hù)產(chǎn)生的垃圾一定，過(guò)多的處理中心會(huì)造成資源的浪

13、費(fèi)；但少建立廚余垃圾中轉(zhuǎn)站會(huì)增大拖車(chē)的運(yùn)輸距離，每天投入的運(yùn)輸費(fèi)用便會(huì)增多。所以需要更多的約束條件使這些目標(biāo)同時(shí)達(dá)到最優(yōu)的即所謂的最優(yōu)決策，我們追求的只能是，在用戶(hù)產(chǎn)生垃圾量一定的情況下，保證在盡量減少運(yùn)輸成本的條件下，少建立廚余垃圾處理場(chǎng)，產(chǎn)生最大的經(jīng)濟(jì)效益，即在這樣的思想下，找出最優(yōu)組合規(guī)劃。建立優(yōu)化問(wèn)題的模型最主要的是用數(shù)學(xué)符號(hào)和式子表述決策變量、構(gòu)造目標(biāo)函數(shù)和確定約束條件。對(duì)于本體來(lái)講，建立目標(biāo)函數(shù)，在能處理運(yùn)輸路線和廚余垃圾中心個(gè)數(shù)上，找尋一個(gè)權(quán)衡兩者的最優(yōu)組合。5、模型建立5.1問(wèn)題一、二、三中垃圾費(fèi)用產(chǎn)生關(guān)系如下圖：垃 圾 收 運(yùn) 總 費(fèi)用垃 圾 站 費(fèi) 用人 工 費(fèi) 用運(yùn) 輸

14、費(fèi) 用廚建余設(shè)垃費(fèi)圾用站垃成圾本站運(yùn)行工人月薪運(yùn)輸車(chē)油費(fèi)5.2問(wèn)題二、三、清運(yùn)垃圾車(chē)線路示意圖：5.3南山區(qū)垃圾轉(zhuǎn)運(yùn)站分布圖：5.5南山區(qū)垃圾處理中心運(yùn)行數(shù)據(jù) 參 數(shù)（單 位） 數(shù) 值垃圾轉(zhuǎn)運(yùn)站站數(shù)m（座） 38大型廚余垃圾處理中心運(yùn)行成本e（元/噸） 150小型垃圾廚余處理中心運(yùn)行成本f（元/噸） 200大型垃圾廚余處理中心處理能力q（噸/日） 200小型垃圾廚余處理中心處理能力l（公斤/日） 200-300 大型垃圾廚余處理中心建設(shè)成本h（萬(wàn)元/座） 4500小型垃圾廚余處理中心建設(shè)成本h（萬(wàn)元/座） 285.4：南山區(qū)垃圾轉(zhuǎn)運(yùn)站坐標(biāo)： 建立以垃圾焚燒廠為原點(diǎn)建立直角坐標(biāo)系垃圾焚燒廠（1.

15、00，0.00） a（8.57，1.67） b（14.26，16.54）c（17.52，20.45） d（18.84，19.45） e（22.46，18.92）f（19.87，22.46） g（18.76，24.46） h（19.37，30.22）i（15.64，32.2.） j（15.16，32.81） k（21.33，42.73）l（23.97，66.97） m（29.16，75.09） n（36.62，76.99）o（30.67，71.57） p（34.24，33.60） q（40.98，56.17）r（40.40，52.44） s（36.75，51.83） t（34.98，45.43）

16、u（41.86，41.12） v（28.31，38.21） w（33.42，38.36）x（26.01，32.68） y（36.94，29.69） z（44.00，31.33）a（29.87，26.33） b（42.70，24.58） c（32.07，20.29）d（24.84，2.67） e（25.11，0.44） f（47.52，40.08）g（46.75，68.47） h（56.46,56.67） i（57.12，55.48）j（63.47，57.57） k（56.33，28.50） l（17.97，27.81）55深圳南山區(qū)垃圾轉(zhuǎn)運(yùn)站轉(zhuǎn)運(yùn)量等情況統(tǒng)計(jì)表：序號(hào)垃圾轉(zhuǎn)運(yùn)站名稱(chēng)位置運(yùn)營(yíng)單位廂

17、數(shù)垃圾轉(zhuǎn)運(yùn) 量(噸/日)1九街站深南大道南頭中學(xué)旁德盈利公司1202玉泉站玉泉路寶龍路口德盈利公司2253動(dòng)物園站西麗湖路旁德盈利公司2204平山村站南山區(qū)平山村內(nèi)德盈利公司1255牛城村站南山區(qū)牛成村內(nèi)環(huán)衛(wèi)總站156科技園站科苑南路與濱海大道交匯處西側(cè)環(huán)衛(wèi)總站2207同樂(lè)村站同樂(lè)村內(nèi)環(huán)衛(wèi)總站258松坪山（二）站高新北區(qū)朗山一路綠地內(nèi)環(huán)衛(wèi)總站2109大新小學(xué)站南頭街大新小學(xué)旁環(huán)衛(wèi)總站13010南山村站東濱路與前海路交匯處環(huán)衛(wèi)總站22511陽(yáng)光(白芒關(guān)外)站南山區(qū)白芒關(guān)外德盈利公司11012月亮灣大道站西部綠化長(zhǎng)廊北端環(huán)衛(wèi)總站44013光前站龍珠三路光前村旁環(huán)衛(wèi)總站12014北頭站前海路北頭村旁

18、德盈利公司11515涌下村站桃園路涌下村內(nèi)德盈利公司12016白石洲南站白石洲路與石洲中路交叉東南角環(huán)衛(wèi)總站13017前海公園站南山區(qū)前海公園內(nèi)環(huán)衛(wèi)總站11618深圳大學(xué)站校園內(nèi)環(huán)衛(wèi)總站21519官龍村站南山區(qū)官龍村內(nèi)環(huán)衛(wèi)總站11520松坪山站南山區(qū)松坪山第五工業(yè)區(qū)內(nèi)環(huán)衛(wèi)總站22521南光站南山區(qū)南光村內(nèi)環(huán)衛(wèi)總站11522南園站南山區(qū)南園村內(nèi)環(huán)衛(wèi)總站11523望海路站望海路避風(fēng)塘對(duì)面蛇口市政13024花果路站花果路蛇口小學(xué)旁蛇口市政23025福光站南山區(qū)福光村內(nèi)環(huán)衛(wèi)總站11026新圍村站沙河西路新圍村旁環(huán)衛(wèi)總站12027大沖站深南大道大沖村旁環(huán)衛(wèi)總站23528沙河市場(chǎng)站南山區(qū)沙河市場(chǎng)旁環(huán)衛(wèi)總站

19、13029龍井龍珠五路龍井村旁環(huán)衛(wèi)總站11530南山市場(chǎng)南新路南山市場(chǎng)旁環(huán)衛(wèi)總站12531麻勘站南山區(qū)麻勘村內(nèi)環(huán)衛(wèi)總站11032白芒站南山區(qū)白芒村內(nèi)環(huán)衛(wèi)總站1833大石磡站南山區(qū)大磡村內(nèi)環(huán)衛(wèi)總站23034長(zhǎng)源村站南山區(qū)長(zhǎng)源村內(nèi)環(huán)衛(wèi)總站1535華僑城站僑城東路西側(cè)華僑城清潔27036疏港小區(qū)站興海大道旁陽(yáng)光三環(huán)34037西麗路站西麗監(jiān)督隊(duì)樓下環(huán)衛(wèi)總站11538塘朗站塘朗工業(yè)區(qū)內(nèi)環(huán)衛(wèi)總站210合計(jì)638045.4問(wèn)題一模型建立： 對(duì)于問(wèn)題1的模型建立，討論如何確定余垃圾處理中心的數(shù)量和位置，已使得垃圾清運(yùn)成本最低。根據(jù)前面模型家屬，首先討論如何確定垃圾廚余中心的數(shù)量和位置，可以利用集合覆蓋模型初步

20、確定一系列廚余垃圾處理中心的待選地址。利用集合覆蓋模型已確定垃圾處理中心的待選點(diǎn)后，運(yùn)用整數(shù)規(guī)劃建立整個(gè)垃圾清運(yùn)系統(tǒng)總費(fèi)用現(xiàn)值最小模型，進(jìn)行總體優(yōu)化，從垃圾處理中心待選點(diǎn)中優(yōu)選出處理中心位置的最優(yōu)組合，確定最優(yōu)組合中每座垃圾處理中心接納的垃圾量。在垃圾轉(zhuǎn)運(yùn)站和處理中心的位置和數(shù)量已確定的情況下，整個(gè)垃圾清運(yùn)過(guò)程中所發(fā)生的費(fèi)用主要取決于規(guī)劃期內(nèi)垃圾從轉(zhuǎn)運(yùn)站到處理中心的運(yùn)輸費(fèi)用，垃圾處理中心的固定投資費(fèi)用，垃圾處理中心的運(yùn)行費(fèi)用。上述3種費(fèi)用都與處理中心位置、規(guī)模密切相關(guān)。約束方程： 目標(biāo)函數(shù)為從現(xiàn)有m座垃圾收集站的位置中優(yōu)選出可以覆蓋m座垃圾轉(zhuǎn)運(yùn)站的最小數(shù)目的廚余垃圾垃圾處理中心;約束式1表示每

21、一座垃圾轉(zhuǎn)運(yùn)站的垃圾均被清運(yùn);約束式2是滿足廚余垃圾垃圾處理中心處理能力的要求;約束式3表示垃圾轉(zhuǎn)運(yùn)站和廚余垃圾垃圾處理中心的垃圾量非負(fù);約束式4是垃圾轉(zhuǎn)運(yùn)站是否位十第k座廚余垃圾處理中心附近的決策變量;約束式5是第i座垃圾轉(zhuǎn)運(yùn)站是否有垃圾清運(yùn)到第k座垃圾處理中心的決策變量。 費(fèi)用現(xiàn)值最小模型:約束方程：uikwk (i=1,2,.m,k=1,2,.p)問(wèn)題二模型建立：對(duì)于問(wèn)題2的模型建立，在問(wèn)題1的基礎(chǔ)上，垃圾處理中心的數(shù)量和位置已經(jīng)確定，討論如何設(shè)計(jì)垃圾清運(yùn)車(chē)的清運(yùn)路線，使得垃圾清運(yùn)的成本最小。垃圾清運(yùn)成本包括收集線路產(chǎn)生費(fèi)用和轉(zhuǎn)運(yùn)線路產(chǎn)生費(fèi)用，更具本文深圳市南山區(qū)所給的實(shí)際數(shù)據(jù)，無(wú)法得知

22、小區(qū)垃圾收集點(diǎn)的信息，故對(duì)垃圾清運(yùn)成本之考慮從垃圾中轉(zhuǎn)站到垃圾處理中心線路中所產(chǎn)生的費(fèi)用。 那么，目標(biāo)函數(shù)為以運(yùn)輸成本、垃圾清運(yùn)時(shí)間和資源化利用為計(jì)算單項(xiàng)。如下: 其中： 為運(yùn)輸成本分量垃圾轉(zhuǎn)運(yùn)約束分量為堆策略分量，保證各車(chē)次總垃圾資源含量具有明顯差別 式為車(chē)次k所轉(zhuǎn)運(yùn)垃圾的總資源含量，為點(diǎn)i的垃圾資源含量，d(f)為各車(chē)次總資源含量的方差，方差越大，說(shuō)明各車(chē)次資源含量具有明顯差別，資源歸類(lèi)更明確為道路網(wǎng)絡(luò)圖所有頂點(diǎn)的集合，n為中占站數(shù)，為了方便，廚余垃圾處理中心標(biāo)記為0點(diǎn)，垃圾轉(zhuǎn)運(yùn)站標(biāo)記為，t為總車(chē)輛數(shù)。為0-1整型規(guī)劃變量，且=為i到j(luò)的距離，k為規(guī)劃車(chē)次序數(shù)，m為總車(chē)次數(shù)。點(diǎn)i要求的轉(zhuǎn)運(yùn)

23、時(shí)間，點(diǎn)i開(kāi)始時(shí)間，為點(diǎn)i結(jié)束時(shí)間為提前到達(dá)轉(zhuǎn)運(yùn)點(diǎn)的懲罰因子為延遲收集完成轉(zhuǎn)運(yùn)作業(yè)的懲罰因子4.2.23約束條件 （1） （2） （3） （4） （5） （6） 式(1)限定了所有垃圾轉(zhuǎn)運(yùn)點(diǎn)必須目只能訪問(wèn)一次; 式(2)限定了每車(chē)次中訪問(wèn)垃圾轉(zhuǎn)運(yùn)點(diǎn)的重量和體積總和必須低于垃圾運(yùn)輸車(chē)的載重量限制; 式(3)限定每一車(chē)次的路線必須從點(diǎn)0(中轉(zhuǎn)站)出發(fā); 式(4)限定每一次車(chē)必須返回點(diǎn)0(中轉(zhuǎn)站); 式(5)限制每車(chē)次中若進(jìn)入一個(gè)垃圾轉(zhuǎn)運(yùn)點(diǎn)則必須從該點(diǎn)出來(lái); 式(6)限制堆任意車(chē)次k最多通過(guò)一次垃圾處理中心，從而保證每輛車(chē)都可經(jīng)過(guò)垃圾處理中心。問(wèn)題三模型的建立： （3-1） （3-2）滿足的約束條件

24、為： （3-3） （3-4） （3-5） （3-6） （3-7） （3-8） （3-9） （3-10） （3-11） （3-12） （3-13）目標(biāo)函數(shù)(3-1)式為規(guī)劃使用年限內(nèi)費(fèi)用現(xiàn)值最小模型，涵蓋了收運(yùn)系統(tǒng)中收集、中轉(zhuǎn)和運(yùn)輸3個(gè)階段中所發(fā)生的四部分費(fèi)用，通過(guò)貼現(xiàn)率r進(jìn)行現(xiàn)值轉(zhuǎn)換，將其有機(jī)的結(jié)合在一起(每年以360天計(jì))。其中第一項(xiàng)和第三項(xiàng)是處理站和中轉(zhuǎn)站的固定成本，第二項(xiàng)是運(yùn)輸車(chē)輛的運(yùn)行成本，等于中轉(zhuǎn)站和處理站之間的距離與往返次數(shù)以及單位距離運(yùn)費(fèi)的乘積，第四項(xiàng)是收集車(chē)輛的運(yùn)行成本。其中一t為使用年限，r為進(jìn)行現(xiàn)值轉(zhuǎn)換的貼現(xiàn)率(本文中取10%)。目標(biāo)函數(shù)(3-2)最小化所建立的設(shè)施所產(chǎn)生的

25、負(fù)效用。表示處理站所產(chǎn)生的負(fù)效用與其規(guī)模成正比，與離居民區(qū)的距離成反比。為參數(shù)，反映了相應(yīng)系數(shù)對(duì)效用的影響程約束條件(3-3 )確保每個(gè)收集點(diǎn)僅由一輛垃圾收集車(chē)進(jìn)行收集。約束條件(3-4 )為垃圾收集車(chē)容量的約束條件，滿足在路徑上行駛的每輛都不超過(guò)其容量。約束條件( 3-5 )是一系列路徑連續(xù)約束，他是指某點(diǎn)的垃圾收集由同一輛車(chē)運(yùn)出。約束條件(3-6 )保證每個(gè)收集車(chē)輛的路徑最多駛向一個(gè)中轉(zhuǎn)站。約束條件(3-7 )保證任何兩個(gè)到達(dá)中轉(zhuǎn)站的車(chē)輛不會(huì)在同一個(gè)收集路徑上。 約束條件(3-8 ) , ( 3-9 )保證每個(gè)中轉(zhuǎn)站只要選定就有收集車(chē)輛到達(dá)。 約束條件(3-10 )保證只選取一個(gè)處理站。最

26、后三個(gè)約束條件(3-11)、(3-12 )和(3-13 )保證滿足整數(shù)約束。模型的求解第一個(gè)問(wèn)題的解法： 目標(biāo)函數(shù)為從現(xiàn)有m座垃圾收集站的位置中優(yōu)選出可以覆蓋m座垃圾收集站的最小數(shù)目的中轉(zhuǎn)站選點(diǎn);約束式1表示每一座垃圾收集站的垃圾均被清運(yùn);約束式2是滿足垃圾中轉(zhuǎn)站中轉(zhuǎn)能力的要求;約束式3表示垃圾站和中轉(zhuǎn)站的垃圾量非負(fù);約束式4是垃圾收集站是否位十第k座垃圾中轉(zhuǎn)站附近的決策變量;約束式5是第i座垃圾收集站是否有垃圾收運(yùn)到第k座中轉(zhuǎn)站的決策變量。對(duì)中轉(zhuǎn)站待選點(diǎn)進(jìn)行確定，運(yùn)用啟發(fā)式算法進(jìn)行集合覆蓋模型優(yōu)化步驟如下: 第一步，確定128座垃圾收集站的相對(duì)位置和距離; 第二步，根據(jù)垃圾收集最優(yōu)半徑450

27、m，找出每一個(gè)可以作為中轉(zhuǎn)站的收集點(diǎn)以提供垃圾收集服務(wù)的服務(wù)范圍內(nèi)的收集點(diǎn)集合a(k), k=1,2,.,m,即距離該收集點(diǎn)距離小十或等十垃圾最優(yōu)收集半徑的所有收集點(diǎn)的集合。 第三步，找到可以給每一個(gè)收集點(diǎn)提供垃圾收集服務(wù)的可做為中轉(zhuǎn)站的收集點(diǎn)的集合bpi) , i =1,2,.,m，一般來(lái)說(shuō)，a(k)和b(i)這兩個(gè)集合是一致的，但是考慮到其他的一些限制條件，就可能出現(xiàn)差異。 第四步，在b（i）中，將其中的子集省去，以簡(jiǎn)化問(wèn)題。例如:若b(1) = (1,2,3,4) ,b（2) =（1,2,3) , b（3) =（1,2,3,4,5)，則b(1)和 b(2)是b(3)的一個(gè)子集，可以省去以

28、簡(jiǎn)化問(wèn)題。 第五步，確定合適的組合解。在問(wèn)題被簡(jiǎn)化后，在有限的侯選點(diǎn)上選擇一個(gè)組合解是可行的。為滿足模型目標(biāo)即以最小數(shù)量的設(shè)施點(diǎn)覆蓋所有的需求點(diǎn)，應(yīng)盡可能少地確定待選點(diǎn)，從組合解中剔除可以被合并的待選點(diǎn)。針對(duì)該城區(qū)社會(huì)、經(jīng)濟(jì)、交通等的實(shí)際狀況，確定費(fèi)用現(xiàn)值最小模型各參數(shù)取值。對(duì)十待建垃圾中轉(zhuǎn)站的固定投資fk，根據(jù)其實(shí)際接納的垃圾量，結(jié)合實(shí)際工程經(jīng)驗(yàn)假定為分段常數(shù)函數(shù)進(jìn)行估算;垃圾收集站、中轉(zhuǎn)站和處理場(chǎng)之間的距離和引用物流理論中的折線距離，即： 代入費(fèi)用，得 大型廚余垃圾處理中心p（座） 3小型廚余垃圾處理中心n（座） 1 名稱(chēng) 坐標(biāo)大型垃圾廚余處理中心a （28.76,27.64）大型垃圾廚余

29、處理中心b （49.16,42.93）大型垃圾廚余處理中心c （39.69,57.53）小型垃圾廚余處理中心d （3.61,10.52）第二個(gè)問(wèn)題的解法： (2)遺傳模擬退火算法實(shí)現(xiàn)a算法步驟 1確定初始種群，確定初始溫度； 2若達(dá)到退火結(jié)束溫度，結(jié)束算法;若沒(méi)有，對(duì)每個(gè)染色體進(jìn)行變異以模擬退火概率決定是否接受； 3對(duì)染色體進(jìn)行交配，以一定規(guī)則用子代替換父代； 4以一定概率，對(duì)染色體進(jìn)行變異，降低溫度，轉(zhuǎn)到2。遺傳模擬退火算法流程圖利用編程求解計(jì)算出16輛垃圾轉(zhuǎn)運(yùn)車(chē)，清運(yùn)垃圾至處理中心的最佳線路，結(jié)果如下表：車(chē)輛序號(hào)清運(yùn)路線垃圾量（t）11-s1-2-s1-24-s2-1-s1-26-s250

30、27-5-s2-10-30-s1-34-37-s3-36-s340319-18-s3-19-s2-11-s2-27-s4-23-s250426-s3-2-s1-2-29-s3-29-s3-23-s25058-s2-6-s3-18-s3-31-s4-35-s45066-s3-3-s1-14-s2-32-s4-38-s348717-s2-16-s1-3-s1-9-s2-17-s246833-s4-35-s4-36-s3-37-s4-29-s350935-s4-12-s1-14-27-s4-25-s3-10-s1501035-s4-36-s3-33-s4-10-s1-4-20-s2501121-s2

31、-35-s4-33-s4-21-22-s3401235-s4-12-s1-15-s2-16-s1-28-s3-22-s3601316-s1-15-s2-9-s2-4-s1-27-s4-35-s460149-s2-4-s1-24-s2-20-s2-27-s4-36-s3601528-s3-24-s2-11-s2-12-s1-23-s2-30-s1601628-s3-36-s3-20-s2-35-s4-12-s150總和804第三個(gè)問(wèn)題的求解：遺傳算法計(jì)算流程：確定實(shí)際問(wèn)題參數(shù)集對(duì)參數(shù)進(jìn)行編碼初始化種群適應(yīng)度函數(shù)的計(jì)算1.計(jì)算目標(biāo)函數(shù)2.函數(shù)值 適應(yīng)值3.適應(yīng)值的調(diào)整評(píng)價(jià)群體群體p（t+1）群體p

32、（t）滿足停止規(guī)則結(jié)果3個(gè)基本操作算子1.選擇2.交叉3.變異遺傳操作 從上圖可以看出，遺傳算法的運(yùn)行為一個(gè)典型的迭代過(guò)程，其必須完成的工作內(nèi)容和基本步驟如下: (1)選擇編碼策略，將解空間中的解數(shù)據(jù)表示成遺傳空間的基因型串結(jié)構(gòu)數(shù)據(jù)，這些結(jié)構(gòu)數(shù)據(jù)的不同組合便構(gòu)成了不同的編碼; (2)定義適應(yīng)度函數(shù)f (x) (3)確定遺傳策略，包括選擇群體大小m，選擇、交叉、變異方法，以及角定交叉概率pc、變異概率pm等遺傳參數(shù); m為群體大小，即群體中所含個(gè)體的數(shù)量，一般取100500; t為遺傳算法的終止進(jìn)化代數(shù)，一般取為100500; pc為交叉概率，一般取為0.40.99; pm為變異概率，一般取為0

33、.0001 0.1。 (4)隨機(jī)初始化生成群體p;(5)計(jì)算群體中個(gè)體位串解碼后的適應(yīng)值f (x) ;(6)按照遺傳策略，運(yùn)用選擇、交叉和變異算子作用于群體，形成下一代群(7)判斷群體性能是否滿足某一指標(biāo)，或者己完成預(yù)定迭代次數(shù)，不滿足則返回步驟(6)，或者修改遺傳策略再返回步驟(6).。 算法中涉及到的參數(shù)有種群規(guī)模、交叉概率、變異概率、進(jìn)化代數(shù)或進(jìn)化時(shí)間。綜合考慮遺傳算法求解過(guò)程中求解的效率與計(jì)算效率之間的關(guān)系，本文設(shè)定種群規(guī)模為100;交叉概率為0.8;變異概率為0.07;進(jìn)化代數(shù)設(shè)置為500代。經(jīng)由上述遺傳算法用c+開(kāi)發(fā)語(yǔ)言在microsoft visual studio 2008運(yùn)行

34、環(huán)境中編程求解，運(yùn)行程序得到結(jié)果如圖下圖所示。模型評(píng)價(jià)問(wèn)題一模型；優(yōu)點(diǎn)：通過(guò)兩個(gè)互補(bǔ)模型的連立復(fù)合，使得垃圾處理中心數(shù)量、位置，于經(jīng)濟(jì)因素相互聯(lián)系，相互制約。從而得到較為一般的單獨(dú)模型更理想的優(yōu)化組合。缺點(diǎn)：模型在選取待選中心時(shí)，是離散選取而非連續(xù)選取。致使最終組合解可能存在不穩(wěn)定因素，忽略一部分優(yōu)化點(diǎn)。復(fù)合模型計(jì)算較單一模型計(jì)算更大。問(wèn)題二模型；優(yōu)點(diǎn)：模型運(yùn)用物流運(yùn)輸線路優(yōu)化模型，并利用遺傳退火算法求解，可以兼顧到遺傳算法的并行遍利和退火算法的高效搜索。并避開(kāi)np問(wèn)題，使得求解速度較快。缺點(diǎn)：由于遺傳退火算法需要一些特定的初值。所以初值的選取好壞對(duì)最終結(jié)果有一定影響。問(wèn)題三模型；優(yōu)點(diǎn)：選址路

35、徑模型把選址問(wèn)題與路徑問(wèn)題當(dāng)作整體對(duì)待。從而允許中轉(zhuǎn)站和處理中心為未知變量，符合題目的要求。缺點(diǎn)：模型利用遺傳退火算法進(jìn)行求解，算法時(shí)間復(fù)雜度較大。附錄一:lrp遺傳算法程序部分代碼1.主程序namespace逆向物流lrp模型public partial class逆向物流lrp模型:formpublic逆向物流lrp模型0initializecomponent();gs=new settings()settings:collectandcollect=new list();=0, portl=cpl”，port2=tp 1”); ost=()，name=cpl”); /settings.d

36、ealandtrans=new list(); /settings.dealandtrans.add(new relation()cost=0, distence=0,fortl=tp 1”，port2=dpl”);/settings.transports=new list();name=tp 1”/settings.transports.add(new port()capability=0, cost=0,);private group creategroup() var basicelements=settings.collectports.select(cp=element(cp:nam

37、e, cp).tolist();new var group=new group(); group.aberranceprobability=numericupdownaberrance. value; group.aimfunction=new daimfuilction(aimfunction); group.basicelement=basicelements; group.besttype=besttype.minvalue; eventhandler(groupee evolved); return group; private void group_ evolved(object s

38、ender, heredityeventargs e) best=e.bestelement; changeprocessbar(e.evolveera.tostring(); /showbest(e.evolveera.tostring();private delegate void dchangeprocessbar(string era);private void changeprocessbar(string era)private double distence(decimal distence, int year) var a1lports(collectport)a.someth

39、ing).tolistq;element.select(alist a1lcars;var check=false;foreach (var car in allcars)var portsonecar=a1lports. where(a=a.carno=car.no).tolist(); car.distence+=settings.parkadncollect.single(a=a.port2一portsonecar0.name).distence;collectport last=null;foreach (var cp in portsonecar)if (last!=null) va

40、r cc=settings.collectandcollect.singleordefault(a=(a.portl一cp.name&a.port2一last.name) (a.port2= cp.name&a.portl= last.name);if (cc一null)return decimal.maxvalue/4;car.distence+=cc.distence;last=cp; car.transportvar tpuse=allcars:select(a=a.transport).tolist();var valuetp=(double)tpuse.sum(a= a.cost);

41、/中轉(zhuǎn)站容量foreach (var tp in tpuse)刀容量var capabilityneed=allcars.where(a= a.transport.name一tp.name).sum(a二a. weight);if (capabilityneedtp.capability) return decimal:maxvalue/4;/確定處理廠var min=double:maxvalue; port dealport =null; foreach (var d in settings.dealports) var valueadd=settings.dealandtrans.whe

42、re(a= a.port2=d:nametpuse.exists(b= b.name一a.porfl).sum(a=distence(math.ceiling(a1lcars.where(b=b.transport.name一a.port1).sum(b=b. weight)/5)*a.distence, 1); if (valueadd(double)decimal.maxvalue/4)?decimal.maxvalue/4:(decimal)total;private port choosetransport(collectport collectport, lista1lports)v

43、ar min=decimal.maxvalue;port port=null;foreach (var tp in settings.transports) /距離 var value=settings.collectandtrans:single(a= a.portl一collectport.name&a.port2一tp.name).distence;if (valuea.use).tolist(); /collectport.transport(port)settings.transportsrandom.next(settings.transports.count).clone();

44、settings.collectandcollectrandom.next(settings.collectandcollect.count); private void打開(kāi)配置toolstripmenuitem click(object sender,eventargs e) using (var ofd=new openfiledialog()if (ofd.showdialog()= dialogresult.ok)trysettings=settings.load(ofd.filename); readsettings(); catch (exception ex) messagebo

45、x.show(this, ex:message,”提示”messageboxbuttons.ok, messageboxicon.information); private group group;private exception exception;private void開(kāi)始toolstripmenuitem_click(object sender, eventargs e)carcount=(int)(settings.collectports.sum(a= a.capability)/settings. carcapability)+1;best=null;開(kāi)始toolstripme

46、nuitem.enabled = false;toolstripprogressbar.value=0;toolstripprogressbar.maximum=(int)numericupdownera.value;toolstripprogressbar.visible=true;listviewstation.items.clear();group=creategroup();exception=null;backgroundworker.runworkerasync();l/try/ best=group.calculate();/llcatch (exception ex)/this

47、.exception=ex;!if (exception!=null)/ messagebox.show(exception.tostring(),”錯(cuò)誤”);/開(kāi)始toolstripmenuitem.enabled二true;/toolstripprogressbar.visible=false;/showbest(，最終結(jié)果”);private int carcount;private list best; new+1).tostring(),index十十;listviewstation.items.insert(index,newlistviewitem(newstring ”目標(biāo)值，, value.tostring(), )toolstripstatuslabelvalue.text=value.tostring();/gc.collect();this.refresh); private voiddoworke