垃圾分類收運(yùn)模式下車輛路徑問題建模與仿真

狄衛(wèi)民 王 然

(鄭州大學(xué)管理工程學(xué)院 河南 鄭州 450001)

0 引 言

垃圾分類收運(yùn)問題屬于車輛路徑問題范疇，為普遍推行垃圾分類制度，亟需解決垃圾分類收運(yùn)車輛路徑問題，建立與垃圾種類相匹配的低成本收運(yùn)體系。

在傳統(tǒng)車輛路徑相關(guān)文獻(xiàn)研究中，大多考慮了車輛裝載能力限制。例如：賀冰倩等[2]考慮車輛最大載重量和最大體積約束，研究了快遞收派混合車輛路徑優(yōu)化問題，設(shè)計(jì)了改進(jìn)的禁忌搜索算法進(jìn)行求解；呂俊杰等[3]則研究了基于客戶分流策略的配送中心車輛路徑問題，設(shè)計(jì)改進(jìn)的遺傳算法進(jìn)行求解。針對單中心單車型車輛路徑優(yōu)化問題，胡乃平等[4]主要考慮時(shí)間約束建立數(shù)學(xué)模型，利用分解協(xié)調(diào)算法和遺傳算法求解；Qi等[5]則考慮時(shí)間窗建立多目標(biāo)數(shù)學(xué)模型，設(shè)計(jì)了一種基于模因算法的多目標(biāo)進(jìn)化算法求解。針對單中心多車型車輛路徑優(yōu)化問題，葛顯龍等[6]主要考慮碳排放因素和時(shí)間窗建立數(shù)學(xué)模型，設(shè)計(jì)了一種結(jié)合聚類分析方法和掃描算法的混合遺傳算法求解；何東東等[7]主要考慮車輛行駛過程中產(chǎn)生的油耗和碳排放量建立數(shù)學(xué)模型，設(shè)計(jì)了改進(jìn)的禁忌搜索算法求解；郭海湘等[8]主要考慮車輛碳排放量建立數(shù)學(xué)模型，設(shè)計(jì)了混合啟發(fā)式算法、混合遺傳算法和混合蟻群算法進(jìn)行求解。針對多中心多車型車輛路徑優(yōu)化問題，陳呈頻等[9]建立整數(shù)規(guī)劃模型，設(shè)計(jì)了多染色體遺傳算法進(jìn)行求解。

一些文獻(xiàn)又考慮了產(chǎn)品的特殊性研究車輛路徑優(yōu)化問題。其中，針對多產(chǎn)品單車型車輛路徑優(yōu)化問題，陳久梅等[10]考慮不同生鮮農(nóng)產(chǎn)品對冷藏環(huán)境的要求不同，建立生鮮農(nóng)產(chǎn)品多隔室車輛路徑優(yōu)化模型，利用粒子群算法進(jìn)行求解；Zhang等[11]又考慮產(chǎn)品體積限制和產(chǎn)品破損成本建立數(shù)學(xué)模型，利用遺傳算法求解；Azi等[12]考慮車輛由于時(shí)間限制而執(zhí)行多條路線的情況建立數(shù)學(xué)模型，設(shè)計(jì)了基于列生成算法的精確算法求解。針對多產(chǎn)品多車型車輛路徑優(yōu)化問題，劉家利等[13]考慮了企業(yè)運(yùn)力不足時(shí)可租賃外部車輛的情況，建立混合整數(shù)規(guī)劃模型，設(shè)計(jì)了兩階段自適應(yīng)遺傳算法求解。針對城市生活垃圾車輛收運(yùn)路徑優(yōu)化問題，吳勇剛等[14]分別建立基于收運(yùn)路程和基于車輛行駛時(shí)間的數(shù)學(xué)規(guī)劃模型，利用遺傳算法求解；雷悅等[15]則采用帶站的標(biāo)準(zhǔn)數(shù)學(xué)模型，利用蜂群優(yōu)化算法求解。然而這些文獻(xiàn)均未考慮垃圾分類以及不同種類的垃圾需由不同類型車輛收運(yùn)的情況。

綜上，本文考慮垃圾分類以及垃圾種類-車輛類型匹配的情況，研究多種類多車型的垃圾收運(yùn)車輛路徑優(yōu)化問題，建立數(shù)學(xué)模型，利用遺傳算法求解。

1 問題描述與模型建立

1.1 問題描述

