有垃圾量變動的生活垃圾收運車輛調(diào)度干擾管理研究

符俊波, 馬慧民, 張 爽, 雷 悅

(1.上海理工大學 管理學院,上海 200093; 2.上海電機學院 商學院,上海 201306)

有垃圾量變動的生活垃圾收運車輛調(diào)度干擾管理研究

符俊波1, 馬慧民2, 張 爽1, 雷 悅2

(1.上海理工大學 管理學院,上海 200093; 2.上海電機學院 商學院,上海 201306)

為解決由垃圾收集點垃圾量變化引發(fā)的生活垃圾收運車輛調(diào)度干擾問題,提出基于干擾管理思想的擾動恢復策略和方案.通過分析干擾事件對垃圾收運系統(tǒng)的擾動,構(gòu)建垃圾收運車輛調(diào)度的擾動辨識和擾動度量,并以新方案與原方案偏差最小為目標,建立擾動恢復數(shù)學模型.設(shè)計基于車輛收運路徑編碼方式的遺傳算法,求解該類問題.為統(tǒng)一車輛收運狀態(tài),引入虛擬收集點概念,并對干擾管理目標函數(shù)中的懲罰參數(shù)進行研究.最后,通過實例進行仿真實驗,并與重調(diào)度結(jié)果進行比較,驗證干擾管理模型和遺傳算法的有效性.研究結(jié)果表明,干擾管理可以有效降低計劃偏離度,并合理控制成本.

生活垃圾; 車輛調(diào)度; 垃圾量變動; 干擾管理; 遺傳算法

生活垃圾收運系統(tǒng)是由收集、運輸和中轉(zhuǎn)3個環(huán)節(jié)組成,各個環(huán)節(jié)合理配置、協(xié)調(diào)配合,才能獲得最大的環(huán)境、社會和經(jīng)濟效益.但隨著車輛故障、交通擁堵、垃圾量變動等不確定事件的發(fā)生,垃圾收運系統(tǒng)時常受到干擾.不僅影響收運系統(tǒng)的正常運行,甚至造成環(huán)境的污染.因此,如何準確辨識不確定事件對垃圾收運系統(tǒng)的擾動,并迅速做出調(diào)整方案,使系統(tǒng)以最小代價盡快恢復正常運行,是生活垃圾收運車輛調(diào)度研究的一個重要問題.

1 文獻研究綜述

處理車輛調(diào)度干擾問題的經(jīng)典方法有:隨機車輛路徑方法、魯棒優(yōu)化方法、scheduling和rescheduling方法.干擾管理與上述經(jīng)典方法不同,它不是針對干擾事件發(fā)生后的狀態(tài)完全重新建模和優(yōu)化,而是最小化干擾對原計劃沖擊的一種管理方法.Yu等[1]給出了干擾管理的定義,該定義可分為3層意思理解:第一層是制定并執(zhí)行最優(yōu)或次優(yōu)計劃;第二層是識別干擾事件;第三層是形成有效的使系統(tǒng)擾動最小的干擾管理新方案.Clausen等[2]也基本認為干擾事件發(fā)生后,干擾管理的目標是使新方案相對于原方案的擾動最小.

干擾管理需要根據(jù)實際情況,針對不同的干擾事件建立相應(yīng)的恢復模型和有效的求解算法,以便快速、及時地給出處理干擾事件的最優(yōu)調(diào)整方案.目前,干擾管理思想己經(jīng)在航班計劃[3]、生產(chǎn)調(diào)度[4]、供應(yīng)鏈協(xié)調(diào)[5]、項目管理[6-7]等方面得到了應(yīng)用.在車輛調(diào)度方面,胡祥培等[8]從客戶不滿意度、配送成本以及路徑偏離程度3個方面度量物流配送系統(tǒng)中的擾動,采用禁忌搜索算法對有需求量變動的干擾事件進行了仿真實驗.王旭坪等[9-10]分析了顧客時間窗變化和發(fā)貨量變化這兩個干擾事件對配送系統(tǒng)造成的擾動.丁秋雷[11]運用行為科學中行為感知與運籌學中定量的研究手段,分析了客戶時間窗變化這類干擾事件對受擾主體的影響.阮俊虎等[12]分析的是直升機和車輛聯(lián)合運送中出現(xiàn)中轉(zhuǎn)點變化的干擾問題.馬慧民等[13]針對城市生活垃圾收運中出現(xiàn)的車輛故障這一干擾事件,提出了基于初始計劃偏離的擾動度量方法,建立了相應(yīng)的干擾管理模型.上述研究在特定類型干擾問題的建模和求解方面取得了一定的成果,然而在擾動度量懲罰參數(shù)的取值上缺乏分析.生活垃圾收運系統(tǒng)干擾管理的研究目前尚未形成理論體系,包括擾動辨識分析、擾動度量方法,以及大規(guī)模問題的實時求解算法等內(nèi)容都有待深入研究.

