Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
474154 | Computers & Operations Research | 2008 | 9 Pages |
The swath segment selection problem (SSSP ) is an NPNP-hard combinatorial optimization problem arising in the context of planning and scheduling satellite operations. It was defined by Muraoka et al. [ASTER observation scheduling algorithm. In: Proceedings of SpaceOps 1998, Tokyo, Japan, 1998] and Knight and Smith [Optimal nadir observation scheduling. In: Proceedings of the fourth international workshop on planning and scheduling for space (IWPSS 2004), Darmstadt, Germany, 2004], who respectively proposed a greedy algorithm, named ASTER, and a branch-and-bound algorithm based on a network flow relaxation. Here we tackle the problem with more advanced mathematical programming tools: using a Lagrangean relaxation, coupled with a Lagrangean heuristic and subgradient optimization, we solve in one hour instances with up to 500 000 swath segments within 0.4%0.4% of the optimum. The algorithm also proves experimentally superior to commercial MIP solvers in computing heuristic solutions.