臺灣博碩士論文加值系統

隨著產業的競爭提升，保全產業面臨到同行競爭激烈的情況。保全業者認為必需開拓更多的服務機會及找出未來發展的方向。近幾年，隨著物流產業蓬勃發展，保全業者順著此潮流，因而跨入物流產業。有鑑於此，本研究試著探討在保全的巡邏任務中結合車輛配送後，建構模式並發展啟發式求解法，並與原先尚未結合的兩獨立運作系統之總距離成本作一比較，以確認是否達到較低的成本。
本研究共分為三個模式，傳統車輛配送模式(模式一)、保全巡邏路徑模式(模式二)與巡邏結合車輛配送模式(模式三)，主要目的皆為最小化總距離成本。其中，模式二與模式三皆有考量保全巡邏問題的三大特性，即分區性、責任性與突發需求性，本研究依此特有的三大特性，結合傳統車輛途程問題模式，發展出符合模式三的分區突發需求性車輛途程問題模式。三模式皆以相同的方法求解，即運用最鄰近法產生初始解，並以模擬退火法改善尋優，期望以最有效率及品質較佳的方式求得目標值。
本研究乃為比較模式三，與模式一及模式二之成本總和做一比較與探討。為求驗證結果公正可信，設計測試例題方面，模式三的總需求點集合為模式一的總需求點及模式二的總需求點之結合。成本比較方面，將以總距離成本、總車輛數、載貨率、總固定成本與突發巡邏需求點發生機率等面向進行比較與分析。
結果顯示，巡邏結合車輛配送模式之總距離與總車輛數成本，確實比尚未合併的兩獨立系統之總距離與總車輛數成本，效果顯著。載貨率方面，因為模式三之需求點，50%為配送需求點，50%為巡邏需求點，故表現較傳統車輛配送模式不佳，但結果實可接受與理解。總固定成本方面，發現在某些情況下適合兩模式合併。突發巡邏需求點發生機率方面，在區域性治安情況不同，且當需求點個數超過200時，確實會影響巡邏結合車輛配送模式的可行性。
不過綜觀成本比較，巡邏結合車輛配送模式確實比尚未結合的兩獨力系統表現佳，所獲得的結果值得相關產業參考與依據。

With increasing competition, every business organization tries to develop new sales channels depending on its logistic capability. The managements of security company believe that they must develop new opportunities to survive in the future. In recent years, the security company had entered into the business of logistic distribution. This study is a preliminary study of the security service combined with the vehicle routing service. The main objective of this model is to minimize total cost of distance as well as number of vehicle.
Three models are developed in this research. The first model is a traditional vehicle routing model, the second model is emergent traveling salesman problem with time window problem, and the third model is emergent vehicle routing problem with time window problem. The second and third model involves partitioning constraints, radius constraints, and emergency constraints. A heuristic algorithm is developed to solve the three models. The solution algorithm includes the nearest neighbor heuristic to get the initial solution, and the simulated annealing algorithm to find the near optimal solution.
Three numerical examples are used to illustrate the effectiveness of the proposed models and the solution algorithm. The results indicate that the third model is attractive from distance viewpoint. In addition, the total number of vehicle required in the third model is also lower than sum of the first and the second models. However, the vehicle utilization of the third model is lower than sum of the first and the second models. The experimental results also indicate that the probability of emergence is a critical factor which can decide whether the third model is profitable.

