Optimizing patrolling routes using Maximum Benefit k-Chinese Postman Problem
Files
Publication or External Link
Date
Authors
Advisor
Citation
DRUM DOI
Abstract
Providing security and safety in urban areas is of paramount importance. The objective of this study is to find several routes for police patrolling vehicles in order to maximize the benefit based on the historical data of a given area such as crime rate. To this end, we first formulate the problem as a maximum benefit k-Chinese Postman Problem and find the optimal solutions for small size networks. We then employ the tabu search metaheuristic method to develop an algorithm that finds close to optimal solutions for the corresponding networks. A comparison between the results of the mathematical model and the metaheuristic algorithm reveals that the results are in a good agreement in terms of accuracy and the quality. The proposed algorithm is then used to find solutions for the city of College Park.