1、城市生活垃圾管理系統研究摘要本文對城市垃圾管理系統進行了研究，并對其中城市垃圾年產量的預測及垃圾收運車的路線選擇進行了著重分析。首先，對城市垃圾的年產量進行預測。分析搜集數據得出垃圾的年產量與許多因素有相關關系，且它自身并沒有隨時間變化的明顯趨勢。對各因素進行灰色關聯度分析，得到影響垃圾年產量的主要的因素為：人口、住宅使用面積、消費水平、可支配收入。并用回歸分析的方法求出了垃圾的年產量與各主要因素之間的函數關系（以北京市為例）：由于主要因素的變化規律明確，用GM(1,1)模型對各主要因素進行預測，結果見附表1。然后將各因素的預測值代入回歸方程，得到2008年垃圾年產量的預測值為680萬噸。對比

2、趨勢預測（692.7萬噸）及2008年的真實值（672萬噸）進行檢驗，得到模型準確性好，實用性強的結論。其次，設計垃圾收運車的運行路線，使整個收運過程路程最短，并在此基礎上讓每輛車的收運時間均勻。分析問題，將其轉化為一輛無限大容量的車遍歷所有收集點的最短路徑問題（TSP），運用現代優化算法中的遺傳算法進行求解，見表11。再讓垃圾收運車沿求出的路線收集垃圾，當垃圾量等于或略小于200后前往中轉站（為一條線路），卸載完垃圾后再前往下一個收集點，如此往復進行。進而可以計算出每輛車所需時間為：結果經過的線路段路線花費總時間第一輛車線路5、線路6、線路7、線路106.998小時第二輛車線路4、線路8、線

3、路9、線路117.106小時第三輛車線路1、線路2、線路36.103小時由于遺傳算法的種群選擇比較大（為200）所以結果具有很強的穩定性，并且算法是全局尋優的，具有實用性。路線的安排中，車載重量為都未達到200，留有一定得穩定裕量，使模型有較強的魯棒性。關鍵詞： 灰色關聯度；多元線性回歸；GM(1,1)；遺傳算法；TSP問題；一、問題重述隨著人類生產和生活的不斷發展，由此而產生的垃圾對生態環境及人類生存帶來極大的威脅，成為重要的社會問題。一般認為，城市生活垃圾的影響因素包括地理位置、人口、經濟發展水平（生產總值）、居民收入以及消費水平、居民家庭能源結構等等。城市生活垃圾產量是垃圾管理系統的關鍵

4、參數，因此對未來某段時間內垃圾產量的準確預測，是相關垃圾管理部門做出管理規劃的前提。另外，城市垃圾自其產生到最終被送到處置場處理，需要環衛部門對其進行收集與運輸，這一過程稱為城市垃圾的收運。收運過程可簡述如下：每天垃圾車從車庫出發，經過收集點收集垃圾，當垃圾負載達到最大裝載量時，垃圾車運往中轉站，在中轉站卸下所有收運的垃圾，然后再出站收集垃圾，如此反復，直到所有收集點的垃圾都被收集完，垃圾車返回車庫。（以上收運過程均在各點的工作區間之內完成。）請利用數學方法建立以下問題的數學模型，并求解模型，對模型的結果做出合理分析和解釋。1. 查閱相關文獻，搜集垃圾產量數據，在此基礎上建立城市生活垃圾產量中

5、短期預測模型，并且分析模型的準確性和實用性。2. 在收運過程已知下述四個條件下，如何安排垃圾收運車的收運路線，使在垃圾收運車的行車里程盡可能的少，或者垃圾收運時間盡可能短？(1)車庫和收集點、收集點與中轉站、中轉站與車庫的距離；(2)各收集點每天的垃圾產量；(3)每輛垃圾收運車的最大載荷；(4)垃圾收集點、車庫、中轉站的工作區間。請給出規劃以上垃圾收運路線的數學模型，并設計出有效的算法，針對附錄中給出的數據，求解模型。并且對模型的適用性、算法的穩定性和魯棒性做出分析。二、模型的假設與符號說明2.1模型的假設1忽略每天交通高低峰的路況區別及其他特殊情況，即垃圾收運車的行駛速度保持不變；2城市兩點

