巡邏車輛途程問題

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：6

、訪客IP：3.147.140.129

姓名

陳思齊(Sz-Chi Chen) 查詢紙本館藏

畢業系所

土木工程學系

論文名稱

巡邏車輛途程問題
(The Patrol Car Routing Problem)

相關論文

★ 圖書館系統通閱移送書籍之車輛途程問題	★ 起迄對旅行時間目標下高速公路匝道儀控之研究
★ 結合限制規劃法與螞蟻演算法求解運動排程問題	★ 共同邊界資料包絡分析法在運輸業之應用-以國內航線之經營效率為例
★ 雙北市公車乘客知覺服務品質、知覺價值、滿意度、行為意向路線與乘客之跨層次中介效果與調節式中介效果	★ Investigating the influential factors of public bicycle system and cyclist heterogeneity
★ A Mixed Integer Programming Formulation for the Three-Dimensional Unit Load Device Packing Problem	★ 高速公路旅行時間預測之研究--函數資料分析之應用
★ Behavior Intention and its Influential Factors for Motorcycle Express Service	★ Inferring transportation modes (bus or vehicle) from mobile phone data using support vector machine and deep neural network.
★ 混合羅吉特模型於運具選擇之應用-以中央大學到桃園高鐵站為例	★ Preprocessing of mobile phone signal data for vehicle mode identification using map-matching technique
★ 含額外限制式動態用路人均衡模型之研究	★ 動態起迄旅次矩陣推估模型之研究
★ 動態號誌時制控制模型求解演算法之研究	★ 不同決策變數下動態用路人均衡路徑選擇模型之研究

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

巡邏車輛途程問題(Patrol Car Routing Problem, PCRP)係指巡邏車從總部出發，依照預先設定之目標繞行管轄範圍內之節點或路段，然後回到總部結束勤務謂之。PCRP依照問題之性質可以概分成三類：(1)節點之車輛途程問題(Vehicle Routing Problem, VRP)，(2)節線之中國信差問題(Chinese Postman Problem, CPP)，(3)前兩者之混合，為一般性車輛途程問題。本研究針對第一類與第二類問題深入探討，納入即時性(犯罪案件隨時隨地發生)與時窗限制(特定時間與地點為犯罪熱點)之可能性，並以增設虛擬節點與虛擬節線的方式將節線之中國信差問題轉換成節點之車輛途程問題，相較於以往文獻，將虛擬點之間距離合理轉換，並建構為混合整數規劃模型。針對含即時性之巡邏車輛途程問題，利用滾動時間之概念，在關鍵時點上，納入即時性需求考量，對所建構之數學模型重複求算其初始路線與進行路線改善，以獲得近似最佳解。
本研究產生30組測試例題作為測試分析，歸納出巡守時間長短影響線上巡邏車數，線上巡邏車數進一步影響巡邏車到案發現場的反應時間。而隨機案件的產生，擾動了原先規劃的路線，進一步影響了總使用車輛數及巡邏班次，同時巡邏車支援案發點亦造成總旅行時間的變長。最後本研究與巡邏實務運作方式比較，以驗證模型與演算法之正確性。

摘要(英)

The patrol car routing problem (PCRP) is the problem of finding a minimum cost route for the patrol cars, subject to the condition that the patrol cars cruise certain nodes or links of a network. The PCRP can be regarded as an extension of the conventional vehicle routing problem with time windows (VRPTW) and Chinese postman problem with time windows (CPPTW). In this paper we approximate the PCRP by adopting the time rolling horizon approach in which a mixed integer optimization subproblem, is repetitively formed and solved so as to take into account the incoming real-time information. A heuristic comprising route construction and route improvement is developed. Thirty numerical problems and real applications are provided for demonstration.

關鍵字(中)

★ 時窗限制
★ 中國信差問題
★ 車輛途程問題
★ 即時性

關鍵字(英)

★ Time Windows Constraints
★ Vehicle Routing Problem
★ Chinese Postman Problem
★ Real Time

論文目次