本文以干擾管理思想為基礎(chǔ),對服務(wù)型生活垃圾收運系統(tǒng)中出現(xiàn)的有垃圾收集點垃圾量變化的問題進行研究,針對生活垃圾收運系統(tǒng)的特點提出路線偏離、載重偏離、收運次數(shù)偏離和收運費用偏離4種擾動度量,設(shè)計基于車輛收運路徑的自然數(shù)編碼表示方法,探究路線偏離懲罰參數(shù)的合理取值范圍.最后,通過實例驗證干擾管理模型和遺傳算法的有效性.

2 擾動的分析及恢復策略

2.1 擾動辨識

2.2 擾動度量

干擾管理思想的關(guān)鍵是以原計劃為基礎(chǔ)快速生成對系統(tǒng)擾動最小的調(diào)整方案,同時保持成本盡量低.在生活垃圾收運車輛調(diào)度干擾管理研究中,系統(tǒng)擾動主要體現(xiàn)在收運路線的偏離上,成本主要體現(xiàn)在車輛的固定啟動費用以及收運費用上.

a. 路線偏離的度量.

(1)

b. 收運載重偏離的度量.

(2)

c. 收運次數(shù)偏離的度量.

(3)

d. 收運費用偏離的度量.

(4)

2.3 擾動恢復策略

根據(jù)王旭平等[9-10]在物流配送中提出的擾動恢復策略,本文結(jié)合生活垃圾收運車輛的特點,提出車輛自救策略、鄰近救援策略和增派救援策略3種生活垃圾收運車輛的擾動恢復策略.

a. 車輛自救策略:通過微調(diào)受擾車輛垃圾收集點的服務(wù)順序保證收運系統(tǒng)正常運行.

b. 鄰近救援策略:通過調(diào)度在途的其他車輛輔助受擾車輛完成剩余任務(wù).可調(diào)度的車輛同時滿足兩個條件:一是要在受擾任務(wù)的時間窗范圍內(nèi)到達受擾任務(wù)收集點的位置;二是施救車輛尚有空間可以利用.

c. 增派救援策略:從車場新派車輛對受擾任務(wù)進行救援.增派車輛費用包括兩部分:一是增派車輛的行駛費用;二是啟動車輛的固定費用.

3 干擾管理模型的構(gòu)建

3.1 問題的描述及假設(shè)

本文對有垃圾收集點垃圾量變化這一干擾事件進行研究,在不能改變干擾事件發(fā)生的同時,要求制定出對整個收運系統(tǒng)影響最小的調(diào)整方案.本文假設(shè),在垃圾收運系統(tǒng)中,各垃圾收集點、車場、中轉(zhuǎn)站位置已知,初始路線為收運距離最短的最優(yōu)路線.當干擾事件發(fā)生時,垃圾收運系統(tǒng)能迅速獲取所有車輛的位置、行駛時間、裝載情況等信息.

3.2 構(gòu)造虛擬收集點

本文為統(tǒng)一車輛收運狀態(tài),引入虛擬垃圾收集點概念,從而將所有車輛統(tǒng)一到車場或是中轉(zhuǎn)站.

干擾發(fā)生時車輛所處狀態(tài)共分3種情況,建立相應(yīng)情況下的虛擬收集點方法如下:a.車輛正在前往下一收集點途中,則將車輛前往的收集點設(shè)為虛擬收集點;b.車輛正在對收集點進行服務(wù),則將該收集點設(shè)為虛擬收集點;c.車輛在車場,此時無需設(shè)立虛擬收集點.

3.3 數(shù)學模型

