多品類生活垃圾收運的車輛路徑優(yōu)化問題研究

賈焙皓

摘?要：近年來隨著中國逐步制定并開展垃圾分類的政策法規(guī)，多品類生活垃圾分類收運問題就逐步凸顯出來。國內(nèi)使用多車艙車輛收運多品類生活垃圾的研究還較少，針對這一需求，本文基于生活垃圾分類利用多車艙垃圾收運車輛同時收運多品類生活垃圾的收運問題，以降低城市生活垃圾收運成本為目標(biāo)，構(gòu)建考慮車輛收運成本的多品類垃圾收運車輛的路徑優(yōu)化模型，并進(jìn)行仿真實驗，用蟻群算法對算例進(jìn)行求解，驗證了算法模型的良好尋優(yōu)效果，為新式垃圾車輛的投產(chǎn)使用提供參考。

關(guān)鍵詞： 生活垃圾收運;多品類;車輛路徑優(yōu)化;蟻群算法

文章編號： 2095-2163（2021）01-0114-06 中圖分類號：X799.3 文獻(xiàn)標(biāo)志碼：A

【Abstract】In recent years， as China has gradually formulated and implemented waste classification policies and regulations， the problem of the classification and transportation of multi-category domestic waste has gradually become prominent. Domestic research on the use of multi-cabin vehicles to collect and transport multi-category domestic waste is still rare. In response to this demand， this article is based on the classification of domestic waste and uses multi-cabin waste collection and transportation vehicles to simultaneously collect and transport multi-category domestic waste to alleviate the problem of collection and transportation. The cost of collection and transportation of municipal solid waste is the goal. The route optimization model of multi-category waste collection and transportation vehicles considering the cost of vehicle collection and transportation is constructed， and simulation experiments are carried out. The ant colony algorithm is used to solve the example， which verifies the good optimization of the algorithm model. The effect provides a reference for the production and use of new garbage vehicles.

【Key words】domestic waste collection and transportation; multi-category; vehicle routing optimization; ant colony algorithm

0 引?言

自從2017年國家發(fā)展和改革委員會、住房和城鄉(xiāng)建設(shè)部出臺《生活垃圾分類制度實施方案》[1]以來，垃圾分類已經(jīng)在北京、上海、廣州等地成功實施，但是隨著垃圾分類時代的來臨，傳統(tǒng)的垃圾處理能力與垃圾分類處理能力之間的問題日趨凸顯，如何將多品類城市生活垃圾做到分類收集運輸，促進(jìn)后端垃圾資源化處理是當(dāng)下亟需解決的問題。

由于中國城市生活垃圾分類處理才剛剛起步[2～3]，許多城市在垃圾分類、經(jīng)費投入、管理體系等方面還存在不足，在分類收運方法上仍處于不斷探索之中。中國寧波市鄞州區(qū)環(huán)衛(wèi)部門為了適應(yīng)街道定時定點分類投放的新政策，改裝了一種兩類一體垃圾收運車輛，實現(xiàn)廚余垃圾和其他垃圾同步收運，既減少車輛和人員的投入，又可實現(xiàn)居民一次性投遞，大大提升了居民和管理部門的滿意度。

1 文獻(xiàn)綜述

城市多品類生活垃圾收運模式是一種有載重限制的逆向車輛路徑問題，與經(jīng)典的車輛調(diào)度問題存在一定的差別，目前國內(nèi)外研究成果較少。僅就國內(nèi)來說，大量的學(xué)者從垃圾收運主體（環(huán)衛(wèi)部門和垃圾收運公司）入手，將垃圾車輛收運調(diào)度問題方面需考慮的主要因素，分為2個方面，即：固定成本和收運路徑成本。其中，固定成本包括工人工作成本和車輛使用成本;收運路徑成本則重點涉及2個方面，就是：時間成本和距離成本。具體來說，在時間成本上，主要從垃圾收集的頻次[4]、中轉(zhuǎn)站排隊時間[5]、裝卸時間[6]以及其他的影響上述因素的效率懲罰成本等方面進(jìn)行拓展研究;在距離成本上，主要是從車輛的行駛成本、碳排放成本、車輛故障維修成本[7～9]等方面進(jìn)行了研究探索。在同時使用多隔間的車輛問題上，研究還并不充分，且研究焦點大多集中在：生產(chǎn)車間調(diào)度[10]和零售貨物的配送[11]上?，F(xiàn)行的貨物調(diào)度運輸情況都是以各類物品單獨運送為主，都是以多車型多品類的貨物調(diào)度為研究對象，對多品類貨物的同時調(diào)度研究較少。

