A hybrid spectral clustering simulated annealing algorithm for the street patrol districting problem

Abstract

Abstract Reasonable districting plays an important role in the patrolling process. In this paper, workload attributes are considered, and a mixed integer programming model is developed to solve the street patrol districting problem (SPDP). The improved spectral clustering algorithm named spectral clustering algorithm based on the road network (SCRn) and simulated annealing algorithm (SA) are combined. This results in a hybrid algorithm called SCRn-SA. The SCRn-SA algorithm is tested on small examples and real instances in Zhengzhou, China. The experimental results show that the proposed algorithm is effective for solving SPDP. It has better performance when compared to other advanced algorithms.

Keywords

• Street patrol
• The districting problem
• Road network
• Spectral clustering algorithm
• Simulated annealing algorithm