摘要 i
目錄 iv
圖目錄 vi
表目錄 vii
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 4
1.3 研究範圍與假設 5
1.4 研究架構與流程 6
第二章 文獻探討 8
2.1 保全巡邏路徑模式 8
2.1.1 保全的定義與任務 8
2.1.2 旅行銷售員問題 10
2.2 傳統物流中心之配送路徑模式 13
2.2.1 傳統物流中心之配送模式 13
2.2.2 傳統車輛途程問題及不同性質的車輛途程問題 14
2.3 車輛途程問題的求解方法 17
2.3.1 車輛途程問題解法 17
2.3.3 其他不同性質之車輛途程問題求解文獻回顧 23
2.4 田口實驗方法 26
2.5 文獻總結 29
第三章 模式建構與求解方法 30
3.1 問題定義與描述 30
3.2 模式建構 33
3.2.1 配送中心之傳統車輛途程問題模式 33
3.2.2 保全巡邏任務之分區突發需求性旅行銷售員問題模式 35
3.2.3 結合巡邏與配送問題之突發需求性車輛途程問題模式 37
3.2.4 模式驗證 39
3.3 啟發式求解法之步驟 40
3.3.1 初始路徑規畫階段及步驟 42
3.3.2 模擬退火法之路徑改善步驟 43
3.3.3 突發需求路徑規畫 51
第四章 例題測試與分析 52
4.1 例題設計及相關說明 52
4.2 參數設定及求解法驗證 56
4.2.1 模式一參數設定 58
4.2.2 模式二參數設定 60
4.2.3 模式三參數設定 63
4.2.4 參數確認實驗 65
4.2.5 求解法驗證 67
4.3 結果分析與比較 68
4.4 車輛數、載貨率與總固定成本之比較與分析 75
4.5 突發事件發生機率對混合模式之影響 82
第五章 結論與未來研究方向 87
5.1 結論 87
5.2 建議未來研究方向 88
參考文獻 89

英文部分
1.Anily, S., Bramel, J. and Hertz, A., “A 5/3-approximation algorithm for the clustered traveling salesman tour and path problems,” Operations Research Letters, Vol. 24, No. 1-2, pp. 29-35, 1999.
2.Calvo, R. W. and Cordone, R., “A heuristic approach to the overnight security service problem,” Computers and Operations Research, Vol. 30, pp. 1269-1287, 2003.
3.Chiang, W. C. and Russell, R. A., “Simulated Annealing Metaheuristics for the Vehicle Routing Problem with Time Windows,” Annals of Operations Research, Vol. 63, pp. 3-27, 1996.
4.D’Amico, S.,J., Wang, S., J., Batta, R., and Rump, C., M., “A simulated annealing approach to police district design” Computers and Operations Research, Vol. 29, pp. 667-684, 2002.
5.Gendreau, M., Hertz, A. and Laporte, G., “The traveling salesman problem with backhauls,” Computers and Operations Research, Vol. 23, No. 5, pp.501-508, 1996.
6.Haghani, A. and Jung, S., “A dynamic vehicle routing problem with time-dependent travel times,” Computers and Operations Research, Vol. 32, pp.2959-2986, 2005.
7.Ichoua, S., Gendreau, M., and Potvin, J., Y., “Vehicle dispatching with time-dependent travel times,” European Journal of Operational Research, Vol. 144, pp. 379-396, 2003.
8. Potvin, J. Y. and Rousseau, J. M., “A Parallel Route Building Algorithm for the Vehicle Routing and Scheduling Problem with Time Windows,” European Journal of Operational Research, Vol. 66, pp. 331-340, 1993.
9.Psaraftis, H. N., “Dynamic vehicle routing: Status and Prospects,” Annals of Operations Research, Vol. 61, pp. 143-164, 1995.
10.Regan, A. C., Mahmassani, H. S., Jailiet, P., “Improving efficiency of commercial vehicle operations using real-time information: potential uses and assignment strategies,” Transportation Research Record, Vol.1493, pp.188-198, 1994.
11.Solomon, M. M., “Algorithms for the Vehicle Routing and Scheduling Problems with Time Windows Constraints,” Operations Research, Vol. 35, No. 2, pp.254-265, 1987.
12.Swihart, M. R. and Papastavrou, J. D., “A stochastic and dynamic model for the single-vehicle pick-up and delivery problem,” European Journal of Operational Research, Vol. 114, pp. 447-464, 1999.
13.Tavakkoli-Moghaddam, R., Safaei, N., Gholipour, Y., “A Hybrid simulated annealing for capacitated vehicle routing problems with the independent route length,” Applied Mathematics and Computation, Vol. 176, pp. 445-454, 2006.
14.Taillard, E., Badeau, P., Gendreau, M., Guertin, F., Potvin, J. Y., “A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows,” Transportation Science, Vol. 31, No. 2, pp. 170-186, 1997.
15.Van Breedam, A., “Improvement heuristics for the Vehicle Routing Problem based on Simulated Annealing,” European Journal of Operational Research, Vol. 86, pp. 480-490, 1995.