根據(jù)上述描述,建立垃圾收運車輛干擾管理的數(shù)學模型.

目標函數(shù):

min[R(k)+Q(k)+P(k)+C(x)]

(5)

約束條件:

?i∈CL

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

pk≤pkmax,?k∈K

(14)

(15)

ETi≤Tik≤LTi

(16)

K≤NK

(17)

式中:mi表示生活垃圾收集點i的垃圾量;Qk表示車輛k的最大載重;CL表示干擾發(fā)生后新建立的收集點的集合;pkmax為車輛k限定的最大收運次數(shù);CM表示虛擬收集點的集合,且CM?CL;[ETi,LTi]為收集點i的服務(wù)時間窗;n+1表示車場;NK表示車場可調(diào)用車輛數(shù)目.

式(6)和式(7)保證每個收集點只能被訪問一次;式(8)對車次的載重進行限制;式(9)表示從車場出發(fā)和回到車場的車輛數(shù)目均為K;式(10)～(12)保證車輛從車場出發(fā),最終回到車場;式(13)保證虛擬點第一個得到服務(wù);式(14)對車輛收集次數(shù)進行約束;式(15)為變量整數(shù)約束;式(16)為收集時間窗約束,若車輛由收集點i駛向收集點j,則收集點j的訪問時間Tjk=Tik+tij+si,其中tij為由i行駛至j的時間,si為收集點i的收集時間;式(17)表示可使用車輛數(shù)目約束.

4 求解算法設(shè)計

本節(jié)采用遺傳算法思想,設(shè)計干擾恢復模型的求解算法,具體包括:編碼與解碼設(shè)計、種群初始化、適應(yīng)度函數(shù)和遺傳操作.

4.1 染色體編碼與解碼

對于車輛路徑問題,遺傳算法染色體的編碼形式已有多種表示方法.為了提高算法的效率,本文在初始最優(yōu)路徑的基礎(chǔ)上采用垃圾收集點插入到車輛路徑中的方式以更好地得到干擾調(diào)度方案.其中,垃圾收集點用自然數(shù)1,2,3,…,n表示,車場、中轉(zhuǎn)站分別用自然數(shù)n+1,n+2表示.

初始最優(yōu)路徑:首先,采用基于垃圾收集點的自然數(shù)編碼機制,根據(jù)收集點的數(shù)目隨機生成種群規(guī)模為Popsize,長度為n的初始染色體;其次,經(jīng)過進化N代,多次實驗,得到最優(yōu)染色體;最后采用馬慧民等[13]的染色體解碼方式,將最優(yōu)染色體Rbest根據(jù)容量約束得到Rsub,并將車場和中轉(zhuǎn)站信息加入染色體中,使之形成完整的收運路徑.

干擾管理染色體編碼:采用基于車輛收運路徑的自然數(shù)編碼機制,根據(jù)干擾發(fā)生時未被服務(wù)的收集點數(shù)目Num(CL),隨機生成長度為Num(CL),最大值為pmaxK的初始染色體R.

干擾管理染色體解碼:首先將未被服務(wù)的垃圾收集點從最優(yōu)路徑Rsub中剔除,得到Rdissub.其次根據(jù)染色體R將未被服務(wù)的收集點依次加入到Rdissub中,如pmax=3,CL=[3 8 7],Rdis=[1 3 5],則表示將垃圾收集點3插入車輛1的第1次收運中,垃圾收集點8插入車輛1的第3次收運中,垃圾收集點7插入車輛2的第2次收運路線中.最后根據(jù)車輛的最大收運次數(shù)重組染色體,加入車場和中轉(zhuǎn)站信息,使之形成完整干擾管理調(diào)度方案.

4.2 種群初始化

首先隨機生成一個種群規(guī)模為Popsize的初始種群.其次為加快尋優(yōu)速度,且保證種群的多樣性,本文根據(jù)Rsub得出其干擾管理模型的染色體R0,并將初始種群的1/5替換為R0.

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

為保證算法在可行解空間里進行尋優(yōu),建立容量約束懲罰函數(shù)及時間約束懲罰函數(shù):

式中:Tpk為車輛k第p次收運所消耗的時間;M為無窮大正數(shù).

本文目標函數(shù)為最小化問題,故建立適應(yīng)度函數(shù):1/(R(k)+Q(k)+P(k)+C(x)+Cl(k)+Ct(k)).

