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

Shih-Wei Lin (), Sirui Guo and Wen-Jie Wu
Additional contact information
Shih-Wei Lin: Department of Information Management, Chang Gung University, Taoyuan 33302, Taiwan
Sirui Guo: Department of Information Management, Chang Gung University, Taoyuan 33302, Taiwan
Wen-Jie Wu: Department of Information Management, Chang Gung University, Taoyuan 33302, Taiwan

Mathematics, 2024, vol. 12, issue 19, 1-24

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 (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/12/19/3089/pdf (application/pdf)
https://www.mdpi.com/2227-7390/12/19/3089/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:12:y:2024:i:19:p:3089-:d:1491158

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().