垃圾分類收運模式下車輛路徑問題建模與仿真

2021-08-12 08:33:10狄衛民

計算機應用與軟件 2021年8期

狄衛民王然

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

0 引言

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

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

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

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

1 問題描述與模型建立

1.1 問題描述

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

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

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

1.2 符號說明

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

1.3 數學模型

建立如下數學模型：

(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)為目標函數，表示最小化車輛啟動成本和運輸成本之和；式(2)表示每個垃圾站i只有1輛w類型車輛經過；式(3)表示車輛v必須從垃圾中轉站j出發并返回；式(4)表示車輛v最多服務某一垃圾站i一次；式(5)表示車輛v只能在垃圾站之間單向行駛；式(6)表示車輛v的裝載能力限制；式(7)表示車輛v啟動約束；式(8)、式(9)為0-1約束。

2 算法

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

2.1 染色體編碼

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

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

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

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

2.2 染色體解碼

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

(1) 選取某一類型車輛服務的垃圾站所對應的基因串B，基于車輛裝載能力限制進行解碼，使每一輛車經過一個先從垃圾中轉站駛出，然后在裝載能力限制內經過最大數量的垃圾站，最后駛入垃圾中轉站的完整過程。一輛車裝載完畢，啟動下一輛車，直到所有垃圾站內的由該種類型車輛收運的垃圾裝載完畢。如圖2所示，其中“→”表示路徑指向。

圖2 初始解碼示意圖

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

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

圖3 插入過程示意圖

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

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

2.3 適應度計算

對每一條染色體，將其解碼結果代入目標函數計算目標函數值，令其倒數為適應度。

2.4 遺傳操作

(1) 選擇。采用輪盤賭法執行選擇操作。用上一代保存的適應度最優的個體替換最劣個體，采用輪盤賭法執行選擇操作。

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

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

3 仿真

3.1 仿真構建

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

圖4 設施位置示意圖

表1 各節點之間車輛行駛距離 km

續表1

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

表2 垃圾站內不同種類的垃圾量 t/天

續表2

3.2 仿真結果

利用MATLAB語言編程，在計算機上運行239.83 s結束，迭代趨勢如圖5所示，最小成本和平均成本均隨著迭代次數的增加而降低，二者之間的間距也逐漸趨于穩定。在計算機上多次運行，運行時間均在189 s～317 s之間。可見，遺傳算法有效，并且能夠在短時間內給出模型的滿意解。

圖5 遺傳算法迭代趨勢圖

運行結果顯示，總成本為1 740.8元，最優染色體為[ 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 ]，為便于展示，將不同類型車輛的收運路徑用“|”間隔。最優染色體解碼后得到12條收運路線，如表3所示，該垃圾中轉站需擁有5輛類型1車輛分別收運路線1-5上的廚余垃圾，2輛類型2車輛分別收運路線6-7上的有害垃圾，5輛類型3車輛分別收運路線8-12上的可回收垃圾和其他垃圾。可以看出，在垃圾種類和車輛類型必須匹配的條件下，不同類型車輛的收運路徑均不相同，所有垃圾站內不同種類的垃圾都被收運至垃圾中轉站，表明模型及算法均有效。