Exact solution of the evasive flow capturing problem

Okan Arslan, Ola Jabali, Gilbert Laporte

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)
2 Downloads (Pure)

Abstract

The Evasive Flow Capturing Problem is defined as the problem of locating a set of law enforcement facilities on the arcs of a road network to intercept unlawful vehicle flows traveling between origin-destination pairs, who in turn deviate from their route to avoid any encounter with such facilities. Such deviations are bounded by a given tolerance. We first propose a bilevel program that, in contrast to previous studies, does not require a priori route generation. We then transform this bilevel model into a single-stage equivalent model using duality theory to yield a compact formulation. We finally reformulate the problem by describing the extreme rays of the polyhedral cone of the compact formulation and by projecting out the auxiliary variables, which leads to facet-defining inequalities and a cut formulation with an exponential number of constraints. We develop a branch-and-cut algorithm for the resulting model, as well as two separation algorithms to solve the cut formulation. Through extensive experiments on real and randomly generated networks, we demonstrate that our best model and algorithm accelerate the solution process by at least two orders of magnitude compared with the best published algorithm. Furthermore, our best model significantly increases the size of the instances that can be solved optimally.

Original languageEnglish
Pages (from-to)1625-1640
Number of pages16
JournalOperations Research
Volume66
Issue number6
Early online date13 Nov 2018
DOIs
Publication statusPublished - 30 Nov 2018

Keywords

  • Bilevel programming
  • Branch-and-cut
  • Evasive flow capturing
  • Location
  • Projection
  • Routing

ASJC Scopus subject areas

  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint

Dive into the research topics of 'Exact solution of the evasive flow capturing problem'. Together they form a unique fingerprint.

Cite this