A branch and price algorithm for EOS constellation imaging and downloading integrated scheduling problem. (April 2019)

• Record Type: Journal Article
• Authors: Hu, Xiaoxuan; Zhu, Waiming; An, Bo; Jin, Peng; Xia, Wei
• Is Part Of: Computers & operations research. Volume 104(2019)
• Page Start: 74
• Page End: 89
• Publication Date: 2019-04
• Subjects: EOS constellation -- Integrated scheduling -- Branch and price -- Primal dual column generation; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2018.12.007
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: Provided a novel mixed integer linear program formulation for the satellite scheduling problem. Decomposed the problem with Dantzig–Wolfe method, resulting in a tighter reformulation. Developed a branch and price algorithm and proposed an efficient dynamic programing algorithm for the subproblems. Developed a heuristic by utilizing the generated columns to find integer solutions. Tested the algorithm on highly-simulated instances and three types of random instances. Abstract: Earth observation satellite (EOS) constellation imaging and downloading integrated scheduling (EOSCIDIS) is a challenging optimization problem with several engineering applications. Given a large number of imaging requests and a constellation consisting of a group of EOSs, a workable schedule must be developed for each EOS to allow for imaging and downloading in the most efficient manner given a certain scheduling horizon. No studies have proposed exact algorithms for the EOSCIDIS problem, although it has considerable potential for applications. In this paper, we developed a branch and price (B&P) algorithm for the EOSCIDIS problem. First, we decomposed the problem by extracting the sub-structure of the problem, and the decomposition resulted in a master problem and multiple pricing problems. Solving the linear relaxed master problem with column generation (CG) method provides a very tight upper bounds for the primal problem. We then embedded the CG process into a branch and bound (B&B) framework to find optimal integer solutions. In order to accelerate the convergence of the algorithm, we developed a heuristic utilizing the generated columns to construct feasible integer solutions to prune B&P tree branches earlier. We tested the B&P algorithm on highly-simulated instances that are constructed according to the Chinese Gaofen-1 satellite and 3 types of random instances which correspond to short, medium and long term scheduling respectively. Both results show that our method could find high-quality solutions with optimality gap less than 10% for most instances using reasonable computational costs .