臺灣博碩士論文加值系統

本論文旨在討論以蟻群演算法與禁忌演算法與模擬退火演算法於最佳化物流車輛派遣
之路徑規劃，利用市面上所販售之電子地圖做為費洛蒙路徑儲存工具，藉由已知路線與客
戶位置並考慮時間窗的限制，以亂數產生派遣指令，當前方物流車遇到障礙時，立即將費
洛蒙路徑藉由GPRS行動網路傳回控管中心，控管中心立即將此時間窗內的障礙標示為禁忌
區域，並且可以在控管中心的管制軟體中查詢該區座標，同時變更後方物流車行走路線，
即時下傳至車上電腦，完成路徑更新，不必等待物流車回到物流中心，即時閃避障礙區
域，等待該路徑累積足夠的路徑數量，就可以運用模擬退火演算法分析歷史資料，並參考
路線行車成本與道路容量限制，找出一條最具有經濟價值的路線，同時考量客戶查詢需
求，於系統內增加 GSM簡訊查詢貨物即時位置以增加系統價值，藉由服務功能的提升，增
加競爭力。

Since man invented the first satellite, searching
& positioning and communication have existed around
our life. From high-secret national defense industries
to traffic scale control GPS (Global Positioning System)
played a key role in these works. On the thoughts that
how to prevent serious car accidents caused by heavy
trucks and cars-stolen, to invent a monitoring system
that can positioning, warning in advance, anti-stealing
, protection for people and cars becomes a necessary
research.
In this study, we will develop full-functional “An ant
algorithm used to solve the Vehicle Routing Problem” or
transmitting location of positioning object through
signals of MODEM, SMS, VOICE by “GSM (Global System for
Mobile Communication)”. Car owner can real-time find or
search his car condition with mobile phone by connecting
table computer, notebook computer, and pocket-computer.
This system has low-cost, convenience, easy-operating and
doesn’t need expensive and complex manage system only need
to pay low cost mapping software.
The functions in this project are as following:
(1) Taking advantage of MODEM, SMS, and VOICE signals
through GPRS (General Packet Radio Services) or GSM
(Global System for Mobile Communications) to
positioning destination objects.
(2) Map route history data decoder.
(3) Map route history data refresh.
(4) SMS signals decoder.
(5) TOA (Time of Arrival,TOA) data decoder.

目　錄

摘 要 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥Ⅰ
ABSTRACT‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥Ⅱ
誌 謝 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥Ⅲ
目 錄 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥Ⅳ
表目錄‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥Ⅴ
圖目錄‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥Ⅵ
第一章 緒 論‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥1
1.1 研究背景與動機‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥1
1.2 研究目的‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥12
1.3 研究範圍與限制‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥13
1.4 研究架構‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥14
1.5 研究流程‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥15
第二章 文獻探討‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥17
2.1 路徑規劃演算法‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥17
2.2 最佳化演算法‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥17
2.3 啟引式搜尋法‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥19
2.4 供應鏈的演進‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥26
2.5 行動通訊無線定位法‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥27
第三章 研究方法‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥32
3.1 問題描述‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥32
3.2 研究方法‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥32
3.3 問題定義與研究‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥36
第四章 實驗設計與分析‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥42
4.1 目標設定‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥42
4.2 費洛蒙路徑檔案格式‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥43
4.3 演算法執行‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥45
4.4 實驗結果‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥46
4.5 物流車路徑資料‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥47
4.6 實驗電路‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥50
4.6.1 實驗電路設計規劃初期驗證‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥50
4.6.2 貨物查詢系統實際完成成品‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥51
4.6.3 GPRS電路 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥55
4.6.7 GPS 電路 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥56
4.7 GPS系統規格‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥57
4.8 GPRS系統規格‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥61
第五章 究結論與後續研究方向‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥66
5.1 研究結論‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥66
5.2 後續研究方向‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥66
參考資料‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥68


表目錄

表2.1 最佳化與模擬法之比較‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥18
表3.1 TS與SA方法比較‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥41
表4.1 物流車遞送貨物行走路徑比較 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥46
表4.2 GPS規格說明 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥57
表4.3 GPS一般操作條件 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥58
表4.4 GPS絕對操作條件 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥58
表4.5 GPS晶片操作規格 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥59
表4.6 GPS直流參數列表 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥59
表4.7 GPS I/O 介面定義 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥60
表4.8 參數列表‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥64



圖目錄