6、之間的manhattan距離能很好的表示他們之間的實際距離；3所搜集到得數據真實可靠，且具有代表性；4忽略遺傳算法本身所造成的系統誤差；2.2符號說明：參考數列，表示時刻；：表示第比較數列；：表示比較數列對參考數列在時刻的關聯系數；：數列對參考數列的關聯度；：分辨系數；：表示回歸系數；：階單位矩陣；：回歸誤差平方和；：GM(1,1)模型的初始數據；：級比偏差；：分別表示人口、住宅使用面積、消費水平、可支配收入；：表示垃圾年產量；：表示經過第段線路所花費的時間；：為 變量，當為1時表示第輛車通過第段線路，當為0時表示第 輛車不通過第段線路；：表示第輛車通過路線花費的總時間；：三輛車走過所有路線的

7、總時間；三、問題分析3.1 問題分析問題一，在搜集相關數據的基礎上，對影響垃圾管理規劃的主要因素垃圾產量進行預測。分析問題我們發現，影響垃圾產量的因素很多，如：人口數量、居民生活水平等，而且垃圾產量并沒有隨年份變化的明顯趨勢。因此，必須首先找到影響垃圾年產量的主要的因素，然后對垃圾年產量與主要因素進行多元回歸分析，得到回歸方程，進而進行垃圾產量的預測。預測過程必須遵循以下兩條原則：連貫性原則：是指所研究對象的發生和發展按照一定規律進行，這個規律在其發生和發展過程中貫穿始終，事物未來發展與過去、現在的發展無根本不同。類推的原則：是指事物必須有某種結構，而這種結構及其變化要有一定的模型，可以根據所

8、測定的模型，可以根據所測定的模型，類比過去和現在，預測未來。為預測垃圾的年產量，首先應該進行各主要因素數值的預測。因為影響垃圾年產量的因素，都有明顯的規律可以遵循，所以我們使用GM（1，1）模型對個主要指標進行了預測。最終將主要指標的預測值代入回歸方程得到所要預測的垃圾年產量。問題二，垃圾收運車從車庫出發后，要將所有收集點的垃圾收集完并運往中轉站，但是垃圾收運車的載重量不能超過200，所以，在垃圾收運車負載達到最大載重量時要前往中轉站，卸下所有垃圾后再返回繼續收集?？梢韵燃僭O垃圾車的載重量無限大，可一次將垃圾全部收集完畢，因此暫不考慮中轉站問題，而直接從車庫出發，找到一條遍歷所有收集點的最短路

9、徑，從而將問題轉化為TSP問題，這樣就可求得最短收集路線。但是由于垃圾收集點高達275個，使用常規方法根本無法在有效時間內完成計算，因此這里考慮使用現代優化算法中的遺傳算法進行求解。然后，再讓垃圾收運車沿求出的路線收集垃圾，當垃圾量等于或略小于200后前往中轉站，卸載完垃圾后再前往下一個收集點，如此往復進行。進而可以計算出所需時間，以此可以決定至少需要使用的垃圾收運車數目。將經歷每次到中轉站之間的收集路線作為一條子路線，將這些子路線均衡地分配給每輛車執行即可。四、模型的建立與求解4.1 基于多元線性回歸的生活垃圾預測模型 城市生活垃圾產量的準確預測是進行城市固體廢物處理處置系統科學決策的基礎。

10、只有對未來進行準確的預測，才能夠對未來處理規模、處理能力以及處理要求進行確定，進而才能根據需要，對處理處置系統進行科學篩選和決策。然而，影響垃圾質和量變化的因素很多，主要有三類：一、影響垃圾質和量變化的內在因素，主要是指直接導致生活垃圾質和量變化的因素，如人口數量、居民生活水平、城市建設水平等。人口增加，在其他因素不變的情況下垃圾產量必然增加；同樣，由于經濟的發展，居民生活水平的提高，居民消費品的數量與類別增加，相應垃圾產量也會增加；城區范圍增大，保潔區面積增大，垃圾產生量也增大。影響垃圾質變化的因素有居民生活水平、能源結構、生活的地域差異以及消費方式等。如在以燃煤為主的地區以及北方采暖期，生

