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

R.R.H. Dewil; Pieter Vansteenkiste; Dirk Cattrysse; Dirk Van Oudheusden

doi:10.1016/j.ejor.2015.05.067

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

R.R.H. Dewil
, Pieter Vansteenkiste
, Dirk Cattrysse
, Dirk Van Oudheusden

Research output: Contribution to Journal › Article › Academic › peer-review

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.

Original language	English
Pages (from-to)	27
Number of pages	36
Journal	European Journal of Operational Research
Volume	247
Issue number	1
DOIs	https://doi.org/10.1016/j.ejor.2015.05.067
Publication status	Published - 16 Nov 2015

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 7 Affordable and Clean Energy

Keywords

routing
minimum cost network flow
multi-commodity
patrol routing
orienteering problem

Access to Document

10.1016/j.ejor.2015.05.067

Persistent URL (handle)

Persistent link

Cite this

@article{072de6d3cad44e9a92ba5e7287f6656a,

title = "A minimum cost network flow model for the maximum covering and patrol routing problem",

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.",

keywords = "routing, minimum cost network flow, multi-commodity, patrol routing, orienteering problem",

author = "R.R.H. Dewil and Pieter Vansteenkiste and Dirk Cattrysse and \{Van Oudheusden\}, Dirk",

year = "2015",

month = nov,

day = "16",

doi = "10.1016/j.ejor.2015.05.067",

language = "English",

volume = "247",

pages = "27",

journal = "European Journal of Operational Research",

issn = "0377-2217",

publisher = "Elsevier B.V.",

number = "1",

}

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

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 -

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

Abstract

UN SDGs

Keywords

Access to Document

Persistent URL (handle)

Fingerprint

Cite this