臺灣博碩士論文加值系統

旅行者問題發展至今，已漸講求實用性，主要應用於旅遊計畫、生產排程
等方面。旅遊計畫通常須考慮時間及成本兩績效衡量標準，屬於雙目標旅
行者問題。旅遊計畫除了旅行地點的排定外，各據點間交通工具的安排，
亦是行程計劃的重點。傳統旅行者問題通常只假設單一工具，這限制了旅
行者問題的應用。有鑑於此，本研究發展雙目標—多工具旅行者問題，以
期使旅行者問題之應用更切合實際。本研究所發展之雙目標—多工具旅行
者問題的解題方法可依使用者所期望的時間、成本預算，排定一系列滿足
限制的旅行行程。只要使用者輸入時間、成本權數，便可得到一建議行程
。本研究所發展的法則最大的特色在於找出一系列相對較佳解，以便使用
者有較大的選擇空間，而所產生的建議解則可加速使用者進行決策。本研
究所發展的演算法則與LINDO　所產生之最佳解進行比較。結果顯示，所
發展的演算法中，以 Alg1.1 所產生解的品質最佳，且亦具解題快速等優
點。雙目標—多工具旅行者問題為一剛開始發展的領域，本研究針對數學
模式及解題方法進行探討，期望藉由此研究成果，使旅行者問題有更廣泛
的應用。

The classical Traveling Salesman Problem (TSP) has been
sucessfully applied to a broad variety of real word situation
from tour scheduling and production scheduling problems. The
tour scheduling problem is a typical bicriterion TSP containing
both of time and cost criteria. The tour scheduling problem
consists of itinerary and travel tools between each city pairs.
The classical TSP considers only a single tool between cities
that limits practical application. In this research we are
interesting in the bicriterion-multivariant version of TSP. The
heuristic algorithms can construct a series of the itinerary
with time and budget limits. The traveler can get a near
optimal solution by inputting time and cost weights. A set of
undominated solutions will be found by solving these heuristic
algorithms. A set of undominated solutions helps user to make
more flexible decision than a single solution, and the near
optimal solution increases user's decision making speed. This
research also evaluate the performance of those heuristic
algorithms by comparing them with the result of LINDO. The
conclusion is that Alg1.1 is the most efficient method among
these heuristic algorithms. The bicriterion-multivariant TSP (
BMTSP ) is a new area. This research developed the mathematical
model and heuristic algorithms to the BMTSP. We hope that the
result of this research can expand the applications of TSP to
more practical problems.