11、活垃圾中無機灰渣的含量較高。二、影響垃圾質和量變化的社會因素，主要指社會行為準則、社會道德規范、法律規則制度等，是一種外部的、間接的因素。如國家推行垃圾減量、回收和再利用措施，可以大幅度減少垃圾最終處理量；垃圾分類收集則是從源頭改善垃圾的質，減少后續垃圾的處理難度，利于垃圾回收而減少垃圾最終處理量。三、影響垃圾質和量變化的個體因素，主要是指垃圾產生的主體人類本身個體的行為習慣和受教育程度等。對生活垃圾質和量進行預測，需綜合以上三種因素，通過這些因素的變化情況，分析垃圾質和量的變化趨勢，從而得出預測值。因而我們選取人口、生產總值、居民可支配收入、居民消費性支出、社會消費品零售總額、平均每人生活消

12、費能源、人均住宅使用面積等作為生活垃圾預測的因子集，進一步的對生活垃圾產量的變化進行研究。4.1.1 基于灰色關聯的主要因素提取對于主要影響因素的提取，數理統計中通常運用回歸分析、方差分析、主成份分析等系統分析的方法進行分析。但這些方法都不可避免的存在以下的幾點不足之處：1)要求有大量數據；2)要求樣本服從某個典型的概率分布；3)計算量大；4)可能出現量化結果與定性分析結果不符的現象。然而，灰色關聯分析的基本思想是根據序列曲線幾何形狀的相似程度來判斷其聯系是否緊密。曲線越接近，相應序列之間的關聯度就越大，反之就越小。由灰色關聯度導出灰色關聯序，以進行優勢分析，從而知道在眾多的影響因素中，哪些是

13、主要因素，哪些是次要因素。這使得灰色關聯分析對樣本量的多少和樣本有無規律都同樣適用，而且計算量小，十分方便，更不會出現量化結果與定性分析結果不符的情況。因此，我們選用灰色關聯分析從給定的因素集中提取影響城市生活垃圾的主要因素。選取參考數列，本文為生活垃圾的年產量，表示時刻（年代）。假設有個比較數列則稱 （1）為比較數列對參考數列在時刻的關聯系數，其中為分辨系數。稱（1）式中、分別為兩級最小差及兩級最大差。一般來說，分辨系數越大，分辨率越大；越小，分辨率越小。（1）式定義的關聯系數是描述比較數列與參考數列在某時刻的關聯度的一種指標，由于各個時刻都有一個關聯數，因此信息顯得過于分散，不便于比較，為

14、此我們給出 （2）為數列對參考數列的關聯度。并做如下分析：若存在，滿足，則稱因素優于，記為。若恒有，則稱為最優因素。其算法流程圖如下：計算灰色關聯矩陣計算因素關聯序計算因素關聯序是否有最優因素？確定準優因素確定最優因素結束是否通過灰色相關度分析，就能較為準確的提取出影響城市垃圾產量的主要因素。4.1.2 因素之間的多重共線性的分析通過灰色相關度分析，我們能找出影響城市垃圾產量的主要因素。但各個因素之間還存在很強的多重共線性關系，即不同的因素之間的相關性非常的好?？赡苷怯捎谶@種多重共線性關系造成了一些不是主要的因素通過了關聯度分析。為使選擇的因素之間的多重共線性關系盡可能的少可做如下的處理：（

15、一）刪除不重要的解釋變量 解釋變量之間存在共線性，說明解釋變量所提供的信息是重疊的，可以刪除不重要的解釋變量減少重復信息。但從模型中刪去解釋變量時應該注意：從實際經濟分析確定為相對不重要并從偏相關系數檢驗證實為共線性原因的那些變量中刪除。如果刪除不當，會產生模型設定誤差，造成參數估計嚴重有偏的后果。（二）追加樣本信息 多重共線性問題的實質是樣本信息的不充分而導致模型參數的不能精確估計，因此追加樣本信息是解決該問題的一條有效途徑。但是，由于資料收集及調查的困難，要追加樣本信息在實踐中有時并不容易。（三）利用非樣本先驗信息 非樣本先驗信息主要來自經濟理論分析和經驗認識。充分利用這些先驗的信息，往往

