考慮工作量平衡的餐飲垃圾多行程收運路線優(yōu)化

張燕，李子鑫，劉進平

(大連海事大學，交通運輸工程學院，遼寧大連 116026)

0 引言

作為具有悠久飲食文化的國家，近年來隨著經(jīng)濟發(fā)展和城市化進程的加快，我國城市的各大餐館和企事業(yè)單位食堂產(chǎn)生的餐飲垃圾也隨之激增。為改善環(huán)境，更有效地利用資源，很多城市開始試點餐飲垃圾分類收運和處理。然而，高收運成本成為推進餐飲垃圾分類管理的一大障礙，如何以更低的成本完成餐飲垃圾的分類收運成為實施垃圾分類管理的重中之重[1]。同時，隨著智慧城市成為未來城市的發(fā)展理念，很多行業(yè)和企業(yè)嘗試采用優(yōu)化算法降本增效，但大多數(shù)算法只關(guān)注成本，沒有考慮工作人員的人本需求[2]。本文針對餐飲垃圾的收運特點提出相應的收運模型及算法，致力于在降低餐飲垃圾分類收運成本的同時，提升駕駛員的工作滿意度，對于提升城市廢物管理水平，推動城市的可持續(xù)發(fā)展具有重要意義。

在以往的相關(guān)研究中，不少學者針對居民生活垃圾的收運路線優(yōu)化問題進行了研究。例如，LEI等[3]考慮生活垃圾的周期性收運路線優(yōu)化和車輛調(diào)度問題，建立多周期的車輛路徑問題模型，并采用兩階段算法求解問題；ASEFI 等[4]考慮多種廢物類型的收運問題，建立車隊規(guī)模和混合車輛路徑優(yōu)化問題模型，并對小規(guī)模問題進行求解；ALIAHMADI等[5]考慮運營成本和收運時間兩個目標，建立帶時間窗的多行程車輛路徑問題模型，并采用多目標優(yōu)化算法求解問題；閆芳等[6]結(jié)合智能垃圾桶提出動態(tài)生活垃圾收運優(yōu)化策略，通過粒子群算法獲得初始收運方案，然后，采用重置優(yōu)化算法實時調(diào)整收運路徑。同時，也有學者結(jié)合新的技術(shù)方法，例如，李明月等[7]考慮時間成本及環(huán)境成本，提出一種基于GIS技術(shù)與改進蟻群算法的垃圾收運路徑優(yōu)化方法；GLAESER 等[8]針對地下廢物收運系統(tǒng)，建立以收運成本最小化為目標的垃圾箱分配和車輛路徑問題的數(shù)學模型，并設計變鄰域啟發(fā)式算法求解問題。

與城市生活垃圾的收運不同，餐飲垃圾的收運路線優(yōu)化問題需要考慮以下因素：首先，由于各個餐飲企業(yè)及企事業(yè)單位食堂產(chǎn)生餐飲垃圾量和高峰時段不同，因此，需要針對不同的企業(yè)類型設置不同的收運頻率、收運時段和服務時間窗，以便均衡各個時段的垃圾收運量；第二，餐飲垃圾含水量大，難以壓縮，餐飲垃圾收運車在每個收運時段內(nèi)需要多次進出餐飲垃圾處理廠進行卸貨；第三，城市餐飲企業(yè)集中于商業(yè)區(qū)或者小吃街附近，因此，在設計優(yōu)化路線時需考慮實際道路的擁堵因素以及限行要求。

因此，餐飲垃圾的收運路線優(yōu)化是一個考慮時間窗約束的多行程車輛路徑問題(Multi-Trip Vehicle Routing Problem with Time Windows,MTVRPTW)，學者們針對該問題提出了不同的模型和算法。例如，F(xiàn)RANCOIS 等[9]建立以總行駛距離為目標函數(shù)的多行程車輛路徑數(shù)學模型，并設計帶有多行程算子的自適應大鄰域搜索算法；彭勇等[10]考慮帶時間窗的多行程交換箱甩掛路徑問題，并設計混合遺傳算法，以充分利用司機日常工作時間；PAN 等[11]以最小總運輸距離為目標，研究城市物流配送中時變路網(wǎng)下的多行程車輛路徑問題，并采用混合元啟發(fā)式算法求解問題。但是，現(xiàn)有研究大多考慮的都是單一車場，且大多是以總行駛距離或時間為目標函數(shù)，缺少針對餐飲垃圾的收運特點所提出的相應模型和算法。

