Publication Type

Journal Article

Version

publishedVersion

Publication Date

11-2025

Abstract

The Agile Earth Observation Satellite scheduling selects and sequences satellite observations of possible targets on the Earth’s surface, each with a specific profit and multiple time windows. The objective is to maximize the collected profit of all observations completed under some operational constraints. The problem can be modeled as a variant of the Team Orienteering Problem with Time Windows (TOPTW). The key differences with the regular TOPTW are twofold: first, a time-dependent transition time is required for each pair of consecutive observations to adjust the camera’s look angles. Second, the time windows of each target vary during different observation cycles, called “orbits”. Some targets are invisible during certain orbits. We call this variant the Time-dependent Team Orienteering Problem with Variable Time Windows. In this paper, we present an efficient branch-and-cut-and-price (BCP) algorithm that exploits the problem’s characteristics to solve it to optimality. Some algorithmic enhancements have been implemented, such as a Lagrangian bound, an ng-path relaxation, a primal heuristic, and subset-row inequalities. Extensive experiments on different configurations of benchmark instances demonstrate the superior performance of the proposed BCP algorithm and its algorithmic enhancements. Moreover, the primal heuristic yields a high-quality lower bound and outperforms state-of-the-art heuristics. Finally, we adopt our framework to solve the well-known TOPTW, and our algorithm is much faster than state-of-the-art exact algorithms.

Keywords

Orienteering problem, Branch-and-cut-and-price, Subset-row inequalities, Ng-path relaxation

Discipline

Artificial Intelligence and Robotics | Theory and Algorithms

Research Areas

Intelligent Systems and Optimization

Areas of Excellence

Sustainability

Publication

European Journal of Operational Research

Volume

326

Issue

3

First Page

427

Last Page

438

ISSN

0377-2217

Identifier

10.1016/j.ejor.2025.04.014

Publisher

Elsevier

Additional URL

https://doi.org/10.1016/j.ejor.2025.04.014

Download

Share

COinS