Publication Type

Journal Article

Version

acceptedVersion

Publication Date

3-2024

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.

Keywords

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

Discipline

Databases and Information Systems

Research Areas

Data Science and Engineering

Publication

Expert Systems with Applications

Volume

238

ISSN

0957-4174

Identifier

10.1016/j.eswa.2023.121996

Publisher

Elsevier

Additional URL

https://doi.org/10.1016/j.eswa.2023.121996

Download

Share

COinS