城市居民產(chǎn)生的生活垃圾，自行或由物業(yè)人員分類投放到指定垃圾站，每一個(gè)垃圾站內(nèi)不同種類的垃圾需要由指定類型的車輛收運(yùn)到垃圾中轉(zhuǎn)站進(jìn)行處理(例如：大件垃圾拆解、可回收物收集貯存、有害垃圾收集貯存、廚余垃圾預(yù)處理等)，處理后產(chǎn)生的固體垃圾再分別運(yùn)到大型垃圾分揀中心、焚燒廠、填埋廠、回收廠等處理廠進(jìn)行二次處理。由于集中到垃圾中轉(zhuǎn)站的垃圾量較大，一般只需直運(yùn)到各處理廠，因此不考慮該部分的車輛路徑問題。又由于生活垃圾收運(yùn)受到行政區(qū)規(guī)劃的影響，本文只考慮單個(gè)行政區(qū)內(nèi)含有一個(gè)垃圾中轉(zhuǎn)站的情況。在車輛類型有限、垃圾種類有限、車輛類型與垃圾種類匹配、不同類型的車輛有不同的裝載能力限制、垃圾站內(nèi)每一種類型的垃圾量均不超過車輛最大裝載能力限制的情況下，為了使車輛啟動(dòng)成本與運(yùn)輸成本之和最小，需要解決的問題有：

(1) 垃圾中轉(zhuǎn)站需要分別擁有各類型車輛各幾輛。

(2) 每一輛車需要服務(wù)哪幾個(gè)垃圾站及其收運(yùn)順序。

1.2 符號說明

為便于模型建立，設(shè)定如下符號：有m個(gè)垃圾站，記為I={1,2,…,m}；1個(gè)垃圾中轉(zhuǎn)站，記為m+1；g種車輛類型，記為W={1,2,…,g}；h輛車，記為V={1,2,…,h}；s種垃圾類型，記為P={1,2,…,s}；w類型車輛的運(yùn)載能力記為Capw；w類型車輛的單位距離運(yùn)輸成本記為cw；w類型車輛的啟動(dòng)費(fèi)用記為rw；垃圾站i的p類垃圾的量記為dip；記節(jié)點(diǎn)a、b∈U={1,2,…,m,m+1}，節(jié)點(diǎn)a與節(jié)點(diǎn)b之間的距離記為tab；若車輛v屬于w類型車輛，則ovw為1，否則為0；若w類型車輛可收運(yùn)p類垃圾，則qwp為1，否則為0。決策變量：若車輛v啟動(dòng)，則xv為1，否則為0；若車輛v從節(jié)點(diǎn)a到節(jié)點(diǎn)b，則yabv為1，否則為0。

1.3 數(shù)學(xué)模型

建立如下數(shù)學(xué)模型：

(1)

(2)

(3)

(4)

yaiv+yiav≤1a,i=1,2,…,m，v=1,2,…,h

(5)

(6)

yabv≤xva,b=1,2,…,m+1，v=1,2,…,h

(7)

xv∈{0,1}v=1,2,…,h

(8)

yabv∈{0,1}a,b=1,2,…,m+1，v=1,2,…,h

(9)

式(1)為目標(biāo)函數(shù)，表示最小化車輛啟動(dòng)成本和運(yùn)輸成本之和；式(2)表示每個(gè)垃圾站i只有1輛w類型車輛經(jīng)過；式(3)表示車輛v必須從垃圾中轉(zhuǎn)站j出發(fā)并返回；式(4)表示車輛v最多服務(wù)某一垃圾站i一次；式(5)表示車輛v只能在垃圾站之間單向行駛；式(6)表示車輛v的裝載能力限制；式(7)表示車輛v啟動(dòng)約束；式(8)、式(9)為0-1約束。

2 算 法

考慮到建立的多種類多車型垃圾收運(yùn)車輛路徑優(yōu)化模型的復(fù)雜性，采用遺傳算法進(jìn)行求解。根據(jù)模型多維度的特點(diǎn)，提出基于車輛類型的染色體編碼方法、基于車輛裝載能力限制的染色體解碼方法，算法主要功能模塊如下。

2.1 染色體編碼

基于車輛類型的染色體編碼方法，能夠保證每個(gè)垃圾站內(nèi)的每種垃圾都能夠被相匹配的車輛收運(yùn)1次，滿足垃圾種類-車輛類型匹配和車輛服務(wù)限制約束。編碼步驟為：

(1) 垃圾站編號為1-m，對于某一類型車輛，按照實(shí)值編碼規(guī)則，生成一個(gè)由數(shù)字1-m組成、數(shù)字不重復(fù)隨機(jī)排列的長度為m的基因串，表示該類型車輛的收運(yùn)路徑。

