Evasive Flow Capture

Abstract

The flow-capturing location-allocation problem (FCLAP) consists of locating facilities in order to maximize the number of flow-based customers that encounter at least one of these facilities along their predetermined travel paths. In FCLAP, it is assumed that if a facility is located along (or "close enough"' to) a predetermined path of a flow, the flow of customers is considered captured. However, existing models for FCLAP do not consider the likelihood that targeted users may exhibit non-cooperative behavior by changing their travel paths to avoid fixed facilities. Examples of facilities that targeted subjects may have an incentive to avoid include weigh-in-motion stations used to detect and fine overweight trucks, tollbooths, and security and safety checkpoints. The location of these facilities cannot be adequately determined with the existing flow-capturing models.

This dissertation contributes to the literature on facility location by introducing a new type of flow capturing framework, called the "Evasive Flow Capturing Problem" (EFCP), in which targeted flows exhibit non-cooperative behavior by trying to avoid the facilities. The EFCP proposed herein generalizes the FCLAP and has relevant applications in transportation, revenue management, and security and safety management. This work formulates several variants of EFCP. In particular, three optimization models, deterministic, two-stage stochastic, and multi-stage stochastic, are developed to allocate facilities given different availability of information and planning policies. Several properties are proved and exploited to make the models computationally tractable. These results are crucial for solving optimally the instances of EFCP that include real-world road networks, which is demonstrated on case studies of Nevada and Vermont.