Evasive flow capture: A multi-period stochastic facility location problem with independent demand

Nikola Marković, Ilya O. Ryzhov and Paul Schonfeld

European Journal of Operational Research, 2017, vol. 257, issue 2, 687-703

Abstract: We introduce the problem of locating facilities over a finite time horizon with the goal of intercepting stochastic traffic flows that exhibit evasive behavior, which arises when locating weigh-in-motion systems, tollbooths, vehicle inspection stations, or other fixed flow-capturing facilities used for law enforcement. The problem can be formulated as a multi-stage, mixed-integer stochastic program; however, under certain independence assumptions, this can be reformulated as a large two-stage stochastic program, enabling us to solve much larger instances. We additionally propose an algorithm based on Lagrangian relaxation that separates the reformulated stochastic program into a variant of a deterministic knapsack problem and a sum of time-decoupled single-period stochastic programs that can be solved independently. The model and algorithm are tested on instances involving road networks of Nevada and Vermont. A comparison with the previously studied single-period stochastic programming approach shows that the newly proposed multi-period model substantially reduces the expected cost.

Keywords: Location; Flow capture; Multi-period planning; Stochastic flows; Network model (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037722171630635X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:257:y:2017:i:2:p:687-703

DOI: 10.1016/j.ejor.2016.08.020

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().