動態式準則評估於旅遊行程安排之最優化

DYNAMIC CRITERIA EVALUATION FOR TOUR SCHEDULING OPTIMIZATION

張宏瑋(Hung-Wei Chang)

指導教授 ： 張應華

大同大學/經營設計學院/資訊經營學系所/碩士(2007年)

摘要

決策問題在日常生活中隨處可見，然而大部分所遇到的問題是比較簡單，所以要做出一個適當的決策不是件難事。但當問題晉升到「規劃」、「計畫」及「設計」層次時，決策考量因子越形複雜，決策限制式也愈多，決策的制訂亦趨困難，因此形成了所謂複雜的多準則決策問題(Multi-Criteria Decision Making Problems)。然而人類決策制定的考量因子與限制條件，往往會隨時間而改變。故加入「時間」觀點動態的來剖析決策制訂過程，可以讓決策成果更貼近所需。
本研究即以多準則決策為基礎，輔以動態決策概念，採用共演化式遺傳演算法(Co-evolutionary Genetic Algorithms)來發展模仿人類動態思考模式，以解決複雜的多準則決策問題，並以台灣北部旅遊行程規劃為例，利用遺傳演算法平行處理之優點及共演化機制的準則動態評估特性，透過一系列的旅遊行程規劃模擬，來檢驗共演化式遺傳演算法運用於多準則決策問題的適用性。
經實驗研究測試一般遺傳演法、傳統作業研究與共演化式遺傳演算法後，證實共演化式遺傳演算法不僅僅能模仿人類解決事情的方式來處理問題，並且可以加速找到最佳滿意解的速度。在未來研究方面，可將共演化式遺傳演算法應用於其他領域以供實務上各決策系統開發設計之參考。

關鍵字

動態準則評估 ； 多準則決策問題 ； 共演化式遺傳演算法 ； 最佳化 ； 旅遊行程規劃

並列摘要

People always make decisions in their daily life. However, the most problems are easy to solve. So it can make a property decision. But the more complex problems, the more criteria we have to care about. The decisions become more and more difficult. It forms the Multi-Criteria Decision Making Problems (MCDM). The criteria may be altered by the time. Owing to this reason, it must consider the viewpoint of time into the decision-making process.
This research is based on the dynamic multi-criteria decision-making concept. Adopting co-evolutionary genetic algorithms to solve decision-making problems, it combines the general genetic algorithm with co-evolutionary mechanism to simulate the human thinking to provide the solutions. This paper uses northern Taiwan traveling scheduling for demonstration, and make use of the advantage of genetic algorithms (implicated parallel processing ability and the auto-adjusting capacity) to modify the drawback of traditional methods. After making a serious of experiment to simulate the tour planning that can test the suitable of using co-evolutionary genetic algorithms.
This paper test some tour planning problems and it can find some advantages of co-evolutionary mode. Such as it can not only simulate the thought how people to figure out the problem but also accelerate to find the satisfied answers. So this research provides some reference on decision system developing and design in the future.

並列關鍵字

Optimization ； Dynamic Evaluation Mechanism ； Multi Criteria Decision Making ； Co-evolutionary Genetic Algorithms ； Tour Planning

參考文獻

[2] Bielli, M., Caramia M. and Carotenuto P., 2002, ”Genetic algorithms in bus network optimization”, Transportation Research, Part C 10, pp.19-34.

[6] Delgadoa, M. R., F. V. Zubenb and F. Gomideb, Coevolutionary genetic fuzzy systems: a hierarchical collaborative approach, Fuzzy Sets and Systems, vol.141, 2004, pp.89-106.

[7] Ehrlich, P.R., P.H. Raven, 1964, ButterDies and plants: a study in coevolution, Evolution vol.18 pp586–608.　

[8] Garey, M. R. and Johnson D. S. 1979, Computers and intractability: A guide to the theory of NP-completeness. Freeman, San Francisco.

[9] Goldberg, D.E., 1989, “Genetic Algorithms in search, optimization and machine learning”, Addison Wesley.