摘要................................................................................................................................I
Abstract....................................................................................................................... II
目錄..............................................................................................................................VI
圖目錄.......................................................................................................................VIII
表目錄...........................................................................................................................X
第一章緒論................................................................................................................1
1.1 研究背景與動機.............................................................................................1
1.2 研究目的.........................................................................................................2
1.3 研究範圍與假設.............................................................................................2
1.3.1 研究內容..............................................................................................3
1.3.2 研究假設..............................................................................................3
1.4 研究內容與流程.............................................................................................5
第二章文獻回顧........................................................................................................8
2.1 巡邏勤務與巡邏方式.....................................................................................8
2.1.1 巡邏勤務..............................................................................................8
2.2 車輛途程問題與相關問題...........................................................................10
2.2.1 時窗限制車輛途程問題....................................................................11
2.2.2 時窗限制車輛途程問題之求解方法................................................11
2.2.3 含依時性旅行成本之即時車輛途程問題........................................16
2.2.4 小結....................................................................................................17
2.3 中國信差問題...............................................................................................17
2.3.1 中國信差問題之分類........................................................................17
2.3.2 完全方向性之中國信差問題............................................................19
2.3.3 節線途程問題轉換成節點途程問題................................................26
2.3.4 小結....................................................................................................32
第三章模型建構......................................................................................................33
3.1 節點途程問題模型建構...............................................................................33
3.1.1 模型假設............................................................................................34
3.1.2 符號說明............................................................................................35
3.1.3 數學模型............................................................................................36
3.1.4 巡邏情境分析....................................................................................38
3.2 節線途程問題...............................................................................................40
3.2.1 模型假設............................................................................................40
3.2.2 符號說明............................................................................................41
3.2.3 數學模型............................................................................................43
3.2.4 對應轉換............................................................................................45
第四章求解演算法..................................................................................................55
4.1 車輛途程問題求解方法...............................................................................55
4.1.1 依時性旅行時間................................................................................55
4.1.2 時空網路與臨界點............................................................................56
4.2 路線建構.......................................................................................................57
4.3 综和求解流程...............................................................................................59
4.4 節線途程問題求解流程...............................................................................61
第五章範例測試與分析..........................................................................................63
5.1 節點途程問題之範例測試...........................................................................63
5.1.1 範例題庫的建立................................................................................63
5.1.2 範例(1)測試的結果...........................................................................65
5.1.3 線上巡邏車數對平均反應時間之影響.............................................69
5.1.4 測試問題大小與求解時間之關係....................................................71
5.1.5 小結....................................................................................................72
5.2 實務運作資料與模型求解結果之比較......................................................73
5.3 節線問題之數例分析...................................................................................78
第六章結論與建議..................................................................................................82
6.1 結論...............................................................................................................82
6.2 建議...............................................................................................................83
參考文獻......................................................................................................................86
附錄一說明溫玉彬(2001)時窗限制下之中國信差問題.......................................90
附錄二詳細資料......................................................................................................93
附錄三針對無方向性路段後續研究方向.............................................................99
附錄四針對即時案件處理以及VRP 與實際路網之轉換.................................102

參考文獻

