The Dynamic Team Orienteering Problem

Emre Kirac, Ashlea Bennett Milburn and Ridvan Gedik

European Journal of Operational Research, 2025, vol. 324, issue 1, 22-39

Abstract: This study introduces a new 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 (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221725000347
Full text for ScienceDirect subscribers only

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:eee:ejores:v:324:y:2025:i:1:p:22-39

DOI: 10.1016/j.ejor.2025.01.009

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().