Branch-and-cut-and-price for agile earth observation satellite scheduling

Guansheng Peng, Jianjiang Wang, Guopeng Song, Aldy Gunawan, Lining Xing and Pieter Vansteenwegen

European Journal of Operational Research, 2025, vol. 326, issue 3, 427-438

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: Agile satellite scheduling; Orienteering problem; Branch-and-cut-and-price; Subset-row inequalities; Ng-path relaxation (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221725002644
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:326:y:2025:i:3:p:427-438

DOI: 10.1016/j.ejor.2025.04.014

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 ().