本文首先建立具有時間窗約束的多行程餐飲垃圾收運問題的混合整數(shù)規(guī)劃模型，并根據(jù)問題特點設計混合自適應大鄰域搜索算法。在模型和算法中，考慮駕駛員的各項工作需求，例如，保障駕駛員的午休以及工作強度不超標，保證駕駛員之間的工作平衡；同時，還考慮城市實際路網(wǎng)的擁堵情況，得到既節(jié)省成本又降低碳排放，還能提高駕駛員工作滿意度的最優(yōu)路線。

1 問題描述與模型建立

1.1 問題描述

本文考慮城市中的餐飲垃圾收運路線優(yōu)化問題，其中，餐飲垃圾的收運來源包括各種不同類型的餐館和企事業(yè)單位食堂。首先，根據(jù)各類型餐館和單位食堂的營業(yè)特點，設定兩種收運頻率：每天兩次或每天一次。對于夜市及早餐為主的餐飲企業(yè)，每天上午(時段1)收運一次，對于不供應晚餐的企事業(yè)單位食堂等，每天下午(時段2)收運一次；對于全天營業(yè)的餐館及食堂，每天上午和下午各收運一次。

餐飲垃圾的收運網(wǎng)絡由餐飲垃圾的收運點、車場和餐飲垃圾處理廠組成。每輛餐飲垃圾收運車在每個收運時段內(nèi)完成一個混合的多行程任務，如圖1 所示。每輛車收運任務的第一段行程為開放式行程，車輛從車場空車出發(fā)，沿途訪問收運點之后，到達處理廠卸貨，之后的收運任務是以處理廠為中心的多個閉合式行程，最后一段是完成收運任務后空載返回車場的行程。

圖1 混合多行程的餐飲垃圾收運路線示例Fig.1 Illustration of hybrid multi-trip food waste collection route

駕駛員在上午時間段的收運任務完成后，返回車場午休后，再進行下午的收運。駕駛員每天的工作任務總時長不超過最長工作時間，并且各個駕駛員之間的工作量盡可能平衡。同時，本文考慮車輛在實際道路行駛過程中的擁堵因素，將車輛在任意兩點間的行駛時間計為正常行駛時間加上擁堵時間。假設餐飲垃圾的處理設施容量足夠大，每個收運點的餐飲垃圾不允許分批收運。該問題的目標是在保證駕駛員工作量不超標且平衡的情況下為每個時段設計合理的收運路線，從而最小化收運過程中的車輛固定成本和燃油成本。

1.2 模型參數(shù)與變量

(1)相關(guān)集合

Na={1,2,…,n}——所有餐飲垃圾收運點的集合，其中，n為收運點數(shù)目；

Ne={0,1,2,…,n,n+1}——包含車場、收運點和處理廠的擴展集合，其中，0為車場，n+1 為餐飲垃圾處理廠；

Np——在時段p收運的所有收運點集合；

V={1,2,…,Vmax}——收運車輛集合，其中，Vmax為收運車輛的總數(shù)量；

P={1,2,…,T}——餐飲垃圾收運時段集合。

(2)參數(shù)定義

對于收運點(i,j)∈Ne，車輛k∈V，時段p∈P，定義以下參數(shù)。

tˉij——收運車在收運點(i,j)間的正常行駛時間(min)；

Qmax——餐飲垃圾收運車的最大凈載量(kg)；

cV——收運車的單位固定運營成本(元·d-1·輛-1)，包含車輛折舊和駕駛員薪酬；

cS——收運車在擁堵和裝卸服務時的怠速燃油成本(元·min-1)；

cD——收運車正常行駛時的單位燃油成本(元·min-1)；

H——收運車在每個時段內(nèi)可以進行多行程收運的最大次數(shù)；

M——極大的正數(shù)。

(3)決策變量

1.3 數(shù)學模型

