Simulated annealing with reinforcement learning for the set team orienteering problem with time windows

Vincent F. Yu, Nabila Yuraisyah Salsabila, Shih Wei Lin*, Aldy Gunawan

*Corresponding author for this work

Research output: Contribution to journalJournal Article peer-review

Abstract

This research investigates the Set Team Orienteering Problem with Time Windows (STOPTW), a new variant of the well-known Team Orienteering Problem with Time Windows and Set Orienteering Problem. In the STOPTW, customers are grouped into clusters. Each cluster is associated with a profit attainable when a customer in the cluster is visited within the customer's time window. A Mixed Integer Linear Programming model is formulated for STOPTW to maximizing total profit while adhering to time window constraints. Since STOPTW is an NP-hard problem, a Simulated Annealing with Reinforcement Learning (SARL) algorithm is developed. The proposed SARL incorporates the core concepts of reinforcement learning, utilizing the ε-greedy algorithm to learn the fitness values resulting from neighborhood moves. Numerical experiments are conducted to assess the performance of SARL, comparing the results with those obtained by CPLEX and Simulated Annealing (SA). For small instances, both SARL and SA algorithms outperform CPLEX by obtaining eight optimal solutions and 12 better solutions. For large instances, both algorithms obtain better solutions to 28 out of 29 instances within shorter computational times compared to CPLEX. Overall, SARL outperforms SA by resulting in lower gap percentages within the same computational times. Specifically, SARL outperforms SA in solving 13 large STOPTW benchmark instances. Finally, a sensitivity analysis is conducted to derive managerial insights.

Original languageEnglish
Article number121996
JournalExpert Systems with Applications
Volume238
DOIs
StatePublished - 15 03 2024
Externally publishedYes

Bibliographical note

Publisher Copyright:
© 2023 Elsevier Ltd

Keywords

  • Set orienteering problem
  • Simulated annealing
  • Team orienteering problem with time windows

Fingerprint

Dive into the research topics of 'Simulated annealing with reinforcement learning for the set team orienteering problem with time windows'. Together they form a unique fingerprint.

Cite this