基于垃圾分類-多品類生活垃圾收運的車輛路徑問題，是屬于多車廂車輛路徑問題（Multi-Compartment Vehicle Routing Problem，MC-VRP）。國外早在1979年就證實該問題具有實際意義，且2006年Fallahi等人[12]解決了倉庫庫存的配送問題，即：m種不同的產(chǎn)品必須由一組相同的車輛交付給客戶，每輛車都帶有m容量有限的隔間，其與多隔間垃圾收集問題不同，允許不同的車輛向同一客戶交付不同的產(chǎn)品。在國內(nèi)的冷鏈物流中，運用多隔間多溫共配模式較多，陳婧怡等人[13]采用多溫區(qū)冷藏車， 構(gòu)建考慮運輸成本、貨損成本、制冷成本的路徑優(yōu)化模型， 利用遺傳算法對算例進(jìn)行求解， 借助ArcGIS規(guī)劃最短路徑，取得較好的成效，證明了多隔間收運模式的可行性。

但是在生活垃圾資源化回收利用這種逆向物流問題中，利用多隔間的收運車輛進(jìn)行收運的研究還不多。本文是在基于垃圾分類的情況下，來研究新式多品類城市生活垃圾收運車輛的路徑優(yōu)化問題，該研究與現(xiàn)有的垃圾路線優(yōu)化問題的區(qū)別主要體現(xiàn)在： 考慮了垃圾收運資源化的分類特性;考慮了多品類生活垃圾實際收運過程中的同時性。并與傳統(tǒng)“一類一車”的各品類單獨分開收運模式作對比分析，研究多品類生活垃圾同時收運模式下相對于傳統(tǒng)的收運系統(tǒng)的優(yōu)劣，為中國垃圾分類收運的推進(jìn)提供參考。

2 問題提出

研究問題描述：在一個收運區(qū)域內(nèi)，有一個停車場，一個垃圾中轉(zhuǎn)站和多個垃圾收集點，車場有多輛同類型的車輛，每臺車輛都有多個容量大小固定的車箱隔室，不同車箱隔室的容量可以不同;每個垃圾收集點都有多種垃圾品類，不同品類的垃圾需要放在不同的隔室進(jìn)行收運，同時每個收集點需要在一次服務(wù)中完全滿足。假設(shè)已知如下條件：

（1）每個垃圾收集點的各類垃圾量已知。

（2）車場和收集點、收集點和收集點、收集點和中轉(zhuǎn)站、中轉(zhuǎn)站和車場的距離已知。

（3）每輛車每個隔間的額定載重限制已知。

（4）垃圾收運車輛勻速行駛且速度已知。

研究可知，垃圾車輛的收運過程可概述為：收運車輛均從停車場出發(fā)，對垃圾收集點進(jìn)行服務(wù)，當(dāng)收運車輛任一隔間滿載或完成最后一個收集點時，返回至中轉(zhuǎn)站卸載，重復(fù)上述過程，直至服務(wù)完成所有點的垃圾收運工作后，車輛重新返回車場，完成收運工作，其收運過程示意圖如圖1所示。

