Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6896429 | European Journal of Operational Research | 2015 | 10 Pages |
Abstract
This paper shows how the maximum covering and patrol routing problem (MCPRP) can be modeled as a minimum cost network flow problem (MCNFP). Based on the MCNFP model, all available benchmark instances of the MCPRP can be solved to optimality in less than 0.4s per instance. It is furthermore shown that several practical additions to the MCPRP, such as different start and end locations of patrol cars and overlapping shift durations can be modeled by a multi-commodity minimum cost network flow model and solved to optimality in acceptable computational times given the sizes of practical instances.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
R. Dewil, P. Vansteenwegen, D. Cattrysse, D. Van Oudheusden,