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

白曉燕

摘?要：為解決居民點(diǎn)大件垃圾尺寸變化對(duì)原始收運(yùn)計(jì)劃造成的擾動(dòng)問題，提出擾動(dòng)辨識(shí)和擾動(dòng)度量方法，并以對(duì)收運(yùn)系統(tǒng)擾動(dòng)最小為目標(biāo)，建立干擾管理模型。最后通過實(shí)例仿真實(shí)驗(yàn)，驗(yàn)證干擾管理模型和算法的有效性。

關(guān)鍵詞： 大件垃圾;車輛調(diào)度;干擾管理;尺寸變化

文章編號(hào)： 2095-2163（2021）01-0079-06 中圖分類號(hào)：X799.3 文獻(xiàn)標(biāo)志碼：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且整體性強(qiáng)而需要拆解后再利用或處理的廢棄物[1]，通常都具有較高的回收價(jià)值。大件垃圾的收運(yùn)系統(tǒng)由收集、運(yùn)輸、處理共同組成，各個(gè)環(huán)節(jié)相互協(xié)調(diào)、合理規(guī)劃、優(yōu)化調(diào)度才能使整個(gè)大件垃圾收運(yùn)系統(tǒng)達(dá)到最優(yōu)化。但隨著居民預(yù)約上門收運(yùn)的時(shí)間窗的變化、大件垃圾的尺寸變化（大件垃圾的長、寬、高的信息錯(cuò)誤）等不可控制的客觀環(huán)境發(fā)生變化，就會(huì)造成原定路線的最優(yōu)方案的不能有效啟動(dòng)。結(jié)合干擾管理思想，對(duì)干擾事件進(jìn)行擾動(dòng)辨識(shí)和擾動(dòng)度量，分析干擾事件發(fā)生后可能會(huì)引起變化的變量、對(duì)整個(gè)大件垃圾收運(yùn)系統(tǒng)調(diào)度的影響及對(duì)擾動(dòng)的變量進(jìn)行偏離度量后，構(gòu)建大件垃圾預(yù)約上門收運(yùn)的干擾管理模型，為干擾事件發(fā)生時(shí)快速有效地啟動(dòng)應(yīng)急預(yù)案，最大程度地降低干擾事件的影響，保證大件垃圾預(yù)約上門收運(yùn)系統(tǒng)的持續(xù)高效的正常運(yùn)轉(zhuǎn)。

1 文獻(xiàn)概述

干擾管理的作用旨在當(dāng)干擾事件發(fā)生后，快速生成對(duì)系統(tǒng)擾動(dòng)最小的調(diào)整計(jì)劃，同時(shí)考慮費(fèi)用，但是并非只是費(fèi)用最小化。

干擾管理的研究越來越受到學(xué)界的關(guān)注，研究工作也在陸續(xù)展開。在有關(guān)干擾管理領(lǐng)域的研究方面，Yu等人[2]定義了干擾管理，Clausen等人[3]也基本認(rèn)為干擾事件發(fā)生后，干擾管理的目標(biāo)是使新方案相對(duì)于原方案的擾動(dòng)最小。文獻(xiàn)[4-9]都根據(jù)干擾管理思想，對(duì)不同干擾事件做出了一系列的研究處理，建立模型求解。

本文以干擾管理思想為基礎(chǔ)，對(duì)大件垃圾預(yù)約上門收運(yùn)系統(tǒng)中出現(xiàn)的大件垃圾尺寸變化的問題進(jìn)行研究，針對(duì)大件垃圾預(yù)約上門收運(yùn)系統(tǒng)的特點(diǎn)提出收運(yùn)容積偏離、收運(yùn)次數(shù)偏離、收運(yùn)距離偏離和路線偏離四種擾動(dòng)度量，提出大件垃圾預(yù)約上門收運(yùn)干擾管理模型，通過對(duì)收運(yùn)路線的局部實(shí)時(shí)調(diào)整，優(yōu)化干擾事件發(fā)生前的初始計(jì)劃路線，從而生成在線調(diào)整方案。

