臺灣博碩士論文加值系統

本論文探討具傾斜觀測功能之單一衛星遙測取像排程問題。排程的目標為求取單一軌道上，衛星行經任務取像分布區域上空時，在不中斷攝影之一次取像過程中完成的最大取像任務數目。此為NP-hard的組合最佳化問題，不易在合理的時間內應用傳統的數學規劃法求得最佳解。我們將建構一個通用啟發法(meta-heuristics)—串聯演算法(Serial Algorithm)來求近似解，先對取像任務用最早開始時間優先規則(Earliest Start Time First，EST)排序，再串聯兩種鄰域搜尋法—倒轉子路徑法(sub-tour reversal)和節線交換法(K-OPT)，產生不同結構之鄰域解，讓搜尋往其他區域前進，並援用禁忌搜尋法(Tabu Search，TS)之記憶功能，反覆進行演算排程。
最後，應用計算機模擬實驗，以串聯演算法演算所得之目標函數值，較單一使用倒轉子路徑法或節線交換法，改善的樣本數達到5成以上，又在總任務數目為50個、分布範圍λ=1.6時，平均改善了10.32%及8.91%，證實了串聯演算法的應用價值。

This thesis presents the research and development of the remote imaging scheduling problem for single satellite with inclinable observation. The objective function of the scheduling problem of the satellite passing through the imaging area on single orbit to take images between one consecutive imaging operation is to maximize the number of jobs. For the optimization problem which is NP-hard in computational complexity, classical dynamic programming is too time-consuming for optimal solutions. This thesis will develop a meta-heuristics method—Serial Algorithm. In the first place, schedule the jobs with EST, then connect sub-tour reversal and K-OPT serially to produce neighborhood solutions of different structure for searching toward other areas, and use the memory function of Tabu Search to compute repeatedly.
In the end ,simulating the computation experience with computer, the numbers of improved samples using Serial Algorithm achieves 50%, and the average performance is better 10.32% and 8.91% than the one of sub-tour reversal and K-OPT when the number of total jobs is 50 and the λ(imaging area)is 1.6 .To sum up, Serial Algorithm is good at solving the remote imaging scheduling problem of the satellite.

摘要…………………………………………………………………i
Abstract…………………………………………………………ii
目錄…………………………………………………………………iii
表目錄………………………………………………………………v
圖目錄………………………………………………………………vi

第一章 緒論……………………………………………………1
1.1　研究動機與目的……………………………………………1
1.2　研究方向與方法……………………………………………2
1.3　論文架構……………………………………………………4

第二章　 預備知識與文獻回顧…………………………………5
2.1　 遙測衛星之探討…………………………………………5
2.1.1 衛星的種類及用途………………………………………5
2.1.2 遙測衛星…………………………………………………7
2.1.3 衛星遙測取像之限制因素………………………………9
2.2　 排程理論…………………………………………………11
2.2.1　排程問題…………………………………………………11
2.2.2　排程演算複雜度…………………………………………14
2.3　 常見的通用啟發法………………………………………17
2.3.1　禁忌搜尋法………………………………………………17
2.3.2　遺傳演算法………………………………………………19
2.3.3　模擬退火法………………………………………………20
2.3.4　倒轉子路徑法……………………………………………21
2.3.5　節線交換法………………………………………………23
2.4　遙測取像排程分析…………………………………………27
2.4.1 衛星基本資料分析………………………………………27
2.4.2 任務座標與衛星傾測角度分析…………………………28

第三章　 主要研究結果…………………………………………31
3.1　問題描述……………………………………………………31
3.2　遙測取像鏡頭旋轉公式之推算……………………………33
3.3　串聯演算法之建構…………………………………………38
3.3.1　串聯演算法結構…………………………………………39
3.3.2　演算法流程分析…………………………………………45
3.4　計算機模擬實驗……………………………………………49
3.4.1　以不同的總任務數目及分布範圍演算之結果…………50
3.4.2　實驗結果統計歸納………………………………………57

第四章　結論與後續的研究………………………………………63
參考文獻……………………………………………………………66

