A minimum cost network flow model for the maximum covering and patrol routing problem

作者：Dewil R^*; Vansteenwegen P; Cattrysse D; Van Oudheusden D

来源：European Journal of Operational Research, 2015, 247(1): 27-36.

DOI：10.1016/j.ejor.2015.05.067

• Routing
• Problem structuring
• Minimum Cost Network Flow Problem
• Multi-commodity

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.

• 出版日期2015-11-16