An official website of the United States government
This article describes a new spatial optimization model, the Multiple Gradual Maximal Covering Location Problem (MG‐MCLP). This model is useful when coverage from multiple facilities or sensors is necessary to consider a demand to be covered, and when the quality of that coverage varies with the number of located facilities within the service distance, and the distance from the demand itself. The motivating example for this model uses a coupled GIS and optimization framework to determine the optimal locations for acoustic sensors—typically used in police applications for gunshot detection—in Tuscaloosa, AL. The results identify the optimal facility locations for allocating multiple facilities, at different locations, to cover multiple demands and evaluate those optimal locations with distance‐decay. Solving the MG‐MCLP over a range of values allows for comparing the performance of varying numbers of available resources, which could be used by public safety operations to demonstrate the number of resources that would be required to meet policy goals. The results illustrate the flexibility in designing alternative spatial allocation strategies and provide a tractable covering model that is solved with standard linear programming and GIS software, which in turn can improve spatial data analysis across many operational contexts.
more »
« less
A family of models in support of realistic drug interdiction location decision‐making
Abstract Long‐standing federal drug‐control policy aims to reduce the flow of narcotics into the USA, in part by intercepting cocaine shipments en route from South American production regions to North American consumer markets. Drug interdiction efforts operate over a large geographic area, containing complex drug trafficking networks in a dynamic environment. The extant interdiction models in the operations research and location science literature do not realistically model the objectives of and constraints on the interdiction forces, and therefore counterdrug organizations do not employ those models in their decision‐making processes. This article presents three new models built on the maximal covering location problem (MCLP): the maximal covering location problem for interdiction (MCLP‐I), multiple‐demand maximal covering location problem (MD‐MCLP), and multiple‐type maximal covering location problem (MT‐MCLP). These are novel formulations that permit multiple types of demands and facilities to be covered, and the utility of these formulations is demonstrated in the context of counterdrug operations. Optimal interdiction locations are determined within the geography of the Central American transit zone, using a coupled GIS and optimization framework. The results identify the optimal interdiction locations for known or estimated drug shipments and can constrain those optimal locations by differentiating among drug traffickers, the types of interdiction resources, and agency jurisdictions. This research both demonstrates the flexibility in designing alternative interdiction scenarios and presents novel covering models that may be extended to other application areas and operational contexts.
more »
« less
- PAR ID:
- 10445255
- Publisher / Repository:
- Wiley-Blackwell
- Date Published:
- Journal Name:
- Transactions in GIS
- Volume:
- 26
- Issue:
- 4
- ISSN:
- 1361-1682
- Page Range / eLocation ID:
- p. 1962-1980
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Counterdrug interdiction efforts designed to seize or disrupt cocaine shipments between South American source zones and US markets remain a core US “supply side” drug policy and national security strategy. However, despite a long history of US-led interdiction efforts in the Western Hemisphere, cocaine movements to the United States through Central America, or “narco-trafficking,” continue to rise. Here, we developed a spatially explicit agent-based model (ABM), called “NarcoLogic,” of narco-trafficker operational decision making in response to interdiction forces to investigate the root causes of interdiction ineffectiveness across space and time. The central premise tested was that spatial proliferation and resiliency of narco-trafficking are not a consequence of ineffective interdiction, but rather part and natural consequence of interdiction itself. Model development relied on multiple theoretical perspectives, empirical studies, media reports, and the authors’ own years of field research in the region. Parameterization and validation used the best available, authoritative data source for illicit cocaine flows. Despite inherently biased, unreliable, and/or incomplete data of a clandestine phenomenon, the model compellingly reproduced the “cat-and-mouse” dynamic between narco-traffickers and interdiction forces others have qualitatively described. The model produced qualitatively accurate and quantitatively realistic spatial and temporal patterns of cocaine trafficking in response to interdiction events. The NarcoLogic model offers a much-needed, evidence-based tool for the robust assessment of different drug policy scenarios, and their likely impact on trafficker behavior and the many collateral damages associated with the militarized war on drugs.more » « less
-
Despite more than 40 years of counterdrug interdiction efforts in the Western Hemisphere, cocaine trafficking, or ‘narco-trafficking’, networks continue to evolve and increase their global reach. Counterdrug interdiction continues to fall short of performance targets due to the adaptability of narco-trafficking networks and spatially complex constraints on interdiction operations (e.g., resources, jurisdictional). Due to these dynamics, current modeling approaches offer limited strategic insights into time-varying, spatially optimal allocation of counterdrug interdiction assets. This study presents coupled agent-based and spatial optimization models to investigate the co-evolution of counterdrug interdiction deployment and narco-trafficking networks’ adaptive responses. Increased spatially optimized interdiction assets were found to increase seizure volumes. However, the value per seized shipment concurrently decreased and the number of active nodes increased or was unchanged. Narco-trafficking networks adaptively responded to increased interdiction pressure by spatially diversifying routes and dispersing shipment volumes. Thus, increased interdiction pressure had the unintended effect of expanding the spatial footprint of narcotrafficking networks. This coupled modeling approach enabled the study of narco-trafficking network evolution while being subjected to varying interdiction pressure as a spatially complex adaptive system. Capturing such co-evolution dynamics is essential for simulating traffickers’ realistic adaptive responses to a wide range of interdiction scenarios.more » « less
-
We present a progressive approximation algorithm for the exact solution of several classes of interdiction games in which two noncooperative players (namely an attacker and a follower) interact sequentially. The follower must solve an optimization problem that has been previously perturbed by means of a series of attacking actions led by the attacker. These attacking actions aim at augmenting the cost of the decision variables of the follower’s optimization problem. The objective, from the attacker’s viewpoint, is that of choosing an attacking strategy that reduces as much as possible the quality of the optimal solution attainable by the follower. The progressive approximation mechanism consists of the iterative solution of an interdiction problem in which the attacker actions are restricted to a subset of the whole solution space and a pricing subproblem invoked with the objective of proving the optimality of the attacking strategy. This scheme is especially useful when the optimal solutions to the follower’s subproblem intersect with the decision space of the attacker only in a small number of decision variables. In such cases, the progressive approximation method can solve interdiction games otherwise intractable for classical methods. We illustrate the efficiency of our approach on the shortest path, 0-1 knapsack and facility location interdiction games. Summary of Contribution: In this article, we present a progressive approximation algorithm for the exact solution of several classes of interdiction games in which two noncooperative players (namely an attacker and a follower) interact sequentially. We exploit the discrete nature of this interdiction game to design an effective algorithmic framework that improves the performance of general-purpose solvers. Our algorithm combines elements from mathematical programming and computer science, including a metaheuristic algorithm, a binary search procedure, a cutting-planes algorithm, and supervalid inequalities. Although we illustrate our results on three specific problems (shortest path, 0-1 knapsack, and facility location), our algorithmic framework can be extended to a broader class of interdiction problems.more » « less
-
Illicit Wildlife Trade (IWT) is a serious global crime that negatively impacts biodiversity, human health, national security, and economic development. Many flora and fauna are trafficked in different product forms. We investigate a network interdiction problem for wildlife trafficking and introduce a new model to tackle key challenges associated with IWT. Our model captures the interdiction problem faced by law enforcement impeding IWT on flight networks, though it can be extended to other types of transportation networks. We incorporate vital issues unique to IWT, including the need for training and difficulty recognizing illicit wildlife products, the impact of charismatic species and geopolitical differences, and the varying amounts of information and objectives traffickers may use when choosing transit routes. Additionally, we incorporate different detection probabilities at nodes and along arcs depending on law enforcement’s interdiction and training actions. We present solutions for several key IWT supply chains using realistic data from conservation research, seizure databases, and international reports. We compare our model to two benchmark models and highlight key features of the interdiction strategy. We discuss the implications of our models for combating IWT in practice and highlight critical areas of concern for stakeholders.more » « less
