
系統識別號 
U00262407201817390300 
論文名稱(中文) 
道路網路上多巡邏路線的最佳化探索演算法 
論文名稱(英文) 
Discovery of Multiple Patrolling Paths on Road Networks 
校院名稱 
成功大學 
系所名稱(中) 
資訊工程學系 
系所名稱(英) 
Institute of Computer Science and Information Engineering 
學年度 
106 
學期 
2 
出版年 
107 
研究生(中文) 
黃昊慈 
研究生(英文) 
HaoTzu Huang 
學號 
P76054347 
學位類別 
碩士 
語文別 
英文 
論文頁數 
39頁 
口試委員 
指導教授莊坤達 口試委員謝孫源 口試委員高宏宇 口試委員李政德

中文關鍵字 
巡邏問題
多路徑規劃
子模

英文關鍵字 
Patrolling problem
Multiple Path planning
Submodularity

學科別分類 

中文摘要 
巡邏路徑規劃是各種應用領域中經常考慮的重要問題，例如城市安全警察巡邏、公共衛 生防疫、公共交通路線設計和自動機器人監測等。在已知道路網路和任務點的前提下，巡邏 問題是找到一組沿著這些任務點行進的路徑，以實現監視或保護該區域的目的。在滿足路徑 數量和長度限制的前提下，多巡邏路線(MMP)是巡邏問題的概括。在同時考慮POI的覆蓋 率並依照應用的需求下，MMP的目標函數使用子模函數來建模。由於MMP有計算上有高複 雜度，我們為了有效率的解決這個問題提出的解決方案就是多巡邏路線的最佳化探索演算法 (MPPD)，為對應不同應用的需求，演算法是由兩種方法組成。CandidateSelection分為 兩個階段，即candidategeneration和pathselection。在candidategeneration的階段，我們直 觀的改良了幾個經典的最短路徑演算法來生成優良的路徑候選人。我們採用貪婪演算法從前 一階段的候選中選擇路徑。由於我們的問題有子模的特性，所以我們透過引入CELF優化， 在維持一定品質的前提下加速了選擇路徑的過程。SeedExpansion利用期望最大化(EM) 法來找出作為路徑延展的最佳起點們。CandidateSelection提供了更高品質的解決方案，卻 也花費了更多執行時間，而SeedExpansion則提供了可以在較短時間維持一定品質的選擇方案。

英文摘要 
The patrolling path planning is an important issue frequently considered in the application of various domains, such as police patrolling in urban security, epidemic prevention in public health, route design for public transportation and automatic robot guardian. Given a road network and a set of task points, the patrolling problem is to find a set of paths that traveling along the points to achieve the purpose of monitoring or guarding the territory. The multiple patrolling paths (MMP) is a generalization of patrolling problems satisfying constraints of path number and length, of which the objective is modeling the POI coverage and application dependent requirement as a submodular function.
To efficiently deal with the high computational complexity of MMP Problem, we pro pose a solution, Multiple Patrolling Path Discovery(MPPD) consisting of two methods to deal with diverse applications with different consideration. CandidateSelection is divided into two phases, namely candidategeneration and pathselection. In the phase of candidategeneration, we implement a couple of heuristic methods for generating optimal path candidates by adopt ing several classical shortest path algorithms. Using paths generated in the previous phase as candidates, we use a Greedy algorithm to select paths. By introducing CELF optimization, we accelerate the process of pathselection with the guarantee of performance owing to the property of submodularity. Utilizing the ExpectationMaximization (EM) Algorithm, Seed Expansion addresses the problem by identifying the optimal seeds for path expansion. While CandidateSelection provides the solution with higher revenue along with execution time, Seed Expansion efficiently generates a path set maintaining in a certain level of quality.

