An Improved Genetic Algorithm for Bi-objective Dynamic Orienteering Problem with Time Windows

This paper proposes an Improved Genetic Algorithm combined with Path-Reconstruction operators (IGAPR) to solve the Dynamic Orienteering Problem with Time Windows (DOPTW). In this problem, task nodes appear dynamically, challenging the solution strategies of traditional orienteering problems. We divide the entire planning horizon into multiple static time periods and apply a heuristic genetic algorithm within each period to generate high-quality solutions. Experimental results on modified Solomon and Cordeau benchmark instances demonstrate that our approach outperforms traditional greedy algorithms and conventional genetic algorithms in terms of path rewards and fitness value. Additionally, the paths generated by our method adapt to dynamic changes and exhibit good scalability as the number of nodes increases.