基于粒子群算法的大件垃圾預約上門收運干擾管理研究

白曉燕

摘?要：為解決居民點大件垃圾尺寸變化對原始收運計劃造成的擾動問題，提出擾動辨識和擾動度量方法，并以對收運系統擾動最小為目標，建立干擾管理模型。最后通過實例仿真實驗，驗證干擾管理模型和算法的有效性。

關鍵詞： 大件垃圾;車輛調度;干擾管理;尺寸變化

文章編號： 2095-2163（2021）01-0079-06 中圖分類號：X799.3 文獻標志碼：A

【Abstract】In order to solve the problem of door-to-door collection and transportation vehicle scheduling interference caused by the size change of bulky waste in residential areas， the disturbance identification method and disturbance measurement strategy are proposed according to the interference management idea， and the interference management model is established with the goal of minimum disturbance to the collection and transportation system. Finally， an example simulation experiment is used to verify the effectiveness of the interference management model and algorithm.

【Key words】bulky waste; vehicle scheduling; interference management; size change

0 引?言

大件垃圾指重量超過5kg或體積大于0.2m3或長度超過1m且整體性強而需要拆解后再利用或處理的廢棄物[1]，通常都具有較高的回收價值。大件垃圾的收運系統由收集、運輸、處理共同組成，各個環節相互協調、合理規劃、優化調度才能使整個大件垃圾收運系統達到最優化。但隨著居民預約上門收運的時間窗的變化、大件垃圾的尺寸變化（大件垃圾的長、寬、高的信息錯誤）等不可控制的客觀環境發生變化，就會造成原定路線的最優方案的不能有效啟動。結合干擾管理思想，對干擾事件進行擾動辨識和擾動度量，分析干擾事件發生后可能會引起變化的變量、對整個大件垃圾收運系統調度的影響及對擾動的變量進行偏離度量后，構建大件垃圾預約上門收運的干擾管理模型，為干擾事件發生時快速有效地啟動應急預案，最大程度地降低干擾事件的影響，保證大件垃圾預約上門收運系統的持續高效的正常運轉。

1 文獻概述

干擾管理的作用旨在當干擾事件發生后，快速生成對系統擾動最小的調整計劃，同時考慮費用，但是并非只是費用最小化。

干擾管理的研究越來越受到學界的關注，研究工作也在陸續展開。在有關干擾管理領域的研究方面，Yu等人[2]定義了干擾管理，Clausen等人[3]也基本認為干擾事件發生后，干擾管理的目標是使新方案相對于原方案的擾動最小。文獻[4-9]都根據干擾管理思想，對不同干擾事件做出了一系列的研究處理，建立模型求解。

本文以干擾管理思想為基礎，對大件垃圾預約上門收運系統中出現的大件垃圾尺寸變化的問題進行研究，針對大件垃圾預約上門收運系統的特點提出收運容積偏離、收運次數偏離、收運距離偏離和路線偏離四種擾動度量，提出大件垃圾預約上門收運干擾管理模型，通過對收運路線的局部實時調整，優化干擾事件發生前的初始計劃路線，從而生成在線調整方案。

2 大件垃圾預約上門收運干擾管理模型

2.1 問題描述及假設

本文針對大件垃圾預約收運過程中居民點的大件垃圾尺寸發生變化時，所引起的大件垃圾收運車輛的調度干擾問題進行研究。干擾管理的目標是使管理后的新方案與初始方案的偏差最小且盡量保持初始方案的最優;基于對大件垃圾預約上門收運路線最優化研究的基礎上進行干擾管理的研究。本文假設當干擾事件發生時，大件垃圾收運系統能夠迅速獲取所有收運車輛的位置、車廂裝載情況等信息。在保證大件垃圾收運車輛車廂最大容積率和裝載率的情況下，初始路線是收運距離最短的最優路線。

大件垃圾的預約收運過程：每輛大件垃圾收運車輛由車庫出發，至下單預約收運服務的居民點進行大件垃圾的收運工作，收運完畢后再至下一居民點收運，直至車輛滿載不能繼續裝載大件垃圾時，至大件垃圾處理廠卸空大件垃圾;每輛車依次循環工作，直至服務完所有的居民點，至大件垃圾處理廠卸空，車輛駛回車庫。大件垃圾預約上門收運如圖1所示。已知：

