TY - JOUR
T1 - A minimum cost network flow model for the maximum covering and patrol routing problem
AU - Dewil, R.R.H.
AU - Vansteenkiste, Pieter
AU - Cattrysse, Dirk
AU - Van Oudheusden, Dirk
PY - 2015/11/16
Y1 - 2015/11/16
N2 - 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.
AB - 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.
KW - routing
KW - minimum cost network flow
KW - multi-commodity
KW - patrol routing
KW - orienteering problem
UR - https://www.scopus.com/pages/publications/84937519710
UR - https://www.scopus.com/inward/citedby.url?scp=84937519710&partnerID=8YFLogxK
U2 - 10.1016/j.ejor.2015.05.067
DO - 10.1016/j.ejor.2015.05.067
M3 - Article
SN - 0377-2217
VL - 247
SP - 27
JO - European Journal of Operational Research
JF - European Journal of Operational Research
IS - 1
ER -