(2) 共有g(shù)種類型車輛，則生成g個(gè)長度為m的基因串，將其橫向連接，生成一條長度為g×m染色體A，所有類型車輛的收運(yùn)路徑，如圖1所示。

圖1 基于車輛類型的染色體編碼示意圖

2.2 染色體解碼

基于車輛裝載能力限制的染色體解碼方法中，首先，按照車輛裝載能力限制，對染色體進(jìn)行解碼得到該條染色體對應(yīng)的各類型車輛初始數(shù)量以及每一輛車的初始收運(yùn)路徑；然后，在車輛裝載能力范圍內(nèi)，通過調(diào)整車輛數(shù)量和車輛路徑對該初始解進(jìn)行改進(jìn)，確定最終車輛數(shù)量以及各車輛的收運(yùn)路徑。解碼步驟為：

(1) 選取某一類型車輛服務(wù)的垃圾站所對應(yīng)的基因串B，基于車輛裝載能力限制進(jìn)行解碼，使每一輛車經(jīng)過一個(gè)先從垃圾中轉(zhuǎn)站駛出，然后在裝載能力限制內(nèi)經(jīng)過最大數(shù)量的垃圾站，最后駛?cè)肜修D(zhuǎn)站的完整過程。一輛車裝載完畢，啟動(dòng)下一輛車，直到所有垃圾站內(nèi)的由該種類型車輛收運(yùn)的垃圾裝載完畢。如圖2所示，其中“→”表示路徑指向。

圖2 初始解碼示意圖

(2) 增加一輛同類型車輛，記其編號為n+1，初始路徑為m+1→m+1，初始裝載量Cap=0，初始運(yùn)輸成本變化值ΔEi(n+1)=0。

(3) 基因串B上的某一垃圾站i，其在原車輛路徑中的前后節(jié)點(diǎn)分別為a、b；將該垃圾站i插入新增車輛路徑中，新增車輛路徑的車輛運(yùn)輸成本增加值最小的插入點(diǎn)為最優(yōu)插入點(diǎn)，其前后節(jié)點(diǎn)分別為a′、b′。于是，垃圾站i轉(zhuǎn)入新增車輛路徑后運(yùn)輸成本的變化值Δei=cwo(n+1)w(-tai-tib+tab-ta′b′+ta′i+tib′)。圖3以垃圾站1插入到新增車輛的初始路徑中的過程為例進(jìn)行示意。

圖3 插入過程示意圖

(4) 對每一個(gè)垃圾站i計(jì)算Δei，取最小值為ΔEi。若ΔEi<0且Cap+dip≤Capw，令ΔEi(n+1)=ΔEi，執(zhí)行本次插入，并更新相關(guān)參數(shù)，返回步驟(3)；否則，轉(zhuǎn)到步驟(5)。

(6) 若所有類型車輛路徑均已解碼完畢，結(jié)束；否則，返回步驟(1)。

2.3 適應(yīng)度計(jì)算

對每一條染色體，將其解碼結(jié)果代入目標(biāo)函數(shù)計(jì)算目標(biāo)函數(shù)值，令其倒數(shù)為適應(yīng)度。

2.4 遺傳操作

(1) 選擇。采用輪盤賭法執(zhí)行選擇操作。用上一代保存的適應(yīng)度最優(yōu)的個(gè)體替換最劣個(gè)體，采用輪盤賭法執(zhí)行選擇操作。

(2) 交叉。采用交叉兩個(gè)染色體對應(yīng)兩點(diǎn)之間基因串的方法執(zhí)行交叉操作。以交叉概率隨機(jī)選擇進(jìn)行交叉的兩個(gè)染色體，然后隨機(jī)選擇某一種類垃圾的收運(yùn)路徑，確定交叉位置所在區(qū)間，接著隨機(jī)選擇該區(qū)間上的兩點(diǎn)，確定交叉位置，最后交叉兩點(diǎn)之間的相同基因，避免交叉后路徑中出現(xiàn)數(shù)字重復(fù)的情況。例如交叉的兩個(gè)基因段為[1 2 3 4]和[2 5 6 1]，交叉后形成的新基因段為[2 3 4 1]和[1 2 5 6]。

(3) 變異。采用同一染色體上兩點(diǎn)互換變異的方法執(zhí)行變異操作。以變異概率隨機(jī)選擇進(jìn)行變異的兩個(gè)染色體，然后隨機(jī)選擇某一種類垃圾的收運(yùn)路徑，確定變異位置所在區(qū)間，接著隨機(jī)選擇該區(qū)間上的一點(diǎn)以及其鄰點(diǎn)，確定變異位置，最后互換兩點(diǎn)之間的基因。

