Bi-criteria dynamic location-routing problem for patrol coverage

Abstract

In this paper, we address the problem of dynamic patrol routing for state troopers for effective coverage of highways. Specifically, a number of state troopers start their routes at temporary stations (TS), patrol critical locations with high crash frequencies, and end their shifts at other (or the same) TS so the starting points for the next period are also optimized. We determine the number of state troopers, their assigned routes, and the locations of the TS where they start and end their routes. The TS are selected from a given set of potential locations. The problem, therefore, is a multi-period dynamic location-routing problem in the context of public service. Our objective is to maximize the critical location coverage benefit while minimizing the costs of TS selections, vehicle utilizations, and routing/travel. The multi-objective nature of the problem is handled using an ɛ-constraint approach. We formulate the problem as a mixed integer linear programming model and solve it using both off-the-shelf optimization software and a custom-built, efficient heuristic algorithm. The heuristic, utilizing the hierarchical structure of the problem, is built on the decomposition of location and routing problems. By allowing routing to start from multiple locations, our model improves the coverage by as much as 12% compared with the single-depot coverage model.

Keywords:

• bi-criteria
• multi-period
• location-routing problem
• heuristics
• public service
• practice of OR

after two revision

This research has been supported by the University Transportation Center for Alabama Grants UTCA-09104 and UTCA-11113.

after two revision

This research has been supported by the University Transportation Center for Alabama Grants UTCA-09104 and UTCA-11113.

Acknowledgements

The authors thank the University Transportation Center for Alabama for providing support for this research under the grant UTCA-11113. The authors also thank the Center for Advanced Public Safety at the University of Alabama (http://care.cs.ua.edu/) for providing the data for this research. Finally, the authors are grateful for the constructive comments of the two anonymous referees.

Notes

1 CPLEX is a trademark of IBM.