1. 蕭玉文，2006，警察勤務實用論，台灣警察專科學校，pp. 99-105。
2. 鄭文竹，2003，警察勤務，中央警察大學，pp. 119-148。
3. 小崛旭，1976，外勤警察全書，立花書局，pp. 33。
4. 溫玉彬，2001，(指導教授：王小璠)，時窗限制下之中國郵差問題，國立清華大學工業工程與工程管理學系碩士論文，新竹。
5. 楊廣益，1992，(指導教授：李治綱)，單行道系統網路設計模式之研究，國立成功大學交通管理科學研究所碩士論文，台南。
6. 劉建宏，2005，(指導教授：陳惠國)，含時窗限制式卡車與拖車途程問題之研究，國立中央大學土木工程研究所碩士論文，中壢。
7. 廖慧凱，2006，(指導教授：陳惠國)，道路災害搶修與緊急物流配送問題之探討，國立中央大學土木工程研究所碩士論文，中壢。
8. 池昆霖，2006，(指導教授：陳惠國)，區位途程與易腐性商品排程之研究，國立中央大學土木工程研究所碩士論文，中壢。
9. Assad, A., Pearn, W. and Golden, B., 1985, “The Capacitated Chinese Postman Problem: Lower Bounds and Solvable Case,” MS/S Working Paper 85-032, University of Maryland.
10. Aminu, U.F. and Eglese, R.W., 2006, “A Constraint Programming Approach to the Chinese Postman Problem with Time Windows,” Computers and Operations Research, 33, pp. 3423-3431.
11. Beltrami, E., and Bodin, L., 1974, “Network and Vehicle Routing for Municipal Waste Collection,” Networks, Vol. 4(1), pp. 65-94
12. Braysy, O. and Gendreau, M., 2005a, “Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithm,” Transportation Science, Vol. 39, No.1, pp. 104-118.
13. Braysy, O. and Gendreau, M., 2005b, “Vehicle Routing Problem with Time Windows, Part II: Metaheuristics,” Transportation Science, Vol. 39, No.1, pp. 119-139.
14. Bodin, L., Golden, B., Assad, A. and Ball M., 1983, “Routing and Scheduling of Vehicles and Crews,” Computers and Operations Research, Vol. 10, pp. 63-211
15. Chen, H.K., Hsueh, C.F., and Chang, M.S., 2006, “The Real-time Time-dependent Vehicle Routing Problem,” Transportation Research Part E, Vol. 42, pp. 383-408.
16. Christofides, N., 1973, “The Optimum Traversal of a Graph,” Omega Vol. 1, pp.719-732.
17. Dror, M. 2000, Arc Routing: Theory, Solutions and applications, Boston: Kluwer Academic Publishers.
18. Edmonds, J., and E. L. Johnson, 1973, “Matching, Euler Tours and the Chinese Postman,” Mathematical Programming, Vol. 5, pp. 88-124.
19. Euler, L. (J.R. Newman, ED.), 1953, “Leonhard Euler and the Koenigsberg Bridges,” American Scientist, Vol. 189, pp. 66-70.
20. Fisher, M. and Jaikumar, R. 1981, “A Generalized Assignment Heuristic for Vehicle Routing,” Networks, Vol. 11, pp.109-124.
21. Gendreau, M. and Laporte, G., 1995, “Arc Routing Problems, Part I: The Chinese Postman Problem,” Operations Research, Vol. 43, No.2, pp. 231.
22. Gillett, B. and Miller, L., 1974, “A Heuristic Algorithm for the Vehicle Dispatch Problem,” Operations Research, Vol. 22, pp. 340-349.
23. Golden, B. and Wong, R. T., 1981, “Capacitated Arc Routing Problems,” Network, Vol. 11, pp. 305-315.
24. Golden, B., DeArmon J. S. and Baker, E. K., 1983, “Computational Experiments with Algorithms for a Class of Routing Problems,” Computers and Operations Research. 10, pp. 47-59.
25. Guan, M., 1962, “Graphic Programming Using Odd and Even Points,” Chinese Mathematics, Vol. 1, pp. 273-277.
26. Guan, M. 1984a, “A Survey of the Chinese Postman Problem,” Journal of Mathematical Research and Exposition, Vol. 4, pp. 113-119 (in Chinese).
27. Guan, M. 1984b, “On the Windy Postman Problem,” Discrete Mathematics Vol. 6, pp. 657-664.
28. Hsueh, C.F., Chen H.K., and Chou, H.W., 2007, Vehicle Routing for Relief Logistics in Natural Disasters, Working Paper at National Central University, Jungli, Taiwan.
29. James, Q. and Wilson O. W., Varieties of Police Behavior, (New York：Atheneum, 1993, pp. 1-27.
30. Lin, S., Kernighan B., 1973. “An Effective Heuristic Algorithm for the Traveling Salesman Problem,” Operations Research, 21, pp. 498-516.
31. Lin, Y., and Zhao Y., 1988, “A New Algorithm for the Directed Chinese Postman Problem,” Computers and Operations Research, 15(6), pp. 577-584.
32. Mole, R.H. and Jameson, S.R., 1976, “A Sequential Route-Building Algorithm Employing a Generalised Savings Criterion,” Operational Research Society Vol. 27, pp. 503-527.
33. Pearn, W-L, Assad, A, Golden, B. L. 1987, “Transforming Arc Routing into Node Routing Problems,” Computers and Operations Research Vol. 14(4), 285-288.
34. Potvin, J. Y., Rousseau J. M., 1995, “An Exchange Heuristic for Routing Problems with Time Windows,” Journal of the Operational Research Society, 46, 1433-1446.
35. Potvin, J.Y., Kervahut, T., Garcia, B.L., and Rousseau, J.M., 1996, “The Vehicle Routing Problem with Time Windows Part I: Tabu Search,” INFORMS Journal on Computing, Vol. 8, No.2, pp. 158-164.
36. Or, I., 1976, Traveling Salesman-Type Combinatorial Problems and Their Relation to the Logistics of Blood Banking. Ph.D. Thesis, Department of Industrial Engineering and Management Science, Northwestern University, Evanston, IL., USA.
37. Samuel Walker, 1994, Sense and Nonsense about Crime and Drugs, third edition. , Wadsworth Publishing Company, California, pp.134.
38. Solomon, M. M., 1986. “On the Worst-case Performance of Some Heuristics for the Vehicle Routing and Scheduling Problem with Time Windows Constraints,” Networks, Vol. 16, pp. 161-174.
39. Solomon, M. M., 1987. “Algorithm for the Vehicle Routing and Scheduling Problems with Time Windows Constraint,” Operations Research, Vol. 35, pp. 254-265.
40. Solomon, M. M., J. Desrosiers., 1988. “Time Windows Constrained Routing and Scheduling Problems,” Transportation Science, Vol. 22, pp. 1-13.
41. Stern, H. and Dror, M., 1979, “Routing Electric Meter Readers,” Computers and Operations Research. Vol. 6, pp. 209-223.
42. Wilson, O. W. and McLaren, Roy C., 1997, Police Administration, Fourth Edition, pp. 320-321, Mcgraw Hill, New York.

指導教授

陳惠國(Huey-Kuo Chen)

審核日期

2007-7-23

推文