（1）車庫和居民點，居民點和居民點，居民點和處理廠，處理廠和車庫的距離;

（2）各居民點的大件垃圾進行裝箱處理后的長（lik）、寬（wik）、高（hik）、體積（vik）和質量（qik）;

（3）各居民點的大件垃圾數量（ei）;

（4）車庫、各居民點、處理廠的地理位置（坐標）;

（5）收運車輛車廂的額定載重（Q）和額定體積（L*W*H）{即：車廂的長（L）、寬（W）、高（H）}，和車廂沿X、Y、Z軸的重心范圍;

（6）收運車輛的行駛速度（即：距離/速度=行駛時間）;

（7）每個居民點被服務的時間si。

其中，假設每件大件垃圾的被收運時間為0.2，si=居民點的大件垃圾數ei*0.2;收運車輛在處理廠的停留時間=大件垃圾裝載總數*0.2。

2.2 擾動辨識

2.3 擾動度量

干擾管理的思想就是生成對系統擾動最小的調整方案，且考慮原目標函數最優化。對此擬展開研究論述如下。

（1）大件垃圾收運容積偏離的度量。數學公式可寫為：

其中，Δνik表示居民點i處的第k件大件垃圾的體積變化量，Δνik=Vgp-V0gp，V0gp表示原路線車輛p第g次裝載體積，Vgp表示新路線車輛p第g次裝載體積; gp表示新路線車輛p收運的次數;μ表示與原路線相比，新路線中大件垃圾增加單位體積的懲罰參數。

（2）收運次數的偏離。數學公式可寫為：

其中，gp表示車輛p收運的次數，g0p表示原路線車輛p收運的次數。

（3）收運距離偏離的度量。數學公式可寫為：

其中，C0表示初始方案中所有居民點的集合; c1表示增派一輛收運車輛的固定成本;c2表示收運車輛行駛單位距離的成本;x0ijp表示初始方案中的決策變量;xijp表示干擾管理方案中的決策變量;d0ij表示初始方案中居民點i，j之間的距離;dij表示干擾管理方案中居民點i，j之間的距離;CLp表示車輛p尚未完成上門收運的居民點集合。

（4）路線偏離的度量。數學公式可寫為：

其中，+、-分別表示和大件垃圾收運原路線相比，新路線中新增/減少一條邊的懲罰參數;r+p表示屬于大件垃圾收運新路線但不屬于原路線的線邊集合;r-p表示屬于大件垃圾收運原路線但不屬于新路線的線邊集合。

2.4 擾動恢復策略

根據符俊波等人提出的擾動恢復策略，本文結合大件垃圾收運過程及收運特點，提出自救策略、鄰近救援策略和增派救援策略3種大件垃圾收運車輛的擾動恢復策略[9]。

2.5 建立虛擬收集點

本文為統一車輛收運狀態，引入大件垃圾虛擬收集點概念[9]，將所有的收運車輛統一至車庫或者大件垃圾處理廠。按照干擾發生時收運車輛狀態建立虛擬收集點，對此可做闡釋分述如下：

（1）大件垃圾收運車輛正在行駛至下一居民點的途中，則將收運車輛前往的居民點設為收集點。

（2）大件垃圾收運車輛正在對居民點進行收運服務，則將該居民點設為虛擬收集點。

（3）大件垃圾收運車輛在車庫/處理廠，則無需設立虛擬收集點[9]。

2.6 干擾管理模型建立

本次研究得到的大件垃圾預約上門收運干擾管理的數學模型詳見如下。

（1）目標函數。對應的數學公式可表示為：

（2）保證虛擬收集點第一個得到服務，且最終從大件垃圾處理廠返回到車庫。對應數學公式可表示為：

（3）每個居民點被服務且只被服務一次。對應數學公式可表示為：

