Abstract: By introducing the ideas of k-means clustering,genetic algorithm andminimum vertex cover,a global optimal police patrol car configuration and deployment for the department of traffic police is proposed.In this setting,k-meansclustering is used to generate N center points based on the density of the intersections and completed the police patrol car initialization configuration.Thenthe genetic algorithm is adopted to receive a global optimal patrol route as reference and finally the Dijkstra algorithm is employed to calculate the patrol deployment routes.Meanwhile,the calculation methods of the shortest path is given between any two intersections and the location of police cars at anymoments,as well as regional coverage and travel time of the N police patrol cars.Toverify its validity,sensitivity analysis on the budget,the number of patrol cars is performed to identify the possible solutions.Experimental results show this method is robust and can effectively improve the effectiveness of patrol deployment and the routes kept varied with good property of concealment.

Key words: regional coverage, k-means algorithm, scheduling, Dijkstra algorithm, genetic algorithm