Indicator-Based Artificial Bee Colony Algorithm for Solving a Bi-objective Moving-Target Traveling Salesman Problem with Uncertainty
TL;DR
This paper investigates a novel bi-objective moving-target traveling salesman problem with uncertainty, where the target trajectories are uncertain, and proposes an Indicator-based Artificial Bee Colony (I-ABC) algorithm to efficiently approximate the Pareto front.
Abstract
This paper investigates a novel bi-objective moving-target traveling salesman problem with uncertainty, where the target trajectories are uncertain. The objective is to maximize the number of visited targets within a bounded region while minimizing the travel cost. This problem is formulated as a bi-objective two-stage stochastic program with recourse. The first-stage decision determines a planned visiting sequence before the realization of target trajectories, and the second-stage recourse decision allows the agent to return to the depot in advance when the remaining targets are expected to leave the bounded region. We adopt the sample average approximation approach to approximate the expected objective values by empirical average over a finite set of sampled scenarios. To efficiently approximate the Pareto front, we propose an Indicator-based Artificial Bee Colony (I-ABC) algorithm. We introduce a ratio-based binary indicator into both the environmental selection and evolutionary mechanisms, incorporate a parallel-distance measure to preserve population diversity, and adopt an elitist strategy in the scout bee phase to enhance convergence. Extensive experiments in simulated environments demonstrate that the proposed I-ABC algorithm outperforms the state-of-the-art algorithms.