Self-adaptive heuristic algorithms for the dynamic and stochastic orienteering problem in autonomous transportation system

This paper studies a task execution and routing problem in the autonomous transportation system that maps to the famous orienteering problem (OP) in operations research. By extending the classical OP to stochastic and dynamic OP with stochastic travel time and service time, an investigation is conducted that aims to optimize the selection of travel routes with the objective of maximizing the total collected rewards in accordance with the time availability of self-adaptive agent (e.g., unmanned aircraft vehicles and unmanned ground vehicle). Three self-adaptive multi-stage heuristics-based adjustment strategies (i.e., Insertion-and-Removal Heuristics, Hybrid Simulated Annealing-Tabu Search-based Re-Optimization, and Threshold-based Re-Optimization) are proposed to equip the autonomous agent with the ability of real-time routing adjustment in the context of the dynamic and stochastic orienteering problem. Finally, benchmark simulation experiments are used to test the effectiveness of all the three proposed adjustment strategies. The experimental results show that, compared with a priori solutions acquired by a static meta-heuristic algorithm (Hybrid Simulated Annealing-Tabu Search algorithm), the three strategies can improve the solution qualities at different levels.