根據(jù)以上參數(shù)和變量定義，本文所考慮的帶時間窗約束的混合多行程的餐飲垃圾收運問題(HMTVRPTW)的數(shù)學模型(模型M)為

目標函數(shù)式(1)表示最小化所有時段的總收運成本，包括車輛的固定運營成本、車輛在交通擁堵以及裝卸作業(yè)時的怠速燃油成本和正常行駛時的燃油成本。

式(2)～式(15)是關(guān)于混合多行程收運路線的約束。其中，式(2)表示第一段的開放行程需要從車場出發(fā)；式(3)表示收運車的第一段開放行程中不可以從車場直接到達處理廠；式(4)表示最后一段的空載行程必須返回車場；式(5)和式(6)表示實際派出收運車的數(shù)量不超過最大數(shù)量；式(7)表示收運車需完成當前時段內(nèi)所有收運點的收運任務；式(8)表示收運車不訪問不屬于當前時段的收運點；式(9)表示收運車在每個收運點收運完成后，需離開；式(10)表示各收運點自身無路徑產(chǎn)生；式(11)表示收運車訪問收運點之后，需前往處理廠卸貨，不可以從收運點直接返回車場；式(12)表示每個時段內(nèi)收運車執(zhí)行多行程的最大數(shù)量限制；式(13)～式(15)表示收運車被使用時才會產(chǎn)生多行程路徑。

式(16)～式(18)為收運車容量相關(guān)的約束。其中，式(16)表示各收運點的垃圾量需一次性收集完；式(17)表示收運車收運的垃圾不超過其最大凈載量；式(18)表示開放行程中，收運車需在車場空車出發(fā)，并在到達處理廠后卸空垃圾。

式(19)～式(26)為時間相關(guān)的約束。其中，式(19)表示加上擁堵時間后的收運車實際行駛時間；式(20)～式(23)表示收運車到達各點的訪問時間需滿足路線訪問順序；式(24)表示收運車的到達時間必須小于各收運點的最晚收運時間窗；式(25)和式(26)為工作平衡性約束。

2 問題求解與算法設計

本文建立的模型M為混合整數(shù)規(guī)劃模型，對于小規(guī)模問題，采用AMPL+GUROBI直接求解，得到最優(yōu)解。當問題規(guī)模較大時，模型M無法在有效時間內(nèi)求解。為滿足求解大規(guī)模實際問題的需要，本文設計了混合自適應大鄰域搜索算法(Hybrid Adaptive Large Neighborhood Search algorithm,HALNS)，在短時間內(nèi)得到問題的近似最優(yōu)解。

2.1 啟發(fā)式算法的設計及實現(xiàn)

自適應大鄰域搜索算法(Adaptive Large Neighborhood Search,ALNS)是在大鄰域搜索算法(Large Neighborhood Search,LNS)的基礎上，加上算子權(quán)重的自適應調(diào)整，即在每次迭代時會根據(jù)當前解的質(zhì)量更新算子的權(quán)重，從而使算法在尋優(yōu)過程中能自主調(diào)整各個算子被選擇的概率。本文提出的HALNS 算法在ALNS 算法的基礎上，加入局部搜索算子，以提升算法的尋優(yōu)能力。HALNS 算法的整體流程如圖2所示。

圖2 HALNS算法流程Fig.2 Flowchart of HALNS

2.2 初始解的構(gòu)造及初始解

根據(jù)問題多行程路線的特點，本文采用三維矩陣對解進行編碼，如圖3所示。所有車的路線組成一個完整的解，每輛車的路線由多個行程組成。為保證解的可行性，需要保證每輛車的行程總數(shù)不超過車輛最大行程數(shù)，且每段行程的收運量均不超過收運車的最大容量。

為獲得初始可行解，采用貪婪算法構(gòu)造初始路線，具體過程如下：首先，按節(jié)點編號順序選擇收運點，以加入空車的行程路線，當該行程中垃圾量達到收運車的最大載量Qmax時，新增下一段行程，并將剩余的收運點增加到新行程中，循環(huán)此過程直至該收運車的總行駛時間達到駕駛員的工作最晚時間；然后，選取新的收運車，并重復上述步驟；直至該時段所有收運點均完成。