中文部份
16.王至誠，「台灣地區保全業經營管理的特性與問題之研究」，碩士論文，國立中山大學高階經營管理碩士班，2000。
17.李洪鑫，「含時間窗車輛途程問題各演算法適用範圍之探討」，碩士論文，私立東海大學工業工程研究所，2000。
18.林志鴻、陳春益、許晉嘉，「宅配業車輛路線規劃問題之啟發式解法」，中華民國運輸學會，第18屆論文研討會，2003。
19.吳淵齊，「物流中心運輸成本及短缺罰金之最佳化模式」，碩士論文，國立雲林科技大學工業工程與管理研究所，
20.柯景文，「禁制搜尋法於動態車輛巡迴路線問題之研究」，碩士論文，私立逢甲大學交通工程與管理研究所，2002。
21.許晉嘉，「宅配業貨物配送路線規劃問題之研究」，碩士論文，國立成功大學交通管理研究所，2003。
22.敖君璋，「禁制搜尋法於軟性時窗限制之車輛途程問題研究」，碩士論文，私立元智大學工業工程研究所，1999。
23.張有恆，「現代物流管理」，華泰文化事業股份有限公司，2005。
24.張美香，「含時窗限制之動態需求車輛途程規劃問題」，碩士論文，私立中華大學經營管理研究所，(2001)。
25.梅明德、謝浩明，「時窗限制動態車輛路線問題之線上型路線建立啟發式解法」，運輸學刊，第13卷第二期，pp. 73-111，2001。
26.曾維豪，「軟性時窗與回程撿收之車輛途程問題研究」，碩士論文，私立元智大學工業工程研究所，2000。
27.楊世隆、何明洲、傅美惠，「保全概論」，台北：五南圖書出版股份有限公司，2005。
28.郭幸民、郭人介，「An Efficient Composite Algorithm For the Traveling Salesman Problem」，中華民國運輸學會，第17屆論文研討會，pp. 1007-1014，2001。
29.郭秋泔，「考慮旅行時間限制下之隨機旅行銷售員問題-以國際快遞業為例」，碩士論文，國立高雄第一科技大學運輸與倉儲營運研究所，2004。
30.劉曉君，「轉接點位址問題之啟發式解法」，碩士論文，私立大葉大學工業工程研究所，2000。
31.陳建緯，「大規模旅行銷售員問題之研究：鄰域搜尋法與巨集啟發式解法之應用」，碩士論文，國立交通大學運輸工程與管理研究所，2001。
32.陳致元，「單一物流中心車輛途程問題求解模式之空間分析研究」，碩士論文，國立台灣大學地理環境資源研究所，2001。
33.駱芳梧，「考量整備及拆卸時間之開放型工廠排程問題研究」，碩士論文，私立大葉大學工業工程研究所，2002。
34.韓復華、卓裕仁，「門檻接受法、噪音擾動法與搜尋空間平滑法在車輛路線問題之應用研究與比較分析」，運輸學刊，第9卷第三期，pp. 113-144，1996。
35.顏成佑，「基因演算法求解軟性時窗車輛途程問題之研究」，碩士論文，私立元智大學工業工程研究所，2000。
36.羅中育，「田口品質工程應用於模擬退火法參數組合之研究-以旅行推銷員問題(TSP)為例」，碩士論文，國立雲林科技大學工業工程與管理研究所，2000。
37.蘇鈺玲，「旅行推銷員問題之啟發式解法暨車輛路線規畫之應用」，碩士論文，私立義守大學管理科學研究所，1996。