الگوریتم شاخه و قیمت برای تصویربرداری صورت فلکی EOS
ترجمه نشده

الگوریتم شاخه و قیمت برای تصویربرداری صورت فلکی EOS

عنوان فارسی مقاله: یک الگوریتم شاخه و قیمت برای تصویربرداری صورت فلکی EOS و دانلود مسئله زمانبندی یکپارچه
عنوان انگلیسی مقاله: A branch and price algorithm for EOS constellation imaging and downloading integrated scheduling problem
مجله/کنفرانس: کامپیوترها و تحقیق در عملیات - Computers & Operations Research
رشته های تحصیلی مرتبط: مهندسی کامپیوتر
گرایش های تحصیلی مرتبط: مهندسی الگوریتم ها و محاسبات، مهندسی نرم افزار، برنامه نویسی کامپیوتر
کلمات کلیدی فارسی: صورت فلکی EOS، زمانبندی یکپارچه، شاخه و قیمت، تولید اولیه ستون دو گانه
کلمات کلیدی انگلیسی: EOS constellation، Integrated scheduling، Branch and price، Primal dual column generation
نوع نگارش مقاله: مقاله پژوهشی (Research Article)
شناسه دیجیتال (DOI): https://doi.org/10.1016/j.cor.2018.12.007
دانشگاه: School of Management, Hefei University of Technology, Hefei, China
صفحات مقاله انگلیسی: 16
ناشر: الزویر - Elsevier
نوع ارائه مقاله: ژورنال
نوع مقاله: ISI
سال انتشار مقاله: 2019
ایمپکت فاکتور: 3/976 در سال 2018
شاخص H_index: 133 در سال 2019
شاخص SJR: 1/859 در سال 2018
شناسه ISSN: 0305-0548
شاخص Quartile (چارک): Q1 در سال 2018
فرمت مقاله انگلیسی: PDF
وضعیت ترجمه: ترجمه نشده است
قیمت مقاله انگلیسی: رایگان
آیا این مقاله بیس است: بله
کد محصول: E11315
فهرست مطالب (انگلیسی)

Abstract

1- Introduction

2- Literature review

3- Problem description

4- Problem formulation

5- A branch and price algorithm

6- Computational experiments

7- Conclusion and future work

References

بخشی از مقاله (انگلیسی)

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 .

Introduction

Earth observation satellites (EOSs) are launched for the primary purpose of collecting surface images from orbit. EOS imagery has recently been used in agriculture, map making, land surveys, and disaster warning and recovery (Madry, 2013). An EOS constellation is an imaging system with a certain geometrical shape, composed of a group of EOSs providing coordinated ground coverage. These systems are beneficial as they reduce revisit time, the duration between repeated observations of the same site. Multiple EOS constellations have been commissioned in recent years, including the French Pléiades (Lemaître et al., 2002) and Italy‘s COSMO-SkyMed (Bianchessi and Righini, 2008). Presently, several countries have committed to enhancing EOS constellation infrastructure, particularly China, which will continue to increase investment in this field. An EOS will first image a series of ground-based sites and then store the acquired image data to on-board memory (i.e., high performance hard disks). These data are then downloaded to ground stations during radio communications, freeing storage resources for subsequent observations. This process requires manual intervention, in which commands are computed according to workable imaging and downloading schedules. EOS constellation imaging and downloading integrated scheduling (EOSCIDIS) is an optimization problem that has become of interest as the number of constellations in operation has increased. Given a large number of imaging requests and limited imaging and downloading resources (EOS constellation), an optimal imaging and downloading schedule would allow for imaging and downloading in the most efficient manner given a certain scheduling horizon. The EOSCIDIS problem is a generalization of the EOS scheduling (EOSS) problem.