2.3 適應度函數(shù)

為滿足收運時間窗和駕駛員工作平衡的約束，構(gòu)造帶懲罰函數(shù)的適應度函數(shù)fs，即

式中：zs——當前解s的目標函數(shù)；

Es，Ls——當前解s中，違反式(25)和式(26)的工作時間；

η——懲罰系數(shù)(經(jīng)實驗，取η=500)，表示當前解s違反時間窗式(25)和式(26)時的單位時間懲罰成本。

適應度函數(shù)fs的值越小，表明當前解的質(zhì)量越高。

2.4 鄰域解的更新及算子設計

根據(jù)問題特性，本文設計了3 種移除算子和2 種插入算子，以獲得新的鄰域解。為產(chǎn)生新的鄰域解，需要先從當前解中移除m個收運點，再將這些點插入到新的位置里。在每次迭代中，移除的收運點數(shù)目m從范圍中隨機產(chǎn)生，其中，|Np|表示當前時段收運點的總數(shù)量，λ1和λ2分別表示要移除的收運點占總收運點數(shù)的下界與上界比例值(0＜λ1＜λ2＜1)。經(jīng)實驗，本文選取λ1=0.10，λ2=0.25。各個算子的規(guī)則如下。

(1)移除算子

①R1隨機移除

從當前解中隨機移除一個收運點。

②R2最差點移除

移除使當前解適應度值增加最多的收運點。定義當前解s 中收運點i 的邊際成本，其中，表示從當前解s 中移除收運點i 后的適應度值，將最大的點移除。

③R3相關(guān)移除

根據(jù)收運節(jié)點之間的相似度進行移除[12]，即先隨機移除一個收運點i，再移除與收運點i相似度最高的收運點j。本文通過距離、交通狀況、時間窗要求及餐飲垃圾量這4方面衡量相似度，收運節(jié)點i和j的相似度R(i,j)為

式中：dij——收運點i和j之間的距離；

cij——收運點之間的交通狀況；

|li-lj|——收運點之間最晚開始服務的時間差異；

|qi-qj|——收運點之間的需求差異；

?、ρ、σ、?——影響因素的權(quán)重。

R(i,j)越小，表示相似度最大。

(2)插入算子

①INS1貪婪插入

將從當前時段的收運路線中移除的收運點插入到使得當前解的適應度值增加最少的位置。

②INS2最大后悔值準則插入

令fk表示當前解的適應度值，用fik表示當前解插入收運點i后第k低的適應度值，令ΔFk=fik-fk，當k≤k'時，滿足ΔFk≤ΔFk'，定義后悔值ci=ΔF2-ΔF1，表示把收運點i插入到當前解的最優(yōu)位置和次優(yōu)位置的差值，將最大后悔值的收運點插入到當前解中。

(3)局部搜索算子

使用移除和插入算子產(chǎn)生新的鄰域解之后，采用局部搜索算子改善產(chǎn)生的鄰域解，改善后的解作為當前解。每次迭代的改進次數(shù)為ω次，每次使用的算子從以下5種隨機選擇。

①LS1轉(zhuǎn)移(Shift)

隨機選擇一輛車，從該車的一段行程中隨機選擇一個收運點，移動到其他行程中。

②LS2交換(Swap)

隨機選擇兩輛車，從已有行程中隨機選擇兩個收運點，交換兩收運點位置。

③LS3 2-opt搜索

從某一行程中隨機選擇兩個收運點，翻轉(zhuǎn)兩點之間的收運點順序。

④LS4 2-opt*搜索

隨機選擇兩輛車，從不同行程路徑中隨機選擇兩個收運點，交換該兩點之后的收運路徑。

⑤LS5 平衡性改進(Balance)

對于工作結(jié)束時間超過駕駛員最晚工作時間的多行程路線，從中隨機選取一段行程，并將其插入到另外一條工作時間較短的多行程路線中，使各個路線的總工作時間盡可能平衡。

