IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v35y2023i6p1286-1307.html

The Hot Spot Coverage Patrol Problem: Formulations and Solution Approaches

Author

Listed:
  • Yuchen Luo

    (Advanced Analytics Group, Bain & Company, Boston, Massachusetts 02116)

  • Bruce Golden

    (Robert H. Smith School of Business, University of Maryland, College Park, Maryland 20742)

  • Rui Zhang

    (Leeds School of Business, University of Colorado Boulder, Boulder, Colorado 80309)

Abstract

When designing a patrol route, it is often necessary to pay more attention to locations with high crime rates. In this paper, we study a patrol routing problem for a fleet of patrol cars patrolling a region with a high-crime neighborhood (HCN) consisting of multiple hot spots. Considering the disorder and chaos in the HCN, at least one patrol car is required in the HCN at any given time during the patrol. We call this routing problem the hot spot coverage patrol problem (HSCPP). In the HSCPP, the importance of a patrol location is quantified by a prize, and the prize is collected if a patrol car visits the location. Our objective is to maximize the sum of prizes collected by the patrol cars, obeying all operational requirements. We propose mathematical formulations and develop several solution approaches for the HSCPP. The global approach consists of finding the routing solution for all patrol cars with a single integer programming (IP) formulation. The partition approach involves first partitioning the region geographically and solving the routing problem in each subregion with two IP formulations. Next, we strengthen the partition approach by developing a column generation (CG) approach in which the initial columns of the CG approach are the solutions generated from the partition approach. We conduct a detailed computational case study using instances based on real crime data from Montgomery County, Maryland. To further understand the computational tractability of our solution approaches, we also perform a sensitivity analysis using synthetic instances under various scenarios.