16、有助于解決多重共線性問題。（四）改變解釋變量的形式 改變解釋變量的形式是解決多重共線性的一種簡易方法，例如對于橫截面數據采用相對數變量，對于時間序列數據采用增量型變量。（五）逐步回歸法 逐步回歸（Stepwise Regression）是一種常用的消除多重共線性、選取“最優”回歸方程的方法。其做法是將逐個引入自變量，引入的條件是該自變量經F 檢驗是顯著的，每引入一個自變量后，對已選入的變量進行逐個檢驗，如果原來引入的變量由于后面變量的引入而變得不再顯著，那么就將其剔除。引入一個變量或從回歸方程中剔除一個變量，為逐步回歸的一步，每一步都要進行 F 檢驗，以確保每次引入新變量之前回歸方程中只包含顯

17、著的變量。這個過程反復進行，直到既沒有不顯著的自變量選入回歸方程，也沒有顯著自變量從回歸方程中剔除為止。本文采用（五）逐步回歸的方法，將灰色關聯度分析得到的各變量（主要因素）的排列次序依次加入變量，逐次記錄計算結果，觀察每一個因素對系統的影響，包括方面：對擬合優度的影響；對調整后的擬合優度的影響；參照檢驗值考察自身的零系數概率。在變量篩選過程中，我們通過細致地觀察各變量在不斷變換的方程模式中的具體表現，以數據為基礎，將定量分析和定性分析有機地結合起來，最終確定模型的最適變量。4.1.3 多元線性回歸分析多元回歸分析的模型為：（3）式中都是與無關的未知參量，其中成為回歸系數?，F得到個獨立觀察數據

18、由（3）得（4）記（4）式表示為其中，階單位矩陣。模型（3）中的參數用最小二乘法估計，即選取估計值，使當時，時，誤差平方和達到最小。將影響垃圾產量的各因素數據代入模型求得各個系數。4.1.4 基于GM（1,1）模型的指標預測 （1）灰色預測的方法設已知參考數據列為，做一次累加（）生成數列其中。求均值數列：則。于是建立灰微分方程為相應的白化微分方程為記，則由最小二乘法，求得使達到最小值的。于是求解白化微分方程得。 (2) 灰色預測的步驟:數據的檢驗與處理首先，為了保證模型方法的可行性，需要對已知數據列做必要的檢驗處理。設參考數據為，計算數列的級比如果所有的級比都落在可容覆蓋內，則數列可以作為模型

19、的數據進行灰色預測。否則，需要對數列做必要的變換處理，使其落入可容覆蓋內。即取適當的常數，作平移變換則使數列的級比:建立模型建立模型，則可以得到預測值，而且。:檢驗預測值（a）殘差檢驗：令殘差為，計算如果，則可認為達到一般要求；如果，則認為達到較高的要求。（b）級比偏差檢驗：首先由參考數據計算出級比，在用發展系數求出相應的級比偏差如果，則可以認為達到一般要求；如果，則認為達到較高的要求。:預測預報由模型所得到的指定時區內預測值，根據實際問題的需要，給出相應的預測預報。根據上述模型，我們能對未來的各因素的值進行預測。然后將預測值代入多元線性回歸模型得到未來時間的城市垃圾產量。4.1.5 預測模型

20、的實現以北京市1999年到2007年的各個指標的情況為例，對2008年北京市的垃圾產量進行預測，并用2008年的實際值對其準確性進行對比檢驗。表1是1999年到2007 年的各個指標數據。預測步驟：利用灰色關聯度求取垃圾產量與各因素之間的相關性關系，得到垃圾產量與各個因素的關聯度見表2?？梢钥闯鋈丝?、住宅使用面積、消費水平、可支配收入與垃圾產量相關度較大。結合逐步回歸的思想，將灰色關聯度分析得到的各主要因素依次加入變量，逐次記錄計算結果，觀察每一個因素對系統的影響，以數據為基礎，將定量分析和定性分析有機地結合起來，最終確定模型的最適變量為：人口、住宅使用面積、消費水平、可支配收入。表1 垃圾產

21、量及其相關因素的數據值時間垃圾量人口生產總值居民收入居民消費水平社會消費品零售總額消費能源住宅使用面積1999449.512572689.69182.77498.41313.3121.415.72000244.413823333.610349.78493.41443.3126.416.8200130313833710.511577.88922.71593.5130.317.62002321.414234330.412463.910284.61673.3136.918.22003454.514565023.813882.611123.81916.7153.918.7200449114936060

