The Capacitated Team Orienteering Problem: An online optimization framework with predictions of unknown accuracy

Davood Shiri, Vahid Akbari and Ali Hassanzadeh

Transportation Research Part B: Methodological, 2024, vol. 185, issue C

Abstract: The Capacitated Team Orienteering Problem (CTOP) is a challenging combinatorial optimization problem, wherein a fleet of vehicles traverses multiple locations, each with distinct prizes, demand weights, and service times. The primary objective is to determine optimal routes for the vehicles that collectively accumulate the highest total prize within capacity and time constraints. The CTOP finds applications across various domains such as disaster response, maintenance, marketing, tourism, and surveillance, where coordinated teams are required to efficiently explore and gather prizes from different sites. The complexity of this problem is further compounded by uncertainties in predicting specific attributes of each location, making it hard to plan routes accurately in advance. In numerous scenarios in practice, subjective predictions for these parameters may exist, but their precise values remain unknown until a location is visited by one of the vehicles. Given the unpredictable nature of these parameters, there is a pressing need for innovative online optimization strategies that can adapt to new information, ensuring the strategic allocation of resources and route planning within set constraints. To address this challenging online optimization problem, we offer a detailed analysis through the lens of theoretical and empirical competitive ratios. We derive an exact tight upper bound on the competitive ratio of online algorithms, and we introduce three novel online algorithms, with two of them achieving optimal competitive ratios. The third algorithm is a polynomial time approximation-based online algorithm with a competitive ratio of 13.53 times the tight upper bound. To evaluate our algorithms, we measure their empirical competitive ratios on randomly generated instances as well as instances from the literature. Our empirical analysis demonstrates the effectiveness of our solutions across a diverse range of simulation scenarios.

Keywords: Online vehicle routing; Competitive ratio; Capacitated Team Orienteering Problem; Uncertainty; Online heuristics (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191261524001085
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:transb:v:185:y:2024:i:c:s0191261524001085

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.trb.2024.102984

Access Statistics for this article

Transportation Research Part B: Methodological is currently edited by Fred Mannering

More articles in Transportation Research Part B: Methodological from Elsevier
Bibliographic data for series maintained by Catherine Liu ().