（4）每條收運路線上的大件垃圾總質量不得超過車輛的最大裝載質量，總體積不得超過車輛的最大裝載體積。對應數學公式可表示為：

（5）保證每件大件垃圾必須全部在收運車輛車廂內部。對應數學公式可表示為;

（6）為保證收運車輛行駛安全，每輛車中的所有的大件垃圾重心必須在一定的安全范圍之內。對應數學公式可表示為;

其中，i，j=1，2，3…，n表示居民點的集合;i，j=0′表示處理廠的集合，i，j=0表示車庫;qi表示居民點i處的大件垃圾總質量;vi表示居民點i處的大件垃圾數量;tij表示車輛在?。╥，j）的行駛時間;si表示居民點i需被服務的時間;wip表示車輛p到達居民點i的時間;居民點i下單預約大件垃圾上門收運服務的時間范圍[ai，bi];L/W/H表示大件垃圾收運車輛車廂的長、寬、高;Q表示收運車輛車廂的最大裝載質量;V（L*W*H）表示收運車輛車廂的最大裝載體積;（XIikp，YIikp，ZIikp）表示車輛p在居民點i處收運的第k個大件垃圾在車輛車廂中的正面右上角坐標;（XIikp，YIikp，ZIikp）表示車輛p在居民點i處收運的第k個大件垃圾在車輛車廂中的側面左下角坐標;[x1，x2]表示收運車輛車廂沿X軸的重心范圍要求; [y1，y2]表示收運車輛車廂沿Y軸的重心范圍要求; [z1，z2]表示收運車輛車廂沿Z軸的重心范圍要求;ei表示居民點i處的大件垃圾數量;Iik表示居民點i處的第k件大件垃圾，k=1，2，3，…，ei;lik、wik、hik、qik分別表示第i個居民點處的第k件大件垃圾的長、寬、高及質量， k=1，2，3…，ei;P=（1，2，3，…，p）表示車輛集合，也可表示取貨路線數量;Iikp表示居民點i處的第k件大件垃圾裝在收運車輛p中;Ijlp表示居民點j處的第l件大件垃圾裝在收運車輛p中;CL表示干擾發生后新建立的收集點的集合;CM表示虛擬收集點的集合，CM∈CL。

3 模型算法設計

干擾事件下的收運車輛調度與三維裝箱聯合優化問題，是較為復雜的組合優化問題，用普通的優化方法難以在短時間內求出最優解，甚至是有效解。粒子群算法實現容易、收斂快、精度高，所以本文引用文獻[10]提出的多相量子粒子群算法，結合車廂裝載檢驗算法來解決此類問題，車廂裝載檢驗算法主要檢驗各收運車輛在其收運過程中車廂中放置的大件垃圾是否滿足三維裝載約束，保證大件垃圾能夠成功裝載。大件垃圾車廂裝載檢驗算法流程見圖2。

4 實例分析

數值試驗平臺為Matlab 9.0，計算機CPU為英特爾酷睿 5、2.6 GHz，8 GB內存，64位Windows10操作系統。

4.1 具體問題描述

案例數據如下：有15個居民點下單預約上門收運大件垃圾服務，當天車庫提供服務的收運車輛可用時間窗范圍為[0，12]，收運車輛行駛速度為50，收運車輛數為3。本文規定車輛車廂的重心范圍約束分別為[0，50]、[5，20]、[0，30]。各居民點需被服務時間跟大件垃圾數成正比，每件大件垃圾需求的服務時間為0.2。各居民點處的大件垃圾數在[1，3]之間隨機生成，每件大件垃圾的長、寬、高分別在[0.2L，0.6L]、[0.2W，0.6W]、[0.2H，0.6H]之間隨機生成。

車庫的位置坐標（x0，y0）、處理廠坐標（x0′，y0′） 、收運車輛車廂的長、寬、高及最大載重，見表1。

居民點位置坐標，各居民點處大件垃圾個數ei、總質量qi，及居民下單預約大件垃圾上門收運服務的時間窗范圍[ai，bi]、各居民點總服務時間si，見表2。各居民點處每件大件垃圾的長、寬、高及質量見表3。