22、.315637.812200.42626.6164.219.12005454.615386886.31765313244.22902.8179.919.52006538.215817870.319977.514825.43275.2194.720.12007600.916339006.221988.715330.43800.2203.320.75表2 垃圾產量與各因素之間的關聯度關聯度人口生產總值可支配收入消費水平消費品零售額平均能耗住宅使用面積垃圾產量0.84130.53410.63150.66130.60450.75860.8339：令人口、住宅使用面積、消費水平、可支配收入分別用表示，對

23、其進行多元線性回歸，利用最小二乘法求得各系數值為：， 。這樣得到回歸方程為： （5）相應的檢驗值為：表3 多元回歸檢驗值檢驗FP結果0.92712.70.015可以看出，檢驗結果比較理想，回歸方程是可信的。：用GM(1,1)模型對各因素2008年的數據進行預測。由人口發展理論及經濟學理論，易知人口、住宅使用面積、消費水平、可支配收入是具有明顯的按時間發展的規律的，所以這些因素能用GM(1,1)模型進行預測。將表1的數據代入4.1.4的模型得到各因素2008年的預測結果。以人口預測為例，見表4從表4中可以看出，北京各年人口的預測值與實際值之間的相對誤差、級比偏差都很小，預測結果比較理想。同理，我

24、們預測得到北京2008年的人均消費水平、人均消費能源、人均住宅使用面積的數據，見表5。表4 人口預測結果人口實際值預測值殘差相對誤差級比偏差19991257125700200013821358.15923.84130.01730.0672200113831392.856-9.85590.0071-0.0248200214231428.44-5.43960.00380.0033200314561464.932-8.93240.0061-0.0023200414931502.357-9.35740.0063-0.0001200515381540.739-2.73860.00180.00452006

25、15811580.10.89970.00060.0023200716331620.46812.53240.00770.007120081660.917表5 相關指標的預測結果因素人均消費水平人均消費能源人均住宅使用面積預測結果17142.82220.997321.3044具體的預測結果見附表1?？梢钥闯鏊麄兊念A測結果都是比較理想的，所以能夠作為對2008年垃圾產量的預測的數據。：利用中的回歸方程（5），及中對各個指標的預測值，求出北京2008年的垃圾產量。將數據代入回歸方程得到北京2008年的垃圾產量為：1275.245-2.6757×1660.917-0.0218×171

26、42.82+10.1925×220.9973+92.489×21.3044=680.3535（萬噸）。4.1.6 結果分析（一）回歸方程負系數分析由回歸方程式（5），我們看到代表人口數量和人均消費水平的系數是負數，這顯然與我們的生活常識及相關性分析不符，見表6。表6 1999年2007年四元線性回歸系數符號情況常數為正數影響趨勢人口數系數為負數人口垃圾產量居民消費性支出系數為負數居民消費性支出垃圾產量平均每人生活消費能源系數為正數平均每人生活消費能源垃圾產量人均住宅使用面積系數為正數人均住宅使用面積垃圾產量為了方便觀察與分析各系數對全國垃圾產量的影響，這里將上述分析分兩階段

27、總結為表7。表7 自變量的系數與北京垃圾產量關系一覽表年份參量常數人口居民消費性支出人均生活消費能源人均住宅使用面積199920032003200719992007從表7中看出：不同年份段，自變量的系數影響北京市垃圾產量的趨勢不同。從1999年2007年段來看，當平均每人生活消費能源、人均住宅使用面積為正影響時，符合人們的一般看法，但人口數和居民消費性支出為負影響卻不好理解，但揭露出一個事實，不同時期各自變量對垃圾產量的貢獻是不同的。對北京市生活垃圾產量進行多元線性回歸，將北京市垃圾產量與諸多因素的關系已反映出來，可以看出每個時間段各因素的影響趨勢不大相同，隨機性強。（二）模型的準確性和實用性

28、分析1、準確性為檢驗模型的準確性，我們用簡單趨勢預測法GM(1,1)模型，對2008年北京市的垃圾年產量進行預測，結果如下表。表8 2008年北京市的垃圾年產量預測結果垃圾量實際值預測值殘差相對誤差級比偏差1999449.5449.5002000244.39279.9103-35.52030.1453-1.05652001303312.9347-9.93470.03280.09822002321.4349.8554-28.45540.0885-0.05412003454.5391.132163.36790.13940.20932004491437.278853.72120.1094-0.035

