運用改良基因演算法求解時間窗越野尋蹤問題及應用於自助旅遊路線規劃

Application of Improved Genetic Algorithm to Solve the Orienteering Problem with Time Windows and Individual Travel Route Planning

越野尋蹤問題(orienteering problem, OP)屬於旅行銷售員問題(traveling salesman problem, TSP)之延伸問題，在OP所延伸出的具時間窗限制之越野尋蹤問題(orienteering problem with time windows, OPTW)中，時間窗之限制也提升求解之複雜度。近年來發展基因演算法(genetic algorithm, GA)結合路徑重連結(path relinking)之方式因應時間窗特性之限制，本研究為探討不同路徑重連結之方式之求解效率，以基因演算法為基礎，設計不同路徑重連結之演算流程求解軟時窗限制之OPTW並進行國際例題之測試。結果顯示所提出之改良基因演算法求解點位數不超過144之問題規模，平均求解誤差為4%以內。未來OPTW可應用於自助旅遊路線之規劃，並可於旅遊網站進行自助旅遊路線規劃之參考，提升自助旅遊服務之客製化程度。

The Orienteering Problem (OP) is an extension of the Traveling Salesman Problem (TSP). At the same time, many algorithms for solving optimization problems have been developed in recent years. The OP problem can be further extended to incorporate time windows, resulting in the Orienteering Problem with Time Windows (OPTW). The time window limitation also increases the complexity of the solution. In recent years, genetic algorithm (GA) combined with Path Relinking has been developed in response to the limitation of time window characteristics. This study is to explore the efficiency of different path relinking methods, based on genetic algorithm, design the calculation process of reconnecting different paths to solve the OPTW problem with soft time window limitation, and test the algorithm with the international example. The results show that the improved genetic algorithm proposed by this research solves the problem scale with no more than 144 points, and the average solution error is within 4%. In the future, OPTW can be applied to the planning of individual travel routes, and can be used as a reference for individual travel route planning on travel websites to enhance the degree of customization of individual travel services.