Applying min-max k postmen problems to the routing of security guards
Loading...
Date
Authors
Willemse, Elias J.
Joubert, Johan W.
Journal Title
Journal ISSN
Volume Title
Publisher
© 2012 Palgrave Macmillan, a division of Macmillan Publishers Limited. .
Abstract
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.
Description
Keywords
Arc routing, Chinese postman problem, Rural postman problem, Tabu search algorithm, Security guard routing, Logistics
Sustainable Development Goals
Citation
Willemse, EJ & Joubert, JW 2012, 'Applying min-max k postmen problems to the routing of security guards', Journal of the Operational Research Society, vol. 63, no. 2, pp. 245-260.