29、2005454.6488.8699-34.26990.0754-0.20762006538.2546.5479-8.34790.01550.05562007600.9611.0308-10.13080.0169-0.00142008672692.691520.69150.030791從表中的數據可以看出用簡單的趨勢預測的結果并不理想。兩種預測的結果與實際值的對比如下：表9 預測結果對比2008年實際值GM(1,1)回歸預測數值672692.6915680.3535誤差020.69158.3535由上面的分析可以看出，回歸預測的精度要高于簡單的趨勢預測，準確性較好。2、實用性分析由于垃圾產量的變

30、化并沒有，明顯的數值規律可以遵循，所以一些簡單的趨勢預測方法并不能很好的描述它發展變化。而且這些完全基于觀察值的預測，并沒有分析其內在成因，這樣會有產生誤差的累積過程，不能用于短中期預測。然而，運用灰色關聯的方法找到與垃圾產量有明顯關系的主要因素，這樣就找到了垃圾產量變化的內因；用多因素線性回歸的方法將這些主要的因素有機的結合在一起，有利于研究垃圾產量變化的規律，可以避免誤差的累積。由于影響垃圾產量的主要的經濟、社會因素的發展規律已經非常明確和完善，站在對其中的各個主要的經濟、社會因素進行預測，然后代入回歸方程間接地預測垃圾的產量的方法是可行的也是實用的。4.2 問題二模型的建立與求解4.2.

31、1 基于遺傳算法的模型由于在垃圾收運的過程中，垃圾收集車的數目不確定，因此首先需要估算出在車庫工作區間內所需的最少垃圾收集車數。由于所有收集點的垃圾總量為2132.5，小于每輛垃圾車每天的負載總量2200.0，且總計275個垃圾收集點，也小于每輛垃圾車每天最多經過的垃圾收集點個數500。因此在不考慮車庫工作區間的情況下，用一輛車從車庫出發，遍歷所有收集點的最短路徑，最后回到車庫，從而將問題轉換為模型。由于含有276個點的模型數據量十分龐大，通過查閱相關資料知道，普通算法的模型最適合的規模是25個點左右，求解起來比較容易。因此這里考慮采用現代優化算法中的遺傳算法進行求解，用于解答類似問題的組合優

32、化問題的全局最優解。遺傳算法（，簡稱）是一種基于自然選擇原理和自然遺傳機制的搜索（尋優）算法，它是模擬自然界中的生命進化機制，在人工系統中實現特定目標的優化。遺傳算法的實質是通過群體搜索技術，根據適者生存的原則逐代進化，最終得到最優解或準最優解。它必須做以下操作：初始群體的產生、求每一個體的適應度、根據適者生存的原則選擇優良個體、被選出的優良個體兩兩配對，通過隨機交叉其染色體的基因并隨機變異某些染色體的基因后生成下一代群體，按此方法使群體逐代進化，直到滿足進化終止條件。其實現方法如下：(1)根據具體問題確定可行解域，確定一種編碼方法，能用數值串或字符串表示可行解域的每一解。(2)對每一解應有一

33、個度量好壞的依據，它用一函數表示，叫做適應度函數，適應度函數應為非負函數。(3)確定進化參數群體規模、交叉概率、變異概率、進化終止條件。表10 生物遺傳概念在遺傳算法中的對應關系生物遺傳概念遺傳算法中的作用適者生存算法停止時，最優目標值的解有最大的可能被留住個體解染色體解的編碼基因解中每一分量的特征適應性適應度函數值種群根據適應度函數值選取的一組解交配通過交配原則產生一組新解的過程變異編碼的某一分量發生變化的過程為便于計算，一般來說，每一代群體的個體數目都取相等。群體規模越大、越容易找到最優解，但由于受到計算機的運算能力的限制，群體規模越大，計算所需要的時間也相應的增加。進化終止條件指的是當進