3 仿 真

3.1 仿真構(gòu)建

以鄭州市高新區(qū)某垃圾中轉(zhuǎn)站服務(wù)片區(qū)作為仿真區(qū)域，區(qū)域內(nèi)設(shè)有17處垃圾站，用編號1-17表示，垃圾中轉(zhuǎn)站用編號18表示，各設(shè)施位置如圖4所示。通過高德地圖開放平臺測量各垃圾站之間、垃圾中轉(zhuǎn)站與垃圾站之間的車輛行駛最短距離作為節(jié)點(diǎn)之間的距離，如表1所示。節(jié)點(diǎn)之間的車輛往返路徑受到城市道路約束，導(dǎo)致節(jié)點(diǎn)之間的往返距離存在差異。

圖4 設(shè)施位置示意圖

表1 各節(jié)點(diǎn)之間車輛行駛距離 km

續(xù)表1

類型1車輛為密封清運(yùn)車、類型2車輛為密封專用車、類型3車輛為普通車，最大裝載量分別為6、3、5(單位：t)，車輛單位距離運(yùn)輸成本分別為4、3、3.5(單位：元/km)，車輛啟動(dòng)成本每天分別為150、120、100(單位：元/輛)。生活垃圾分為廚余垃圾、可回收物、有害垃圾和其他垃圾四類，每個(gè)垃圾站內(nèi)不同種類的垃圾量如表2所示。其中廚余垃圾由類型1車輛收運(yùn)，有害垃圾由類型2車輛收運(yùn)，可回收垃圾和其他垃圾由類型3車輛收運(yùn)。設(shè)定遺傳算法參數(shù)中種群大小100，最大迭代次數(shù)2 000次，交叉概率0.7，變異概率0.2。

表2 垃圾站內(nèi)不同種類的垃圾量 t/天

續(xù)表2

3.2 仿真結(jié)果

利用MATLAB語言編程，在計(jì)算機(jī)上運(yùn)行239.83 s結(jié)束，迭代趨勢如圖5所示，最小成本和平均成本均隨著迭代次數(shù)的增加而降低，二者之間的間距也逐漸趨于穩(wěn)定。在計(jì)算機(jī)上多次運(yùn)行，運(yùn)行時(shí)間均在189 s～317 s之間?？梢?，遺傳算法有效，并且能夠在短時(shí)間內(nèi)給出模型的滿意解。

圖5 遺傳算法迭代趨勢圖

運(yùn)行結(jié)果顯示，總成本為1 740.8元，最優(yōu)染色體為[ 1 4 15 16 6 7 8 10 12 17 9 5 14 2 13 11 3 | 4 15 16 13 14 11 17 10 5 8 1 6 9 7 12 2 3 | 1 15 14 7 12 17 3 9 5 8 4 13 11 16 6 10 2 ]，為便于展示，將不同類型車輛的收運(yùn)路徑用“|”間隔。最優(yōu)染色體解碼后得到12條收運(yùn)路線，如表3所示，該垃圾中轉(zhuǎn)站需擁有5輛類型1車輛分別收運(yùn)路線1-5上的廚余垃圾，2輛類型2車輛分別收運(yùn)路線6-7上的有害垃圾，5輛類型3車輛分別收運(yùn)路線8-12上的可回收垃圾和其他垃圾?？梢钥闯觯诶N類和車輛類型必須匹配的條件下，不同類型車輛的收運(yùn)路徑均不相同，所有垃圾站內(nèi)不同種類的垃圾都被收運(yùn)至垃圾中轉(zhuǎn)站，表明模型及算法均有效。

表3 車輛收運(yùn)路徑

圖6以路線1為例進(jìn)行示意，由于車輛行駛路徑受城市道路約束，導(dǎo)致同一車輛的收運(yùn)路徑存在交叉的情況，這符合實(shí)際。

圖6 路線1的車輛收運(yùn)路徑示意圖

4 結(jié) 語

本文根據(jù)《生活垃圾分類制度實(shí)施方案》具體內(nèi)容，在垃圾分類收運(yùn)背景下，研究多種類多車型垃圾分類收運(yùn)車輛路徑優(yōu)化問題，采用遺傳算法予以求解，通過仿真驗(yàn)明了模型及算法的有效性。本文為解決生活垃圾分類收運(yùn)車輛規(guī)劃問題提供思路，期望促進(jìn)垃圾分類形成前端分類投放、中端分類收運(yùn)、末端分類處理的完整體系。