基于智能垃圾桶的垃圾分類動(dòng)態(tài)收運(yùn)路徑優(yōu)化問題研究

收稿日期：2022-05-23；修回日期：2022-07-15" 基金項(xiàng)目：教育部人文社科一般項(xiàng)目（19YJC630198）；中國(guó)博士后面上項(xiàng)目（2019M653345）；重慶交通大學(xué)研究生科研創(chuàng)新項(xiàng)目（2022S0064）

作者簡(jiǎn)介：閆芳（1985-），女（通信作者），河南開封人，副教授，碩導(dǎo)，博士，主要研究方向?yàn)椴淮_定理論及應(yīng)用、智能算法設(shè)計(jì)及應(yīng)用、物流交通網(wǎng)絡(luò)設(shè)計(jì)與優(yōu)化（yanfang@cqjtu.edu.cn）；鄧德萍（1998-），女，重慶開州人，碩士研究生，主要研究方向?yàn)橹腔畚锪髋c供應(yīng)鏈工程；柴福良（1968-），男，四川崇州人，高級(jí)工程師，主要研究方向?yàn)槔锪髂Ｊ郊把b備研發(fā)、垃圾預(yù)處理技術(shù)及裝備研發(fā).

摘 要：針對(duì)城市生活垃圾分類收運(yùn)過程中存在的環(huán)境二次污染和垃圾產(chǎn)生量不確定性等問題，提出了一種基于智能垃圾桶的動(dòng)態(tài)收運(yùn)車輛路徑優(yōu)化方法。建立以最小化碳排放成本、燃油消耗成本、固定成本和車輛延遲到達(dá)懲罰成本為目標(biāo)的動(dòng)態(tài)車輛路徑優(yōu)化模型。采用滾動(dòng)時(shí)域的方式將動(dòng)態(tài)問題轉(zhuǎn)換為一系列靜態(tài)問題，并設(shè)計(jì)兩階段算法進(jìn)行求解。首先采用粒子群算法對(duì)收運(yùn)車輛路徑進(jìn)行規(guī)劃，而后在每個(gè)時(shí)域末，綜合考慮待清運(yùn)垃圾桶的位置和垃圾量、垃圾收運(yùn)車輛的位置和裝載量以動(dòng)態(tài)調(diào)整現(xiàn)有車輛路徑。研究結(jié)果表明，相較于傳統(tǒng)的靜態(tài)收運(yùn)方案，動(dòng)態(tài)垃圾收運(yùn)方案能夠在降低車輛運(yùn)輸成本和碳排放成本的同時(shí)，顯著降低由于清運(yùn)不及時(shí)造成的環(huán)境二次污染的風(fēng)險(xiǎn)。

關(guān)鍵詞：垃圾分類收運(yùn)；智能垃圾桶；碳排放；動(dòng)態(tài)車輛路徑；滾動(dòng)時(shí)域；粒子群算法