2 大件垃圾預(yù)約上門收運(yùn)干擾管理模型

2.1 問題描述及假設(shè)

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

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

（1）車庫和居民點(diǎn)，居民點(diǎn)和居民點(diǎn)，居民點(diǎn)和處理廠，處理廠和車庫的距離;

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

（3）各居民點(diǎn)的大件垃圾數(shù)量（ei）;

（4）車庫、各居民點(diǎn)、處理廠的地理位置（坐標(biāo)）;

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

（6）收運(yùn)車輛的行駛速度（即：距離/速度=行駛時(shí)間）;

（7）每個(gè)居民點(diǎn)被服務(wù)的時(shí)間si。

其中，假設(shè)每件大件垃圾的被收運(yùn)時(shí)間為0.2，si=居民點(diǎn)的大件垃圾數(shù)ei*0.2;收運(yùn)車輛在處理廠的停留時(shí)間=大件垃圾裝載總數(shù)*0.2。

2.2 擾動(dòng)辨識(shí)

2.3 擾動(dòng)度量

干擾管理的思想就是生成對(duì)系統(tǒng)擾動(dòng)最小的調(diào)整方案，且考慮原目標(biāo)函數(shù)最優(yōu)化。對(duì)此擬展開研究論述如下。

（1）大件垃圾收運(yùn)容積偏離的度量。數(shù)學(xué)公式可寫為：

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

（2）收運(yùn)次數(shù)的偏離。數(shù)學(xué)公式可寫為：

其中，gp表示車輛p收運(yùn)的次數(shù)，g0p表示原路線車輛p收運(yùn)的次數(shù)。

（3）收運(yùn)距離偏離的度量。數(shù)學(xué)公式可寫為：

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

（4）路線偏離的度量。數(shù)學(xué)公式可寫為：

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

2.4 擾動(dòng)恢復(fù)策略

根據(jù)符俊波等人提出的擾動(dòng)恢復(fù)策略，本文結(jié)合大件垃圾收運(yùn)過程及收運(yùn)特點(diǎn)，提出自救策略、鄰近救援策略和增派救援策略3種大件垃圾收運(yùn)車輛的擾動(dòng)恢復(fù)策略[9]。

2.5 建立虛擬收集點(diǎn)

本文為統(tǒng)一車輛收運(yùn)狀態(tài)，引入大件垃圾虛擬收集點(diǎn)概念[9]，將所有的收運(yùn)車輛統(tǒng)一至車庫或者大件垃圾處理廠。按照干擾發(fā)生時(shí)收運(yùn)車輛狀態(tài)建立虛擬收集點(diǎn)，對(duì)此可做闡釋分述如下：

（1）大件垃圾收運(yùn)車輛正在行駛至下一居民點(diǎn)的途中，則將收運(yùn)車輛前往的居民點(diǎn)設(shè)為收集點(diǎn)。

（2）大件垃圾收運(yùn)車輛正在對(duì)居民點(diǎn)進(jìn)行收運(yùn)服務(wù)，則將該居民點(diǎn)設(shè)為虛擬收集點(diǎn)。

（3）大件垃圾收運(yùn)車輛在車庫/處理廠，則無需設(shè)立虛擬收集點(diǎn)[9]。

2.6 干擾管理模型建立

本次研究得到的大件垃圾預(yù)約上門收運(yùn)干擾管理的數(shù)學(xué)模型詳見如下。

（1）目標(biāo)函數(shù)。對(duì)應(yīng)的數(shù)學(xué)公式可表示為：

（2）保證虛擬收集點(diǎn)第一個(gè)得到服務(wù)，且最終從大件垃圾處理廠返回到車庫。對(duì)應(yīng)數(shù)學(xué)公式可表示為：

（3）每個(gè)居民點(diǎn)被服務(wù)且只被服務(wù)一次。對(duì)應(yīng)數(shù)學(xué)公式可表示為：

