請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/39098
標題: | 衛星取像排程之研究 Satellite Imaging Scheduling: Algorithm Design and Application |
作者: | Wei-Cheng Lin 林偉誠 |
指導教授: | 張時中(Shi-Chung Chang) |
關鍵字: | 拉氏釋限法,禁制搜尋法,混合演算法,衛星排程,地面觀測衛星,最佳化,整數規劃, Satellite Scheduling,Earth Observation Sateiilte,Integer Programming,Lagrangian Relaxation,Optimization,Tabu Search,Hybrid Algorithm, |
出版年 : | 2005 |
學位: | 博士 |
摘要: | 本論文研究之目的為設計並發展一新式佳化排程演算法來求解新一代低軌道地面觀測衛星取像排程問題,尤其是福爾摩沙衛星二號(FORMOSAT-2)的每日取像排程問題。福爾摩沙衛星二號每天飛經台灣上空兩次,每次約10分鐘之經過時間。其針對台灣陸地以及鄰近海域進行近即時之大氣、海洋及陸地遙測取像作業,以獲得近即時的衛星遙測影像資料,來滿足不同的取像需求。取像作業是針對某一特定取像區域進行取像,而取像需求則為一個或一個以上的取像作業組合。為使衛星能在不同取像區域間進行連續取像或分散取像,取像前須進行衛星位置的移動與衛星姿態(鏡頭拍攝角度)的調整。當衛星位於取像區域上方進行垂直取像時可獲得最佳之取像品質,因此為確保取像品質,每一取像區域須在一限定時間範圍內取像完畢。福爾摩沙衛星二號每日取像排程問題,就學理上而言是屬於具有工作組合(job-assembly)、順序相依機器設置效應(sequence-dependent setup effect)、時效區間(constrain of operating time window)諸項特性的單一機器排程問題。此排程問題首先被描述成一個整體(monolithic)的整數規劃問題(Integer Programming Problem),其計算複雜度為NP-hard。以部分取像作業完工來近似目標函數中取像需求須完全完工的方式,可將排程問題轉化為一可分解(separable)的整數規劃問題。
有識於問題數學模型的可分解性,並且擷取文獻中SPOT-5衛星取像排程的研究成果,本研究以拉氏釋限法(Lagrangian Relaxation)與禁制搜尋法(Tabu Search)分別來發展佳化演算法。拉氏釋限法解除機器容量限制式,儲存空間限制式以及能源消耗限制式等等具備設置效應的耦合限制式之後,將整個排程問題分解成獨立取像作業子問題組合。取像作業子問題考慮最佳開始取像時間以獲得最佳取像品質,因此每一個子問題可利用線性搜尋法來求解。而拉式乘數是採用Held等人(1974)所發展的次梯度(Subgradient)方法來進行最佳化。最後,利用釋限問題的解,發展出一貪心啟發式法則(Greedy-based Heuristic),以求得一完全符合所有限制式的排程。禁制搜尋法包含有如下五項特色:貪心式搜尋程序、釋限擴大可行解邊界、動態禁制保有機制(dynamic Tabu tenure mechanism)、增強化搜尋(intensification)、以及多樣化搜尋(diversification),使得求解極具效能。其核心搜尋程序為在以部分限制式所構成的搜尋空間上,進行貪心式取像作業的安插與移除,使得目標函數值最小化。 利用隨機的方式產生40類400個真實的福爾摩沙衛星二號每日取像排程測試問題,以測試在不同問題維度(problem dimension)與問題複雜度對兩解法的影響。比較結果顯示拉氏釋限法可求得近似最佳對偶解(near dual optimal)並且在計算速度上取得優勢,而禁制搜尋法則因採納增強化與多樣化搜尋機制,使得其有較佳的排程產出。同時,兩種混合(hybrid)拉氏釋限法與禁制搜尋法兩佳化演算法優點,以增進求解效能的設計方法CASCADE與COMBINATION也在本論文中提出並加以實現。CASCADE採用禁制搜尋法來直接改善拉氏釋限法的排程產出,而COMBINATION則將禁制搜尋法發展成為拉氏釋限法中調可行解的啟發式法則(Heuristic)。數值實驗結果顯示在導入禁制搜尋法之後,兩混合方法確實能有效地改善拉氏釋限法的排程產出。此外,在相同演算次數與程式碼的條件之下,兩混合方法與禁制搜尋法在平均佳化值(optimality)上並無顯著之差異。由上述結果可知,調可行解的啟發式法則對於拉氏釋限法的求解效能有著極大的影響,而禁制搜尋法的多樣化搜尋機制能提供多樣的搜尋點來進行大範圍的搜尋,以避免陷入區域最小值(local minimum)的情形,因此禁制搜尋法的求解效能可不受初始搜尋點的影響。本研究顯示禁制搜尋法適用於求解福爾摩沙衛星二號的每日取像排程問題。 This thesis presents the research and development of a novel imaging scheduling system for the newest generation of low-orbit, earth observation satellite, FORMOSAT-2. FORMOSAT-2 passes through Taiwan twice daily in approximately 10 minutes each time. The mission of FORMOSAT-2 is to perform near real-time, remote imaging of ocean and landmass in the vicinity of Taiwan. The daily imaging scheduling problem of FORMOSAT-2 includes considerations of various imaging requests (jobs) with different reward opportunities, changeover efforts between two consecutive imaging operations (tasks), cloud coverage effects, and the availability of satellite resource. It belongs to a class of single-machine scheduling problems with salient features of job-assembly characteristic, sequence-dependent setup effect, and the constraint of operating time window. The scheduling problem is first formulated as a monolithic integer programming problem, which is NP-hard in computational complexity. An approximation of the weighted penalty of incomplete jobs by penalties of individual tasks facilitates a separable integer programming problem. For problems of such high complexity, dynamic programming and exhaustive search techniques are either too time-consuming or impractical for optimal solutions. Rule-based or heuristic approaches can reduce the computation time drastically but the resultant optimality may be unsatisfactory. In view of the separable problem structure and researching findings about imaging scheduling of SPOT-5 in the literature, two solution approaches, Lagrangian relaxation and Tabu search, are adopted for novel solution algorithm design and investigation of their effectiveness. The Lagrangian relaxation algorithm design exploits the separable problem structure and relaxes coupling constraints with setup effect to decompose the problem into independent subproblem, each being a simple search for one task’s beginning imaging time within its time window. To solve the dual problem, Lagrangian multipliers are iteratively updated by subgradient (SG) method. For simplicity, a greedy-based feasibility adjustment heuristic is implemented to modify a dual solution into a feasible primal solution. It consists of constraint-violation resolving and task rescheduling. This heuristic is quick in computation and east to implement which exploits the separable problem structure and takes advantage of Lagrangian multipliers obtained from solving the dual. The Tabu search algorithm design integrates some important ideas including a greedy-based searching process, boundary extension by constraint relaxation, a dynamic Tabu tenure mechanism, intensification, and diversification. Core to three Tabu steps, Exploration, Intensification, and Diversification, are simply the greedy-based task’s insertion-and-removal process over partially constrained search space with the evaluation of primal objective function. Numerical results of 40 classes of 400 realistic instances indicate that Lagrangian relaxation algorithm achieves near-optimal dual solutions and has an advantage in computational efficiency. With the help of intensification and diversification, Tabu search algorithm is superior in optimality. Furthermore, two hybrid schemes, CASCADE and COMBINATION, are designed for performance improvement. CASCADE adopts Tabu search techniques to improve the solution quality of Lagrangian relaxation algorithm directly. COMBINATION then deals with the development of Tabu search-based feasibility adjustment heuristic in Lagrangian relaxation algorithm. Numerical results of 7 classes of 70 test cases for 10-minute scheduling time horizon indicate that the two hybrid algorithms improve the solution quality of Lagrangian relaxation algorithm significantly. Under the same TS iteration process (maximum iteration number and program), there are no significant differences on optimality among two hybrid algorithm and pure TS algorithm. It is concluded that the design of feasibility adjustment heuristic has significant impact on the performance of Lagrangian relaxation algorithm. Tabu search algorithm is independent on the initial schedule. Since using the solutions of Lagrangian relaxation algorithm as initial schedules to Tabu search algorithm did not bring better solutions. This is because the Diversification Tabu step has done exclusive exploration over diverse schedules, which helps Tabu search algorithm to escape from trapping in a local optimum. In conclusion, Tabu search algorithm design is good at solving the daily imaging scheduling problem of FORMOSAT-2. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/39098 |
全文授權: | 有償授權 |
顯示於系所單位: | 電機工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-94-1.pdf 目前未授權公開取用 | 2.48 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。