現在位置首頁 > 博碩士論文 > 詳目
  • 同意授權
論文中文名稱:飛機座位配置之研究 [以論文名稱查詢館藏系統]
論文英文名稱:An approach for airline seats allocation [以論文名稱查詢館藏系統]
院校名稱:臺北科技大學
學院名稱:管理學院
系所名稱:工業工程與管理研究所
畢業學年度:98
出版年度:99
中文姓名:劉宇倫
英文姓名:Yu -Lun Liu
研究生學號:96378033
學位類別:碩士
語文別:中文
口試日期:2009-12-10
論文頁數:39
指導教授中文名:吳建文
口試委員中文名:陳凱瀛;陳鵬文
中文關鍵詞:整數線性規劃
英文關鍵詞:Set Packing ProblemGRASPLinear Programming
論文中文摘要:顧客對於一家公司的滿意度,關係著顧客是否會再次接受這家公司的服務,也同時影響這家航空公司的風評,畢竟在現今資訊流動如此快速的時代,壞的商譽只會讓這家公司缺乏競爭力。有鑑於此,本研究針對飛機座位的配置做出規劃,希望能夠透過座位的配置,達到提昇顧客滿意度的目的。本研究利用集合包裝的概念,將座位配置的規劃問題轉換成整數線性規劃的問題,使用GRASP演算法來求解。最後再與Lingo8.0軟體所得之結果互相比較,實驗結果證實GRASP演算法所得之結果與Lingo8.0軟體所求得的結果相當接近。
論文英文摘要:This thesis consider a seat allocation problem for airlines, with focus on increasing customer satisfaction. An algorithm based on greedy randomized adaptive search procedure is proposed. Experiments were performed and the results show the competitiveness of the proposed algorithm.
論文目次:中文摘要---------------i
英文摘要--------------ii
誌謝-----------------iii
目錄------------------iv
表目錄----------------vi
圖目錄---------------vii
第一章 緒論------------1
1.1 研究背景與動機---------1
1.2 研究目的---------------1
1.3 研究範圍---------------2
1.4 研究流程---------------2

第二章 文獻探討-------4
2.1關於集合包裝問題、集合切割問題和集合覆蓋問題之比較--------------4
2.2關於收益管理應用於座位管理的研究--------------------------------- 6
2.3裝載問題研究之整理-----7
2.3.1二維度裝載問題--------------------7
2.3.1.1物件形狀與裝載空間的形狀--------7
2.3.1.2裝載順序----------------------------7
2.3.1.3不規則裝載物件與儲存空間的表示方----9
2.3.2其他與裝載問題相關的研究問題----------9
2.3.2.1 材料切割問題(Cutting Stock Problem)---9
2.3.2.2 棧板堆疊問題(Pallet Loading Problem--10
2.3.2.3 背包問題(knapsack problem)---------- 10
2.3.2.4 裝箱問題(Bin Packing Problem)--------10
2.4 GRASP演算法的介紹與應用----------- 11


第三章 研究方法-------- 12
3.1問題描述與座位配置規則------------- 12
3.2列舉出旅行團每種可行座位配置的方法- 14
3.3 計算可行座位配置的成本------------ 17
3.4將座位配置問題以SPP的概念轉換成數學模型-- 18
3.5使用GRASP求解數學規劃模型-----------------22
3.5.1第一階段找出一組可行的座位配置-------22
3.5.2區域搜尋階段(k-p交換法)--------------23
3.5.3GRASP完整的求解流程------------------26
第四章 實驗與實驗結果----------------27
4.1實驗績效之判定方式----------------- 27
4.2 實驗結果---------------------------28
4.2.1 實驗數據-----------------------28
4.2.2 實驗比較結果-------------------29
4.2.3 時間相近的情況下兩種方法之結果比較-34
4.2.4 加入privileges status之實驗--------36

第五章 結論與建議-----------------------38
5.1 結論---------------------38
5.2 未來研究方向以及相關之應用---38

參考文獻----------------------------------39
論文參考文獻:[1].A.Tajima, S. Misono , “Using a set packing formulation to solve airline seat allocation-reallocation problems”, Journal of the Operation Research Society of Japan ,Vol.42 N0.1, 1999.
[2].P.S.You , “An efficient computational approach for railway booking problems”, European Journal of Operational Research 185, pp. 811–824, 2008.
[3].S.Yan, J.C.Chang , “Airline cockpit crew scheduling”, European Journal of Operational Research 136, pp. 501–511, 2001.
[4].Y.Azar , L.Epstein , “On Two Dimensional Packing”, JOURNAL OF ALGORITHMS 25, pp. 290-310,1997.
[5].D.W. Pentico , “The assortment problem: A survey”, European Journal of Operational Research 190, pp. 295–309, 2008.
[6].X.Delorme , X.Gandibleux , J.Rodriguez , “GRASP for set packing problems”, European Journal of Operational Research 153, pp.564–580, 2004.
[7].W.K. Wong, X.X. Wang, P.Y. Mok , S.Y.S. Leung , C.K. Kwong , “Solving the two-dimensional irregular objects allocation problems by using a two-stage packing approach”, Expert Systems with Applications 36, pp. 3489–3496, 2009.
[8].K. A. Dowsland , W. B. Dowsland , “Packing Problem”, European Journal of Operational Research 56, pp. 2-14, 1992.
[9].胡釗維、尤子彥,”亞航買最新的飛機,卻賣最便宜的機票 全球最佳廉價航空“,商業周刊 第1129期,2009-07-13。
[10].J.Bautista, J.Pereira , “A GRASP algorithm to solve the unicost set covering problem”, Computers & Operations Research 34 pp. 3162 – 3173,2007.
[11].吳泰熙,吳奕樺,張欽智,”以基因演算法求解單原片方形物件排列問題”,Journal of Science and Engineering Technology, Vol. 2, No. 3, pp. 75-83,2006。
[12].吳泰熙,邱創鈞,賴志昌,”以協力演化遺傳演算法求解容器堆疊問題”,Journal of Technology, Vol. 22, No. 2, pp. 117-125,2007。
[13].S.Binato, G.C.de Oliveira, and J.L.de Araújo , “A Greedy Randomized Adaptive Search Procedure for Transmission Expansion Planning”, IEEE TRANSACTIONS ON POWER SYSTEMS, Vol. 16, NO. 2, 2001.
論文全文使用權限:同意授權於2013-02-05起公開