以文化基因演算法求解大型多目標且具時窗限制之車輛路由問題

Abstract

具時間窗車輛路由問題 (Vehicle Routing Problem with Time Windows, VRPTW) 為車輛路由問題(Vehicle Routing Problem)再加上時間窗限制，而車輛路由問題係為一個派車站派出多輛車輛服務顧客點，在生活實務上已經有相當廣泛的運用，包括宅配、垃圾回收車路線規劃、銀行運鈔車及定點巡邏車路線規劃。 本論文以具時窗限制之車輛路由問題為主題，其求解目標為最小化車輛數和總行駛距離，由柏拉圖最佳化觀點求解，提出文化基因演算法的求解方法。此文化基因演算法採用共生關係，即為允許違反限制解存在於族群中，初始解產生時會產生合法解與違反限制解，再由基因演算法以多目標進行最佳化。基因演算法產生交配產生的子代會使用突變策略進行修復與改善，接著區域搜尋法對產生的子代進行目標的最佳化或是對族群的多樣性加以擾動，藉此產生的子代會依一定比例讓違反限制解存活於族群中。 測試問題集是以Gehring與Homberger (1999)建立的200個顧客點大型問題集，問題集中有6大類共56個問題。本研究以多目標求解問題的過程中，探討不可行解存在於族群中對於文化基因演算法中族群演化造成的影響。