中圖分類號(hào)：TP399"" 文獻(xiàn)標(biāo)志碼：A""" 文章編號(hào)：1001-3695（2022）12-014-3620-06

doi："" 10.19734/j.issn.1001-3695.2022.05.0239

Research on optimization of dynamic collection and transportation route of

garbage classification based on intelligent garbage cans

Yan Fang1， Deng Deping1， Chai Fuliang2

（1. School of Economics amp; Management， Chongqing Jiaotong University， Chongqing 400074， China; 2. Chongqing Environment amp; Sanitation Group Co， Ltd.， Chongqing 401120， China）

Abstract：

In order to solve the problem of secondary environmental pollution and uncertainty of waste generation in the process of urban domestic waste sorting and transportation， this paper proposed a dynamic vehicle collection and transportation route optimization method based on intelligent garbage cans. Taking the minimum of carbon emission cost， fuel consumption cost， fixed cost and vehicle late arrival penalty cost as the optimization objective， this paper established dynamic vehicle routing optimization model. The dynamic vehicle route optimization method transformed the dynamic problem into a series of static problems by means of rolling time domain， and designed a two-stage algorithm to solve the model. Firstly， this method used particle swarm algorithm to plan the path of the collection and transportation vehicles， and then at the end of each time domain， comprehensively considered the location of newly added garbage cans and the amount of garbage， the location and loa-ding of vehicles to dynamically adjust existing vehicle routes. The research results show that， compared with the traditional sta-tic collection and transportation scheme， the dynamic garbage collection and transportation scheme can significantly reduce the risk of secondary environmental pollution caused by untimely removal and transportation while reducing vehicle transportation costs and carbon emission costs.

Key words：garbage sorting collection and transportation; intelligent garbage cans; carbon emission; dynamic vehicle routing; rolling time domain; particle swarm algorithm

0 引言

由于城鎮(zhèn)化進(jìn)程的加快和城鄉(xiāng)環(huán)衛(wèi)一體化的推進(jìn)，城市生活垃圾量急劇增加，使得城市生活垃圾及時(shí)清運(yùn)壓力進(jìn)一步增加。據(jù)國(guó)家統(tǒng)計(jì)局和OECD 數(shù)據(jù)顯示，近幾年我國(guó)生活垃圾產(chǎn)量以 5%左右的漲幅逐年上升［1］。據(jù)統(tǒng)計(jì)，2020年全國(guó)大、中城市生活垃圾產(chǎn)生量約為2.36億噸。另一方面，2020年9月，我國(guó)在第七十五屆聯(lián)合國(guó)大會(huì)上宣布：中國(guó)力爭(zhēng)于2030年前二氧化碳排放達(dá)到峰值，努力爭(zhēng)取2060 年前實(shí)現(xiàn)“碳中和”。為響應(yīng)國(guó)家生態(tài)政策，城市生活垃圾收運(yùn)網(wǎng)絡(luò)構(gòu)建及路徑規(guī)劃過程中也須充分考慮碳排放相關(guān)因素。

然而，城市生活垃圾的產(chǎn)生量具有顯著的隨機(jī)性，這種不確定性給生活垃圾的及時(shí)清運(yùn)帶來(lái)了更大的挑戰(zhàn)。隨著智能垃圾收集終端的逐漸普及，對(duì)時(shí)變的垃圾量信息的實(shí)時(shí)收集和處理成為可能。如何有效利用數(shù)據(jù)，打破傳統(tǒng)的生活垃圾固定線路收運(yùn)模式，降低由于垃圾清運(yùn)不及時(shí)對(duì)居民生活環(huán)境造成的負(fù)影響，具有重要的理論和實(shí)踐意義。

城市生活垃圾分類收運(yùn)車輛路徑優(yōu)化問題屬于帶容量約束的車輛路徑問題（capacitated vehicle routing problem，CVRP）。目前，已有許多學(xué)者對(duì)城市生活垃圾分類收運(yùn)路徑優(yōu)化問題進(jìn)行了研究。趙今越等人［2］考慮車輛裝載容量約束、硬時(shí)間窗約束、裝載率對(duì)成本的影響，以最小化運(yùn)輸成本和車輛固定成本為目

標(biāo)建立了數(shù)學(xué)模型，來(lái)解決垃圾分類收運(yùn)路徑問題。周雙牛等人［3］考慮車輛載重對(duì)碳排放量的影響，建立了以最短路徑和極小化碳排放量為目標(biāo)的綠色垃圾收運(yùn)路徑優(yōu)化模型，并設(shè)計(jì)改進(jìn)的DMBSO算法優(yōu)化收運(yùn)路徑。Erdin等人［4］建立了基于混合整數(shù)線性規(guī)劃（MILP）的模型來(lái)優(yōu)化電動(dòng)垃圾車收運(yùn)路線。當(dāng)在收運(yùn)過程中出現(xiàn)一些突發(fā)情況，比如交通堵塞、垃圾量變化等，此時(shí)按照固定線路收運(yùn)模式可能會(huì)導(dǎo)致收運(yùn)系統(tǒng)效率低、部分收集點(diǎn)垃圾溢出等問題。Lu等人［5］將物聯(lián)網(wǎng)技術(shù)應(yīng)用于檢測(cè)垃圾桶的填充水平，僅收運(yùn)達(dá)到填充閾值的垃圾桶，可以降低環(huán)境二次污染的概率。Ghiani等人［6］利用GIS自動(dòng)識(shí)別突發(fā)事件，如垃圾車因交通堵塞而停車、在紅綠燈處停車等，以動(dòng)態(tài)規(guī)劃垃圾車的路徑，能夠提高公眾對(duì)垃圾收集系統(tǒng)的可信度。

盡管現(xiàn)有成果從不同角度對(duì)城市生活垃圾收運(yùn)的車輛路徑問題進(jìn)行了研究，但基于待收運(yùn)點(diǎn)垃圾量變化制定動(dòng)態(tài)收運(yùn)方案的研究相對(duì)較少。考慮待收運(yùn)點(diǎn)垃圾量隨機(jī)性的車輛路徑問題屬于基于動(dòng)態(tài)需求的VRP。目前，已有許多學(xué)者對(duì)此類問題進(jìn)行了研究。李陽(yáng)等人［7］針對(duì)客戶點(diǎn)不斷更新的動(dòng)態(tài)需求車輛路徑問題，依據(jù)滾動(dòng)時(shí)域?qū)ぷ鲿r(shí)間進(jìn)行劃分，并設(shè)計(jì)基于延遲服務(wù)的周期性客戶點(diǎn)實(shí)時(shí)重置策略和混合變鄰域人工蜂群算法優(yōu)化車輛路徑。范厚明等人［8］制定了連續(xù)性和周期性相結(jié)合的優(yōu)化策略來(lái)解決客戶需求動(dòng)態(tài)變化、多中心多車型的動(dòng)態(tài)車輛路徑問題。南麗君等人［9］采用了定期更新策略來(lái)解決帶時(shí)間窗的動(dòng)態(tài)需求車輛路徑問題。賈永基等人［10］提出了基于時(shí)域劃分的求解算法，在每個(gè)時(shí)域末處理動(dòng)態(tài)需求，從而實(shí)現(xiàn)車輛路徑的循環(huán)優(yōu)化與更新。然而，針對(duì)生活垃圾動(dòng)態(tài)收運(yùn)問題的研究成果相對(duì)較較少，Cao等人［11］采用灰色系統(tǒng)理論預(yù)測(cè)垃圾產(chǎn)生量，并根據(jù)垃圾量實(shí)時(shí)優(yōu)化收運(yùn)車輛路徑。Zhang等人［12］考慮季節(jié)變化、居民日常消費(fèi)和環(huán)保意識(shí)等多種因素，采用Bertsimas穩(wěn)健優(yōu)化方法來(lái)描述垃圾產(chǎn)生量的不確定性，并以此動(dòng)態(tài)調(diào)整收運(yùn)車輛路徑。

綜上，本文在現(xiàn)有研究的基礎(chǔ)上，建立以最小化碳排放成本、燃油消耗成本、固定成本和車輛延遲到達(dá)懲罰成本的垃圾分類動(dòng)態(tài)收運(yùn)路徑優(yōu)化模型；而后采用滾動(dòng)時(shí)域?qū)ぷ鲿r(shí)間進(jìn)行劃分，將動(dòng)態(tài)問題轉(zhuǎn)換為一系列靜態(tài)問題，并設(shè)計(jì)初始路徑和動(dòng)態(tài)調(diào)整兩階段算法進(jìn)行求解，并通過一系列標(biāo)準(zhǔn)算例分析了算法的有效性；最后以重慶市南岸區(qū)的垃圾收運(yùn)系統(tǒng)為例對(duì)本文提出的模型和算法的有效性作進(jìn)一步驗(yàn)證和討論。

1 問題描述與數(shù)學(xué)模型

1.1 問題描述

基于智能垃圾桶的垃圾分類動(dòng)態(tài)收運(yùn)車輛路徑問題可以描述為：一輛或多輛垃圾收運(yùn)車輛分別從中轉(zhuǎn)站出發(fā)，對(duì)區(qū)域內(nèi)可監(jiān)測(cè)垃圾填充水平的智能垃圾桶進(jìn)行收運(yùn)，車輛滿載或完成所有垃圾桶的收運(yùn)后返回中轉(zhuǎn)站。各垃圾桶的垃圾量隨時(shí)間變化，且車輛只收運(yùn)垃圾量達(dá)到閾值要求的垃圾桶，未達(dá)到閾值的延遲清運(yùn)。在車輛出發(fā)前，先對(duì)已知達(dá)到收運(yùn)閾值的垃圾桶規(guī)劃收運(yùn)路徑。隨著收運(yùn)任務(wù)進(jìn)行，會(huì)陸續(xù)新增達(dá)到收運(yùn)閾值的待清運(yùn)垃圾桶。此時(shí)，需結(jié)合新增待清運(yùn)垃圾桶的位置和垃圾量，根據(jù)當(dāng)前收運(yùn)系統(tǒng)中的車輛位置和車輛裝載量，重新規(guī)劃路徑，直到完成所有垃圾桶的收運(yùn)。

對(duì)本文的模型假設(shè)如下：

a）智能垃圾桶和中轉(zhuǎn)站的位置已知；

b）智能垃圾桶的垃圾產(chǎn)生量相互獨(dú)立，服從正態(tài)分布［13］；

c）車輛在每個(gè)智能垃圾桶作業(yè)的時(shí)長(zhǎng)相等。

1.2 符號(hào)定義

本文所涉及的模型參數(shù)及定義如表1所示。

決策變量：

xkij=1" 車輛k從節(jié)點(diǎn)i到j(luò)0" 否則

wi=1" 垃圾桶i的垃圾量超過某一閾值0" 否則

1.3 模型建立

目標(biāo)函數(shù)包括車輛運(yùn)輸?shù)娜剂舷某杀尽⑻寂欧懦杀尽⒐潭ǔ杀竞蛻土P成本。負(fù)載估計(jì)法是現(xiàn)有研究關(guān)于計(jì)算車輛燃油消耗的方法，認(rèn)為油耗是由運(yùn)輸距離和負(fù)載決定的，并以此為基礎(chǔ)對(duì)油耗消耗率進(jìn)行估計(jì)［14］。本文借鑒負(fù)載估計(jì)法計(jì)算車輛k從節(jié)點(diǎn)i到j(luò)的燃油消耗：

rkij=（r0k+r*k-r0kQk×Ckij）×dij"" k∈KR∪Ko（1）

因此，燃料消耗成本可表示為

F1=pf×∑i∈NB∪NT ∑j∈NB∪NT ∑k∈KR∪Korkij×xkij（2）

碳排放成本可表示為

F2=pc×∑i∈NB∪NT ∑j∈NB∪NT ∑k∈KR∪Koφ×rkij×xkij（3）

固定成本包括折舊費(fèi)、工資、稅費(fèi)等，可表示為

F3=∑i∈NT ∑j∈NB ∑k∈KR∪Koxkij×Pk（4）

懲罰成本：垃圾收運(yùn)車輛在規(guī)定時(shí)限之后抵達(dá)待收運(yùn)垃圾桶，可能會(huì)導(dǎo)致垃圾溢出造成環(huán)境二次污染，故對(duì)遲到的收運(yùn)作業(yè)應(yīng)制定相應(yīng)的懲罰成本，如式（5）所示。

μi（cki）=δ（cki-1） cki gt; 10 cki≤1

i∈NB，k∈KR∪Ko（5）

目標(biāo)函數(shù)可表示為

min Obj =pf×（∑i∈NB∪NT ∑j∈NB∪NT ∑k∈KR∪Korkij×xkij）+

pc×（∑i∈NB∪NT ∑j∈NB∪NT ∑k∈KR∪Koφ×rkij×xkij）+

∑i∈NT ∑j∈NB ∑k∈KR∪Koxkij×Pk+∑i∈NBμi（cki）（6）

車輛從中轉(zhuǎn)站出發(fā)到各個(gè)滿足收運(yùn)條件的垃圾收集點(diǎn)，對(duì)可回收垃圾和其他垃圾進(jìn)行收運(yùn)。式（7）表示流量平衡約束。式（8）表示子回路約束，其中|Sk|表示車輛k收運(yùn)垃圾桶的數(shù)量。式（9）表示每輛可回收垃圾收運(yùn)車有且僅訪問每個(gè)站點(diǎn)一次。式（10）表示每輛其他垃圾收運(yùn)車有且僅訪問每個(gè)站點(diǎn)一次。式（11）表示車容量約束。式（12）表示車輛的發(fā)車時(shí)間。式（13）表示車輛k到達(dá)節(jié)點(diǎn)j的時(shí)間。

∑i∈NB∪NTxkij=∑i∈NB∪NTxkji" j∈NB∪NT，k∈KR∪Ko（7）

∑i∈NB∪NT ∑j∈NB∪NTxkij≤|Sk|" k∈KR∪Ko（8）

∑j∈NB∪NT ∑k∈KRxkij=1" i∈NB∪NT（9）

∑j∈NB∪NT ∑k∈Koxkij=1" i∈NB∪NT（10）

∑i∈NB ∑j∈NB∪NTq×cki×xkij≤Qk（11）

tk≥min{t|∑i∈NBqit×wi≥αQ}" k∈KR∪Ko（12）

tjk =tk+tks（∑i∈NB∪NT ∑j∈NB∪NTxkij-1）+

∑i∈NB∪NT ∑j∈NB∪NTxkij×dijvk k∈KR∪Ko（13）

2 算法設(shè)計(jì)

本文考慮收運(yùn)車輛作業(yè)過程中垃圾產(chǎn)生量的隨機(jī)性，采用滾動(dòng)時(shí)域的方式將工作時(shí)長(zhǎng)T等分為多個(gè)時(shí)域，新增待作業(yè)任務(wù)V會(huì)隨時(shí)間順序進(jìn)入相應(yīng)的時(shí)域，垃圾收運(yùn)方案P在時(shí)域間連續(xù)傳遞、迭代，進(jìn)而將動(dòng)態(tài)問題轉(zhuǎn)換為一系列靜態(tài)問題。滾動(dòng)時(shí)域動(dòng)態(tài)優(yōu)化過程如圖1所示。

具體求解過程分為初始路徑階段和動(dòng)態(tài)調(diào)整階段。在垃圾收運(yùn)車輛出發(fā)前，確定垃圾收運(yùn)閾值、待收運(yùn)垃圾桶的位置和需要的車輛數(shù)量，采用粒子群算法對(duì)收運(yùn)車輛的初始路徑進(jìn)行規(guī)劃。隨著車輛收運(yùn)任務(wù)的執(zhí)行，時(shí)域向后滾動(dòng)，在每個(gè)時(shí)域末更新系統(tǒng)信息并調(diào)整車輛路徑。更新的信息包括正在執(zhí)行收運(yùn)任務(wù)的車輛數(shù)量、車輛載重、車輛位置以及新增垃圾桶的數(shù)量、位置、垃圾量。若存在新增達(dá)到收運(yùn)閾值的垃圾桶，則在車輛載重約束下，按照目標(biāo)函數(shù)增加最小的規(guī)則，將新增任務(wù)插入現(xiàn)有路徑。剩余不滿足車輛載重的新增待作業(yè)垃圾桶，劃歸待規(guī)劃垃圾桶集合S，利用PSO算法規(guī)劃路徑進(jìn)行收運(yùn)。若不存在新增達(dá)到收運(yùn)閾值的垃圾桶，車輛路徑保持不變，直到完成所有垃圾桶的收運(yùn)。算法流程如圖2所示。

2.1 初始路徑算法設(shè)計(jì)

1）車輛數(shù)量

為滿足動(dòng)態(tài)調(diào)整階段的收運(yùn)任務(wù)，在利用PSO算法規(guī)劃路徑前，應(yīng)確定收運(yùn)車輛的數(shù)量。式（14）為車輛數(shù)量的計(jì)算規(guī)則。

Nveh=「∑i∈NB（qi′+Δqi′）α×Q（14）

其中：α為車輛發(fā)車閾值；Q為車輛最大載重；qi′為當(dāng)前系統(tǒng)中達(dá)到收運(yùn)閾值各垃圾桶i的垃圾量；Δqi′為車輛從中轉(zhuǎn)站出發(fā)行駛至各個(gè)垃圾桶i期間，各垃圾桶的垃圾增量，Δqi′服從正態(tài)分布。

2）PSO粒子的編碼與解碼

粒子群算法（PSO）是由Kennedy和Eberhart在1995年提出的一種智能算法［15］。它通過個(gè)體最優(yōu)以及群體最優(yōu)修正粒子速度，迭代尋找滿意解。粒子群算法求解車輛路徑問題需要經(jīng)過編碼和解碼步驟。本文借鑒Wu等人［13］的編/解碼方式，構(gòu)造3×N維向量矩陣解決有N個(gè)垃圾桶的垃圾收運(yùn)車輛路徑問題。第一維表示車輛序號(hào)向量；第二維表示垃圾桶序號(hào)向量；第三維表示車輛訪問垃圾桶的排序向量，是［0，1］的隨機(jī)數(shù)。圖3的編碼矩陣為PSO算法的一個(gè)粒子。設(shè)置中轉(zhuǎn)站編號(hào)為0，根據(jù)解碼規(guī)則，收運(yùn)垃圾的車輛路徑如解碼矩陣所示。

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

Fitness=Obj+M∑k∈KR∪Komax{∑i∈NB ∑j∈NB∪NTqixkij-Q，0}（15）

其中：Fitness表示適應(yīng)度函數(shù)；Obj表示解碼后的目標(biāo)函數(shù)值；M是一個(gè)足夠大的正數(shù)。當(dāng)車輛在路徑中的載重超過車輛的最大載重Q時(shí)，即∑i∈NB ∑j∈NB∪NTqixkij gt; Q時(shí)，M可以使得粒子的適應(yīng)度值變大。

4） 粒子狀態(tài)更新

在每一次迭代中，粒子通過跟蹤兩個(gè)極值來(lái)更新位置。粒子自身找到的最優(yōu)解pbest，整個(gè)種群找到的最優(yōu)解gbest。

vi（t+1） =ωi（t）×vi（t）+c1×rand（）×（pbesti（t）-xi（t））+

c2×rand（）×（gbesti（t）-xi（t））（16）

vi（t+1）=vmax if vi（t+1）gt;vmax

vi（t+1）=vmin if vi（t+1）lt;vmax（17）

xi（t+1）=xi（t）+vi（t+1）（18）

ω（t）=ω（T）+T－tT［ω（1）－ω（T）］（19）

式（16）表示速度更新公式，其中c1、c2表示學(xué)習(xí)因子。式（17）限定了速度的范圍。式（18）表示位置更新公式。ω為慣性權(quán)重，動(dòng)態(tài)ω具有更好的尋優(yōu)效果［16］，因此本文采用線性遞減權(quán)重策略，具體如式（19）所示。其中ω（t）表示第t代的慣性權(quán)重，ω（1）表示初始時(shí)的慣性權(quán)重，ω（T）表示終止時(shí)的慣性權(quán)重。

2.2 動(dòng)態(tài)優(yōu)化算法設(shè)計(jì)

在滾動(dòng)時(shí)域末，更新的信息包括當(dāng)前執(zhí)行收運(yùn)任務(wù)的車輛數(shù)量、車輛載重、車輛位置以及新增垃圾桶的數(shù)量、位置、垃圾量。在當(dāng)前路徑執(zhí)行插入操作之前，各收運(yùn)車輛應(yīng)為已規(guī)劃但未收運(yùn)的垃圾桶預(yù)留收運(yùn)空間。根據(jù)車輛的載重盈余ΔQk、垃圾量qi′以及車輛從當(dāng)前位置行駛至新增垃圾桶時(shí)間段內(nèi)的新增垃圾桶的垃圾增量Δqi′，設(shè)置車載約束：

qi′+Δqi′≤ΔQk" i∈NB，k∈KR∪KO（20）

若滿足式（20），則按照目標(biāo)函數(shù)增加最小的規(guī)則，將該垃圾桶插入相應(yīng)收運(yùn)路徑；否則將該垃圾桶劃歸待規(guī)劃垃圾桶集合S，并按照初始路徑算法為新派車輛規(guī)劃收運(yùn)路徑。

3 算例分析

進(jìn)行算例驗(yàn)證分析時(shí)，相關(guān)參數(shù)的設(shè)定為：垃圾桶產(chǎn)生的垃圾量服從正態(tài)分布［13］、垃圾收運(yùn)閾值為w、垃圾桶的容量為0.5 t、垃圾收運(yùn)車輛裝載量為6 t；PSO算法中初始種群個(gè)數(shù)20、學(xué)習(xí)因子c為1.5、迭代次數(shù)為1 000；空載油耗率r0為0.16 L/km、滿載油耗率r*為0.377 L/km、單位燃油碳排放系數(shù)φ為3.15 kg/L、單位燃料價(jià)格pf為8 CNY/kg、單位碳排放價(jià)格pc為0.025 CNY/kg；車輛固定成本為100 CNY/輛。本文算法編程工具采用MATLAB r2020b，操作系統(tǒng)為 Windows 10，電腦內(nèi)存 8.00 GB，CPU為雙核酷睿i7-9750H，主頻2.6 GHz。

3.1 標(biāo)準(zhǔn)算例

為驗(yàn)證算法的有效性，選取帶容量約束的車輛路徑問題（CVRP）基準(zhǔn)數(shù)據(jù)庫(kù)（數(shù)據(jù)集：Christofides and Eilon，1969）進(jìn)行結(jié)果對(duì)比分析。本文從數(shù)據(jù)庫(kù)中選取小規(guī)模算例3個(gè)（E-n22-k4、E-n23-k3、E-n33-k4），中規(guī)模算例2個(gè)（E-n51-k5、E-n76-k8），大規(guī)模算例1個(gè)（E-n101-k8）。

3.1.1 標(biāo)準(zhǔn)算例垃圾收運(yùn)閾值靈敏度分析

垃圾收運(yùn)閾值決定了車輛執(zhí)行收運(yùn)任務(wù)時(shí)，垃圾桶的最低垃圾量。若垃圾收運(yùn)閾值設(shè)置得過低，收運(yùn)時(shí)垃圾桶還有較多空間收集垃圾，則會(huì)因?yàn)檫^早執(zhí)行清運(yùn)任務(wù)而造成系統(tǒng)效率低下；若垃圾收閾值設(shè)置得過高，收運(yùn)時(shí)垃圾溢出，則會(huì)造成環(huán)境二次污染，影響居民生活環(huán)境［5］。可見，垃圾收運(yùn)閾值的設(shè)置非常重要。Wu等人［13］通過算例測(cè)試發(fā)現(xiàn)垃圾收運(yùn)閾值在0.65～0.75可以獲得最優(yōu)值。Hannan等人［17］發(fā)現(xiàn)垃圾收運(yùn)閾值設(shè)置為0.7能夠?qū)崿F(xiàn)最大的成本節(jié)約和碳排放減少。文獻(xiàn)［18，19］認(rèn)為垃圾收運(yùn)閾值在0.7～0.75能夠縮短收運(yùn)距離、提高收運(yùn)效率、減少燃料消耗和二氧化碳排放。Lu等人［5］將垃圾收運(yùn)閾值設(shè)置為0.6進(jìn)行算例驗(yàn)證。本文選取小規(guī)模算例E-n22-k4、中規(guī)模算例E-n51-k5和大規(guī)模算例E-n101-k8為代表作靈敏度分析，垃圾收運(yùn)閾值設(shè)置0.5起以0.1為步長(zhǎng)遞增至0.9，在每個(gè)預(yù)設(shè)閾值下求解10次，并以本文的總成本、碳排放成本和距離為對(duì)比指標(biāo)，求解結(jié)果如表2～4所示。其中best、aver 表示算法所求解的最小值和平均值。

由表2可知，在小規(guī)模算例E-n22-k4中，當(dāng)w=0.6時(shí)，成本、碳排放、距離的最小值和平均值都較優(yōu)。由表3可知，在中規(guī)模算例E-n51-k5中，當(dāng)w=0.5時(shí)，成本的最小值較優(yōu)；當(dāng)w=0.6時(shí)，成本的平均值以及碳排放、距離的最小值和平均值都較優(yōu)。由表4可知，在大規(guī)模算例E-n101-k8中，當(dāng)w=0.7時(shí)，成本的最小值較優(yōu)；當(dāng)w=0.6時(shí)，成本的平均值以及碳排放、距離的最小值和平均值都較優(yōu)。綜上，考慮算法求解質(zhì)量和穩(wěn)定性，在本文的垃圾分類動(dòng)態(tài)收運(yùn)車輛路徑問題中，針對(duì)CVRP基準(zhǔn)數(shù)據(jù)庫(kù)的小規(guī)模算例、中規(guī)模算例以及大規(guī)模算例都應(yīng)選取w=0.6參與后續(xù)算例求解和分析。

3.1.2 計(jì)算結(jié)果分析

為了驗(yàn)證不同客戶規(guī)模算例下算法的有效性。將目標(biāo)函數(shù)改為與文獻(xiàn)［20］一致的碳排放成本、燃油消耗成本和固定成本，并選取LSHA和PSO算法［20］對(duì)CVRP數(shù)據(jù)集求解結(jié)果進(jìn)行對(duì)比分析。在垃圾收運(yùn)閾值w=0.6時(shí)，對(duì)各算例重復(fù)求解10次，得到總成本、碳排放成本和距離的平均值，求解結(jié)果如表5所示。表6是在總成本、碳排放成本、距離指標(biāo)上本文算法相較于LSHA和PSO算法的改進(jìn)效果分析。

由表5、6可知，本文設(shè)計(jì)的算法在各規(guī)模算例上，總成本、碳排放和距離都優(yōu)于LSHA和PSO算法，尋優(yōu)能力較強(qiáng)。相較于LSHA算法，總成本和碳排放指標(biāo)都在小規(guī)模算例E-n22-k4上的改進(jìn)最為顯著，分別為16.1%和29.24%；距離指標(biāo)在小規(guī)模算例E-n33-k4上的改進(jìn)最為顯著，為30.09%。相較于PSO算法，總成本和碳排放指標(biāo)都在小規(guī)模算例E-n22-k4上的改進(jìn)最為顯著，分別為23.26%和36.53%；距離指標(biāo)在小規(guī)模算例E-n33-k4上的改進(jìn)最為顯著，為37.38%。綜上，本文設(shè)計(jì)算法尋優(yōu)能力較強(qiáng)，能夠有效求解城市生活垃圾收運(yùn)動(dòng)態(tài)車輛路徑問題。

3.2 仿真算例

為進(jìn)一步驗(yàn)證算法的有效性，選取重慶市南岸區(qū)的50個(gè)垃圾桶和1個(gè)垃圾中轉(zhuǎn)站，對(duì)可回收垃圾的收運(yùn)進(jìn)行模擬，其他垃圾的收運(yùn)與可回收垃圾收運(yùn)的規(guī)劃方法相同。標(biāo)號(hào)0為垃圾中轉(zhuǎn)站，標(biāo)號(hào)1～50為垃圾桶，中轉(zhuǎn)站及垃圾桶的分布如圖4所示。

3.2.1 仿真算例垃圾收運(yùn)閾值靈敏度分析

將垃圾收運(yùn)閾值設(shè)置為0.5起，以0.1為步長(zhǎng)遞增至0.9，在每個(gè)預(yù)設(shè)閾值下對(duì)該仿真算例求解10次，求解得到總成本、碳排放成本的最小值best和平均值aver如表7所示。

由表7可知，針對(duì)仿真算例，在垃圾收運(yùn)閾值w由0.5遞增至0.9過程中，總成本和碳排放成本的平均值和最小值呈現(xiàn)U型變化趨勢(shì)。其中，當(dāng)w=0.6時(shí)，碳排放成本的最小值較優(yōu)；當(dāng)w=0.7時(shí)，碳排放成本的平均值以及距離的最小值和平均值都較優(yōu)。因此，在該規(guī)模的仿真算例中，垃圾收運(yùn)閾值為w=0.7時(shí)總體效果最好。

3.2.2 仿真結(jié)果分析

設(shè)置該仿真算例的垃圾收運(yùn)閾值w=0.7，滾動(dòng)時(shí)域的時(shí)間間隔為30 min，垃圾產(chǎn)生量服從正態(tài)分布N（μ，σ2），其中μ=0.35，σ=0.1。

1）車輛初始收運(yùn)路徑

由于垃圾桶的垃圾產(chǎn)生量具有隨機(jī)性，所以單次運(yùn)行結(jié)果方案會(huì)存在不同。本次求解過程中，在60 min時(shí)刻，系統(tǒng)提出發(fā)車需求。達(dá)到收運(yùn)閾值的垃圾桶序號(hào)為：1、4、5、6、7、10、14、15、22 、25、26、28、30、36、43。利用粒子群算法規(guī)劃得到車輛初始收運(yùn)路徑如表8所示。

2）實(shí)時(shí)信息下的收運(yùn)方案調(diào)整

在90 min時(shí)刻，新增達(dá)到收運(yùn)閾值的垃圾桶序號(hào)為2、3、16、17、18、20、21、27、32、40、41、44、45、47、50。此時(shí)，車輛1已完成垃圾桶10、7、6、5的清運(yùn)作業(yè)，車輛2已完成垃圾桶22、28、26、25、43的清運(yùn)作業(yè)。在滿足車載約束的條件下，按照目標(biāo)函數(shù)增加最小的規(guī)則，將新增垃圾桶插入未完成清運(yùn)作業(yè)的路徑。

在120 min時(shí)刻，新增達(dá)到收運(yùn)閾值的垃圾桶序號(hào)為8、11、12、19、23、24、31、33、35、48。此時(shí)，車輛1和2都不滿足車容量約束。因此，新派車輛對(duì)新增的垃圾桶進(jìn)行清運(yùn)作業(yè)。

在150 min時(shí)刻，新增達(dá)到收運(yùn)閾值的垃圾桶序號(hào)為13、29、37、39、42、46。此時(shí)，車輛3已完成垃圾桶23、19、8、12的清運(yùn)作業(yè)，車輛4已完成垃圾桶33、35、48的清運(yùn)作業(yè)。將新增垃圾桶插入未完成清運(yùn)作業(yè)的路徑。

在180 min時(shí)刻，新增達(dá)到收運(yùn)閾值的垃圾桶序號(hào)為9、34、38、49。此時(shí)，車輛3已完成清運(yùn)作業(yè)返回中轉(zhuǎn)站，車輛4已完成垃圾桶33、35、48、29、24、31、42、37的清運(yùn)作業(yè)。因此，將新增垃圾桶插入車輛4未完成清運(yùn)作業(yè)的路徑。此時(shí)，已為所有垃圾桶規(guī)劃收運(yùn)的車輛路徑，待所有車輛返回中轉(zhuǎn)站則完成此次垃圾清運(yùn)作業(yè)。利用本文設(shè)計(jì)的算法求解，完成此次垃圾收運(yùn)方案需要收運(yùn)車輛4輛；總成本973元；碳排放成本141元。具體收運(yùn)車輛動(dòng)態(tài)調(diào)整路徑如表9所示。

此外，為了驗(yàn)證本文提出的垃圾動(dòng)態(tài)收運(yùn)方案的有效性，對(duì)仿真算例分別以靜態(tài)收運(yùn)方案和動(dòng)態(tài)收運(yùn)方案重復(fù)求解10次，得到總成本、碳排放成本以及懲罰成本的平均值如表10所示。其中靜態(tài)收運(yùn)方案不考慮垃圾收運(yùn)閾值，在車輛出發(fā)前以最小化碳排放成本、燃油消耗成本和固定成本為目標(biāo)，采用粒子群算法規(guī)劃所有垃圾桶的收運(yùn)路徑。

由表10可知，相較于傳統(tǒng)的靜態(tài)收運(yùn)方案，本文提出的垃圾動(dòng)態(tài)收運(yùn)方案在懲罰成本上的改進(jìn)最為顯著，為55.73%，在總成本上改進(jìn)了19.78%，在碳排放成本上改進(jìn)了1.44%。因此，本文設(shè)計(jì)的垃圾動(dòng)態(tài)收運(yùn)策略不僅能夠降低車輛運(yùn)輸成本和碳排放成本，還能夠有效降低由于清運(yùn)不及時(shí)造成的環(huán)境二次污染的風(fēng)險(xiǎn)。

4 結(jié)束語(yǔ)

本文研究了針對(duì)垃圾分類的動(dòng)態(tài)收運(yùn)車輛路徑問題，基于生活垃圾收運(yùn)的公益性和特殊性，建立以最小化碳排放成本、燃油消耗成本、固定成本和車輛延遲到達(dá)懲罰成本的垃圾分類收運(yùn)路徑優(yōu)化模型。采用滾動(dòng)時(shí)域的方式將動(dòng)態(tài)問題轉(zhuǎn)換為一系列靜態(tài)問題，并設(shè)計(jì)兩階段算法進(jìn)行求解。首先采用粒子群算法對(duì)收運(yùn)車輛路徑進(jìn)行規(guī)劃，而后在每個(gè)時(shí)域末，綜合考慮待收運(yùn)垃圾桶的位置和垃圾量、收運(yùn)車輛的位置和裝載量以動(dòng)態(tài)調(diào)整車輛路徑。研究結(jié)果表明，相較于傳統(tǒng)的靜態(tài)收運(yùn)方案，本文提出的垃圾動(dòng)態(tài)收運(yùn)方案能夠在降低車輛運(yùn)輸成本和碳排放成本的同時(shí)，顯著降低由于清運(yùn)不及時(shí)造成的環(huán)境二次污染的風(fēng)險(xiǎn)。針對(duì)每個(gè)時(shí)域末，已完成當(dāng)前清運(yùn)作業(yè)但仍有裝載盈余的車輛，在后續(xù)研究中還將考慮延遲其返回中轉(zhuǎn)站的時(shí)間以收運(yùn)更多垃圾桶，從而提高收運(yùn)系統(tǒng)的效率，構(gòu)建性能更優(yōu)的求解算法。

參考文獻(xiàn)：

［1］牟能冶，程馳堯，蔣爾偉，等. 基于多車型多行程的城市生活垃圾分類運(yùn)輸路徑優(yōu)化 ［J］. 安全與環(huán)境學(xué)報(bào)，2022，22（4）： 2199-2208. （Mu Nengzhi，Cheng Chiyao，Jiang Erwei，et al. Urban solid waste classification and transportation path optimization based on multi-vehicle and multi-journey［J］. Journal of Safety and Environment，2022，22（4）： 2199-2208.）

［2］趙今越，馬良，劉勇. 垃圾分類收運(yùn)路徑問題的新型混合蟻群算法求解 ［J］. 計(jì)算機(jī)應(yīng)用研究，2021，38（5）： 1428-1433. （Zhao Jinyue，Ma Liang，Liu Yong. A novel hybrid ant colony algorithm for solving the path problem of garbage classification collection and transportation ［J］. Application Research of Computers，2021，38（5）： 1428-1433.）

［3］周雙牛，李稚，王喆. 低碳視角下改進(jìn)DMBSO算法的垃圾收運(yùn)路徑優(yōu)化 ［J］. 科學(xué)技術(shù)與工程，2021，21（23）： 9932-9939. （Zhou Shuangniu，Li Zhi，Wang Zhe. Optimization of garbage collection and transportation path based on improved DMBSO algorithm from the perspective of low carbon ［J］. Science Technology and Enginee-ring，2021，21（23）： 9932-9939.）

［4］Erdin O，Yetilmezsoy K，Erenolu A K，et al. Route optimization of an electric garbage truck fleet for sustainable environmental and energy management ［J］. Journal of Cleaner Production，2019，234： 1275-1286.

［5］Lu Xulong，Pu Xujin，Han Xiaohua. Sustainable smart waste classification and collection system： a bi-objective modeling and optimization approach ［J］. Journal of Cleaner Production，2020，276： 124183.

［6］Ghiani G，Guerrieri A，Manni A，et al. Estimating travel and service times for automated route planning and service certification in municipal waste management ［J］. Waste Management，2015，46： 40-46.

［7］李陽(yáng)，范厚明，張曉楠. 動(dòng)態(tài)需求下車輛路徑問題的周期性優(yōu)化模型及求解 ［J］. 中國(guó)管理科學(xué)，2022，30（8）：254-266. （Li Yang，F(xiàn)an Houming，Zhang Xiaonan. Periodic optimization model and solution of vehicle routing problem under dynamic demand ［J］. Chinese Management Science，2022，30（8）：254-266.）

［8］范厚明，張躍光，田攀俊，等. 時(shí)變路網(wǎng)下異型車輛動(dòng)態(tài)配置與路徑優(yōu)化 ［J］. 系統(tǒng)工程理論與實(shí)踐，2022，42（2）： 455-470. （Fan Houming，Zhang Yueguang，Tian Panjun，et al. Dynamic configuration and path optimization of special-shaped vehicles under time-varying road network ［J］. Systems Engineering Theory and Practice，2022，42（2）： 455-470.）

［9］南麗君，陳彥如，張宗成. 改進(jìn)的自適應(yīng)大規(guī)模鄰域搜索算法求解動(dòng)態(tài)需求的混合車輛路徑問題 ［J］. 計(jì)算機(jī)應(yīng)用研究，2021，38（10）： 2926-2934. （Nan Lijun，Chen Yanru，Zhang Zongcheng. An improved adaptive large-scale neighborhood search algorithm for mixed vehicle routing problems with dynamic demands ［J］. Application Research of Computers，2021，38（10）： 2926-2934.）

［10］賈永基，丁慧娜，李嘉，等. 考慮時(shí)變速度和動(dòng)態(tài)需求的電動(dòng)車輛路徑問題 ［J］. 工業(yè)工程與管理，2022，27（2）： 59-66. （Jia Yongji，Ding Huina，Li Jia，et al. Electric vehicle routing problem considering time-varying speed and dynamic demand ［J］. Industrial Engineering and Management，2022，27（2）： 59-66.）

［11］Cao Bin，Chen Xinghan，Lyu Zhihan，et al. Optimization of classified municipal waste collection based on the internet of connected vehicles ［J］. IEEE Trans on Intelligent Transportation Systems，2021，22（8）： 5364-5373.

［12］Zhang Sicheng，Zhang Jianwen，Zhao Zhiwei，et al. Robust optimization of municipal solid waste collection and transportation with uncertain waste output： a case study ［J］. Journal of Systems Science and Systems Engineering，2021，31（2）： 204-225.

［13］Wu Hailin，Tao Fengming，Qiao Qingqing，et al. A chance-constrained vehicle routing problem for wet waste collection and transportation considering carbon emissions ［J］. International Journal of Environmental Research and Public Health，2020，17（2）： 458.

［14］陳玉光，陳志祥. 基于準(zhǔn)時(shí)送貨和最小耗油的配送車輛路徑問題研究 ［J］. 中國(guó)管理科學(xué)，2015，23（S1）： 156-164. （Chen Yuguang，Chen Zhixiang. Research on delivery vehicle routing problem based on on-time delivery and minimum fuel consumption ［J］. Chinese Management Science，2015，23（S1）： 156-164.）

［15］Eberhart R，Kennedy J. A new optimizer using particle swarm theory ［C］// Proc of the 6th International Symposium on Micro Machine and Human Science. Piscataway，NJ： IEEE Press，1995： 39-43.

［16］閆芳，彭婷婷. 基于時(shí)空聚類求解帶容積約束的選址—路徑問題 ［J］. 控制與決策，2020，36（10）： 2504-2510. （Yan Fang，Peng Tingting. Study on capacitate location-routing problem based on time-space cluster ［J］. Control and Decision，2020，36（10）： 2504-2510.）

［17］Hannan M A，Begum R A，Al-Shetwi A Q，et al. Waste collection route optimisation model for linking cost saving and emission reduction to achieve sustainable development goals ［J］. Sustainable Cities and Society，2020，62： 102393.

［18］Akhtar M，Hannan M A，Begum R A，et al. Backtracking search algorithm in CVRP models for efficient solid waste collection and route optimization ［J］. Waste Management，2017，61： 117-128.

［19］Hannan M A，Akhtar M，Begum R A，et al. Capacitated vehicle-routing problem model for scheduled solid waste collection and route optimization using PSO algorithm ［J］. Waste Management，2018，71： 31-41.

［20］Wu Hailin，Tao Fengming，Yang Bo. Optimization of vehicle routing for waste collection and transportation ［J］. International Journal of Environmental Research and Public Health，2020，17（14）： 496.