English  |  正體中文  |  简体中文  |  Items with full text/Total items : 26988/38789
Visitors : 2343553      Online Users : 38
RC Version 4.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
Scope Adv. Search
LoginUploadHelpAboutAdminister

Please use this identifier to cite or link to this item: http://ntour.ntou.edu.tw:8080/ir/handle/987654321/16089

Title: 韋伯區位問題與其最佳路徑規劃於網格圖上之研究
Weber location problem and optimal path planning on raster
Authors: Chih-Ping Chen
陳志平
Contributors: NTOU:Department of Merchant Marine
國立臺灣海洋大學:商船學系所
Keywords: 韋伯區位問題;權重區域;四維迷宮路徑演算法;廣義韋伯問題;來源點
Weber location problem;weighted regions;4-geometry maze routing algorithm;generalized Weber problem;multi-sources
Date: 2006
Issue Date: 2011-06-30T08:33:03Z
Abstract: 傳統求解韋伯區位問題(Weber location problem)時,所求得之韋伯點(Weber point)均以直線距離(Euclidean distance)之量度方式於歐幾里德空間(Euclidean space)中依據其總和距離最小化之條件搜尋並與各來源點加以連結路徑,但在應用的平面空間中,由於障礙物(barriers)及不同權重區域(weighted regions)或擁擠區域之存在,將導致該韋伯點之搜尋及與各來源點間之連結路徑更形複雜;而本研究提出以網格式波形傳遞方式產生ㄧ成本累加表,並得以於該累加表上搜尋出廣義韋伯問題(generalized Weber problem)下之韋伯點區位,而後透過四維迷宮路徑演算法(4-geometry maze routing algorithm)於網格圖上回溯搜尋後,可於韋伯點與各來源點之間獲得最佳路徑。 本研究之韋伯區位方法可解決當平面上存有複雜多邊形之障礙物及不同權重區域時搜尋出韋伯點區位,一旦此韋伯點獲得搜尋,韋伯點與各來源點間之連結路徑根據總和距離(或成本)最小條件規劃後不再是直線,如此將使該韋伯區位問題之結果更符合實際區位問題,而本研究提出之演算法亦具有於線性時間複雜度下搜尋韋伯點之能力。
The traditional way to solve the Weber location problem in the Euclidean space is to find a Weber point that links all multi-sources with minimum total distances. But in the real location problem, the existence of barriers and various weighted regions (or congested regions) is complicated the Weber point’s search including the connection between the Weber point and all multi-sources. In this study, the generalized Weber problem find a Weber point (or a single facility location) from an accumulation table, generated by a grid wave propagation approach, is presented. The optimal connection paths between the Weber point and all multi-sources are also obtained by the 4-geometry maze routing algorithm. The Weber location method that developed in this research is able to find the Weber point when many complicated barriers and various weighted regions exist in the plane. Once the Weber point has been found, the path connection with the minimum total distance (or cost) between the Weber point and multi-sources are no longer straight lines. The result of this Weber location problem is more suitable for the real location problem and the algorithm has linear time complexity.
URI: http://ethesys.lib.ntou.edu.tw/cdrfb3/record/#G0M93710014
http://ntour.ntou.edu.tw/ir/handle/987654321/16089
Appears in Collections:[商船學系] 博碩士論文

Files in This Item:

File Description SizeFormat
index.html0KbHTML192View/Open


All items in NTOUR are protected by copyright, with all rights reserved.

 


著作權政策宣告: 本網站之內容為國立臺灣海洋大學所收錄之機構典藏,無償提供學術研究與公眾教育等公益性使用,請合理使用本網站之內容,以尊重著作權人之權益。
網站維護: 海大圖資處 圖書系統組
DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - Feedback