該問題在運籌優(yōu)化領(lǐng)域就是一個圖論求解。文中用G表示整個垃圾收運區(qū)域，G=（V，A），其中，V=Vd∪Vf∪Ve，且節(jié)點Vd={0}表示車場，Vf={1，2，3，…，n}表示n個垃圾收集點，節(jié)點Ve={n+1}表示中轉(zhuǎn)站;A={（i，j），i，j∈V，i≠j}?表示不同節(jié)點之間的弧集。

3 基于垃圾分類下多品類垃圾收運的處理

建立基于垃圾分類收運下，多品類生活垃圾同時收運的數(shù)學(xué)模型為：

決策變量為：

需要指出，本文采用了三下標(biāo)的決策變量進(jìn)行建模，其中，xijk=1表示第k輛車經(jīng)過弧路徑（i，j），否則xijk=0;dij表示收集點i到收集點j之間的距離;C表示單位距離運輸成本;qmi為垃圾收集點i的第?m=1，2，3，…，M?類垃圾量;Qmk表示第k輛車裝載第m類垃圾的最大載重限制。

目標(biāo)函數(shù)（1）表示最小化垃圾收運的費用;約束（2）表示決策變量，為整數(shù)變量0或1;約束（3）表示每輛車都由車場出發(fā);約束（4）表示每輛車收運完成后都返回車場;約束（5）保證每個收集點被服務(wù)且只被服務(wù)一次;公式（6）表示車輛到達(dá)一個點的同時必須離開這個點，保證車輛的路徑始終為環(huán)形;公式（7）表示第n個隔間的載重限制，不能超出其核定載重量;公式（8）和公式（9）表示從車場出發(fā)和最后返回車場時均為空車。

4 算法設(shè)計

目前，對于生活垃圾收運車輛路徑這類NP-hard問題，求解的主要方法是：粒子群算法[5] 、遺傳算法[9]等智能啟發(fā)式優(yōu)化算法，群智能優(yōu)化算法是根據(jù)生物的生活特性，創(chuàng)造出最優(yōu)可行解的尋找方法，不同算法的最大不同特點，就是其將解空間映射為算法尋優(yōu)的特殊行為。蟻群算法（Ant Colony Optimization， ACO），最早是由Dorigo[14]于1992年提出并設(shè)計的一種群智能搜索算法，其在路徑選擇問題的求解上具有天然的優(yōu)勢，因此本文選擇最具特點的蟻群算法作為求解方案。

4.1 垃圾收運路線的蟻群優(yōu)化算法方案

本文在生活垃圾收運問題中的車輛選擇居民垃圾收集點部分，應(yīng)用螞蟻尋找食物的思想來設(shè)計蟻群優(yōu)化算法方案。每一只螞蟻的行走路線在解空間中表示一個可行解，即表示一個可行路徑方案，每個食物點表示一個未服務(wù)的居民垃圾收集點，車輛收集垃圾的過程就相當(dāng)于螞蟻覓食的過程。

在初始時刻，所有的螞蟻都在車場坐標(biāo)出發(fā)，各條路徑上的信息素初始值相等。在移動過程中，下一個收集點的選擇借鑒了文獻(xiàn)[15]隨機(jī)性選擇與確定性選擇相結(jié)合的選擇策略，根據(jù)每條路徑上的信息素濃度σij、能見度φij、車輛的載重限制，并結(jié)合確定規(guī)則和隨機(jī)選擇相結(jié)合的策略來尋找下一個待訪問的收集點j，利用如下公式來表示上述的轉(zhuǎn)移規(guī)則：

依據(jù)如下概率Pki并應(yīng)用輪盤賭法選擇j點

其中，r是[0，1]的隨機(jī)變量;r0為用來控制螞蟻尋找規(guī)則的參數(shù)，在這里取0.5;Nki表示車輛k從i點出發(fā)可以訪問的所有收集點j（滿足車輛各個隔間的載重約束且未被服務(wù)）的集合。

以上就是作為個體的螞蟻路徑選擇的規(guī)則，而蟻群算法是一個借助群體信息交流的智能優(yōu)化算法，信息素的更新規(guī)則就顯得尤為重要，在信息素更新時，本研究采用了最大—最小螞蟻系統(tǒng)的信息素更新方式。