34、化到什么時候結束，它可以設定到某一代進化結束，也可能根據找出近似最優是否滿足精度要求來確定。表10列出了生物遺傳概念在遺傳算法中的對應關系。針對問題二，求解的遺傳算法的參數設定如下：種群大?。鹤畲蟠鷶担航徊媛剩?，交叉概率為1 能保證種群的充分進化。變異率：，一般而言，變異發生的可能性較小。(1)編碼策略采用十進制編碼， 用隨機數列作為染色體， 其中(），, ；每一個隨機序列都和種群中的一個個體相對應，例如一個9城市問題的一個染色體為0.23，0.82，0.45，0.74，0.87，0.11，0.56，0.69，0.78其中編碼位置代表城市，位置的隨機數表示城市在巡回中的順序，我們將這些隨機數按

35、升序排列得到如下巡回：613784925(2)初始種群本文中我們先利用經典的近似算法改良圈算法求得一個較好的初始種群。即對于初始圈，交換與之間的順序，此時的新路徑為：記 ，若 ，則以新的路經修改舊的路經，直到不能修改為止。(3)目標函數目標函數為行遍所有收集點的路徑長度，適應度函數就取為目標函數。我們要求根據題目要求，這里兩點之間的距離為距離：(4)交叉操作我們的交叉操作采用單點交叉。設計如下,對于選定的兩個父代個體，我們隨機地選取第個基因處為交叉點，則經過交叉運算后得到的子代編碼為 和,的基因由的前個基因和的后個基因構成,的基因由的前個基因和的后個基因構成，例如：設交叉點為第四個基因處，則交

36、叉操作的方式有很多種選擇，我們應該盡可能選取好的交叉方式，保證子代能繼承父代的優良特性。同時這里的交叉操作也蘊含了變異操作。(5)變異操作變異也是實現群體多樣性的一種手段，同時也是全局尋優的保證。具體設計如下，按照給定的變異率，對選定變異的個體，隨機地取三個整數，滿足，把之間（包括和）的基因段插到后面。(6)選擇采用確定性的選擇策略，也就是說選擇目標函數值最小的個個體進化到下一代，這樣可以保證父代的優良特性被保存下來。 基于上述遺傳算法原理，通過編程，可以得到最短路徑的分布情況，見圖1。圖1 最短路徑的分布圖4.2.2 考慮垃圾車最大載重量及車庫工作區間的最短路徑分布 在不考慮垃圾車最大載重量

37、和車庫工作區間的情況下，求得最短路徑后，這里將垃圾車的最大載重量的因素考慮進去，暫時仍然不考慮車庫的工作區間，用一輛垃圾車按照上述的最短路徑，從車庫出發開始收運垃圾，當垃圾車內收集的垃圾接近或達到200，但剩余載重量又小于下一站點垃圾量的時候，垃圾車開往垃圾中轉站，在中轉站卸下所有收運的垃圾后，再到下一站點繼續收集垃圾，如此反復，直到所有收集點的垃圾都被收集完，垃圾車返回車庫。 基于上述思路可以得到考慮垃圾車最大載重量的最短路徑分布，見表11。表11 最短路徑路線分布表015519620719820020920420318313416913316588143192131951011119824

38、6270247218250276/1/217252210243245223232233235275269226262257254237271272251253230/1/249259231274248224227214229261220238234215260239225228265222213256267221/1/241219242236273216258263268266240264255822441391571022141216/1/61827175127202123234208189205202190187201185/1/194206184211195199191193854838

39、6142306460376571848056584476532962/1/59915533635750242868904725815135416731755439/1/4977527932702646746673348336457872406943188182212197186108105135124/1/166161921201251731421581541521171711531681309897991211598917810914810017218187146132175/1/86129138160176113931261771631061191031361121801491471151

40、39140/1/1041231451411101111371741571511701221071649611616710211814412815016217915611494/1/0 根據最短路徑分布表，可以得到圖2圖2 考慮垃圾車最大載重量的最短路徑分布從上圖可以看出，由于整個垃圾收運途中，垃圾車共計需要到中轉站11次卸垃圾，因此，最短路徑的路線被分成相對獨立的11個子路線，根據各點的坐標，可以求出最短路徑的總路程為479.6992，垃圾車在各收集點收集垃圾和11次到達中轉站卸載垃圾的工作時間共計為8.2153小時，垃圾車的行車速度為40，可以得到總時間為：479.6992/40+8.215

41、3=20.2078(小時) 由于車庫的工作區間為9小時，同時出于實際情況的考慮，在滿足目標和條件的前提下，所用車輛越少越好，而且，車輛的增多使最后從中轉站到車庫段增多，導致總路程變長，因此需要至少三輛垃圾收運車才能在車庫的工作區間內將垃圾全部運往中轉站。根據垃圾收集點的分布圖不難看出，所有收集點大致分為比較獨立的三塊區域，這里從左至右依次稱為西區、中區和東區。中區和東區距離中轉站距離大致相近，而西區距離中轉站則相對較遠。由于垃圾車需要11次到中轉站卸載垃圾，三輛車無法平均分配，由于西區路程較遠，因此將經過西區的到中轉站的3個子路線分配給一輛車清運，其余8個子路線平均分配給另外兩輛車?；谏鲜鏊?/p>

42、想，這里先以三輛車進行垃圾清運，若能滿足車庫工作區間，則為可行解，若仍然超出車庫的工作區間，則以四輛車進行垃圾清運來計算。三輛車從車庫出發后，分別從155號收集點、241號收集點、49號收集點開始收集垃圾，收集路線見圖3。圖3 三輛車的垃圾收運路線通過計算可以得到，三輛車進行垃圾清運的路程分別為：154.9591、173.8447、159.6432；在各收集點和中轉站收集和卸載垃圾花費的時間分別為：2.2292小時、2.9514小時、3.0347小時；進而可以求出三輛車清運垃圾的總時間分別為6.1031小時、7.2975小時、7.0258小時。則運行的總路程為488.4470，工作時間為三輛車

43、工作時間的最大值7.2975小時。 4.2.3 模型改進通過上圖可以很明顯地看出，盡管模型開始建立時使用一輛車行遍各個點，采用的是全局最優解，但是將路線分配給三輛車行走時，不應定能夠滿足局部最優。從結果也可以看出每輛車工作的時間差距達到1個小時左右，沒有將工作量平均的分配給三輛車執行，導致整個系統工作時間變大。因此，需要對模型進行改進。在模型改進之前，這里需要對距離的應用做出進一步的解釋：距離的定義是為：如上圖所示，若按歐式距離計算，,很顯然得到，但是若按距離計算，可以得到如下關系，,，則有：根據問題二的實際情況，以及距離的性質，如果點為任一收集點，點為車庫，點為中轉站，則可得到如下結論：由車

44、庫出發到達任一收集點，最后再從中轉站返回車庫，該距離即等于從中轉站直接到達收集點的距離。而模型改進的關鍵就在于能夠將11條子路線均衡的分配給三輛車去走，分配的前提條件就是這11個子路線必須是相同情況下的，也即是起點和終點相同。根據上述距離的性質，這里假設所有11個子路線的起點和終點均為中轉站，這樣11個子路線的相關量就可以在同等條件下進行計算了。為了能夠將11個子路線進行量化，這里綜合考慮各個路線的長度和每個節點花費的時間，由于車輛進行勻速行駛，因此可以將路程化為等效時間，即將路程除以速度。這里給出11個子路線所經歷收集點的起始點和結束點，見表12表12 11個子路線所經歷收集點的起始點和結束

45、點子線路收集點坐標坐標線路1起始點155-48472384183012結束點276-48764844197661線路2起始點217-48781984198208結束點230-48747624200997線路3起始點249-48749394199870結束點221-48698634199883線路4起始點241-48698064199873結束點16-48622054203990線路5起始點6-48615214203864結束點185-48410614200332線路6起始點194-48404234199203結束點62-48220124213081線路7起始點59-48201584213154

46、結束點39-48194704210260線路8起始點49-48176884209915結束點124-48384404197237線路9起始點166-48394564195192結束點175-48459574194648線路10起始點86-48461114194774結束點140-48430104193167線路11起始點104-48430074193186結束點94-48399284188044通過計算可以得出每條線路的等效時間，見表13。表13 11個子線路的等效時間（單位：小時）子路線線路1線路2線路3線路4線路5線路6等效時間2.04582.05761.99981.99801.83691.8007子路線線路7線路8線路9線路10線路11等效時間1.66171.76351.69421.69901.6504設表示經過第段線路所花費的時間；為變量，當為1時表示第輛車通過第段線路，當為0時表示第輛車不通過第段線路；表示第輛車通過路線花費的總時間，為三輛車經過所有路線的總時間。建立如下的規劃模型：求解結果為：表14 三輛車的線路安排結果結果經過的線路段路線花費總時間第一輛車線路5、線路6、線路7、線路106.998小時第二輛車線