狄衛(wèi)民 王 然
(鄭州大學(xué)管理工程學(xué)院 河南 鄭州 450001)
垃圾分類收運(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é)模型,利用遺傳算法求解。
城市居民產(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)順序。
為便于模型建立,設(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。
建立如下數(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約束。
考慮到建立的多種類多車型垃圾收運(yùn)車輛路徑優(yōu)化模型的復(fù)雜性,采用遺傳算法進(jìn)行求解。根據(jù)模型多維度的特點(diǎn),提出基于車輛類型的染色體編碼方法、基于車輛裝載能力限制的染色體解碼方法,算法主要功能模塊如下。
基于車輛類型的染色體編碼方法,能夠保證每個(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 基于車輛類型的染色體編碼示意圖
基于車輛裝載能力限制的染色體解碼方法中,首先,按照車輛裝載能力限制,對染色體進(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)。
對每一條染色體,將其解碼結(jié)果代入目標(biāo)函數(shù)計(jì)算目標(biāo)函數(shù)值,令其倒數(shù)為適應(yīng)度。
(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)之間的基因。
以鄭州市高新區(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
利用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)路徑示意圖
本文根據(jù)《生活垃圾分類制度實(shí)施方案》具體內(nèi)容,在垃圾分類收運(yùn)背景下,研究多種類多車型垃圾分類收運(yùn)車輛路徑優(yōu)化問題,采用遺傳算法予以求解,通過仿真驗(yàn)明了模型及算法的有效性。本文為解決生活垃圾分類收運(yùn)車輛規(guī)劃問題提供思路,期望促進(jìn)垃圾分類形成前端分類投放、中端分類收運(yùn)、末端分類處理的完整體系。