Suggested Citation

  • Yuchen Luo & Bruce Golden & Rui Zhang, 2023. "The Hot Spot Coverage Patrol Problem: Formulations and Solution Approaches," INFORMS Journal on Computing, INFORMS, vol. 35(6), pages 1286-1307, November.
    • Handle: RePEc:inm:orijoc:v:35:y:2023:i:6:p:1286-1307
    DOI: 10.1287/ijoc.2022.0192
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2022.0192
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2022.0192?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. P. Matl & R. F. Hartl & T. Vidal, 2018. "Workload Equity in Vehicle Routing Problems: A Survey and Analysis," Transportation Science, INFORMS, vol. 52(2), pages 239-260, March.
    2. Camacho-Collados, M. & Liberatore, F. & Angulo, J.M., 2015. "A multi-criteria Police Districting Problem for the efficient and effective design of patrol sector," European Journal of Operational Research, Elsevier, vol. 246(2), pages 674-684.
    3. Dewil, R. & Vansteenwegen, P. & Cattrysse, D. & Van Oudheusden, D., 2015. "A minimum cost network flow model for the maximum covering and patrol routing problem," European Journal of Operational Research, Elsevier, vol. 247(1), pages 27-36.
    4. Timothy J. Surendonk & Paul A. Chircop, 2020. "On the computational complexity of the patrol boat scheduling problem with complete coverage," Naval Research Logistics (NRL), John Wiley & Sons, vol. 67(4), pages 289-299, June.
    5. Anthony A. Braga & Brandon Turchan & Andrew V. Papachristos & David M. Hureau, 2019. "Hot spots policing of small geographic areas effects on crime," Campbell Systematic Reviews, John Wiley & Sons, vol. 15(3), September.
    6. A. Mor & M. G. Speranza, 2022. "Vehicle routing problems over time: a survey," Annals of Operations Research, Springer, vol. 314(1), pages 255-275, July.
    7. Paul A. Chircop & Timothy J. Surendonk & Menkes H. L. van den Briel & Toby Walsh, 2022. "On routing and scheduling a fleet of resource-constrained vessels to provide ongoing continuous patrol coverage," Annals of Operations Research, Springer, vol. 312(2), pages 723-760, May.
    8. Marielle Christiansen & Kjetil Fagerholt & David Ronen, 2004. "Ship Routing and Scheduling: Status and Perspectives," Transportation Science, INFORMS, vol. 38(1), pages 1-18, February.
    9. Tilk, Christian & Rothenbächer, Ann-Kathrin & Gschwind, Timo & Irnich, Stefan, 2017. "Asymmetry matters: Dynamic half-way points in bidirectional labeling for solving shortest path problems with resource constraints faster," European Journal of Operational Research, Elsevier, vol. 261(2), pages 530-539.
    10. Keskin, Burcu B. & Li, Shirley (Rong) & Steil, Dana & Spiller, Sarah, 2012. "Analysis of an integrated maximum covering and patrol routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(1), pages 215-232.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Paul A. Chircop & Timothy J. Surendonk & Menkes H. L. van den Briel & Toby Walsh, 2022. "On routing and scheduling a fleet of resource-constrained vessels to provide ongoing continuous patrol coverage," Annals of Operations Research, Springer, vol. 312(2), pages 723-760, May.
    2. Sukanya Samanta & Goutam Sen & Soumya Kanti Ghosh, 2022. "A literature review on police patrolling problems," Annals of Operations Research, Springer, vol. 316(2), pages 1063-1106, September.
    3. Xiuqiao Sun & Jian Wang & Weitiao Wu & Wenjia Liu, 2018. "Genetic Algorithm for Optimizing Routing Design and Fleet Allocation of Freeway Service Overlapping Patrol," Sustainability, MDPI, vol. 10(11), pages 1-15, November.
    4. Archetti, C. & Coelho, L.C. & Speranza, M.G. & Vansteenwegen, P., 2026. "Beyond fifty years of vehicle routing: Insights into the history and the future," European Journal of Operational Research, Elsevier, vol. 330(2), pages 355-372.
    5. Chen, Xinyuan & Wu, Shining & Liu, Yannick & Wu, Weiwei & Wang, Shuaian, 2022. "A patrol routing problem for maritime Crime-Fighting," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 168(C).
    6. Freeman, Nickolas K. & Keskin, Burcu B. & Çapar, İbrahim, 2018. "Attractive orienteering problem with proximity and timing interactions," European Journal of Operational Research, Elsevier, vol. 266(1), pages 354-370.
    7. Timothy J. Surendonk & Paul A. Chircop, 2020. "On the computational complexity of the patrol boat scheduling problem with complete coverage," Naval Research Logistics (NRL), John Wiley & Sons, vol. 67(4), pages 289-299, June.
    8. Marjolein Aerts-Veenstra & Marilène Cherkesly & Timo Gschwind, 2024. "A Unified Branch-Price-and-Cut Algorithm for Multicompartment Pickup and Delivery Problems," Transportation Science, INFORMS, vol. 58(5), pages 1121-1142, September.
    9. Wang, Shuaian & Meng, Qiang, 2012. "Liner ship route schedule design with sea contingency time and port time uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 46(5), pages 615-633.
    10. Peng, Xiaoshuai & Zhang, Lele & Thompson, Russell G. & Wang, Kangzhou, 2023. "A three-phase heuristic for last-mile delivery with spatial-temporal consolidation and delivery options," International Journal of Production Economics, Elsevier, vol. 266(C).
    11. Hennig, F. & Nygreen, B. & Christiansen, M. & Fagerholt, K. & Furman, K.C. & Song, J. & Kocis, G.R. & Warrick, P.H., 2012. "Maritime crude oil transportation – A split pickup and split delivery problem," European Journal of Operational Research, Elsevier, vol. 218(3), pages 764-774.
    12. Wu, Lingxiao & Pan, Kai & Wang, Shuaian & Yang, Dong, 2018. "Bulk ship scheduling in industrial shipping with stochastic backhaul canvassing demand," Transportation Research Part B: Methodological, Elsevier, vol. 117(PA), pages 117-136.
    13. Meng, Qiang & Lee, Chung-Yee, 2016. "Liner container assignment model with transit-time-sensitive container shipment demand and its applicationsAuthor-Name: Wang, Shuaian," Transportation Research Part B: Methodological, Elsevier, vol. 90(C), pages 135-155.
    14. Elin Halvorsen-Weare & Kjetil Fagerholt, 2013. "Routing and scheduling in a liquefied natural gas shipping problem with inventory and berth constraints," Annals of Operations Research, Springer, vol. 203(1), pages 167-186, March.
    15. Mutlu, Fatih & Msakni, Mohamed K. & Yildiz, Hakan & Sönmez, Erkut & Pokharel, Shaligram, 2016. "A comprehensive annual delivery program for upstream liquefied natural gas supply chain," European Journal of Operational Research, Elsevier, vol. 250(1), pages 120-130.
    16. Edwin M. Kataka & Thomas O Olwal & Karim Djouani & Prosper Z Sotenga, 2026. "Reinforcement Learning-Based Resource Allocation for Smart Vehicular Networks: A Review," Telecommunication Systems: Modelling, Analysis, Design and Management, Springer, vol. 89(1), pages 1-87, March.
    17. Agra, Agostinho & Christiansen, Marielle & Delgado, Alexandrino & Simonetti, Luidi, 2014. "Hybrid heuristics for a short sea inventory routing problem," European Journal of Operational Research, Elsevier, vol. 236(3), pages 924-935.
    18. Shuaian Wang & Dan Zhuge & Lu Zhen & Chung-Yee Lee, 2021. "Liner Shipping Service Planning Under Sulfur Emission Regulations," Transportation Science, INFORMS, vol. 55(2), pages 491-509, March.
    19. Victoria A. Sytsma, 2024. "Vulnerable Populations, Crime, and a Social Justice and Social Impact Agenda: Lessons for Crime Prevention," The ANNALS of the American Academy of Political and Social Science, , vol. 714(1), pages 40-55, July.
    20. Axel Parmentier & Rafael Martinelli & Thibaut Vidal, 2023. "Electric Vehicle Fleets: Scalable Route and Recharge Scheduling Through Column Generation," Transportation Science, INFORMS, vol. 57(3), pages 631-646, May.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:orijoc:v:35:y:2023:i:6:p:1286-1307. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.