||Discovery of Multiple Patrolling Paths on Road Networks
||Institute of Computer Science and Information Engineering
Multiple Path planning
巡邏路徑規劃是各種應用領域中經常考慮的重要問題，例如城市安全警察巡邏、公共衛 生防疫、公共交通路線設計和自動機器人監測等。在已知道路網路和任務點的前提下，巡邏 問題是找到一組沿著這些任務點行進的路徑，以實現監視或保護該區域的目的。在滿足路徑 數量和長度限制的前提下，多巡邏路線(MMP)是巡邏問題的概括。在同時考慮POI的覆蓋 率並依照應用的需求下，MMP的目標函數使用子模函數來建模。由於MMP有計算上有高複 雜度，我們為了有效率的解決這個問題提出的解決方案就是多巡邏路線的最佳化探索演算法 (MPPD)，為對應不同應用的需求，演算法是由兩種方法組成。Candidate-Selection分為 兩個階段，即candidate-generation和path-selection。在candidate-generation的階段，我們直 觀的改良了幾個經典的最短路徑演算法來生成優良的路徑候選人。我們採用貪婪演算法從前 一階段的候選中選擇路徑。由於我們的問題有子模的特性，所以我們透過引入CELF優化， 在維持一定品質的前提下加速了選擇路徑的過程。Seed-Expansion利用期望最大化(EM) 法來找出作為路徑延展的最佳起點們。Candidate-Selection提供了更高品質的解決方案，卻 也花費了更多執行時間，而Seed-Expansion則提供了可以在較短時間維持一定品質的選擇方案。
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. Candidate-Selection is divided into two phases, namely candidate-generation and path-selection. In the phase of candidate-generation, 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 path-selection with the guarantee of performance owing to the property of submodularity. Utilizing the Expectation-Maximization (EM) Algorithm, Seed- Expansion addresses the problem by identifying the optimal seeds for path expansion. While Candidate-Selection 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
Acknowledgment ...... iii
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 Candidate-Selection.... 16
4.1.1 Candidate-Generation .... 16
4.1.2 Path-Selection..... 18
4.2 Seed-Expansion.... 19
4.2.1 Seed-Identification .... 19
4.2.2 Path-Expansion.... 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
 A. Machado, G. Ramalho, J. Zucker, and A. Drogoul, “Multi-agent patrolling: An empirical analysis of alternative architectures,” in Multi-Agent-Based Simulation, Third International Workshop, MABS 2002, Bologna, Italy, July 15-16, 2002, Revised Papers, 2002, pp. 155–170.
 Y. Chevaleyre, “Theoretical analysis of the multi-agent patrolling problem,” in 2004 IEEE/WIC/ACM International Conference on Intelligent Agent Technology (IAT 2004), 20-24 September 2004, Beijing, China, 2004, pp. 302–308.
 H. Chen, T. Cheng, and J. Shawe-Taylor, “A balanced route design for min-max multiple- depot rural postman problem (MMMDRPP): a police patrolling case,” International Journal of Geographical Information Science, vol. 32, no. 1, pp. 169–190, 2018.
 W. Ghadiry, J. Habibi, A. G. Aghdam, and Y. Zhang, “Non-prespecified starting depot formulations for minimum-distance trajectory optimization in patrolling problem,” Journal of Intelligent and Robotic Systems, vol. 87, no. 3-4, pp. 699–710, 2017.
 S. S. Chawathe, “Organizing hot-spot police patrol routes,” in IEEE International Conference on Intelligence and Security Informatics, ISI 2007, New Brunswick, New Jersey, USA, May 23-24, 2007, Proceedings, 2007, pp. 79–86.
 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.
 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 Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015, 2015, pp. 2118–2124.
 H. Liang and K. Wang, “Top-k 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 08-12, 2018, 2018, pp. 545–554.
 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.
 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.
 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 16-19, 2013, 2013, pp. 16–24.
 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 19-21, 2016, 2016, pp. 800–805.
 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.
 Y. Lu and C. Shahabi, “An arc orienteering algorithm to find the most scenic path on a large-scale road network,” in Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems, Bellevue, WA, USA, November 3-6, 2015, 2015, pp. 46:1–46:10.
 R. Rizzi, A. I. Tomescu, and V. Ma ̈kinen, “On the complexity of minimum path cover with subpath constraints for multi-assembly,” BMC Bioinformatics, vol. 15, no. S-9, p. S5, 2014.
 Y. Tao, C. Sheng, and J. Pei, “On k-skip shortest paths,” in Proceedings of the ACM SIG- MOD International Conference on Management of Data, SIGMOD 2011, Athens, Greece, June 12-16, 2011, 2011, pp. 421–432.
 S. Funke, A. Nusser, and S. Storandt, “On k-path covers and their applications,” VLDB J., vol. 25, no. 1, pp. 103–123, 2016.
 B. Bresar, F. Kardos, J. Katrenic, and G. Semanisin, “Minimum k-path vertex cover,” Discrete Applied Mathematics, vol. 159, no. 12, pp. 1189–1195, 2011.
 X. Li, Z. Zhang, and X. Huang, “Approximation algorithms for minimum (weight) connected k-path vertex cover,” Discrete Applied Mathematics, vol. 205, pp. 101–108, 2016.
 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 3-6, 2015, 2015, pp. 45:1–45:10.
 X. Cao, L. Chen, G. Cong, J. Guan, N. Phan, and X. Xiao, “KORS: keyword-aware optimal route search system,” in 29th IEEE International Conference on Data Engineering, ICDE 2013, Brisbane, Australia, April 8-12, 2013, 2013, pp. 1340–1343.
 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 24-28, 2014, 2014, pp. 313–322.
 E. H. Lu, C. Chen, and V. S. Tseng, “Personalized trip recommendation with multiple constraints by mining user check-in behaviors,” in SIGSPATIAL 2012 International Conference on Advances in Geographic Information Systems (formerly known as GIS), SIGSPATIAL’12, Redondo Beach, CA, USA, November 7-9, 2012, 2012, pp. 209–218.
 W. Zhang and J. Wang, “Location and time aware social collaborative retrieval for new successive point-of-interest 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.
 C. Zhang, H. Liang, and K. Wang, “Trip recommendation meets real-world constraints: POI availability, diversity, and traveling time uncertainty,” ACM Trans. Inf. Syst., vol. 35, no. 1, pp. 5:1–5:28, 2016.
 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-
GIR Conference on Research and Development in Information Retrieval, Shinjuku, Tokyo, Japan, August 7-11, 2017, 2017, pp. 325–334.
 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), 23-25 October 2005, Pittsburgh, PA, USA, Proceedings, 2005, pp. 245–253.
 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.
 J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. M. VanBriesen, and N. S. Glance, “Cost-effective outbreak detection in networks,” in Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Jose, California, USA, August 12-15, 2007, 2007, pp. 420–429.