對于經(jīng)過局部搜索改進的鄰域解，需要使用如下規(guī)則判斷是否將其接受為新的當前解。當新解優(yōu)于當前最好解時，則接受新解；否則，根據(jù)模擬退火接受準則，以概率接受新解，其中，f'為新解的適應度值，f為當前解的適應度值，D表示當前溫度，其初始溫度為D=D0，每次迭代后，D通過D=θD更新，0＜θ ＜1，本文選取D0=30，θ=0.94。最后，若算法連續(xù)迭代φ次未能更新解，或達到最大迭代次數(shù)ψ時，算法終止。本文選取φ=30，ψ=300。

(4)算子權(quán)重的更新

在迭代下一代鄰域解之前，需要依據(jù)當前解的質(zhì)量更新移除和插入算子的權(quán)重。令po表示算子o被選擇的概率，表示在第t次迭代時算子o的權(quán)重，算子被選擇的概率以及算子權(quán)重的迭代方法為

設定移除和插入算子每20代更新一次，其中，算子o的初始得分為10；算子更新參數(shù)α=0.7；表示算子o在第t次更新時，在近20代迭代中被選中的次數(shù)；表示算子o在第t次更新時，在近20次迭代中得到的解的總評分。評分方式如下：若在迭代后得到的鄰域解snew不劣于當前的全局最好解sbest，得 分40；若sbest≤snew≤sold，則得分30；若snew＞sold，但該解被接受，則得分20；否則，得分為0。

3 算例驗證

為驗證所建立的數(shù)學模型和提出算法的有效性，采用不同規(guī)模的算例，將GUROBI 求解數(shù)學模型M得到的解與HALNS和ALNS算法得到的解進行比較。

3.1 算例設置

本文從Solomon 標準算例庫中選取不同規(guī)模的車輛路徑問題算例，并對原數(shù)據(jù)進行以下調(diào)整，適應求解本文問題：(1)劃分兩個收運時段，將需求點劃分為3種收運方式(上午、下午及上下午)，并調(diào)整需求點的時間窗和收運量；(2)原數(shù)據(jù)中僅含有車場，無處理廠，本文選取接近中心的位置虛擬為處理廠位置，并設定車輛在處理廠的卸料時間為5 min；(3)為適應多行程收運，縮減了車容量；(4)原數(shù)據(jù)中不考慮擁堵，故該部分將擁堵時間設置為0；(5)原數(shù)據(jù)中不含收運成本，本文設定每輛車的固定使用成本為200 元·時段-1，燃油成本為1 元·min-1。具體參數(shù)的調(diào)整情況如表1所示。

表1 算例規(guī)模及相關(guān)參數(shù)Table 1 Instance setting and parameters

3.2 算例驗證

算例R1～R5的求解結(jié)果如表2所示，每個算例均采用3 種方法求解，即AMPL+GUROBI 9.5.2 直接求解模型、ALNS 算法和HALNS 算法。其中，ALNS算法采用與HALNS算法相同的初始解產(chǎn)生方案，以及相同的移除和插入算子，但沒有加入局部搜索算子。HALNS 算法中，根據(jù)算例規(guī)模的不同設定不同的局部搜索次數(shù)值(ω)，其中，R1和R2中，ω=50；R3 中，ω=100；R4 中，ω=200；R5 中，ω=1000。HALNS 和ALNS 的算法均采用Python編程實現(xiàn)。

表2 算例求解結(jié)果對比Table 2 Comparison of solutions obtained by different algorithms

表2 的后兩列給出每個算例求解10 次后得到的平均求解時間和平均目標值?？梢钥闯?，對于小規(guī)模算例R1～R3，雖然直接采用GUROBI求解模型M 需要較長時間，但是，可以得到問題的最優(yōu)解或近似最優(yōu)解。HALNS算法和ALNS算法的求解時間較短，但不是每次求解都可以得到最優(yōu)解。相比較之下，HALNS 算法得到最優(yōu)解的次數(shù)多于ALNS 算法，所以，HALNS 算法的平均目標值低于ALNS 算法。當算例規(guī)模增大時，GUROBI 無法在合理時間內(nèi)得到最優(yōu)解，但HALNS 和ALNS 算法都能在短時間內(nèi)得到近似最優(yōu)解，且HALNS 算法在解的質(zhì)量和求解時間上明顯優(yōu)于ALNS算法，所以，HALNS算法更適合求解大規(guī)模問題。綜上，算例求解結(jié)果驗證了本文模型的正確性以及HALNS算法的有效性。

