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