4.2 算法的編碼解碼

本文參考文獻(xiàn)[4]對解空間采用實數(shù)編碼進(jìn)行編碼、解碼等行為，用數(shù)字n=1，2，3，…，N表示居民區(qū)垃圾收集點，數(shù)字0表示中轉(zhuǎn)站，N+1表示車場。

例如：對于解空間ans={2，4，18，24，10，7，1，9}，客戶點對應(yīng)垃圾品類1的產(chǎn)生量為Q1={0.3，0.4，0.9，0.8，0.7，0.6，0.6，0.5}，垃圾品類2的產(chǎn)生量為Q2={0.1，0.2，0.1，0.2，0.1，0.2，0.1，0.1}，車輛的最大載重重量為3，品類1的占比為80%，品類2的占比為20%，則解碼后的結(jié)果為{0，2，4，18，24，0，10，7，1，9，0}，這表示在正常的收運過程中，第一輛車從中轉(zhuǎn)站卸載完畢后出發(fā)進(jìn)行下一次收運，服務(wù)完收集點2，3，18，24四個點后，車輛的任一隔間滿足車輛載重限制后，再折返中轉(zhuǎn)站卸載;同理，第二輛車的行駛路線是服務(wù)收集點10，7，1，9四個點后，由于品類1的隔間到達(dá)載重上限，需要返回中轉(zhuǎn)站處理后繼續(xù)下一次任務(wù)的安排。

4.3 算法實現(xiàn)步驟

結(jié)合以上的算法方案，多品類垃圾收運路線優(yōu)化的基本步驟如下：

Step 1 初始化蟻群數(shù)量Num、迭代步數(shù)iter=1、信息素濃度Tau是元素全為1、且行列數(shù)為該系統(tǒng)所有服務(wù)點個數(shù)的矩陣、各個隔間的車輛載重限制Q等算法參數(shù)，讀取收集點的數(shù)據(jù)，并將所有螞蟻的起始位置都放在車場。

Step 2 讓一只螞蟻從車場出發(fā)，采用順序構(gòu)建解的方式，如果螞蟻在該收集點收集完成后，超出其任一車廂的載重限制，則該點即不進(jìn)行收運，要返回中轉(zhuǎn)站進(jìn)行卸載處理后，再進(jìn)行下一次任務(wù)的安排。

Step 3 按照Step 2以及規(guī)則（10）構(gòu)建出所有螞蟻的可行收運路線R，并用元胞數(shù)據(jù)格式存儲。

Step 4 按照目標(biāo)函數(shù)（1）求各個螞蟻的收運成本，計算出最小成本，并記錄下該代的最佳路徑Rbest以及最小成本。

Step 5 更新迭代信息素。按照最大最小螞蟻系統(tǒng)的信息素更新方式更新。

Step 6 iter=iter+1，若iter

5 仿真實驗

為了驗證本文設(shè)計的多品類生活垃圾收運問題的數(shù)學(xué)模型和算法的有效性，設(shè)計了仿真算例，進(jìn)行了數(shù)據(jù)的數(shù)值仿真實驗，并對結(jié)果進(jìn)行了分析。

5.1 仿真算例

隨機(jī)生成30個居民生活垃圾收集點，一個垃圾收運中轉(zhuǎn)站的坐標(biāo)為（4.91，5.06），一個停車場的坐標(biāo)為（4，8.51），坐標(biāo)單位為km。設(shè)車場共有10輛同類型多隔間生活垃圾收運車輛，所有車輛從同一停車場出發(fā)，并最終回到停車場。單位距離的收運成本C=10元/km;每輛車最大載重量Q=3t。仿真算例中生活垃圾收集點的坐標(biāo)信息以及垃圾數(shù)量見表1。

5.2 參數(shù)設(shè)置及算法比較

