現行警察執行巡邏勤務之路線大多以最近鄰點法串聯巡邏箱簽到的定點巡訪方式進行，其路線大多固定可預期，且因警力有限而無法同時於多處巡邏，導致見警率不彰，治安維護效果有限。隨著人工智慧和物聯網相關技術的成熟，佈署多輛無人巡邏車搭配路徑規劃，可大幅改善上述目前警力巡邏之缺點。
本研究探討之巡邏途程問題旨在如何以最小化車隊總巡邏時間，規劃多輛無人車來巡邏某些具巡邏需求的路段。由於同一路段的正、反向(類似順、逆風)巡邏方式之成本可能不同，因此將代表巡邏範圍之網路圖稱為風向圖(Windy Graph)，而必須經過某些路段的途程規劃問題屬於鄉村型郵差途程(Rural Postman)問題，因此本研究為「風向鄉村型多郵差途程問題」。有別於過往文獻大多將巡邏路段視為無向，本研究將巡邏需求設置在有方向性的節線上，進一步可處理平行節線與單行道之一般網路圖，更能貼近現實情況。
文獻針對風向鄉村型多郵差問題大多以加入排除子迴圈限制式的分支切割演算法(Branch-and-Cut，B&C)求解，在求解過程中一遇到獨立子迴圈即產生新限制式排除之，但此方式常因持續加入的限制式過多而導致求解效率不佳。本研究則首先基於層空網路(Level-space Network)發展一個不用考慮子迴圈的混整數規劃模式，接著保留必巡之節線及相關節點，將各組上述保留之兩節點間在原網路之最短路徑濃縮成為新的節線，以此當成預處理機制來建構一個新的「限縮網路」，再進一步建構其對應的層空網路，於其上實作對應的整數規劃模式求解。
在實際進行數值測試後，我們發現整數規劃模式的求解作法將耗時過長，無法處理中或大型之網路規模，因此本研究將必須巡邏之節線編碼為一組解，利用貪婪式演算法、基因演算法、以及區域搜尋法等啟發式演算法於上述的限縮網路上求解最小化無人車隊總巡邏時間。此外，本研究亦嘗試將貪婪式演算法之求解結果，分別加入數學規劃模式與其他演算法作為初始解以加速其收斂效果。
本研究嘗試進行較完備的數學規劃模式與演算法的數值測試，在測試過不同規模的隨機網路圖後，我們發現數學規劃模式僅可求解小規模的網路，而貪婪式演算法在極短的時間內即可求得一品質尚可的解，若再以此為初始解輸入區域搜尋法後，實驗發現其求解品質穩定，且整體表現較其他二種演算法為佳，有助於被應用在求解較具規模的實際巡邏途程規劃問題。

With more advanced AI and IoT, unmanned autonomous vehicles can replace partial manpower for patrol routing. Current patrol routing practices usually exploit the nearest first heuristics for visit patrol boxes located in different places. Such routes take a longer time and are more predictable. Here we aim at the design of optimal patrol routes in a systematic way considering travel costs, security requirements, and fair workloads among coordinated unmanned patrol vehicles.
To be more realistic, we consider a windy graph with arcs of different lengths in different directions. This leads to a K windy rural postmen problem. In particular, we seek optimal tours for all the unmanned vehicles such that all required road segments are patrolled with minimum travel costs. We propose two integer program (IP) formulation on a level-space network. The first IP formulation can only deal with small networks. The second IP formulation is conducted on a reduced network, where we only consider the nodes adjacent to the required patrolling arcs and treat a shortest path between any two nodes as an arc in this reduced graph. This second IP formulation can solve larger cases but still cannot deal with practical cases.
We design three fast heuristics on the reduced network: Greedy algorithm, Genetic Algorithm (GA), and Local search (LS). Computational experiments indicate the initial solution obtained by GA and further improved by LS can calculate solutions of satisfactory qualities for larger problems.

