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

張燕，李子鑫，劉進平

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

0 引言

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

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

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

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

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

1 問題描述與模型建立

1.1 問題描述

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

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

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

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

1.2 模型參數與變量

(1)相關集合

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

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

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

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

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

(2)參數定義

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

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

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

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

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

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

H——收運車在每個時段內可以進行多行程收運的最大次數；

M——極大的正數。

(3)決策變量

1.3 數學模型

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

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

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

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

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

2 問題求解與算法設計

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

2.1 啟發式算法的設計及實現

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

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

2.2 初始解的構造及初始解

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

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

2.3 適應度函數

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

式中：zs——當前解s的目標函數；

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

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

適應度函數fs的值越小，表明當前解的質量越高。

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

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

(1)移除算子

①R1隨機移除

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

②R2最差點移除

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

③R3相關移除

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

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

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

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

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

?、ρ、σ、?——影響因素的權重。

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

(2)插入算子

①INS1貪婪插入

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

②INS2最大后悔值準則插入

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

(3)局部搜索算子

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

①LS1轉移(Shift)

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

②LS2交換(Swap)

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

③LS3 2-opt搜索

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

④LS4 2-opt*搜索

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

⑤LS5 平衡性改進(Balance)

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

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

(4)算子權重的更新

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

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

3 算例驗證

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

3.1 算例設置

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

表1 算例規模及相關參數Table 1 Instance setting and parameters

3.2 算例驗證

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

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

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

3.3 駕駛員工作平衡性檢驗

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

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

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

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

4 實例分析

為進一步驗證本文的模型和算法在求解實際問題時的有效性，選取大連市中山區的餐飲垃圾收運網絡作為實際案例進行分析。在實例求解中，根據實際調研的結果以及相關文獻中的數據，設定相關數據。

4.1 實例數據

(1)收運點及產生量

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

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

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

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

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

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

表5 常發生擁堵的主干路及擁堵系數Table 5 Congestion coefficients of some main roads

4.2 結果分析

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

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

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

表7 餐飲垃圾收運路線優化結果對比Table 7 Comparison of food waste collection route solutions

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

5 結論

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

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

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

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