車輛途程問題在過去30年來已經被廣泛討論，而且變化形式非常多，本研究將焦點放在時窗限制下多車種車輛途程問題。這是因為由不同車種組成的車隊往往能獲得較單一車種為佳的解，而且現在是一顧客導向的時代，顧客會要求配送車輛於某特定時間來進行服務，因此加入顧客服務時窗可以提高顧客的滿意程度。 車輛途程問題是一NP-hard問題，不易求得精確解，大部分都是利用啟發式解法來求解，但其缺點是易陷入區域最佳解。為了避免此一情況發生，本研究將利用具有隨機與多點搜尋特性的遺傳演算法來求解車輛途程問題。然而傳統的遺傳演算法並沒有處理限制條件的能力，以致於在問題的解空間做全面、隨機性的搜尋，結果很容易產生不合理的子代，只能利用人為的機制如懲罰函數法來做事後的補救工作，這種方式顯得沒有效率，針對此點本研究在進行遺傳演算時將同步考慮問題的限制條件，合理規劃搜尋的方向避免做無謂的搜尋，以提升求解的效率，並在最後以一測試題目利用統計假設檢定方法來比較限制條件下遺傳演算運作模式(採用互換交配運算子)與傳統的遺傳演算運作模式(採用單點交配運算子與雙點交配運算子) 之優劣。 The vehicle problems have been discussed for thirty years. In this work we address the problem of the fleet size and mix vehicle routing problem with time windows. Typically, researchers assume that all vehicles are identical. In this work, we relax the homogeneous fleet assumption and add the time window constraints to satisfy the time requirement of each customer. The vehicle problems are NP-hard problems. Most approaches for solving the vehicle problems are heuristics which are easy to find the local optimal solution. In this research, the genetic algorithm is used to avoid finding the local optimal solution. However, the traditional genetic algorithm is unable to handle the constraints of problems. According to the characteristic of the genetic algorithm, we propose a new genetic algorithm to use the constraints to guide the searching of the solution to the problem and increase the efficiency of the problem solving. At last, we use a test problem to compare the new genetic algorithm with traditional genetic algorithm in terms of the statistical hypothesis test.