3.3 駕駛員工作平衡性檢驗

算例R1～R5 在有平衡性約束和無平衡約束的情況下得到的結(jié)果對比如表3 所示。令ΔTB表示考慮平衡約束時駕駛員的工作時間差(最大工作時長減最小工作時長)，ΔTN表示不考慮平衡約束時駕駛員的總工作時間差，當考慮平衡約束時，對駕駛員的工作量平衡性的改善程度為αB；同樣，令CB表示考慮平衡約束時的總成本，CN表示不考慮平衡約束時的路線總成本，考慮平衡約束后總成本的增加程度為αC，即

表3 工作平衡性對比結(jié)果Table 3 Comparison of workload balancing

表4 油耗參數(shù)定義與取值Table 4 Definition and value for parameters related to fuel consumption

從表3 可以看出，當考慮工作量平衡性約束時，總成本雖有小幅增加(小于2%)，但駕駛員的工作平衡性能得到大幅度改善，尤其當算例規(guī)模增大時，考慮平衡性約束的優(yōu)勢更為明顯。

4 實例分析

為進一步驗證本文的模型和算法在求解實際問題時的有效性，選取大連市中山區(qū)的餐飲垃圾收運網(wǎng)絡作為實際案例進行分析。在實例求解中，根據(jù)實際調(diào)研的結(jié)果以及相關(guān)文獻中的數(shù)據(jù)，設定相關(guān)數(shù)據(jù)。

4.1 實例數(shù)據(jù)

(1)收運點及產(chǎn)生量

首先，依據(jù)大連市目前餐飲垃圾的分類實施情況，收運來源僅考慮大中型餐飲企業(yè)和各企事業(yè)單位食堂。本文通過調(diào)研得到大連市中山區(qū)的228 個餐飲垃圾收運點，并將其位置信息導入到地理信息系統(tǒng)軟件(ARCGIS)中，如圖4所示。根據(jù)文獻[13]確定大中型餐飲企業(yè)餐飲垃圾的產(chǎn)生量均值分別為360 kg·d-1和191 kg·d-1，以均值上下浮動10%為取值范圍隨機產(chǎn)生不同餐飲企業(yè)的產(chǎn)生量。企事業(yè)單位食堂的餐飲垃圾產(chǎn)生量根據(jù)各企事業(yè)單位的在職人數(shù)乘以人均日餐飲垃圾產(chǎn)生量(0.23 kg·d-1·人-1)得到。同時，根據(jù)各餐飲企業(yè)的性質(zhì)和營業(yè)高峰期，確定上下午兩個收運時段和兩種收運頻率。其中，營業(yè)高峰期為晚上的餐飲企業(yè)在每天的時段1，即8:00-12:00收運；營業(yè)高峰期在早上和中午的餐飲企業(yè)在每天的時段2，即14:00-18:00收運；全天營業(yè)的餐飲企業(yè)在時段1和時段2各收運一次。

圖4 大連市中山區(qū)餐飲垃圾收運點示例Fig.4 Illustration of food waste collection points in Zhongshan District,Dalian

(2)收運車輛油耗及道路擁堵系數(shù)

在實例求解時，本文根據(jù)實際調(diào)研的車輛數(shù)據(jù)，結(jié)合BARTH 等[14]開發(fā)的Comprehensive Emission Model 計算收運車以不同速度行駛的油耗，其中，收運車輛以速度v行駛t段時間的油耗為

另外，本文對速度和載重量對于油耗的影響進行靈敏度分析發(fā)現(xiàn)，餐飲垃圾收運車的油耗量對速度的敏感性較高，而對載重量的敏感性較低。因此，本文按照收運車輛在城區(qū)和非城區(qū)的實際行駛路程采用兩種速度。根據(jù)文獻[5,15]，并結(jié)合實際調(diào)研，設定收運車輛在城區(qū)的運行速度v為30 km·h-1，在非城區(qū)的行駛速度v為70 km·h-1。當收運車遇到擁堵路段或在收運點和垃圾處理廠進行作業(yè)時，收運車處在怠速狀態(tài)，根據(jù)文獻[16]設定收運車輛怠速時油耗FC為2.20 L·h-1。收運車的凈載量設定為2.5 t，車輛固定成本為500元·時段-1(每個時段為4 h)，柴油價格為7.2元·L-1。

