以限制多目標演化演算法求解具時窗限制之車輛路由問題

Abstract

「時窗限制車輛路由問題 (Vehicle Routing Problem with Time Windows, VRPTW)」在原有的車輛路由問題 (Vehicle Routing Problem, VRP) 上增添時間的限制，增加了題目的難度，但也更符合現實生活中的需求。此問題的研究已有20多年歷史。過去的精確演算法對於如此困難的問題，往往不能求解規模龐大的輸入。近年許多研究偏好採用多目標最佳化的方式解決，但因此問題的時窗限制較難修復，較少人會提及不合法解的處理。 本研究修改自現有的MOEA-EO [14]。在交換最佳的路由時，總是選擇客戶數目最多的，以祈刪除最多的客戶以減少路由數目。在限制處理上，環境的選擇會依據解的合法性，使用不同的凌越關係來分級。合法的解會使用傳統的解題目標來分級，不合法的解會使用限制的違反量來分級。最後會以交互的方式篩選出可以存活到下一代的個體，適當保留不合法的個體以增加搜尋的廣度。 本演算法對於客戶數目較少的問題已有不錯的表現。在Solomon 25個客戶的問題中，更新了9個最佳解。