巡邏車輛途程問題

The Patrol Car Routing Problem

陳思齊(Sz-Chi Chen)

指導教授 ： 陳惠國

國立中央大學/工學院/土木工程學系/碩士(2007年)

摘要

巡邏車輛途程問題(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

參考文獻

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