應用地理資訊系統於車輛途程問題之研究

An Application of Geographic Information System on

饒怡莊(Yi-Chuang Jao)

指導教授 ： 胡黃德

元智大學/工程學院/工業工程與管理學系/碩士(2000年)

摘要

地理資訊系統的應用技術目前已經到了十分成熟的階段，不論在軍事、地理研究、城鄉規劃或是生活中的駕駛活動等也已見到它的出現。在運輸成本佔很大比例的物流系統中，能否結合學術上的途程理論和先進的資訊科技來降低企業成本、提高收益與增加競爭力，是產學界所共同努力追求的目標。本研究之目的在應用一般車輛途程問題模式於一結合地理資訊系統與資料庫的路徑規劃系統，使用者能利用此一系統透過地理資訊系統規劃、儲存所需之需求點資料。所提出之新啟發式演算法利用節省法來建構初始途程，以途程間交換和途程間插入法來定義兩個循序使用的禁制搜尋法，最後使用包含三種鄰近解搜尋方式的途程內下降法來求得近似最佳解。此演算法在穩健的參數設計下，和以往文獻中13題例題之最佳解做比較，平均誤差率為3.24%;且進行需求點數量為1000的途程規劃時，需時387秒。未來之後續研究亦在本文中提出。

關鍵字

車輛途程問題 ； 塔布搜尋法 ； 地理資訊系統

並列摘要

Nowadays, geographic information system (GIS) is widely used in military, geography, urban planning and development and daily driving. To reduce the cost, raise the benefit and increase the competitive ability with integrating academic theorey and advanced information technology is the common target of both academia and in practice. The aim of this thesis was to develop an application framework which integrated general vehicle routing problem module with geographic information system and database so that users could plan and store the nodes information in routing planning. A new algorithm with saving algorithm, two consecutive tabu searches and inner-route descent method was implemented which needed 387 seconds to execute a test problem with 1,000 nodes. Computational results were reported with an average errror percentage of 3.24% on a sample of thirteen bench mark test problems from the literature. Further researches was also reported in this study.

並列關鍵字

Tabu Search ； Vehicle Routing Problem (VRP) ； Geographic Information System (GIS)

參考文獻

韓復華、楊智凱、卓裕仁，「應用門檻接受法求解車輛路線問題之研究」，運輸計劃季刊，第26卷，第2期，253至280頁，1997.

徐明輝，「多部車一般性車輛途程解算法之研究」，元智工學院工業工程研究所，碩士論文，1997.

林書銘，「禁制搜尋法於含時窗與裝載限制車輛途程問題解算之研究」，元智大學工業工程所，碩士論文，1998.

陳坤賓，「模擬退火演算法應用於車輛途程問題之研究」，元智大學工業工程所，碩士論文，1998.

陳振稻，「單一車輛貨物運輸途程之探討」，元智工學院工業工程研究所，碩士論文，1994.