垃圾處理論文閲讀： A robust periodic capacitated arc routing problem for urban waste collection considering drivers and crew’s working time
- 1、Introduction
- 與城市垃圾收集相關的兩類問題
- 此文章採用第二類問題形式
- 2、模型的設定
- 問題的假設
- 參數、變量的設置
- 3、問題的求解
1、Introduction
固體廢物管理的60% - 80%的成本與收集和運輸有關，廢物的收集、運輸和處置應在最短的時間內，通過最好的方法，並直接從家庭地區到處置地點。
與城市垃圾收集相關的兩類問題
- 第一類 ：有一系列預先定義的具有正向需求的節點，目標是找到覆蓋所有節點的車輛路徑問題(CVRP)的最佳路線；
- 第二類 ：存在一系列具有正需求或零需求的預定義邊，其目標是找到覆蓋所有必需邊（具有正需求的邊）的最佳路線問題（CARP）；
此文章採用第二類問題形式
1、垃圾是沿着邊緣(即有需求的街道或小巷)。
2、車輛的容量是有限的，當車輛穿越所需的邊緣時，其剩餘容量會下降。
3、駕駛員和工作人員的工作時間是除容量約束外，對確定所需車輛數量有很大影響的另一個重要參數。
4、目標被定義為在一週內根據每日計劃確定服務所需邊緣的最佳路線。
2、模型的設定
1、該問題是在規劃的所有時間段內，以最小化車輛的使用成本和所有遍歷邊的遍歷成本為目標函數，確定每輛車的最優車輛數和每輛車可能的多次出行的最優行程。
2、車輛的位置首先是在倉庫中。他們開始他們的旅行，以通過收集廢物來服務所需的邊緣，然後在滿載後返回倉庫。
3、車輛的容量約束和車輛的最大可用時間決定了所需車輛的數量。事實上，司機的工作時間是每輛車可考慮的最長時間。
4、由於需求參數被認為是不確定的，基於Bertsimas和Sim(2004)提出的區間魯棒優化方法，提出了魯棒模型。
問題的假設
1、目標函數除了最小化邊的遍歷成本外，還要最小化滿足總需求所需車輛的數量。
2、每條有需求的邊僅由一輛車提供服務，且問題中僅考慮一個倉庫。
3、車輛是異構的，圖網絡是不對稱的，每輛車從倉庫出發，然後返回倉庫。
4、每種類型的車輛在每條邊都有獨立的平均速度和廢物裝載時間。
5、每個車輛的旅行時間和廢物裝載時間都不同。
6、車輛使用成本是每輛車支付給司機和相關人員的費用。
7、每輛車輛都有一個最長使用時間，表示其駕駛員和工作人員的工作時間。
8、每輛車可能有多次行程
9、計劃是有時限的。計劃期限是一週。每一個需要的邊緣應該每天服務。每輛車的收集計劃以每天為基準確定為每週最優。
10、所需邊緣的需求在給定的不確定性區間內波動。
參數、變量的設置
V：圖網絡中節點的集合
K：車輛的集合
E：網絡中定義的所有邊的集合
Er：網絡中定義的所有需要的邊的集合
T：時間段集
O：可能的多次旅行的集合
S：網絡中定義的所有邊的可選集
V[S]：S中定義的節點的集合
dis(ij)：（i,j）之間的距離
Vel(ijk)：在弧（i,j）上第K輛車的平均速度
Lw(ijk)：在弧（i,j）上第K輛車的廢物裝載時間
d(ijt)：在t時刻，弧（i,j）的廢物不確定性需求
d(ijt)’:在時刻t，弧（i.j）上的廢物的平均需求
cv(k)：第K輛車的使用成本
W(k)：每次行程第K輛車的容量
T(max)：每個period內，車輛的最大可用時間
r：距離與成本的換算比率
M：一個非常大的數
3、問題的求解
由於問題的複雜程度很高，並且考慮到所提出模型的約束條件存在不確定性，因此僅在小規模問題中才可能通過精確方法解決問題。
因此，使用基於啓發式算法和模擬退火（SA）算法的混合算法來近似解決該問題。
實施啓發式算法以生成一些初始解，然後將SA算法應用於提供最佳可行解。
GAMS軟件的CPLEX求解器用於精確解決問題並評估所提出算法的效率。