Team Orienteering Problem with Time Windows and Variable Profit

The Orienteering Problem (OP) is a combinatorial optimization and integer programming problem whose goal is to obtain the optimal route for a vehicle to traverse to deliver to a given set of customers. The objective is to select a subset of nodes to visit to maximize the total collected score given a limited time budget. The OP has numerous applications in various fields such as logistics and tourism. Several variants have been studied, including the Team Orienteering Problem (TOP), the Orienteering Problem with Time Windows (OPTW), and the TOP with Variable Profits (TOPVP). This paper introduces the Team OP with Time Windows and Variable Profits (TOPTWVP). In this case, each node has a predefined time window in which the service must start (in case this node is visited), and the vehicle may spend an amount of time given by a predefined interval so that the profit collected at this node depends on the time spent. We first propose a mathematical model for the TOPTWVP and use OR-Tools to solve small modified benchmark instances. We then propose an algorithm based on Iterated Local Search to solve more difficult modified benchmark instances. The results show that our approach can solve difficult instances with good quality.

---

1. Short article

---

2. Track 6: 15th International Workshop on Computational Optimization

---

3. Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023).