Applying min-max k postmen problems to the routing of security guards

The most essential and alluring characteristic of a security estate is the estate's ability to provide 24-h security to its residents, of which the continual patrolling of roads and paths is vital. The objective of this paper is to address the lack of sufficient patrol route design procedures b...

Full description

Saved in:
Bibliographic Details
Published in:The Journal of the Operational Research Society 2012-02, Vol.63 (2), p.245-260
Main Authors: Willemse, E J, Joubert, J W
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
arc routing
Arithmetic mean
Business and Management
Chinese postman problem
Crime prevention
Exact sciences and technology
Gated communities
General Paper
General Papers
Ground, air and sea transportation, marine construction
Guards
Heuristic
Heuristics
Letter carriers
Management
Mathematical programming
Operational research and scientific management
Operational research. Management science
Operations research
Operations Research/Decision Theory
Road transportation and traffic
Roads & highways
Routing
rural postman problem
security guard routing
Security guards
Security services
Studies
Taboos
Tabu search
tabu search algorithm
Vehicles
Vertices
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The most essential and alluring characteristic of a security estate is the estate's ability to provide 24-h security to its residents, of which the continual patrolling of roads and paths is vital. The objective of this paper is to address the lack of sufficient patrol route design procedures by presenting a tabu search algorithm capable of generating multiple patrol routes for an estate's security guards. The paper shows that the problem of designing these routes can be modelled as an Arc Routing Problem, specifically as min-max k postmen problems. The algorithm is illustrated with a real problem instance from an estate in Gauteng, South Africa. The patrol routes generated by the algorithm provide a significant improvement in the even patrolling of the road network, and a more balanced work distribution among guards. The algorithm is also tested on several benchmark problems from literature.
ISSN:0160-5682
1476-9360
DOI:10.1057/jors.2011.26