4.4 遺傳操作

選擇:選擇算子的作用是提高種群的平均適應(yīng)值,本文采用輪盤賭法與精英個體保留策略相結(jié)合的方式.

交叉變異:本文采用文獻[14-15]中的自適應(yīng)的交叉變異算子,其概率不是固定的0到1的某一值,而是由每一代種群中最優(yōu)個體的適應(yīng)值與其他個體的差額關(guān)系所決定的,交叉概率pc=1/(1+ek(fmin-f)),變異概率pm=1-1/ek(fmin-f).式中:fmin表示種群中個體最小的適應(yīng)值;f表示適應(yīng)值小于平均適應(yīng)值的所有個體的平均值.

5 實例分析

5.1 具體問題描述

本文以上海市某地區(qū)為例,該地區(qū)共有106個生活垃圾收集點,一個車場,一個中轉(zhuǎn)站.其中,生活垃圾收集點編號為自然數(shù)1～106,車場編號為107,中轉(zhuǎn)站編號為108.實地測得各收集點、車場以及中轉(zhuǎn)站的地理坐標,采用百度地圖開放平臺中的Route Matrix API v2.0 Beta測得各收集點之間駕駛模式下的最短距離.該地區(qū)生活垃圾收運車輛為單車型,車輛平均行駛速度為45 km/h,最大載重為5 t,垃圾每桶裝載耗時30 s,車輛每日的收運次數(shù)不超過3次,工人工作時間窗為早上6:00至9:30,本文將時間窗簡化為[0, 3.5].該地區(qū)生活垃圾收集點垃圾量信息如表1所示.

表1 上海市某地區(qū)垃圾收集點垃圾量信息Tab.1 Garbage amount information at garbage collection points in one region of Shanghai

5.2 初始最優(yōu)路線參數(shù)設(shè)置

為驗證模型和算法的可行性,將算法通過Matlab語言實現(xiàn),得出最優(yōu)調(diào)度方案如表2和下頁表3所示.遺傳算法的參數(shù)設(shè)置如下:種群規(guī)模為500,進化代數(shù)為200,選擇概率為0.1,自適應(yīng)算子的概率參數(shù)為0.002 5.為了保證最優(yōu)調(diào)度方案的合理性,本文將第i次實驗的前10條染色體替換為第i-1次實驗的最優(yōu)染色體,進行多次實驗,直至實驗結(jié)果趨于穩(wěn)定.

5.3 干擾管理優(yōu)化結(jié)果

a. 虛擬收集點.

b. 參數(shù)確定.

本文根據(jù)實例,對干擾管理模型目標函數(shù)中收運路線偏離與收運總距離偏離懲罰參數(shù)之間的關(guān)系進行研究,并確定路線偏離懲罰參數(shù)的合理取值范圍,以便于根據(jù)不同的實際應(yīng)用條件靈活取值.

路線偏離的懲罰參數(shù)與收運總距離偏離懲罰參數(shù)的比值越大,則表明越注重路線對系統(tǒng)的擾動,比值越小則表明越注重收運成本對系統(tǒng)的擾動.設(shè)路線偏離數(shù)目為x,收運總距離偏離為y,求解出僅考慮路線偏離時(α+=1,α-=1,c2=1/+)的路線偏離數(shù)目x1和收運總距離偏離y1.此時方案中x1為最小值,即x1=xmin,同時在有效解的范圍內(nèi),y1為最大值,即y1=ymax.同理求解出僅考慮收運總距離偏離時(α+=1/+,α-=1/+,c2=1)的路線偏離數(shù)目x2和收運總距離偏離y2.此時方案中y2為最小值,即y2=ymin,同時在有效解的范圍內(nèi),x2為最大值,即x2=xmax.

表2 初始最優(yōu)路線Tab.2 Initial optimal route

設(shè)路線偏離的懲罰參數(shù)與收運總距離偏離的懲罰參數(shù)的比為β,路線偏離數(shù)目可能的最小值為m,收運總距離偏離可能的最小值為n.在生活垃圾收運系統(tǒng)干擾管理研究中m=1,n為收運總距離保留的有效位數(shù),β的合理取值范圍是[n/(xmax-xmin),(ymax-ymin)/m].