圖1.1 供應鏈運作流程‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥2
圖1.2 供應鏈作業參考模式的管理流程‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥4
圖1.3 GPS空間衛星星座圖 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥5
圖1.4 衛星系統構成圖‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥6
圖1.5 GPS空間衛星星座的平面投影 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥6
圖1.6 地面監控站‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥8
圖1.7 供應鍊各環節與企業各活動的對照 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥11
圖1.8 研習流程 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥14
圖1.9 研究流程圖 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥16
圖2.1 尋求最佳解架構 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥19
圖2.2 退火結晶示意圖 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥21
圖2.3 由蟻巢至食物的正常路徑 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥22
圖2.4 由蟻巢至食物的路徑產生障礙物 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥22
圖2.5 螞蟻繞過障礙物走行到食物 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥22
圖2.6 受費洛蒙影響螞蟻選擇最短路徑繞過障礙物走行到食物 ‥‥‥‥‥‥‥‥‥22
圖2.7 無障礙時的螞蟻走行到食物的狀態 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥23
圖2.8 障礙發生時的螞蟻走行到食物的狀態 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥23
圖2.9 障礙發生後的螞蟻繞行障礙走行到食物的狀態 ‥‥‥‥‥‥‥‥‥‥‥‥‥23
圖2.10 障礙發生一段時間後的螞蟻繞行障礙走行到食物的狀態 ‥‥‥‥‥‥‥‥23
圖2.11 蟻群演算法運作流程‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥25
圖2.12 Cell ID ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥29
圖2.13 定向?物面網格天線 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥31
圖2.14 抵達角度定位法‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥31
圖3.1 物流車輛派遣系統架構 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥34
圖3.2 遞交物品追蹤系統架構 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥35
圖3.3 禁忌演算法 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥39
圖3.4 模擬退火演算法 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥41
圖4.1 服務點整結構圖示 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥42
圖4.2 電子地圖路徑儲存格式 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥43
圖4.3 電子地圖路徑檔案格式轉換 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥44
圖4.4 主程式執行第一頁 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥45
圖4.5 主程式執行第二頁 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥45
圖4.6 第一路徑資料 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥47
圖4.7 第二路徑資料 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥48
圖4.8 第三路徑資料 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥49
圖4.9 貨物查詢系統初期試作電路 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥50
圖4.10 貨物查詢系統完成成品正面‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥51
圖4.11 貨物查詢系統完成成品背面‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥52
圖4.12 GPRS板與GPS板‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥53
圖4.13 模組拆解圖‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥54
圖4.14 GPRS MC55 模組電路圖設計 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥55
圖4.15 GPS 路圖設計‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥56
圖4.16 GPS 模組方塊圖‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥58
圖4.17 MC55/56 系統方塊圖‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥61
圖4.18 MC55/56 與控制器之間的介面‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥62
圖4.19 MC55/56 I/O 接點 ‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥‥63

[1] MobileMap 使用手冊
[2] Magic e-Map 使用手冊
[3] MC55/56 Siemens Cellular Engine, Version 02.06,
DocID MC55/56_hd_V02.06
[4] MC55/56 Siemens Cellular Engine,Hardware Interface Description,
Version 00.01, DocID MC55/56_HD_V00.01
[5] LEADTEK GPS MODULE GPS 9805 Ⅲ DATA SHEET ,Version 1.1,2005-01-20
[6] 林清河(2002)物料管理 ISBN957-609-424-0
[7] 羅敏華(2003)蟻群最佳化演算法於載重限制之車輛途程問題的研究 私立元智大學
工業工程與管理研究所
[8] Doerner. M. Gronalt. R. F. Hartl, M. Reimann. C. Strauss,
and M. Stummer.“SavingsAnts for the Vehicle Rounting
Problem.”POM Working Paper 02/2002,Department of Production and
Operations Management,University of Vienna,2002
[9] Dorigo, Optimization.Learning and Natural Algorithms, Ph.D.
Thesis,Politecnico Di Milano,Italy, 1992.
[10] Dorigo,M,Bonabcau,E,& Theraulaz G.(2000).Ant
algorithms and stigmergy.Future Generation Computer
System,16,851-871
[11] Yiliv Zhao,”Mobile Phone Location Determination and Its Impact
on Intelligent Transportation System”,IEEE Transactions on
Intelligent Transportation Systems,Vol.1,March 2000
[12] James M. Zagami, Steen A. Parl, Julian J. Bussgang, Karen
Devereaux,”Providing Unuversal Location
[13] Gwenael Le Bodic,”Mobile Messaging Technologies and
Services: SMS, EMS and MMS, 2/e”,ISBN: 0470011432
[14] Li Cong, Weihua Zhuang,”Non-line-of-sight Error Mitigation in
TDOA Mobile Location”,Global Telecommunications Conference,2001.
GLOBECOM’01.IEEE,Vol.1,2001
[15] Xin Wang,Zongxin Wang,O’Dea B.”A TOA-Based Location Algorithm
Reducing the Errors Due ro Non-line-of-Sight (NLOS) Propagation”
,Vehicular Technology Conference,2001.VTC 2001 Fall.IEEE VTS
54,Vol.1,2001