為確定主要道路的擁堵系數(shù)，首先，通過高德地圖獲取大連市中山區(qū)的歷史交通擁堵數(shù)據(jù)，并通過計算得到主干道路在各個時段的擁堵系數(shù)，如表5 所示；然后，通過擁堵系數(shù)得到車輛在路線上的擁堵時間(擁堵時間為兩點距離乘擁堵系數(shù))。

表5 常發(fā)生擁堵的主干路及擁堵系數(shù)Table 5 Congestion coefficients of some main roads

4.2 結(jié)果分析

采用HALNS算法求解實例得到的車輛路線如表6所示，其中，HALNS 算法每次迭代的局部搜索次數(shù)ω設定為1000，連續(xù)迭代未更新解次數(shù)φ=30，最大迭代次數(shù)ψ=200。

表6 HALNS算法求解實例得到的收運路線Table 6 Food collection routes obtained by HALNS for real case

HALNS算法與當前某餐飲垃圾智能收運系統(tǒng)中采用的優(yōu)化算法(BAU)求解結(jié)果的對比情況如表7所示。其中，BAU中采用兩階段方法，首先，將收運區(qū)域劃分為6 個子區(qū)域；然后，求解一個旅行商問題，得到各個區(qū)域的收運路線。同時，當前實際優(yōu)化算法設定每個收運點的收運頻率均為每天一次，也未考慮駕駛員的工作量平衡情況以及道路擁堵情況。

表7 餐飲垃圾收運路線優(yōu)化結(jié)果對比Table 7 Comparison of food waste collection route solutions

表7 的對比結(jié)果表明，本文提出的HALNS 算法能對收運路線進行更合理的安排，不僅可以降低14.3%的總收運成本，還能在少用1 輛車的情況下減少2%的總工作時間，使駕駛員的工作平衡性提升57.3%。另外，從環(huán)境角度，通過在模型中考慮擁堵時間，使求解結(jié)果能更有效地規(guī)避擁堵路段，使收運過程中的碳排放量降低12.7%。

5 結(jié)論

本文拓展了對于車輛路線優(yōu)化方面的研究，為城市餐飲垃圾的收運提供了降本增效的實際解決方案，對于提升城市管理水平，加快智慧城市的建設，促進經(jīng)濟、社會和環(huán)境的可持續(xù)發(fā)展具有重要意義。本文得到的主要結(jié)論如下：

(1)所建立的模型M 和提出的算法HALNS 能在降低成本的同時提高駕駛員工作量的平衡性。首先，通過將收運點劃分到不同收運時段，均衡各個時段的垃圾收運量；然后，在優(yōu)化每個時段的收運路線時，考慮駕駛員的工作量平衡約束。優(yōu)化結(jié)果表明，在成本增加值不超過2%的情況下，可以將工作量的平衡性提高36%～98%，而且算例的規(guī)模越大，對于不平衡性的改善效果越明顯。

(2)采用模型和算法能有效求解具有時間窗約束的多行程餐飲垃圾收運問題。對于小規(guī)模問題，直接求解所建立的混合整數(shù)規(guī)劃模型能得到問題的最優(yōu)解；對于中大規(guī)模算例，采用提出的HALNS算法能在較短時間內(nèi)得到問題的近似最優(yōu)解。

(3)研究思路及算法適用于實際問題的求解與優(yōu)化。以大連市中山區(qū)的餐飲垃圾收運為例，考慮實際路網(wǎng)的道路擁堵情況和駕駛員的工作平衡性約束等現(xiàn)實因素時，相比當前實際應用的優(yōu)化算法，HALNS算法能在經(jīng)濟方面降低14.3%的總收運成本，環(huán)境方面降低12.7%的碳排放量，社會方面減少駕駛員總的工作時長，并將工作量的不平衡性改善57.3%。