二階段基因演算法於具時間窗限制車輛路線問題之應用

Abstract

本研究目的為對於具時間窗限制車輛路線問題設計有效的演算法。本研究採用二階段基因演算法求解具時間窗限制車輛路線問題。第一階段以Alvarenga (2007)所提出的基因演算法為基礎並且在建構初始族群、交配以及突變上做些修改，以及啟發式解法來減少旅行成本。第二階段針對第一階段得到的路徑解做改善，並且解決違反時間問題。我們使用Solomon(1983)提出的56題國際標竿例題來進行測試與敏感度分析。測試結果顯示，本研究所提出的演算法是適當的並且符合預期。

The purpose of this research is designing an efficient and effective algorithm for vehicle routing problem with time window. This research proposes a two-phase genetic algorithm approach for solving this problem. The first phase is based on the genetic algorithm introduced by Alvarenga (2007) with some modifications of generation of initial population, crossover and mutation techniques, and an heuristics to reduce travel cost. The second phase aims at improving routes obtained in the first phase and addresses the violated time windows. We use Solomon’s 56 benchmark VRPTW instances for evaluation and sensitivity analysis. Our testing results show that the proposed algorithm is adequate and satisfactory.