[1]唐恒永、趙傳立，排序引論，第一版，科學出版社，北京，第1-16頁，2002。
[2]楊淯琮，中華衛星二號取像訂單排程問題—考慮天氣之隨機特性，碩士論文，國立暨南國際大學資訊管理研究所，2003。
[3]鄭琇璘，最佳化排程理論應用於衛星取像任務規劃之研究，碩士論文，國防大學中正理工學院電子工程研究所，2007。
[4]吳泰熙、張欽智，以禁忌搜尋法則求解推銷員旅行問題，大葉學報，第六卷，第一期，第87-99頁，1997。
[5]林偉誠，衛星取像排程之研究，博士論文，國立臺灣大學電機工程學研究所，2005。
[6]Knox , J. , Tabu search performance on the symmetric TSP, Computers & Operations Research, 21(8),pp.786-802,1994.
[7]林師檀，禁忌搜尋法與遺傳演算法混合模式在地下水復育優選問題之應用，碩士論文，國立中興大學環境工程研究所，2002。
[8]林禹豪，平行禁忌搜尋法於配水管網最佳化設計之應用，碩士論文，國立中興大學環境工程研究所，2003。
[9]劉盈利，螞蟻演算法與禁忌搜尋法之混合模式於配水管網最佳化設計之應用，碩士論文，國立中興大學環境工程研究所，2004。
[10]吳宗樺，強化螞蟻演算法與禁忌搜尋法之混合模式於配水管網最佳化設計之應用，碩士論文，國立中興大學環境工程研究所，2006。
[11]柯惠雯，結合模擬退火法與禁忌搜尋法在流程式生產排程之應用“，碩士論文，大葉大學工業工程研究所，2002。
[12]林惠民，具時窗之多趟次車輛途程問題，碩士論文，元智大學資訊管理學系碩士班，2002。
[13]李俊穎，以禁忌搜尋法求解週期性車輛途程問題，碩士論文，大同大學資訊經營研究所，2004。
[14]張哲維，修正禁忌搜尋法求解週期性車輛途程問題，碩士論文，國立東華大學企業管理學系碩士班，2006。
[15]劉曉君，轉接點位址問題之啟發式解法，碩士論文，大葉大學工業工程研究所，2001。
[16]吳信儀，以改良之進化策略演算法解決排序問題之研究—SRS演算法與多重工作者系統之發展，碩士論文，東海大學工業工程研究所，1996。
[17]Pinedo, M., Scheduling Theory, Algorithms, and Systems, Prentice Hall , London , pp.1-32,1994.
[18]唐恒永、趙傳立，排序引論，第一版，科學出版社，北京，第234-240頁，2002。
[19]楊照崑、楊重駿，未來數學家的挑戰—計算量問題， http://episte.math.ntu.edu.tw/articles/mm/mm_10_2_04/page2.html。(原載於數學傳播十卷二期)
[20]Marianov Vladimir, Daniel Serra and Charles ReVelle, Location of hubs in a competitive environmens , European Journal of Operation Research,114, pp.363-371 , 1999.
[21]Skorin-Kapov Darko and Jadranka Skorin-Kapov, On tabu search for the location of interacting hub facilities, European Journal of Operation Research, 73,pp.502-509,1994.
[22]Abdinnour-Helm Sue, A hybrid heuristic for the uncapacitated hub location problem, European Journal of Operation Research, 106,pp.489-499,1998.
[23]黃俊嘉，多廠整合型生產指派與排程系統之最佳化，碩士論文，國立東海大學工業工程與經營資訊研究所，2005。
[24]林惠民，具時窗之多趟次車輛途程問題，碩士論文，元智大學資訊管理研究所，2002。
[25]林慈傑，以遺傳演算法求解類運輸問題模式化的多廠訂單分配問題，碩士論文，國立臺灣大學工業工程所，2003。
[26]曾煥文，跨廠訂單分配模式之構建—應用模擬退火演算法，碩士論文，元智大學工業工程與管理研究所，1999。
[27]陳雅淑、林穎裕，衛星科技，科學發展，第374期，第70~75頁，2004年2月。
[28] 陳良健，遙測衛星—國土監測好幫手，科學發展，第365期，第28~33頁，2003年5月。
[29] NSPO：http://www.nspo.org.tw/2008c/projects/project2/intro.htm。
[30]Frederick S. Hillier and Gerald J. Lieberman , Interduction to operations research , 8th edition, chapter 13, 2006.(潘昭賢、葉瑞徽譯，作業研究，滄海書局，第十三章，2006。)
[31]【專題】萬物生長靠太陽 認識宇宙之太陽系(2009-01-05)：http://tech.big5.enorth.com.cn/system/2009/01/04/003849358.shtml。
[32]Center for Space and Remote Sensing Research National Central University： http://www.csrsr.ncu.edu.tw/08CSRWeb/ChinVer/
C6TechSupp/C6TechSupp.php。
[33]李建成，一覽無遺—衛星遙測影像，科學發展，第390期，第14~17頁，2005年6月。
[34]黃正中，遙測衛星於民生科技的應用，國研科技，第1期，第13~19頁，2004年1月
[35]劉正千，福爾摩沙二號衛星遙測影像自動處理與應用，自然科學簡訊，第二十卷第一期，第4~12頁，2008年2月。
[36]黃中，台灣看世界的眼睛－福爾摩沙二號，科學發展，第409期，第78頁，2007年1月。
[37]張政亮、張瑞津、紀宗吉，遙測與地理資訊系統應用於大甲溪流域之崩塌災害的調查與分析，地理研究，第43期，第101-121頁，2005年11月。
[38]李瑞陽、姜如憶，應用遙測技術於水稻田判釋之研究，地理研究，第43期，第61-81頁，2005年11月。
[39]Lin, S. and B. W. Kernighan, An Effective Heuristic Algorithm for the Traveling Salesman Problem, Operations Research, Vol. 21, pp.498-516 , 1973.