4.2 初始最優路線參數設置

粒子群算法的參數設置為：種群規模popsize=50，最大迭代次數為gen=100，將算法通過Matlab語言實現，得出大件垃圾收運車輛最優上門收運路線見表4、表5。

為驗證干擾管理的管理有效性，設計干擾事件：大件垃圾收運車輛對居民點12進行上門收運完成后，在至居民點1收運途中，得知居民點1處的大件垃圾的尺寸與居民預約時不符，其高度由14變成18，根據擾動辨識規則Δv31≤V012但ZI112≥H，居民點1處大件垃圾尺寸的變化對大件垃圾預約上門收運系統產生擾動，原收運計劃不可行，需要重新制定上門收運計劃。干擾發生時刻為5.09，根據本文虛擬收集點的定義，得到干擾發生時，虛擬收集點集合為[14，4，1，8，2]，已完成收運的收集點集合為[6，7，13，11，3，12，15，10，9，5]。

4.3 干擾管理優化結果

粒子群算法的參數設置和初始方案相同，干擾管理模型中參數設置為：

μ=0.05，θ=10，c1=100，c2=1，+=1，-=1。用本文設計的干擾管理模型對產生的擾動進行恢復，根據仿真實驗知應采取鄰近救援策略，得到干擾管理結果見表6、表7。

為驗證本文構建模型的有效性，選擇傳統的干擾處理方法-重調度法進行仿真實驗結果的對比，實驗結果見表8。

結果表明，總體上干擾管理優化結果明顯優于重調度結果，大件垃圾預約上門收運干擾管理模型有效，解決了預約上門收運過程中因居民點處大件垃圾尺寸變化對收運系統造成的影響，能夠快速進行擾動恢復，最大程度降低擾動影響，對有關大件垃圾預約上門收運方式的深入研究做了鋪墊。

5 結束語

本文以大件垃圾預約上門收運系統中的大件垃圾尺寸發生變化時的干擾事件進行研究，根據大件垃圾收運系統的特點，提出相應的擾動辨識和擾動度量方法，建立干擾管理模型，最后通過實例仿真實驗驗證了干擾管理模型的有效性，保障了在干擾事件發生時快速生成擾動恢復策略。本文是干擾管理在大件垃圾預約上門收運系統中的成功運用，為解決三維裝箱車輛調度領域中干擾管理所面對的現實問題進行了有益的探索。

參考文獻

[1]GB/T25175-2010. 大件垃圾收集和利用技術要求[S]. 北京：中華人民共和國國家質量監督檢驗檢疫總局，中國國家標準化管理委員會，2010.

[2]YU Gang， QI Xiangtong. Disruption management： Framework， models and applications [M]. Beijing： World Scientific Publishing Co. Pte. Ltd.， 2004.

[3]CLAUSEN J， HANSEN J， LARSEN J. Disruption management operations research between planning and execution[J]. OR/MS today， 2001， 28（5）：40-43.

[4]王旭坪，許傳磊，胡祥培.有顧客時間窗和發貨量變化的車輛調度干擾管理研究[J].管理科學，2008，21（5）：111-120.

[5]張欽，潘暑風.物流配送延遲的一個干擾管理模型[J].系統工程，2008，26（10）：13-16.

[6]王征，胡祥培，王旭坪.行駛時間延遲下配送車輛調度的干擾管理模型與算法[J].系統工程理論與實踐，2013，33（2）：378-387.

[7]馬慧民，羅長見.城市生活垃圾收運車輛調度干擾管理研究[J].工業工程，2015，18（3）：92-97.

[8]阮俊虎，王旭坪.中轉點變化的應急醫療物資聯合運送干擾管理研究[J].運籌與管理，2016，25（4）：114-124.

[9]符俊波，馬慧民，張爽，等.有垃圾量變動的生活垃圾收運車輛調度干擾管理研究[J].上海理工大學學報，2017，39（4）：368-375.

[10]寧濤，王旭坪，胡祥培.行駛受擾延遲下配送車輛調度的干擾管理決策模型[J].系統工程理論與實踐，2019，39（5）：1235-1245.