Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

A Comparison of Local Search Methods for the Multicriteria Police Districting Problem on Graph

Liberatore, F. ORCID: and Camacho-Collados, M. 2016. A Comparison of Local Search Methods for the Multicriteria Police Districting Problem on Graph. Mathematical Problems in Engineering 2016 , pp. 1-13. 10.1155/2016/3690474

[thumbnail of 3690474.pdf] PDF - Published Version
Available under License Creative Commons Attribution.

Download (7MB)


In the current economic climate, law enforcement agencies are facing resource shortages. The effective and efficient use of scarce resources is therefore of the utmost importance to provide a high standard public safety service. Optimization models specifically tailored to the necessity of police agencies can help to ameliorate their use. The Multicriteria Police Districting Problem (MC-PDP) on a graph concerns the definition of sound patrolling sectors in a police district. The objective of this problem is to partition a graph into convex and continuous subsets, while ensuring efficiency and workload balance among the subsets. The model was originally formulated in collaboration with the Spanish National Police Corps. We propose for its solution three local search algorithms: a Simple Hill Climbing, a Steepest Descent Hill Climbing, and a Tabu Search. To improve their diversification capabilities, all the algorithms implement a multistart procedure, initialized by randomized greedy solutions. The algorithms are empirically tested on a case study on the Central District of Madrid. Our experiments show that the solutions identified by the novel Tabu Search outperform the other algorithms. Finally, research guidelines for future developments on the MC-PDP are given.

Item Type: Article
Status: Published
Schools: Computer Science & Informatics
Publisher: Hindawi Publishing Corporation
ISSN: 1024-123X
Date of First Compliant Deposit: 10 January 2020
Date of Acceptance: 6 January 2016
Last Modified: 05 May 2023 01:33

Citation Data

Cited 15 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item Edit Item


Downloads per month over past year

View more statistics