研究生: |
楊宗燁 Zong-Yeh Yang |
---|---|
論文名稱: |
以模擬退火法求解雙目標越野問題 Bi-objective Simulated Annealing for Orienteering Problem |
指導教授: |
喻奉天
Vincent F. Yu |
口試委員: |
郭人介
Ren-Jieh Kuo 林詩偉 Shih-Wei Lin 林振榮 J.-R.Lin |
學位類別: |
碩士 Master |
系所名稱: |
管理學院 - 工業管理系 Department of Industrial Management |
論文出版年: | 2017 |
畢業學年度: | 105 |
語文別: | 中文 |
論文頁數: | 48 |
中文關鍵詞: | 多目標最佳化 、越野問題 、模擬退火法 |
外文關鍵詞: | Multi-objective Optimization, Orienteering problem, Simulated Annealing |
相關次數: | 點閱:875 下載:2 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
多目標問題有別於單一目標問題,其困難之處在於如何在不同的目標中做衡量,如規劃旅程中的移動速度與金錢成本,或是自然生態指數與城市人文指數兩兩間有著互相衝突的特性,旅行者往往面臨到眾多景點中不同特性,在有限的時間與金錢預算中難以做出取捨,然而在多目標規劃(Multi-objective programming)問題中,僅有單一最佳解的情形十分罕見,因此需要一組凌越解集合(Noninferior Solutions),再提供給旅行者做評估、參考或是實際走訪。
過去諸多研究均以透過權重組合函數,使問題簡化為單一目標問題,透過調整權重改變鄰近解的搜尋方向,然而這樣的方法並無考量到在執行鄰近解搜尋時,所有解的集合空間內產生出的新鄰近解與現有凌越勢解集合的相對位置,因此本研究以模擬退火法結合加權函數與解的相對位置發展多目標最佳化演算法,經運算測試後,對於提升求解效率有顯著效果。
Unlike Single-objective programming, the difficulty of Multi-objective programming lies in how to evaluate the different categories of objectives, such as planning the moving speed and money cost during a journey, or analyzing and calculating the conflicting feature between the natural Ecological index and Humanities index. Travelers often encounter numerous characteristics in different tourist attractions, and it becomes hard for them to make choices due to the limitation of time and money. However, in a Multi-objective programming, the case that contains only one optimal solution is very rare, therefore, it is necessary to set up a set of Noninferior Solutions, and then provide these solutions for travelers’ own assessment, reference or visit.
Various studies in the past simplifies a problem into a Single-objective function by increasing weights, and adjusts the searching direction of near solutions by arranging the weights. Nevertheless, this method doesn’t take into account the relative position between the near solutions produced by the all solutions set, and the existing Noninferior solutions set when conducting near solution searching. As a consequence, this study develops an optimal Multi-objective programming algorithm by combining Simulated Annealing and the relative position between weight function and its solution.
Arkin, E. M., M. Held, J. S. B. Mitchell and S. S. Skiena (1998). "Recognizing polygonal parts from width measurements." Computational Geometry-Theory and Applications 9(4): 237-246.
Arkin, E. M., J. S. B. Mitchell and G. Narasimhan (1998). "Resource-constrained geometric network optimization." Proceedings of the fourteenth annual symposium on Computational geometry: 307-316.
Battiti, R. and G. Tecchiolli (1994). "The Reactive Tabu Search." ORSA Journal on Computing 6: 126-140.
Boussaid, I., J. Lepagnot and P. Siarry (2013). "A survey on optimization metaheuristics." Information Sciences 237: 82-117.
Butt, S. E. and T. M. Cavalier (1994). "A heuristic for the multiple tour maximum collection problem." Computers & Operations Research 21(1): 101-111.
Chao, I. M., B. L. Golden and E. A. Wasil (1996). "The team orienteering problem." European Journal of Operational Research 88(3): 464-474.
Czyzak, P., & Jaszkiewicz, A. (1996). "A multiobjective metaheuristic approach to the localization of a chain of petrol stations by the capital budgeting model." Control and Cybernetics 25(1): 177-187.
Gendreau, M., G. Laporte and F. Semet (1998). "A branch-and-cut algorithm for the undirected selective traveling salesman problem." Networks 32(4): 263-273.
Glover, F. (1986). "Future paths for integer programming and links to artificial intelligence." Computers & Operations Research 13(5): 533-549.
Hansen, M. P., A. Jaszkiewicz and D. T. U. I. f. M. Modellering (1998). Evaluating the Quality of Approximations to the Non-dominated Set, IMM, Department of Mathematical Modelling, Technical Universityof Denmark.
Hansen, P., N. Mladenovic and D. Perez-Britos (2001). "Variable neighborhood decomposition search." Journal of Heuristics 7(4): 335-350.
Holland, J. H. (1975). Adaptation in Natural and Artificial Systems, University of Michigan Press.
Kataoka, S. and S. Morito (1988). "An algorithm for single constraint maximum collection problem." Journal of the Operations Research Society of Japan 31: 515-530.
Kirkpatrick, S., C. G. . and M. Vecchi (1983). "Optimization by Simulated Annealing." Science 220: 671-680.
Laporte, G. and S. Martello (1990). "The Selective Traveling Salesman Problem." Discrete Applied Mathematics 26(2-3): 193-207.
Schilde, M., K. F. Doerner, R. F. Hartl and G. Kiechle (2009). "Metaheuristics for the bi-objective orienteering problem." Swarm Intelligence 3(3): 179-201.
Serafini, P. (1994). Simulated Annealing for Multi Objective Optimization Problems. Multiple Criteria Decision Making: Proceedings of the Tenth International Conference: Expand and Enrich the Domains of Thinking and Application. G. H. Tzeng, H. F. Wang, U. P. Wen and P. L. Yu. New York, NY, Springer New York: 283-292.
Suppapitnarm, A., K. A. Seffen, G. T. Parks and P. J. Clarkson (2000). "A simulated annealing algorithm for multiobjective optimization." Engineering Optimization 33(1): 59-85.
Vansteenwegen, P., W. Souffriau, G. Vanden Berghe and D. Van Oudheusden (2009). "Iterated local search for the team orienteering problem with time windows." Computers & Operations Research 36(12): 3281-3290.
Zitzler, E. and L. Thiele (1999). "Multiobjective evolutionary algorithms: A comparative case study and the Strength Pareto approach." Ieee Transactions on Evolutionary Computation 3(4): 257-271.
Zitzler, E., L. Thiele, M. Laumanns, C. M. Fonseca and V. G. da Fonseca (2003). "Performance assessment of multiobjective optimizers: An analysis and review." Ieee Transactions on Evolutionary Computation 7(2): 117-132.