（4）每條收運(yùn)路線上的大件垃圾總質(zhì)量不得超過車輛的最大裝載質(zhì)量，總體積不得超過車輛的最大裝載體積。對(duì)應(yīng)數(shù)學(xué)公式可表示為：

（5）保證每件大件垃圾必須全部在收運(yùn)車輛車廂內(nèi)部。對(duì)應(yīng)數(shù)學(xué)公式可表示為;

（6）為保證收運(yùn)車輛行駛安全，每輛車中的所有的大件垃圾重心必須在一定的安全范圍之內(nèi)。對(duì)應(yīng)數(shù)學(xué)公式可表示為;

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

3 模型算法設(shè)計(jì)

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

4 實(shí)例分析

數(shù)值試驗(yàn)平臺(tái)為Matlab 9.0，計(jì)算機(jī)CPU為英特爾酷睿 5、2.6 GHz，8 GB內(nèi)存，64位Windows10操作系統(tǒng)。

4.1 具體問題描述

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

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

居民點(diǎn)位置坐標(biāo)，各居民點(diǎn)處大件垃圾個(gè)數(shù)ei、總質(zhì)量qi，及居民下單預(yù)約大件垃圾上門收運(yùn)服務(wù)的時(shí)間窗范圍[ai，bi]、各居民點(diǎn)總服務(wù)時(shí)間si，見表2。各居民點(diǎn)處每件大件垃圾的長、寬、高及質(zhì)量見表3。

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

粒子群算法的參數(shù)設(shè)置為：種群規(guī)模popsize=50，最大迭代次數(shù)為gen=100，將算法通過Matlab語言實(shí)現(xiàn)，得出大件垃圾收運(yùn)車輛最優(yōu)上門收運(yùn)路線見表4、表5。

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

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

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

μ=0.05，θ=10，c1=100，c2=1，+=1，-=1。用本文設(shè)計(jì)的干擾管理模型對(duì)產(chǎn)生的擾動(dòng)進(jìn)行恢復(fù)，根據(jù)仿真實(shí)驗(yàn)知應(yīng)采取鄰近救援策略，得到干擾管理結(jié)果見表6、表7。

為驗(yàn)證本文構(gòu)建模型的有效性，選擇傳統(tǒng)的干擾處理方法-重調(diào)度法進(jìn)行仿真實(shí)驗(yàn)結(jié)果的對(duì)比，實(shí)驗(yàn)結(jié)果見表8。

結(jié)果表明，總體上干擾管理優(yōu)化結(jié)果明顯優(yōu)于重調(diào)度結(jié)果，大件垃圾預(yù)約上門收運(yùn)干擾管理模型有效，解決了預(yù)約上門收運(yùn)過程中因居民點(diǎn)處大件垃圾尺寸變化對(duì)收運(yùn)系統(tǒng)造成的影響，能夠快速進(jìn)行擾動(dòng)恢復(fù)，最大程度降低擾動(dòng)影響，對(duì)有關(guān)大件垃圾預(yù)約上門收運(yùn)方式的深入研究做了鋪墊。

5 結(jié)束語

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

參考文獻(xiàn)

[1]GB/T25175-2010. 大件垃圾收集和利用技術(shù)要求[S]. 北京：中華人民共和國國家質(zhì)量監(jiān)督檢驗(yàn)檢疫總局，中國國家標(biāo)準(zhǔn)化管理委員會(huì)，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]王旭坪，許傳磊，胡祥培.有顧客時(shí)間窗和發(fā)貨量變化的車輛調(diào)度干擾管理研究[J].管理科學(xué)，2008，21（5）：111-120.

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

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

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

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

[9]符俊波，馬慧民，張爽，等.有垃圾量變動(dòng)的生活垃圾收運(yùn)車輛調(diào)度干擾管理研究[J].上海理工大學(xué)學(xué)報(bào)，2017，39（4）：368-375.

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