張棟(2017年7月3日)。迪拜招募最新機器警察，配面部識別技術及無人機。雷鋒網。取自https://www.leiphone.com/
Aráoz, J., Fernández, E., & Meza, O. (2009). Solving the prize-collecting rural postman problem. European Journal of Operational Research, 196(3), 886-896.
Archetti, C., Feillet, D., Hertz, A., & Speranza, M. G. (2010). The undirected capacitated arc routing problem with profits. Computers & Operations Research, 37(11), 1860-1869.
Archetti, C., Guastaroba, G., & Speranza, M. G. (2014). An ILP-refined tabu search for the directed profitable rural postman problem. Discrete Applied Mathematics, 163, 3-16.
Assad, A. A., Pearn, W. L., & Golden, B. L. (1987). The capacitated Chinese postman problem: Lower bounds and solvable cases. American Journal of Mathematical and Management Sciences, 7(1-2), 63-88.
Baldacci, R., & Maniezzo, V. (2006). Exact methods based on node‐routing formulations for undirected arc‐routing problems. Networks, 47(1), 52-60.
Benavent, E., Corberán, A., Plana, I., & Sanchis, J. M. (2009). Min‐Max K‐vehicles windy rural postman problem. Networks: An International Journal, 54(4), 216-226.
Black, D., Eglese, R., & Wøhlk, S. (2013). The time-dependent prize-collecting arc routing problem. Computers & Operations Research, 40(2), 526-535.
Bodin, L. D., Golden, B. L., Assad, A., & Ball, M. (1983). Routing and scheduling of vehicles and crews: The state of the art. Computers and Operations Research, 10(2), 63-211.
Chang, Y., & Chen, L. (2007). Solve the vehicle routing problem with time windows via a genetic algorithm. Discrete and continuous dynamical systems supplement, 240-249.
Cherkassky, B. V., Goldberg, A. V., & Silverstein, C. (1999). Buckets, heaps, lists, and monotone priority queues. SIAM Journal on Computing, 28(4), 1326-1346.
Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management science, 6(1), 80-91.
Feillet, D., Dejax, P., & Gendreau, M. (2005). The profitable arc tour problem: solution with a branch-and-price algorithm. Transportation Science, 39(4), 539-552.
Fisher, M. L., & Jaikumar, R. (1981). A generalized assignment heuristic for vehicle routing. Networks, 11(2), 109-124.
Foulds, L., Longo, H., & Martins, J. (2015). A compact transformation of arc routing problems into node routing problems. Annals of Operations Research, 226(1), 177-200.
Goldberg, A. V., & Silverstein, C. (1997). Implementations of Dijkstra’s algorithm based on multi-level buckets. In Network optimization (pp. 292-327). Springer, Berlin, Heidelberg.
Grötschel, M., & Win, Z. (1992). A cutting plane algorithm for the windy postman problem. Mathematical Programming, 55(1-3), 339-358.
Guan, M. (1962). Graphic programming using odd and even points. Chinese Math., 1, 237-277.
Hashimoto, H., & Yagiura, M. (2008, March). A path relinking approach with an adaptive mechanism to control parameters for the vehicle routing problem with time windows. In European Conference on Evolutionary Computation in Combinatorial Optimization (pp. 254-265). Springer, Berlin, Heidelberg.
Karakatič, S., & Podgorelec, V. (2015). A survey of genetic algorithms for solving multi depot vehicle routing problem. Applied Soft Computing, 27, 519-532.
Koskosidis, Y. A., Powell, W. B., & Solomon, M. M. (1992). An optimization-based heuristic for vehicle routing and scheduling with soft time window constraints. Transportation science, 26(2), 69-85.
Lenstra, J. K., & Rinnooy Kan, A. H. G. (1976). On general routing problems. Networks, 6(3), 273-280.
Lin, S. (1965). Computer solutions of the traveling salesman problem. Bell System Technical Journal, 44(10), 2245-2269.
Lo, K. M., Yi, W. Y., Wong, P. K., Leung, K. S., Leung, Y., & Mak, S. T. (2018). A genetic algorithm with new local operators for multiple traveling salesman problems. International Journal of Computational Intelligence Systems, 11(1), 692-705.
Malandraki, C., & Daskin, M. S. (1993). The maximum benefit Chinese postman problem and the maximum benefit traveling salesman problem. European Journal of Operational Research, 65(2), 218-234.
Mei-Ko, K. (1962). Graphic programming using odd or even points. Chinese Math., 1, 273-277.
Minieka, E. (1979). The Chinese postman problem for mixed networks. Management Science, 25(7), 643-648.
Moreira, L. M., Oliveira, J. F., Gomes, A. M., & Ferreira, J. S. (2007). Heuristics for a dynamic rural postman problem. Computers & Operations Research, 34(11), 3281-3294.
Orloff, C. S. (1974). A fundamental problem in vehicle routing. Networks, 4(1), 35-64.
Pearn, W. L. (1994). Solvable cases of the k-person Chinese postman problem. Operations Research Letters, 16(4), 241-244.
Pearn, W. L., & Wang, K. H. (2003). On the maximum benefit Chinese postman problem. Omega, 31(4), 269-273.
Potvin, J. Y., Kervahut, T., Garcia, B. L., & Rousseau, J. M. (1996). The vehicle routing problem with time windows part I: tabu search. INFORMS Journal on Computing, 8(2), 158-164.
Reiter, S., & Sherman, G. (1965). Discrete optimizing. Journal of the Society for Industrial and Applied Mathematics, 13(3), 864-889.
Sherman, L. W., & Weisburd, D. (1995). General deterrent effects of police patrol in crime “hot spots”: A randomized, controlled trial. Justice quarterly, 12(4), 625-648.
Taillard, É., Badeau, P., Gendreau, M., Guertin, F., & Potvin, J. Y. (1997). A tabu search heuristic for the vehicle routing problem with soft time windows. Transportation science, 31(2), 170-186.