論文目次 
中文摘要 ...... i
Abstract..... ii
Acknowledgment ...... iii
Contents..... iv
ListofTables...... vi
ListofFigures ..... vii
1 Introduction..... 1
2 RelatedWork...... 5
2.1 Routing Problem(RP).... 6
2.2 PathCover(PC) ..... 9
2.3 RouteRecommendation(RR) .... 10
3 Problem Formulation.... 12
3.1 ProblemStatement.... 12
3.2 Modeling Submodularity of Multiple Paths for Personal Requirement . . . . . . 13
3.3 FrameworkOverview..... 15
4 MultiplePatrollingPathsDiscovery(MPPD)... 16
4.1 CandidateSelection.... 16
4.1.1 CandidateGeneration .... 16
4.1.2 PathSelection..... 18
4.2 SeedExpansion.... 19
4.2.1 SeedIdentification .... 19
4.2.2 PathExpansion.... 23
5 ExperimentStudy...... 24
5.1 ExperimentalSetup.... 24
5.1.1 DataSetsDescription .... 24
5.1.2 Algorithms .... 26
5.2 ExperimentalResult ..... 27
6 Conclusions ..... 35
Bibliography ...... 36

參考文獻 
[1] A. Machado, G. Ramalho, J. Zucker, and A. Drogoul, “Multiagent patrolling: An empirical analysis of alternative architectures,” in MultiAgentBased Simulation, Third International Workshop, MABS 2002, Bologna, Italy, July 1516, 2002, Revised Papers, 2002, pp. 155–170.
[2] Y. Chevaleyre, “Theoretical analysis of the multiagent patrolling problem,” in 2004 IEEE/WIC/ACM International Conference on Intelligent Agent Technology (IAT 2004), 2024 September 2004, Beijing, China, 2004, pp. 302–308.
[3] H. Chen, T. Cheng, and J. ShaweTaylor, “A balanced route design for minmax multiple depot rural postman problem (MMMDRPP): a police patrolling case,” International Journal of Geographical Information Science, vol. 32, no. 1, pp. 169–190, 2018.
[4] W. Ghadiry, J. Habibi, A. G. Aghdam, and Y. Zhang, “Nonprespecified starting depot formulations for minimumdistance trajectory optimization in patrolling problem,” Journal of Intelligent and Robotic Systems, vol. 87, no. 34, pp. 699–710, 2017.
[5] S. S. Chawathe, “Organizing hotspot police patrol routes,” in IEEE International Conference on Intelligence and Security Informatics, ISI 2007, New Brunswick, New Jersey, USA, May 2324, 2007, Proceedings, 2007, pp. 79–86.
[6] H. Chuangpishit, J. Czyzowicz, L. Gasieniec, K. Georgiou, T. Jurdzinski, and E. Kranakis, “Patrolling a path connecting a set of points with unbalanced frequencies of visits,” in SOFSEM 2018: Theory and Practice of Computer Science  44th International Conference on Current Trends in Theory and Practice of Computer Science, Krems, Austria, January 29  February 2, 2018, Proceedings, 2018, pp. 367–380.
[7] Y. Zeng, X. Chen, X. Cao, S. Qin, M. Cavazza, and Y. Xiang, “Optimal route search with the coverage of users’ preferences,” in Proceedings of the TwentyFourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 2531, 2015, 2015, pp. 2118–2124.
36
[8] H. Liang and K. Wang, “Topk route search through submodularity modeling of recurrent POI features,” in The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval, SIGIR 2018, Ann Arbor, MI, USA, July 0812, 2018, 2018, pp. 545–554.
[9] F. Pasqualetti, J. W. Durham, and F. Bullo, “Cooperative patrolling via weighted tours: Performance analysis and distributed algorithms,” IEEE Trans. Robotics, vol. 28, no. 5, pp. 1181–1188, 2012.
[10] H. Chen, T. Cheng, and S. C. Wise, “Developing an online cooperative police patrol routing strategy,” Computers, Environment and Urban Systems, vol. 62, pp. 19–29, 2017.
[11] O. Y. Xian, M. Chitre, and D. Rus, “An approximate bus route planning algorithm,” in 2013 IEEE Symposium on Computational Intelligence in Vehicles and Transportation Systems, CIVTS 2013, Singapore, April 1619, 2013, 2013, pp. 16–24.
[12] M. Zhao, T. W. S. Chow, and K. F. Tsang, “Vehicle route planning for logistics network optimization via multiple spanning tree,” in 14th IEEE International Conference on Industrial Informatics, INDIN 2016, Poitiers, France, July 1921, 2016, 2016, pp. 800–805.
[13] A. Gunawan, H. C. Lau, and P. Vansteenwegen, “Orienteering problem: A survey of recent variants, solution approaches and applications,” European Journal of Operational Research, vol. 255, no. 2, pp. 315–332, 2016.
[14] Y. Lu and C. Shahabi, “An arc orienteering algorithm to find the most scenic path on a largescale road network,” in Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems, Bellevue, WA, USA, November 36, 2015, 2015, pp. 46:1–46:10.
[15] R. Rizzi, A. I. Tomescu, and V. Ma ̈kinen, “On the complexity of minimum path cover with subpath constraints for multiassembly,” BMC Bioinformatics, vol. 15, no. S9, p. S5, 2014.
[16] Y. Tao, C. Sheng, and J. Pei, “On kskip shortest paths,” in Proceedings of the ACM SIG MOD International Conference on Management of Data, SIGMOD 2011, Athens, Greece, June 1216, 2011, 2011, pp. 421–432.
37
[17] S. Funke, A. Nusser, and S. Storandt, “On kpath covers and their applications,” VLDB J., vol. 25, no. 1, pp. 103–123, 2016.
[18] B. Bresar, F. Kardos, J. Katrenic, and G. Semanisin, “Minimum kpath vertex cover,” Discrete Applied Mathematics, vol. 159, no. 12, pp. 1189–1195, 2011.
[19] X. Li, Z. Zhang, and X. Huang, “Approximation algorithms for minimum (weight) connected kpath vertex cover,” Discrete Applied Mathematics, vol. 205, pp. 101–108, 2016.
[20] S. Funke and S. Storandt, “Personalized route planning in road networks,” in Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems, Bellevue, WA, USA, November 36, 2015, 2015, pp. 45:1–45:10.
[21] X. Cao, L. Chen, G. Cong, J. Guan, N. Phan, and X. Xiao, “KORS: keywordaware optimal route search system,” in 29th IEEE International Conference on Data Engineering, ICDE 2013, Brisbane, Australia, April 812, 2013, 2013, pp. 1340–1343.
[22] A. Gionis, T. Lappas, K. Pelechrinis, and E. Terzi, “Customized tour recommendations in urban areas,” in Seventh ACM International Conference on Web Search and Data Mining, WSDM 2014, New York, NY, USA, February 2428, 2014, 2014, pp. 313–322.
[23] E. H. Lu, C. Chen, and V. S. Tseng, “Personalized trip recommendation with multiple constraints by mining user checkin behaviors,” in SIGSPATIAL 2012 International Conference on Advances in Geographic Information Systems (formerly known as GIS), SIGSPATIAL’12, Redondo Beach, CA, USA, November 79, 2012, 2012, pp. 209–218.
[24] W. Zhang and J. Wang, “Location and time aware social collaborative retrieval for new successive pointofinterest recommendation,” in Proceedings of the 24th ACM International Conference on Information and Knowledge Management, CIKM 2015, Melbourne, VIC, Australia, October 19  23, 2015, 2015, pp. 1221–1230.
[25] C. Zhang, H. Liang, and K. Wang, “Trip recommendation meets realworld constraints: POI availability, diversity, and traveling time uncertainty,” ACM Trans. Inf. Syst., vol. 35, no. 1, pp. 5:1–5:28, 2016.
[26] K. H. Lim, J. Chan, S. Karunasekera, and C. Leckie, “Personalized itinerary recommendation with queuing time awareness,” in Proceedings of the 40th International ACM SI
38
GIR Conference on Research and Development in Information Retrieval, Shinjuku, Tokyo, Japan, August 711, 2017, 2017, pp. 325–334.
[27] C. Chekuri and M. P ́al, “A recursive greedy algorithm for walks in directed graphs,” in
46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2325 October 2005, Pittsburgh, PA, USA, Proceedings, 2005, pp. 245–253.
[28] G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher, “An analysis of approximations for maximizing submodular set functions  I,” Math. Program., vol. 14, no. 1, pp. 265–294, 1978.
[29] J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. M. VanBriesen, and N. S. Glance, “Costeffective outbreak detection in networks,” in Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Jose, California, USA, August 1215, 2007, 2007, pp. 420–429.

論文全文使用權限 
同意授權校內瀏覽/列印電子全文服務，於20180815起公開。同意授權校外瀏覽/列印電子全文服務，於20180815起公開。 