表3 初始最優(yōu)車輛運輸距離及運輸垃圾量Tab.3 Initial optimal transport distance and transported garbage amount

c. 仿真結(jié)果.

對本文實例進行求解得xmin=6,ymax=10.5,xmax=14,ymin=4.4,m=1,收運距離保留一位有效數(shù)字,故n=0.1.因此,β的合理取值范圍為[0.125,6.1].為驗證β取值范圍的合理性,本文設(shè)定c2=1,分別選取β為5 000,100,50,10,5,2,1,0.5,0.2,0.1,0.05,0共12組數(shù)據(jù)進行研究,以變量β為橫坐標,以偏離量為縱坐標,得到如圖1所示的仿真結(jié)果.結(jié)果表明,最優(yōu)解分別在β取5,2,0.2,0.1,0.05處發(fā)生變化,且這些取值均在[0.012 5,6.1]范圍內(nèi).其中β=0即為重調(diào)度方案,此方案中路線偏離數(shù)目為14條,收運總距離偏離為323.92 km.

圖1 不同懲罰參數(shù)下路線偏離與收運總距離偏離的變化Fig.1 Change of route deviation and the total distance deviation under different penalty parameters

由求解結(jié)果可知當β為5 000,100,50,10,5,2,1,0.5,0.2時,應(yīng)采取車輛自救策略,當β為0.1,0.05,0時應(yīng)采取鄰近救援策略.根據(jù)該地區(qū)垃圾收運系統(tǒng)的特點,干擾管理模型中參數(shù)設(shè)置如下:α+=1,α-=1,μ=10,λ=0.5,c1=100,c2=1.運用本文所建數(shù)學模型對擾動進行恢復,得到仿真結(jié)果,此時受擾車輛9應(yīng)采取車輛自救策略,車輛9收運總距離為39.49 km,路線偏離數(shù)目為8條,其余車輛按照原計劃對垃圾收集點進行服務(wù).受擾車輛干擾管理結(jié)果如表4所示.

表4 干擾管理方案Tab.4 Disruption management plan

為驗證本文所建模型的優(yōu)越性,選擇以收運總距離最小化為目標進行全局優(yōu)化調(diào)整的重調(diào)度方法.干擾管理優(yōu)化結(jié)果與重新調(diào)度結(jié)果對比如表5所示.干擾管理方案和重調(diào)度方案中總成本為路線偏離、收運載重偏離、收運次數(shù)偏離以及收運距離與其相應(yīng)的懲罰參數(shù)的乘積之和.

干擾管理優(yōu)化結(jié)果在路線偏離、收運載重偏離、收運次數(shù)偏離以及收運距離上相對于重調(diào)度結(jié)果,優(yōu)化節(jié)省分別為43%,1.8%,0%,-0.15%.雖然在收運距離上干擾管理優(yōu)化結(jié)果略低于重調(diào)度結(jié)果,但在路線偏離和收運載重偏離上干擾管理結(jié)果明顯優(yōu)于重調(diào)度.綜上所述,在解決生活垃圾車輛調(diào)度問題上,干擾管理模型效果顯著.經(jīng)過干擾管理優(yōu)化,即最大程度降低干擾事件對系統(tǒng)的擾動,又兼顧成本最小的目標,得到了有效的新方案.

表5 干擾管理優(yōu)化結(jié)果與重調(diào)度結(jié)果對比Tab.5 Comparison of disruption management optimizing results with rescheduling results

6 結(jié)束語

本文針對生活垃圾收運系統(tǒng)中收集點垃圾量變化干擾事件進行研究.根據(jù)收運系統(tǒng)的特點,設(shè)計相應(yīng)的擾動辨識和擾動度量,建立了相應(yīng)的干擾恢復模型.設(shè)計了基于車輛收運路徑的自然數(shù)編碼機制.最后通過實例仿真實驗并與重調(diào)度方法進行比較,驗證干擾管理模型和遺傳算法的有效性,并確定路線偏離懲罰參數(shù)的合理取值范圍,以便于根據(jù)不同的實際應(yīng)用條件靈活取值,為解決生活垃圾收運干擾管理中面對的現(xiàn)實問題進行了有益的探索.

