The Capacitated Team Orienteering Problem: An online optimization framework with predictions of unknown accuracy
研究了容量约束团队定向问题，提出三种在线算法，其中两种达到最优竞争比，第三种为多项式时间近似算法，并通过随机和文献实例验证了有效性。
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.