Applying the Simulated Annealing Algorithm to the Set Orienteering Problem with Mandatory Visits

Abstract

This study addresses the set orienteering problem with mandatory visits (SOPMV), a variant of the team orienteering problem (SOP). In SOPMV, certain critical sets must be visited. The study began by formulating the mathematical model for SOPMV. To tackle the challenge of obtaining a feasible route within time constraints using the original MILP approach, a two-stage mixed-integer linear programming (MILP) model is proposed. Subsequently, a simulated annealing (SA) algorithm and a dynamic programming method were employed to identify the optimal route. The proposed SA algorithm was used to solve the SOP and was compared to other algorithms, demonstrating its effectiveness. The SA was then applied to solve the SOPMV problem. The results indicate that the solutions obtained using SA are superior and more efficient compared to those derived from the original MILP and the two-stage MILP. Additionally, the results reveal that the solution quality deteriorates as the ratio of the set of mandatory visits increases or the maximum allowable travel time decreases. This study represents the first attempt to integrate mandatory visits into SOP, thereby establishing a new research direction in this area. The potential impact of this research is significant, as it introduces new possibilities for addressing complex combinatorial optimization problems.

Keywords

• set orienteering problem
• mandatory visits
• dynamic programming
• simulated annealing algorithm