[1] YU G,QI X T.Disruption management:framework,models and applications[M].Singapore,River Edge,NJ:World Scientific Publishing Co.Pte.Ltd.,2004.

[2] CLAUSEN J,HANSEN J,LARSEN J.Disruption management operations research between planning and execution[J].OR/MS,2001,28(5):40-43.

[3] YU G,ARGüELLO M,SONG M， et al.A new era for crew recovery at continental airlines[J].Interfaces,2003,33(1):5-22.

[4] 王杜娟,王建軍,劉春來，等.具有惡化效應(yīng)的新工件到達生產(chǎn)調(diào)度干擾管理[J].系統(tǒng)工程理論與實踐,2015,35(2):368-380.

[5] QI X T,BARD J F,YU G.Supply chain coordination with demand disruptions[J].Omega,2004,32(4):301-312.

[6] ZHU G,BARD J F,YU G.Disruption management for resource-constrained project scheduling[J].Journal of the Operational Research Society,2005,56(4):365-381.

[7] 潘逢山,葉春明,姚遠遠.基于混沌粒子群算法的項目調(diào)度干擾問題研究[J].計算機應(yīng)用研究,2013,30 (9):2648-2655.

[8] 胡祥培,孫麗君,王雅楠.物流配送系統(tǒng)干擾管理模型研究[J].管理科學學報,2011,14(1):50-60.

[9] 王旭坪,許傳磊,胡祥培.有顧客時間窗和發(fā)貨量變化的車輛調(diào)度干擾管理研究[J].管理科學,2008,21(5):111-120.

[10] 王旭坪,楊德禮,許傳磊.有顧客需求變動的車輛調(diào)度干擾管理研究[J].運籌與管理,2009,18(4):16-24.

[11] 丁秋雷.客戶時間窗變化的物流配送干擾管理模型——基于行為的視角[J].中國管理科學,2015,23(5):89-97.

[12] 阮俊虎,王旭坪.中轉(zhuǎn)點變化的應(yīng)急醫(yī)療物資聯(lián)合運送干擾管理研究[J].運籌與管理,2016,25(4):114-124.

[13] 馬慧民,羅長見.城市生活垃圾收運車輛調(diào)度干擾管理研究[J].工業(yè)工程,2015,18(3):92-97.

[14] 劉帆.基于遺傳算法的應(yīng)急物流車輛路徑問題研究[D].西安:西安科技大學,2012.

[15] 李欣.自適應(yīng)遺傳算法的改進與研究[D].南京:南京信息工程大學,2008.

(編輯:丁紅藝)

Disruption Management of Garbage Collection and Transportation Vehicle Routing Under the Changing of Garbage Amount

FU Junbo1, MA Huimin2, ZHANG Shuang1, LEI Yue2

(1.BusinessSchool,UniversityofShanghaiforScienceandTechnology,Shanghai200093,China;2.BusinessSchool,ShanghaiDianjiUniversity,Shanghai201306,China)

To deal with the disruption on the garbage collection and transportation vehicle routing caused by the changing of garbage amount at garbage collection point,disruption recovery strategies and solutions were put forward based on the disruption management theory.By analyzing the influence of interference events on the waste collection and transportation system,the disturbance identification and disturbance measurement of vehicle routing were studied,and a mathematical disruption recovery model was established aiming at minimizing the deviation from the original plan.A genetic algorithm based on the vehicle collection and transportation route encoding was designed to solve the problem.In order to unify the vehicle collection and transportation state,the concept of virtual collection point was introduced,and the penalty parameter in disruption management plan was studied.In the end,through simulation experiments and comparing with the rescheduling results,the effectiveness of the disruption management model and genetic algorithm was verified.The results show that the disruption management can reduce the plan deviation effectively,and control the cost reasonably.

garbage;vehiclerouting;garbageamountchange;disruptionmanagement;geneticalgorithm

1007-6735(2017)04-0368-08

10.13255/j.cnki.jusst.2017.04.011

2017-03-06

教育部人文社會科學研究青年基金資助項目(15YJC630089)

符俊波(1992-),男,碩士研究生.研究方向:物流系統(tǒng)管理.E-mail:junbofu@163.com

馬慧民(1981-),男,教授.研究方向:工業(yè)工程、智能優(yōu)化算法.E-mail:mahm81@163.com

X 799.3

A