本文采用Matlab編程，在Windows7系統(tǒng)上，i3處理器的電腦上進(jìn)行運算驗證。將蟻群算法和生活垃圾收運車輛調(diào)度的遺傳算法進(jìn)行比對，來驗

證改進(jìn)的蟻群算法在生活垃圾車輛調(diào)度問題方面求解的性能。人工蟻群的參數(shù)設(shè)置：最大迭代次數(shù)500，蟻群數(shù)量為50只，信息素重要程度因子alpha=1;啟發(fā)函數(shù)重要程度因子beta=3;用來控制轉(zhuǎn)移規(guī)則的參數(shù)r0=0.5;信息素?fù)]發(fā)因子rh0=0.85;更新信息素濃度的常數(shù)Q=5;對比遺傳算法，采用的是改進(jìn)的自適應(yīng)遺傳算子，其參數(shù)設(shè)置：進(jìn)化代數(shù)為500，種群規(guī)模為50，選擇概率為0.1，自適應(yīng)算子的概率參數(shù)為0.0025。為了對比算法求解性能的優(yōu)劣，設(shè)置車輛上品類1的裝載容量占比（α=品類1載重/總載重）α=20%，40%，60%，80%，共4組參數(shù)，對每組參數(shù)分別采用蟻群算法和遺傳算法連續(xù)進(jìn)行10次實驗。實驗結(jié)果數(shù)據(jù)見表2，結(jié)果曲線如圖2、圖3所示。

通過圖2、圖3可知，在選擇合適的算法參數(shù)時，蟻群算法求解多品類生活垃圾同時分類收運問題具有比較好的尋優(yōu)求解效果。無論是最優(yōu)值，還是在平均值上，都優(yōu)于遺傳算法，因此本文采用蟻群算法進(jìn)行求解分析。

5.3 實驗及結(jié)果分析

采用改進(jìn)的人工蟻群算法對模擬仿真算例進(jìn)行求解，為驗證多品類共同分類收運方案的有效性，將其與單品類收運方案的收運成本進(jìn)行了對比，結(jié)果見表2。

多品類共同分類收運成本的變化趨勢如圖4所示。

通過表2以及圖4的多品類共同收運的成本變化，顯然就可以看出：對于垃圾收運點垃圾量為靜態(tài)已知的情況下，隨著各個垃圾品類隔間載重比的變化，收運成本的改變是顯著的，說明車輛各個隔間的載重比例對多品類垃圾同時分類收運的成本影響比較大。

從垃圾量總體數(shù)據(jù)上來看，品類1和品類2的總量比例接近4：1，當(dāng)垃圾收運車輛隔間比例與真實的垃圾總量比例差距較大的情況下，收運成本反而不如各品類單獨收運;相反對于比例適當(dāng)?shù)那闆r下，利用多隔間車廂同時分類收運，能夠降低收運成本。由此可知，根據(jù)垃圾總量的規(guī)律設(shè)計合適的車廂隔間比例能夠大幅提升垃圾收運系統(tǒng)的收運效率，節(jié)省收運成本。

在做實驗的過程中，為了驗證多品類垃圾收運車輛各個品類隔間的比例與實際垃圾產(chǎn)生量的關(guān)系，分別在不同比例的垃圾總量下，進(jìn)行了模擬實驗，垃圾點的位置坐標(biāo)不變，垃圾點的量發(fā)生變化，由于篇幅限制，只展示實驗參數(shù)和結(jié)果見表3。

從表3的結(jié)論可知，多品類收運車廂隔間的最優(yōu)配比與垃圾總量的配比成正相關(guān)。因此要想投入使用新式垃圾收運車輛來分類收運多品類生活垃圾，需要對各品類生活垃圾總量做好統(tǒng)計調(diào)查，適當(dāng)?shù)能囅漭d重配比能有效減少收運成本。

由以上模擬實驗，可以得知在表1的仿真數(shù)據(jù)下，2個品類的車廂隔間載重最佳配比為4：1，也就是品類1的載重占比為80%，采用多品類共同分類收運的模式比單品類分開收運更節(jié)省成本，其最優(yōu)收運方案見表4。

