The Dynamic Team Orienteering Problem

doi:10.1016/j.ejor.2025.01.009

Return

The Dynamic Team Orienteering Problem

2025-01-01

PRE

Emre Kirac *

Ashlea Bennett Milburn

Ridvan Gedik

DOI：10.1016/j.ejor.2025.01.009

Original

Original request for help

Save

Abstract

En 中文

This study introduces anew dynamic routing problem, namely the Dynamic Team Orienteering Problem (DTOP), which is a dynamic variant of the Team Orienteering Problem (TOP). In the DTOP, some customer locations are known a priori, while others are dynamic, with each location associated with a profit value. The goal is to maximize the sum of collected profits by visiting a set of customer locations within a time limit. This problem arises in several practical applications such as disaster relief, technician, tourist, and school bus routing problems. We adopt a Multiple Plan Approach (MPA) to solve the proposed problem, utilizing both a consensus function method and a demand-served method to select the distinguished plan-the most promising solution from a pool of alternative routing plans. To assess the effectiveness of these methods, we employ a sophisticated greedy algorithm tailored to address the unique challenges posed by the DTOP. In addition, we employ a reference offline algorithm designed for solving the static variant of the problem. To facilitate our evaluation, we introduce a comprehensive set of 1161 new benchmark instances for the DTOP, adapted from well-established TOP benchmark instances. Our comparative analysis centers on the average percentage deviation of algorithmic solutions from the reference offline solutions.

Keywords:

Dynamic routing

Team orienteering problem

Vehicle routing

Multiple plan approach