6 結(jié)束語

針對街道商鋪的定時定點分類投放收運的政策，多品類垃圾收運車輛同時收運能有效減少車輛的收運距離，減少居民投放垃圾的次數(shù)，提高了垃圾收運系統(tǒng)的收運效率，從而有效減少城市生活垃圾收運的成本。本文通過對多品類生活垃圾同時分類收運的收運模式，進(jìn)行數(shù)學(xué)建模，設(shè)計改進(jìn)的蟻群算法進(jìn)行求解。求解結(jié)果與數(shù)值分析表明，與傳統(tǒng)的單獨收運模式相比，多隔間車輛收運多品類生活垃圾，能有效降低城市生活垃圾收運成本;不同的垃圾總量比例，影響到車輛艙室容量的比例，不同的車艙容量比例對收運成本的影響較大。本研究為多品類城市生活垃圾同時收運提供理論指導(dǎo)，決策者可以基于不同的垃圾量使用不同的車艙容量比例，得到相應(yīng)的優(yōu)化路線。

參考文獻(xiàn)

[1]佚名. 生活垃圾分類制度實施方案[J].中華環(huán)境，2017（8）：20-21.

[2]楊艷梅.國外城市垃圾處理經(jīng)驗及對我國的啟示[J].環(huán)境保護(hù)與循環(huán)經(jīng)濟(jì)，2014，34（4）：15-18.

[3]何花.建立城市生活垃圾分類收集新模式[J].環(huán)境保護(hù)與循環(huán)經(jīng)濟(jì)，2012，32（5）：15-17.

[4]王雨帆.基于蟻群算法的多頻率垃圾收運路徑優(yōu)化研究[J].物流工程與管理，2016，38（5）：205-206.

[5]王晨頔，穆東.考慮排隊等待時間的北京市城市生活垃圾清運車輛調(diào)度優(yōu)化[J].物流工程與管理，2018，40（5）：68-70，51.

[6]張多雨.引入裝卸時間的垃圾收運路線優(yōu)化[J].物流工程與管理，2016，38（7）：125-127.

[7]雷悅，楊若凡，馬慧民.垃圾收運路線問題的蜂群優(yōu)化算法研究[J].計算機(jī)仿真，2014，31（9）：441-444.

[8]孟凡婷. 考慮節(jié)能減排的物流配送車輛路徑優(yōu)化問題研究[D]. 北京：北京交通大學(xué)，2017.

[9]王瑞明，馬慧民.生活垃圾收運車輛預(yù)防性維修分析[J].物流科技，2019，42（1）：36-40.

[10]徐東洋，李昆鵬，鄭飄，等.多車場多車型多品類供需未匹配與可任意拆分取送貨車輛路徑問題優(yōu)化[J].管理學(xué)報，2020，17（7）：1086-1095.

[11]欒玉麟，郭鵬，王麗敏.時尚行業(yè)零售網(wǎng)點多品類取送貨車輛路徑優(yōu)化研究[J].工業(yè)工程與管理，2020，25（4）：41-49.

[12]FALLAHI A E， PRINS C， CALVO R W. A memetic algorithm and a tabu search for the multi-compartment vehicle routing problem[J]. Computers and Operations Research，2006，35（5）：1725-1741.

[13]陳婧怡，邱榮祖.基于ArcGIS的多溫區(qū)冷藏車輛路徑優(yōu)化[J].上海海事大學(xué)學(xué)報，2019，40（1）：8-13.

[14]DORIGO M. Optimization， Learning and Natural Algorithms（in Italian）[D]. Politecnico di Milano， Italy：Dipartimento di Elettronica， 1992.

[15]李琳，劉士新，唐加福.改進(jìn)的蟻群算法求解帶時間窗的車輛路徑問題[J].控制與決策，2010，25（9）：1379-1383.