This paper presents a bi-level network interdiction model to increase the ef- fectiveness of attempting to disrupt a human tracking network under a resource constrained environment. To model the behavior of the tracker, we present a new interpretation of the traditional maximum ow network problem in which the arc capacity parameter serves as a proxy for the tracker's desirability to travel along segments of the network. The objective for the anti-human tracking stakeholder is to invest resources in detection and intervention e orts throughout the network in a manner that minimizes the tracker's expected maximum desirability of operating on the network. Interdictions are binary, and their e ects are stochastic (i.e., there is a positive probability that a disruption attempt is unsuccessful). We present a multi-stage version of the model, which incorporates the e ect of interdictions be- coming more or less successful over time. Using a genetic algorithm that uses a pseudo-utility ratio for the repair operation, we solve multiple problem instances for a case study of the road network in the Eastern Development Region of Nepal and multiple grid networks. We then discuss observations regarding the impact of probabilistic interdiction success and the implications it has for optimal policies to disrupt a human tracking network with limited resources. keywords : maximum ow network interdiction, human tracking, genetic algorithm Corresponding author. 1 2 1 Introduction Human tracking is a human rights violation a ecting millions of people worldwide and international e orts to prevent, detect, and disrupt these exploitative operations have been growing in recent years. While the precise de nition of human tracking dif- fers from country to country, and even among jurisdictions within the same country, the most widely recognized de nition stems from the Palermo Protocol, which was adopted by the United Nations in 2000. In it, human tracking is de ned as \the recruitment, transportation, transfer, harbouring or receipt of persons, by means of the threat or use of force or other forms of coercion, of abduction, of fraud, of deception, of the abuse of power or of a position of vulnerability or of the giving or receiving of payments or bene ts to achieve the consent of a person having control over another person, for the purpose of exploitation" (UN General Assembly, 2000). While human tracking some- times involves moving victims from one location to another, it is noteworthy to highlight that the de nition of human tracking does not require movement. Although human tracking is globally acknowledged, its US$150 billion annual global industry is far from being signi cantly disrupted (International Labour Oce (ILO), 2017). Human tracking prevalence estimates are notoriously dicult to ob- tain due to the varying jurisdictional de nitions and illicit nature of the crime (Busch- Armendariz et al., 2017). However, the most reliable global estimates indicate that 25 million people were being tracked on any given day in 2016 for labor and/or sex (International Labour Oce (ILO), 2017). While a substantial amount of human tracking research has been conducted in the social sciences, most of the prior research has focused on empirical and qualitative insights to describe victim vulnerabilities, public health implications, and law enforce- ment responses to tracking (e.g., Chisolm-Straker & Stoklosa (2017); Ortiz (2016); Nichols (2016); Farrell & Kane (2020); Weitzer (2014)). While critically important in its own right, this social science literature has also informed an emerging body of opera- tions research literature aimed at providing actionable insight into optimal mechanisms of disrupting human tracking operations (Mayorga et al., 2019; Konrad et al., 2017; Caulkins et al., 2019). These papers speci cally identify the opportunity for network interdiction models to be used to disrupt human tracking networks. Conversely, a recent publication identifying emerging areas of network interdiction research also iden- ti es human tracking as an application area requiring methodological advancements (Smith & Song, 2019). 3 Network interdiction models can be used to gain insights into the best ways to disrupt a human tracking network and can be used in contexts in which human track- ing is occurring with or without movement. In the former, network interdiction models can be used to disrupt human tracking that involves trackers and/or victims moving throughout a physical network. In the latter, network models can be used to represent nancial transactions, social connections, and communication patterns. The model we develop in this paper can be used to disrupt both movement and non-movement network related aspects of human tracking operations. However, we present the model in the context of disrupting the physical movement involved in human tracking operations. For instance, migration has been identi ed as a system condition that enhances an individual's vulnerability to being tracked (Seo-Young, 2015). The United Nations Oce on Drugs and Crime (2013) states that two-thirds of migrants (not all are being tracked) in the East Asia and Paci c region use informal crossing points such as rivers and accessible points of the coasts. As we will discuss in the case study presented in this paper, similar informal crossing also occurs along the Nepal/India border. Due to the many border crossing locations, it can be dicult to monitor all possible crossing points in the region for human tracking activity. This motivates the usefulness of network interdiction models in resource constrained environments. While the potential bene t of using network interdiction models for human tracking intervention is suggested in the aforementioned recent operations research literature, to the best of our knowledge, our work is the rst to begin to tailor network interdiction models to the nuances of human tracking on a physical network (Dimas et al., 2021). The model we present draws assumptions and incorporates nuances of human tracking from the current social science literature. Yet, information regarding the structure and operations of human tracking networks is currently limited, and as such, so is the data to populate network interdiction models. Therefore, our model serves as an illustration of the bene t network interdiction models could have for hu- man tracking disruption e orts and motivates further interdisciplinary collaborations between social scientists and operations researchers to pursue research that identi es ro- bust input parameters and additional factors that need to be incorporated into network interdiction models. Speci cally, we present a bi-level network interdiction model in which there are two players who are self-optimizers based on the other player's actions. Players in our model include the interdictor|who takes an initial action seeking to disrupt the 4 human tracking network|and the tracker|who observes the interdictor's actions and operates on the resulting network. We modeled the tracker's movement using the maximum ow problem where the traditional arc capacity parameters are a proxy for the desirability of a tracker to operate along that arc rather than a literal interpretation of ow; the interdictor desires to minimize this maximum ow, thereby minimizing the tracker's desirability of operating on the network. Interdiction decisions are binary and attempt to reduce the capacity of an arc to zero. However, the result of the decision is stochastic; there is a positive probability that an interdiction decision on an arc is unsuccessful and does not have any e ect on the arc capacity. Additionally, our model is multi-staged and interdiction decisions a ect the probability of successful interdiction in future stages. This assumption is inspired by human tracking literature that states the training and information gained from previous interdictions give interdictors signals about how trackers operate in an area (Farrell et al., 2010). On the other hand, trackers adapt their operations over time in response to interdictions to avoid detection (Surtees, 2008). This adjusted success probability dynamic results in nonlinearities within the model, motivating us to use a genetic algorithm with a tailored repair function to solve the model. We illustrate the impact network interdiction models can have on disrupting human tracking operations through a case study involving census data and the road network from the Eastern Development Region of Nepal. Due to the available data, this paper primarily focuses on law enforcement as interdictors. However, we note that there are many types of non-law enforcement related interventions to human tracking that could be considered by other types of interdictors, including basic needs provi- sion, prevention e orts, increasing access to human tracking hotlines and services for survivors, training healthcare sta to recognize potential signs of tracking, and labor inspections. Indeed, recent human tracking research discusses the need to consider human tracking interventions outside of the criminal justice system and acknowledges that this multi-faceted approach may yield better outcomes (Farrell, Bright, & de Vries, 2019; Farrell & Kane, 2019; Farrell, Dank, et al., 2019). The motivating example for this model is non-governmental organization Love Justice International's human tracking transit monitoring operations in Nepal (Hud- low, 2015). Due to the high tracking ow between Nepal and India's open border, Love Justice International trains sta to identify possible cases of human tracking along the border and at key transit points throughout Nepal. These sta do not have 5 the authority to physically interdict the trackers or stop potential human tracking victims from crossing the border. However, they can ask screening questions to travellers and notify local law enforcement if they observe indicators of tracking or connect po- tential victims to resources to lessen their vulnerability to tracking. Thus, the transit monitoring approach is a human tracking disruption mechanism. Our contributions with this work include: providing one of the rst network in- terdiction models to address human tracking, creating a multi-stage network interdic- tion model with decision dependent interdiction success probabilities with the objective of minimizing the maximum ow, re-framing arc capacity parameters as proxies for arc desirability, and developing a tailored repair function for a genetic algorithm to solve the resulting nonlinear model. The remainder of the paper is organized as follows. Section 2 provides a literature review of related network interdiction models. In Section 3, we present the multi-stage stochastic network interdiction model with decision dependent interdiction probabilities. The genetic algorithm for solving the resulting nonlinear model is discussed in Section 4, and Section 5 presents a case study for the Eastern Development Region of Nepal. Finally, in Section 6, we summarize our results and discuss the practicality of the model. We also propose extensions for the model and solution framework. 2 Literature Review Network interdiction models allow us to analyze human tracking disruption ef- forts by modeling both the tracker's and the interdictor's policies, behaviors, timing, and level of information about the other player. Network interdiction typically models two opposing decision makers on the same network. One decision maker, the defender, is trying to operate on the network as e ectively as possible, while the other, the inter- dictor, takes actions to interrupt the ongoing operation (Smith & Song, 2019). Classical examples consider the defender as a player who desires to protect the network from damage and the interdictor as a player who aims to optimally impair the defender's in- frastructure to reduce network utilization (Smith et al., 2013). In the human tracking case, human trackers are the defenders that seek to operate their tracking networks without disruption, while law enforcement and other anti-tracking stakeholders are the interdictors that attempt to disrupt the tracking network. 6 We now summarize the literature related to illicit network interdiction and broader applications of multi-stage min max ow network interdiction models that in- corporate uncertainty. 2.1 Illicit Network Interdiction While the current literature regarding network interdiction models tailored to the human tracking context is limited to general overview papers (Caulkins et al., 2019; Mayorga et al., 2019; Smith & Song, 2019; Konrad et al., 2017), network interdiction models have been applied to other illicit network applications. The complex nuances of interdicting illicit networks motivate the need for the extending network interdiction theory, as described in a survey of recent advancements in network interdiction models and algorithms (Smith & Song, 2019). In recent years, network interdiction models have been used to disrupt drug tracking (Malaviya et al., 2012; Baycik et al., 2018), nuclear smuggling (Morton et al., 2007; Michalopoulos et al., 2013; Dimitrov et al., 2011; Morton & Pan, 2005), and strengthen border control (Zhang et al., 2018). While, collectively, these papers have considered multi-stage, stochastic extensions to the classic network interdiction model in which players gain information over time, none of the models incorporate all of the features in a maximum ow network interdiction model as we do in this paper. In Malaviya et al. (2012), the authors model an illegal drug supply chain as a deterministic hierarchical social network and solve a maximum ow network interdiction problem. The authors assume that criminals in the upper echelons of the drug supply chain can only be interdicted if the lower-level criminals are rst interdicted to gain more information about the upper-level criminals. This is captured through what the authors refer to as \climbing the ladder" constraints and causes the model to use a multi-stage approach. While Morton et al. (2007) consider stochastic source and sink nodes to model the lack of knowledge about a smuggler's operations, the model is a stochastic short- est path network interdiction model rather than a maximum ow network interdiction model. Additionally, the formulation allows the interdictor/leader to increase the re- silience of the network by taking monitoring actions on the selected arcs while the smug- gler/follower is solving their shortest path problem. Ramirez-Marquez et al. (2010) con- sider both maximizing the shortest path and minimizing the interdiction strategy cost and therefore come up with a bi-objective approach. 7 A wide variety of network types have also been considered in illicit network applications. For example, in Malaviya et al. (2012) the network on which interdictions are being made is a social hierarchical drug network where the interdictor climbs up the hierarchy. Kosmas et al. (2020) also consider a social network of drug tracking and human tracking networks to model how an illicit organization can continue to operate after interdictions if the illicit network can replace interdicted arcs or nodes. This model focuses on the operational and personal connections between people, whereas our paper focuses more on the regional tracking ows. Mahbub (2021) considers interdependent social networks of drug and human tracking with information asymmetry. Physical networks have also been considered in the literature; Morton et al. (2007) consider interdicting nuclear smuggling on a physical network and Baycik et al. (2018) uses a layered drug network which consists of both information and physical networks. The model we present in this paper focuses on interdicting physical networks. 2.2 Multi-stage Min Max Flow Interdiction with Uncertainty The maximum ow network interdiction problem that serves as the basis for our work is one type of network interdiction model in which the interdictor seeks to minimize the maximum amount of ow the adversary can send through the network (Wood, 1993; Smith, 2010). The deterministic interdiction assumption of the traditional maximum ow network interdiction problem is relaxed by Cormican et al. (1998) to allow stochastic interdictions such that the success of the interdiction is not certain. In other words, the decision to interdict may not result in a successful change to the network. The main case that Cormican et al. (1998) studied is the binary interdiction realization case where an interdiction attempt on an arc either makes the ow capacity for that arc zero or does not a ect the capacity at all. Since Cormican et al. (1998), many network interdiction models have focused on minimizing the maximum ow (Smith, 2010), including versions that include uncertainty (Smith et al., 2013; Smith & Song, 2019; Janjarassuk & Linderoth, 2008; Sadeghi & Sei , 2019). Also, evolutionary algorithms have been investigated for the stochastic network interdiction problem (Ramirez-Marquez et al., 2009). Uncertainty can arise in network interdiction models in various places. Held & Woodru (2005) consider interdiction decisions where the underlying network topology is not known with certainty. Morton et al. (2007) aim to nd sensor locations on a network that minimizes the expected maximum reliability path for a potential evader. They consider a case where the source-pair of the evader is not known with certainty but 8 according to a distribution. Zhang et al. (2018) are also interested in locating sensors on a physical network to detect evaders with an uncertain source-sink pair, with the goal of minimizing the expected shortest path. The type of uncertainty we incorporate into the present paper is decision- dependant uncertainty. In network interdiction models with decision-dependent uncer- tainty, scenario occurrence probabilities depend on the interdiction decision; therefore they are not independent of the model decisions. This makes calculations such as ex- pectations and compound probabilities more complex as they can become nonlinear as scenario probabilities can become variables themselves. An example for this case can be seen in in Sadeghi & Sei (2019). They rst linearize a decision-dependent maximum ow interdiction model by using Laumanns et al. (2014)'s distribution shaping and then use Benders decomposition to solve a decision-dependent network interdiction problem where the inner problem is a maximum ow problem for a single stage. The uncertainty in their model lies in the outcome of an interdiction attempt. Other researchers have used probability chains to reformulate the model to allow decision-dependent probability calculations, such as O'Hanley et al. (2013) who use probability chains to reformulate Morton et al. (2007)'s problem of minimizing the expected maximum reliability path problem. Decision-dependent uncertainty is a more general concept observed in other stochastic programming problems outside of the network interdiction sub eld as well, and we refer the readers to models in facility protection and network design for a broader understanding of decision-dependent uncertainty in such (Bhuiyan et al., 2020; Medal et al., 2016). Another important aspect in a multi-stage model with uncertainties is the time- line of events and decisions. While some multi-stage network interdiction models assume that the interdictor wishes to make an interdiction decision, wait to observe the out- come of the interdiction decisions, and then adapt their strategy for future stages based on the outcome of the present stage (e.g., Ketkov & Prokopyev (2020); Borrero et al. (2016); Held & Woodru (2005)), we do not assume such \sequential" decision making. Instead, our approach assumes that the decision maker wishes to determine the interdic- tion decisions for all future time periods at once. This is a realistic assumption in many practical cases as creating a multi-time stage human tracking disruption plan can take a signi cant amount of resources and time to coordinate. Other researchers have also considered multi-stage models in which the decision maker plans for all upcoming stages at time zero (e.g., Malaviya et al. (2012); Baycik et al. (2018)). 9 Table 1: A Summary of Relevant Literature PaperMaximum Flow Inner ProblemMulti-StageStochastic Success Probabilities Borrero et al. (2016) X Held & Woodru (2005) X Janjarassuk & Linderoth (2008) X X Ketkov & Prokopyev (2020) X Mahbub (2021) X Malaviya et al. (2012) X X Morton & Pan (2005) X Morton et al. (2007) X O'Hanley et al. (2013) X Ramirez-Marquez et al. (2009) X X Ramirez-Marquez et al. (2010) Sadeghi & Sei (2019) X X Tezcan and Maass (This Paper) X X X Zhang et al. (2018) X To the best of our knowledge, neither the illicit network interdiction nor the broader network interdiction literature captures all of the features we consider in this paper (see Table 1). Speci cally, we consider a multi-stage min max ow problem with decision-dependent uncertainty. In our model, a scenario's occurrence probability de- pends both on the current stage's and the previous stage's interdiction decisions because of the probability updates we consider. Additionally, our model is one of the rst to present a network interdiction model focusing on a human tracking application and our reinterpretation of the network ow as desirability allows us to represent the decision maker's decision-making from a di erent point of view. 3 The Model 3.1 Model Description In our model we have two players, the interdictor, who we assume to be law en- forcement, and the defender, who we assume to be the human tracker. We use a maximum- ow to model the tracker's decision making process. Rather than a literal interpretation of ow capacity constraints on arcs as is common in most network inter- diction literature, we reinterpret the arc capacity parameters to represent the desirability of a tracker to operate along the arc. In other words, we are assuming the interdic- tor has expert knowledge about how the tracker views the network. We amalgamate this information with the tracker's inherent goal of pro ting from factors such as de- sire for cheap labor and other pulling factors in one part of the network by exploiting vulnerabilities of others in another part of the same network. 10 By using the maximum ow interdiction we also assume that a path through the network is only as good as its weak link (least desirable arc). For the tracker, the stakes of getting caught is too high. Thus, not exceeding the desirability levels can be considered as reducing the activity on that region to avoid being identi ed. From a duality perspective this can be considered as the bottleneck (minimum cut) the tracker has in terms of a certain detection level in the network. Therefore, we assume that the tracker avoids detection in the network by abiding to the desirability levels in the network while trying to maximize the tracking ow. In this paper we assume that both the tracker and the interdictor have the same knowledge of network topology for the tracking operation and there is no infor- mation asymmetry. Another feature of our model is how an interdiction attempt's success gets up- dated over stages based on the decisions taken previously. We assume initial arc interdic- tion successes probabilities are given parameters, and when the interdictor is successful at an interdiction, the success probability for that arc gets updated for the next stage. These updates denote either gaining more experience on a certain arc and operating more e ectively as a direct result, or revealing previous tactics and losing some of the previous success probability. We give a more detailed explanation and motivate these cases in the human tracking context in the upcoming sections. However, one impor- tant assumption we make in this model is that a successful interdiction will only a ect the success probability of that same arc in future time periods. We rst describe a single-stage model which incorporates stochastic interdic- tion success probabilities. We then use this single-stage model to create a base for building the multi-stage extension in Section 3.3, which incorporates dynamic, decision- dependent stochastic interdiction success probabilities. 3.2 Single-Stage Model LetG= (N;A) be a network which has source and sink nodes sandt, respectively. This network of physical locations as nodes and arcs with ow capacities represents how the tracker and the interdictor are perceiving the tracking ows for a geographical region. Therefore, the interdictor desires to minimize the maximum ow between the source and the sink. To minimize the tracker's ow, the interdictor can attempt to disrupt arcs in the network. 11 Mathematically, these interdiction decision variables are represented with a vector y, whereyijtakes value 1 if arc ( i;j) is attempted to be interdicted and 0 if not. We letIijbe the auxiliary interdiction e ectiveness variable identifying whether arc ( i;j) is successfully interdicted ( Iij= 1) or not ( Iij= 0). We will impose constraints such that when no interdiction attempt is made on arc ( i;j) (i.e., when yij= 0),Iijis equal to 0. On the other hand, if an interdiction attempt is made (i.e., when yij= 1),Iij becomes 1 with probability pij; otherwise it is 0. Attempted interdiction either fully reduces the arc capacity to 0 or it does not a ect the arc at all. We let be the space of all possible scenarios with !2 representing an outcome scenario. Parameter cijis the required cost for attempting an interdiction on the arc ( i;j) andRis the budget of the interdictor. The optimal value of the tracker's maximum- ow problem based on the interdictor's decisions ( y) and their realizations ( I) under scenario !is denoted by Q(y;I!). With this notation, the interdictor's problem is: minimize yE[Q(y;I!)] (1) subject toX (i;j)2AcijyijR (2) yij2f0;1g 8(i;j)2A (3) Objective function (1) minimizes the expected value of the maximum- ow through the network from source node sto sink node t. Therefore, E[Q(y;I!)] can be repre- sented asP !2 PyfI!gQ(y;I!), wherePyfI!gis the probability that realization I!will occur under the probability space created by the decision y, which we will discuss in detail shortly. Constraint (2) is the resource limitation constraint for the interdictor and constraint (3) is the domain of the decision variables. Without loss of generality, we can order each arc in the network from 1 to jAj. Then, combining all arc interdiction decisions, realizations for a network under an inter- diction decision can be represented with, I=fI1;I2;:::;IjAjg. This allows the probability of a realization on the network under interdiction decision yto be represented as a mul- tiplication of arc realizations since we assume independence between arcs (Laumanns et al., 2014). We de ne the binary arc realization probabilities under interdiction decision yfor all (i;j)2Aas: PyfI! ijg=8 >< >:yijpij I! ij= 1 (1yij) +yij(1pij)I! ij= 0 12 If an arc interdiction decision is given, (i.e., yij= 1) the arc realization corre- sponding to the successful interdiction has a probability of pij. On the other hand, a failed attempt will have a probability of (1 pij) for the arc. However, if no interdiction attempt for the arc is present, the realization must be zero as well, which is satis ed with the given de nition. Now using the arc realizations we can de ne a full network realization, or in other words, a scenario. The probability of scenario !happening under decision ycan be de ned as; PyfI!g=Y (i;j)2APyfI! ijg This de nition of the decision-dependent scenario probabilities creates a probability space when we consider all of the possible realizations under a given interdiction decision. As the e ect of anti-human tracking e orts varies with respect to where the intervention occurs, we choose to allow the model to incorporate di erent interdiction success probabilities for each arc. We will use these probabilities and update their values based on our previous interdiction actions to estimate how our previous encounters with tracking operations can impact future attempts' success. We will elaborate more on how these probabilities can be estimated in Section 5 when we discuss a case study. The tracker's subproblem for scenario !2 can be seen below where Ais the modi ed version of arc set A with the arc ( t;s) included, i.e A:=A[(t;s). This inclusion of the arti cial return arc ( t;s) with an in nite (or very large) capacity allows us to reformulate the maximum ow problem as a network ow problem (Bertsimas & Tsitsiklis, 1997): Q(y;I!) = maximize xxts (4) subject to 0xijuij(1I! ijyij)8(i;j)2A (5) X j2FS(i)xijX j2RS(i)xji= 08n2N (6) In this optimization problem, objective (4) represents a tracker's desire to maximize the ow through the network. The tracker does this by maximizing the ow on arcxtsafter the interdictor decides which ows to attempt to interdict ( y) and the extent to which the attempts are successful ( I!) are observed. Constraints (5) are the set of equations for the stochastic arc capacities. If arc ( i;j) is not successfully interdicted, the capacity remains at uij. However, if an interdiction is successful, the capacity of the 13 arc is reduced to 0. Constraints (6) are ow balance constraints for each node on the network, where the forward star of i,FS(i), denotes the set of arcs directed out of node iand the reverse star of i,RS(i), denotes the set of arcs directed into i. Note that the same I!can be observed under di erent interdiction decisions as the scenario spaces that interdiction decisions create are not necessarily disjoint and share common scenarios (i.e., successfully interdicted network instances). Therefore, maximum- ow values for these realizations should be identical as well. However, their probability coecient in the expectation calculation can be di erent for every probability space that the interdiction decision ycreates. So, if we calculate maximum ows under all possible scenarios (interdicted networks), the single level problem becomes nding the minimum ow expectation yielding a probability space with a feasible set of binary arc interdictions. 3.3 Multi-Stage Network Interdiction Model In the single-stage model, the interdictor attempts to disrupt some of the arcs in order to minimize the max- ow of the tracker. However, in reality, tracking interventions occur over time and the impact they have varies due to trackers adapting to previous interventions or anti-tracking stakeholders becoming more e ective as more information is gained about the network. We incorporate this dynamic by extending the single-stage model to a multi-stage framework in which we consider updates to the probability of successfully interdicting an arc in future stages if the arc was successfully interdicted in the previous stage. An interdiction does not change the network structure for the next stage; rather, it updates the interdiction success parameters for future stages. We also note that by multi-stage we mean that the optimal interdiction decisions for multiple time periods are determined before observing any realization of the future stages based on the expected outcomes. Thus, our model does not include a sequential or online decision-making nature. 3.3.1 Interdiction Success Parameter Update LetKrepresent the set of stages. Similar to the single-stage model, the probability of interdiction success for an arc ( i;j) during stage k2Kis denotedpk ij. In the multi- stage model, a successful interdiction has two e ects: one short-term and one long-term. The short term e ect eliminates the tracker's desire to use arc ( i;j) in their tracking operation in stage kby reducing the capacity of the arc to 0 for the current 14 stage. Consistent with the human tracking literature, we assume that the capacity of a successfully interdicted arc is only reduced for the current stage. That is, if interdiction e orts are not implemented on arc ( i;j) in future stages, trackers may once again nd arc (i;j) desirable. The long term e ect of a successful interdiction a ects future interdiction success probabilities; we assume that every successful interdiction on an arc ( i;j) will update the probability of the next stage's interdiction success on the same arc ( i;j). We model this update in success probability with the rate parameter . Speci cally, we let 11 denote a measure of the percent change in the interdiction success probability. Its scalar value represents how much new information is worth to the system, and its sign represents who favors from this update. Positive update rates, 0 <1, indicate that the interdictor is becoming more successful at reducing tracking in an area with each successful interdiction. This can happen under the case where law enforcement is discovering the modus operandi of the tracking operation on an arc and then using this information to obtain a higher likelihood of success in further interdictions. For example, a rate of 0.5 means that with each new successful interdiction on arc ( i;j), the probability of successful interdiction on arc (i;j) increases by fty percent of the remaining amount (i.e., 50% of 1 pk ij). That is, an arc that had a pk ij= 0:8 probability of successful interdiction in stage k would increase to the probability pk+1 ij= 0:9 in stagek+ 1 if the interdiction in stage k was successful. On the other hand, successful interdictions can create updates in the favor of the tracker as well. This corresponds to update rates 1<0 and represents the percent reduction in interdiction success in future stages. If a tracker is interdicted on a speci c arc, other trackers may gain knowledge about the interdiction tactics of law enforcement in a manner that allows them to continue operating on the arc with a lower chance of being detected. Therefore, successful interdictions may reduce the likelihood of future successful attempts on an arc. For example, a rate of 0:5 means that with each new successful interdiction on arc ( i;j), the probability of successful interdiction on arc ( i;j) decreases by the fty percent (i.e., 50% of pk ij). That is, an arc that had apk ij= 0:8 probability of successful interdiction in stage kwould decrease to a pk+1 ij= 0:4 likelihood of successful interdiction in stage k+ 1 if the interdiction in stage kwas successful. 15 However, as this is a stochastic model with the outcome of interdictions repre- sented by scenarios, the probability updates for the arcs are also represented in expec- tation terms. We introduce the following equations to update interdiction probabilities for the arcs at each stage. (Note that yandIhave also been indexed by stage for the multi-stage model.) pk+1 ij=8 >< >:pk ij+ (1pk ij)yk ijE[Ik ij] 01 pk ij+pk ijyk ijE[Ik ij]1<0(7) We also use the notation Pk yfI!gto denote the scenario probability for scenario !, which is generated by the interdiction decision y= (y1;y2;:::;yjKj). Each vector yk denotes the corresponding stage's interdiction decision. It is important to note that the future stages' decisions do not a ect previous stages' probability spaces. We use the full interdiction vector yto be consistent. Calculation for the scenario probabilities under interdiction are done similar to the single-stage case, with one major di erence. For the rst stage, interdiction probabilities are parameters and they become active or not depending on the rst stage's interdiction decision. Starting from the second stage, arc interdiction probabilities become variables and change values depending on the previous stage's interdiction decision. Example with Positive Rate Parameter: To illustrate how the update equation works, consider a network with just two nodes, node A and node B, and a single arc connecting them (AB). Suppose the probability that the interdictor successfully inter- dicts this arc if she attempts to is 80% initially ( p1 AB= 0:8) and the update rate is 50% ( = 0:5). When the interdictor attempts to interdict arc (AB), there are two possible scenarios: the interdiction is successful with probability Pk=1 yfI!=1g=p1 ij= 0:8 (as there is only one arc on the network), which results in I1 AB= 1; or the interdiction is unsuccessful with probability Pk=1 yfI!=2g= 1p1 ij= 0:2, which results in I2 AB= 0. Under scenario 1, where the arc is successfully interdicted, the probability of successful interdiction in the next stage becomes pk=2;!=1 AB= 0:8 + (10:8)110:5 = 0:9. Under scenario 2, where the interdiction attempt fails, there is no increase in probabil- ity (pk=2;!=2 AB= 0:8). Therefore, the expected updated probability under the decision of attempting to interdict arc (AB) becomes p2 AB= 0:80:9 + 0:20:8 = 0:88. Example with Negative Rate Parameter: If the update rate was instead  = 0:5, then the successful interdiction in scenario 1 would result in a probability of successful interdiction of pk=2;!=1 AB= 0:8 + 0:811(0:5) = 0:4 in the next stage. 16 If the interdiction attempt was unsuccessful (i.e., scenario 2), there is no change in the success probability ( pk=2;!=2 AB= 0:8). Therefore, the expected updated probability under the decision of attempting to interdict arc (AB) becomes p2 AB= 0:80:4+0:20:8 = 0:48. We use the percentages for the rate variable, , rst and foremost to model the changing incremental e ect of the information gained (i.e., successful interdictions provide information). Since this is a normalized parameter, the magnitude of its e ect depends on the initial success probabilities, p1 ij. For example, when 0 <, if the initial probabilities ( p1 ij) are very low, the interdictor will gain a greater marginal increase in future interdiction success probabilities than compared to a p1 ijvalue near 1. The motivation for this is that a low probability of success may correspond to the interdictor not having much information about the tracking network. Any successful interdictions when the interdictor does not have much information about the network could have a drastic di erence as it provides insights into the ongoing human tracking network in the area. On the other hand, if law enforcement is already e ective against the trackers, successful interdictions will only have a ne-tuning e ect, i.e. they will still increase the success probability but in a relatively slight margin. Symmetrically, if the initial probabilities ( p1 ij) are very low and  <0, the tracker is able to ne tune their evasion tactics to avoid interdiction. If the initial probabilities ( p1 ij) were much higher, the tracker has more opportunity to reduce their likelihood of interdiction in future stages. With the multi-stage nature of the model, the budget parameter Rand the cost parameter ccan become stage dependent as well. Recourse variables and decision variables also depend on the stage of the problem from now on. For the multi-stage version of the model, scenario probabilities can be found using the multiplication of arc realization probabilities given below. As previously mentioned, the pk ijvalues can be found using the probability update formula given the interdiction vector y: Pk yfI! ijg=8 >< >:yk ijpk ij I! ij= 1 (1-yk ij) +yk ij(1pk ij)I! ij= 0(8) 3.3.2 Model Formulation The formulation for the multi-stage stochastic network interdiction with probability updates can be seen below for the case of 0 1. The only change required for model formulation to account for the case of 10 is replacing constraint (12) 17 with the associated 10 equation from (7). minimize y;pX k2KEk[Qk(y;I!)] =X k2KX !2 Pk yfI!gQk(y;I!) (9) subject toX (i;j)2Ack ijyk ijRk8k2K (10) yk ij2f0;1g 8(i;j)2A;8k2K (11) pk+1 ij=pk ij+ (1pk ij)yk ijE[Ik ij]8(i;j)2A;8k2f0;:::;K1g (12) In the above formulation, objective function (9) seeks to minimize the summation of the expected maximum ows over every stage. Constraints (10) are the set of resource constraints for every stage, where each stage has its own budget that does not roll over into future stages. Constraint set (12) ensures that for each arc the probability of the next stage is updated based on the current decision, its expected realization, probability of success, and the update rate. Finally, constraint set (11) is the domain of the interdiction decision variables y. At each stage, the tracker solves the following max- ow problem based on the interdiction decisions yand their outcomes I!. Qk(y;I!) =maximize xxk ts (13) subject toX j2FS(i)xk ijX j2RS(i)xk ji= 0 8i;j2N (14) 0xk ijuij(1I! ijyk ij)8(i;j)2A (15) 4 Solution Approach One common approach to solve network interdiction models is to take the dual of the inner maximization problem and combinine it with the outer minimization problem (Smith et al., 2013; Cormican et al., 1998). This allows the bi-level min-max problem with di erent objective functions to be transformed into a single minimization problem. The dual of the follower's max ow problem is given below with dual variables nand ijcorresponding to (14) and (15). 18 Q! k(y;I!) = minimize ; X (i;j)2A(uij(1I! ijkyijk)) ! ijk (16) subject to ! ik ! jk+ ! ijk08(i;j)2A;8i;j2N (17) ! tk ! sk1 (18) ! ijk08(i;j)2A (19) Combining this problem with the leader's problem we can obtain the equivalent problem: minimize y; ; X k2KE[Qk(y;I!)] =X k2K !2 Pk yfI!gX (i;j)2A(uij(1I! ijkyk ij)) ! ijk (20) subject toX (i;j)2Ack ijyk ijRk8k2K (21) yk ij2f0;1g 8(i;j)2A;8k2K (22) pij;k+1=pijk+ (1pijk)yk ijE[Iijk]8(i;j)2A;8k2f0;:::;jKj1g (23) ! tk ! sk1!2 ;k2K (24) ! ik ! jk+ ! ijk08(i;j)2A (25) ! ijk08(i;j)2A;!2 ;k2K (26) The joint probability for each scenario, Pk yfI!g, contains the multiplication of the binary arc interdiction decisions and interdiction probabilities (which are themselves continuous decision variables after the initial stage due to constraints (12)) . These joint probabilities are also multiplied with the corresponding value of the minimum cut which creates a nonlinear term. We can linearize the multiplication between a scenario's mini- mum cut and its probability by de ning new variables for each scenario and introducing appropriate constraints. However, linearizing the scenario probability term is not trivial as it includes multiplication of each arc's success or failure probabilities. Instead, we use a genetic algorithm (GA) to solve the model with nonlinearities. 4.1 Genetic Algorithm for the Maximum Flow Network Interdiction Model Brie y, GAs are methods for searching a solution space for solutions with the highest (or lowest, depending on the type of the objective) objective values (Mitchell, 1998; 19 Haupt & Haupt, 2004). Motivated by biological evolution, GA terminology usually refers to solutions as individuals and objective functions as tness functions . Each individual is composed of multiple bitsrepresenting speci c decision variable values. To be consistent with the nomenclature we will use the same terminology as well. GAs and evolutionary algorithms are a common method of solving network in- terdiction problems (Ramirez-Marquez et al., 2010; Dai & Poh, 2002; Ramirez-Marquez et al., 2009). Dai & Poh (2002) uses a GA to solve the deterministic maximum ow network interdiction model on a directed graph where each individual represents a cut in the network. Inspired by this approach, we developed a GA for our problem. How- ever, one major di erence is in how we de ne the individuals. Since Dai & Poh (2002) only considers a single-stage deterministic model, each bit in an individual represents which side the corresponding node belongs to after the network is partitioned by a cut. However, since we consider a multi-stage model and we have also coded the interdiction decisions over the arcs, the individuals we consider consist of bits that represent an interdiction decision at stage kfor the corresponding arc. Therefore, the individuals in our solution e ectively consist of jKjcopies of the individuals that are present in a single-stage version, one for each stage. The operations of our GA are described below and a summary of all related GA parameters is given in Table 2. Pseudo-code for the GA is provided in the Appendix. 4.1.1 Representation and Fitness Function Each individual is a binary string of length of jAjjKjwhereAis the set of arcs andKis the set of stages. If an arc ais attempted to be interdicted at stage kthe corresponding bit ( a;k) takes the value 1; otherwise it is 0. Therefore an individual includes interdiction decisions for all of the stages. To evaluate the tness of an individual, we rst generate the possible interdicted networks for each stage with their corresponding probabilities by using Py(I!). Then, we solve the deterministic maximum ow problem for each scenario wand take the expectation over all scenarios by using the hitherto calculated probabilities for each stage. We also update the interdiction probabilities according to the probability update functions we introduced in the multi-stage problem. Therefore, depending on the rate, each stage yields di erent ow amounts and we determine these values iteratively for an individual. Finally, we sum the expected maximum ows over the stages to calculate the tness of an individual. 20 4.1.2 Creating the Initial Population Due to our knapsack constraint (10), we use the primitive primal heuristic from Chu & Beasley (1998) to generate an initial population. This algorithm ensures all individuals in the initial population are feasible by starting with all variables as zeros and then randomly picking a variable and making it one unless it makes the individual infeasible. A population size of 100 individuals was used and was determined through initial experiments that were shown to quickly converge to near-optimal values. 4.1.3 Parent Selection Parent selection is the operation of selecting individuals from the current population in order to conduct reproduction operations, namely crossover and mutation. We have used the tournament selection method with a tournament size of 4 individuals and tness scaling to ensure that we favor better performing individuals more than their raw tness score (see Shukla et al. (2015) for tournament selection and other selection techniques in GAs). 4.1.4 Crossover and Mutation Crossover and mutation are reproductive operations to iterate the GA. After the parent selection operation, we have a set of individuals from the current population to generate the new population. We implemented a uniform crossover function which takes the input as two parents from the parent selection and a random string of zeros and ones. It then assigns the values from the rst parent to the new individual where the random string has values equaling one and values from the second parent where the random string has values equaling zero. Therefore the output becomes a new individual from two parents. The mutation operation essentially changes the bits of the individual following a probability distribution with an aim of reducing the chance of getting stuck at local optimums. We have used the bit ip mutation as we have binary values. This operation ips (changes the ones to zeros and the zeros to ones) the value if the bit is selected to be mutated. We have mutated 5% of selected individuals. We also let 90% of the population be generated from the crossover operation, 5% from the mutation and the rest from the elites. Elite individuals are the best tness function yielding individuals that carry-on through the iterations. 21 4.1.5 Repair Operation As can be seen from above reproduction operations, we do not consider the budget constraint while conducting crossover and mutation, which might generate infeasible individuals for the new generation. Searching through infeasible solutions is not an ecient use of solution time. To handle individuals that exceed the budget constraint and to restrict the ran- dom search to the feasibility set, we implemented an approach that uses pseudo-utility ratios tailored to our network interdiction model with dynamic interdiction success prob- abilities. In their 1998 paper, Chu & Beasley showed that these types of operations perform well for a search with knapsack constraints. Our pseudo-utility ratio considers the expected capacity of an interdicted arc ( i;j) and the cost required to attempt the interdiction:E[capacity ] cost=pijkuij ck ij. This value is an estimate of the interdictor's utility of interdicting each arc on the network. The repair operator uses the ratio as follows. If the individual is infeasible, the operator removes interdiction decisions from the individual for the given stage, starting from the lowest pseudo-utility yielding arcs until it becomes feasible. It is important to note that these values are pre-processed before the algorithm starts iterating. Then the operator starts adding interdiction decisions, starting from the highest ratio yielding ones while considering the budget. The operation terminates when we can not add any more interdiction decisions while staying feasible. We provide an example iteration in the Appendix. 4.2 Termination Criteria The GA terminates when negligible or no improvement is observed between the last 10 generations' best (i.e., lowest tness function yielding) individuals. We have accepted improvements over 0 :0001% of the current tness function as signi cant and selected the number of stalling generations to be 10 to avoid getting stuck at local optimums. A ter- mination guarantee condition that stops the algorithm after 100 iterations/generations is also speci ed, although this condition never became active in our experiments. 4.3 Grid Networks We test our GA on grid-like networks in the spirit of papers like Atamturk et al. (2018) and Janjarassuk & Linderoth (2008). We generate an abrectangular grid network with ahorizontal layers of bnodes each. In these networks horizontal arcs 22 Table 2: Genetic Algorithm Parameters Parameter Description Value PopSize Population size 100 TournSize Tournament size 4 ElitePop Percentage of population generated by keeping elite individuals 5 CrossoverPop Percentage of population generated by crossover 90 MutatePop Percentage of population generated by mutation 5 MutateProb Fraction of individual mutated 0 :1 MaxIter Maximum number of iterations 100 MaxIterNoImprove Maximum number of iterations with no improvement 10 are directed in the orientation of the source and the sink. Vertical arcs are oriented randomly. With these numerical experiments, we aim to illustrate how our GA works and how our problem's solution space di ers from other stochastic network interdiction problems due to decision-dependent success probabilities. We have selected two grid networks for our experiments. The rst is a 3 3 grid network, which we will denote as the small network. The second is a 5 5 grid network and we will denote this network as the large network. In the small network we allow all of the arcs to be interdicted and in the large network we allow half of the arcs in the grid to be interdicted. These interdictable arcs are shown in the Figure 1 with dashes and in red for the large network; the small network can be seen in the Appendix. For each network we denote the source and sink nodes with square shapes. The source node is indicated by node 1 in both networks, and the sink node is indicated by node 11 and 27 in the small and large networks, respectively. Horizontal arcs are arcs that are directed in the immediate direction from the source to the sink, such as arc (1,4) in the large network. An example for a vertical arc from the large network is arc (3,4). Our network sizes are comparable to the smaller networks Janjarassuk & Linderoth (2008) consider, yet are computationally dicult due to the probability updates; each stage's decision changes the other stage's success probabilities and therefore the scenario probabilities became decision variables rather than parameters, adding to the complexity. We have generated random arc capacities ( uij's) and the initial interdiction probabilities ( p1 ij's) for the arcs from uniform distributions with ranges from 1 to 10 and from 0 to 1, respectively. Arc capacities and the initial interdiction probabilities can be seen on the arcs with the corresponding pseuodo-utility in the format of (arc capacity, interdiction probability, psuedo-utility). We use unit costs of interdiction for each; thus, our budgets can be considered as cardinality budgets. 23 Figure 1: Large Network, where the values along the arcs represent (arc capacity, interdiction probability, psuedo-utility) 24 We benchmark the performance of the GA with the optimal solutions we ob- tained from complete enumeration for problem instances with two stages, (i.e., jKj= 2). In this section we will discuss how well the GA converged in our experiments and the e ect of the budget on the solutions. As these networks and their parameters are not generated speci cally for the tracking context, we will conduct our policy related dis- cussion in the case study section. Figure 2: GA Performance on 3x3 Grid Network 25 Figure 3: GA Performance on 5x5 Grid Network Figure 2 and Figure 3 show how well the GA performed for both networks. We present the results of the GA with box plots to present the results of 100 experiments for each setting and the optimal solutions. Our rst observation is the increase in the spread of the solutions that GA converged to as the budget increases for each network. This is an expected observation as the solution space gets larger when the interdiction budget increases. We also observe an increase in the spread as the rate parameter increases within the same budgets for both networks. We also observed that when the rate is positive the optimal solutions always con- sist of having the same set of interdictions in the rst and the second stages. Therefore, we have created a modi ed GA (MGA) that forces the rst and the second stage inter- dictions to be identical. We discuss the reasoning behind this in greater detail in Section 5.2.1. Figures 4 and 5 take a closer look at the performance of the algorithms. Each bar shows the number of GA and MGA solutions that converged to the optimal, that are with-in 1% and 5% of optimality for their respective setting. 26 Figure 4: GA and Modi ed GA Performance on 3 3 Grid Network Figure 5: GA and Modi ed GA Performance on 5 5 Grid Network We can see this in more detail in Figure 4, as well which shows how the best GA solutions in the 100 runs found the optimal solution, or a solution within 1% or 5% of the optimal solution. We observe that most of the GA runs converged to the optimal solution found by enumeration. MGA provided better results for positive rate values as we illustrate in Figure 4 and Figure 5. On the rst row of Figure 4 we observe the MGA converging to optimal solutions more frequently compared to the GA. As GAs 27 iterate in a stochastic fashion we present the cases where the algorithm converges to sub-optimal solutions as well. From these experiments we observe that the convergence to sub-optimal solutions became more frequent when the interdiction budget increases. To give an example, the worst performing set of experiments are when the interdiction budget is equal to 3. In this setting, when the rate is 1, the GA found the optimal solution in 59% of the experiments for the small network, and 88% of the solutions were within 15% of the the optimal solution. For the large network, the GA's performance dropped and it was not able to converge to any solution within 5% of the optimal solution. However, the MGA frequently converges to optimal or near-optimal solutions in this instance. As expected, the GA's performance on the 5 5 grid decreased compared to the 33 grid. We also observe that MGA's performance is better as enforcing the same solution for the both stages reduces the search space. To promote consistency in comparing the results of the GA and MGA across di erent networks, we keep the termination criteria the same for all network instances. Thus, we did not conduct our experiments with dynamic termination criteria based on problem instance's size so this reduction in performance is expected as the search space got larger with the larger network. Tailoring the termination criteria for each network instance may provide better, but less comparable, results. In the next section we also illustrate how the utility measure we built for the GA can be useful for the policy analysis by itself as it gives a measure of arc desirability and the cost over the network. 5 Case Study: Nepal We illustrate the network interdiction model using a case study of trackers operat- ing on a road network in the Eastern Development Region of Nepal. This is motivated by the e orts of non-governmental organizations, such as Love Justice International, who monitor human tracking transit activity along the Nepal-India border (Hudlow, 2015). The Nepal network, which we will discuss in more detail in this section, will have 34 node and 38 arcs, of which 33 are interdictable. 5.1 Parameter and Network Generation Through analyzing six years of Love Justice International's human tracking transit activity data, we identi ed that people crossing the Nepal-India border at Kakarbhitta, 28 Bhadrapur, and Biratnagar who exhibit signs of being potential human tracking vic- tims are commonly from the Taplejung and Khadbari districts (see Dimas et al. (2022) for more details of this data). Using this knowledge, our case study focuses on dis- rupting human tracking along the road network in the Eastern Development Region of Nepal, with Taplejung and Khadbari as source nodes and Kakarbhitta, Bhadrapur, and Biratnagar as sink nodes. We convert this multi-source, multi-sink network into a single source, single sink node network for the network interdiciton model by intro- ducing arti cial source s0and sink nodes t0connected to the Taplejung and Khadbari; and Kakarbhitta, Bhadrapur, and Biratnagar nodes, respecively. In the remainder of the manuscript, we refer to Taplejung and Khadbari as source nodes s; Kakarbhitta, Bhadrapur, and Biratnagar as sink nodes t; the singular arti cial source node as s0; and the singular arti cial sink node as t0. As previously mentioned, the prevalence of human tracking and the nature of how trackers operate on a physical network are largely outstanding research questions due to not having a universally agreed de nition of the crime, the illicit nature of human tracking, and a victim's propensity to not self-identify as victims (Farrell & de Vries, 2020). In the absence of this data, a common approach is to estimate possible tracking ows using the number of human tracking cases investigated, hypothetical tracking indicators and related demographic metrics from high level datasets. Danailova-Trainor et al. (2006) and Hernandez & Rudolph (2015) are two studies that identify factors related to tracking between two countries, including the countries' income di erentials, border policies, migrant populations, and population size. These studies and identi ers are useful for our model, as we use them to generate the desirability parameter for each arc. This parameter limits the maximum ow that can go through an arc and is traditionally referred to as the arc capacity. Therefore, since the tracker wants to maximize the overall expected ow on the network, arcs with a higher desirability (i.e., higher capacity) will be more appealing for the tracker. To obtain the desirability parameters, we rst begin by calculating a measure of the tracking ow ( ust) between every source sink pair ( s;t) using census data and the Danailova-Trainor et al. (2006) and Hernandez & Rudolph (2015) indicators: in- come ratio ( IncDiff st), total population ( PopSum st), and total foreign population (Fpopst) (Government of Nepal Central Bureau of Statistics, 2012). Distances ( Distst) were obtained from UN RCHC in Nepal (2011). Each of these four parameters is weighted by a respective value from w, where w=fwIncDiff;wPopSum;wDist;wFpopg= 29 f1:208;0:783;0:974;0:393g. These values are originally from Hernandez & Rudolph's (2015) regression analysis and used in this case study with illustrative purposes to show how the di erent tracking indicators may be weighted di erently. For a more realistic study, future research is needed to obtain better estimators that are tailored to the con- text being modeled. The arc capacities representing desirability of tracking between two locations ( ust) is calculated as: ust=wIncDiffIncDiff st+wPopSumPopSum st+wDistDistst+wFpopFpopst Table 3 provides the resulting baseline ow estimates. Table 3: Flow Between each Source-Sink Pair SourcenSink Biratnagar Bhadrapur Kakarbhitta Khadbari 3 2 1 Taplejung 3 2 2 The above function generates a normalized estimation of the tracking ow between every source and every sink. However, it is also important to know the various paths trackers can take between source and sink nodes. We obtain this information from the Nepal road network as shown in Figure 6 (UN RCHC in Nepal, 2011), where triangles denote source nodes, stars denote the sink nodes, and squares denote transit nodes. Each node represents a district in the Eastern Development Region of Neapl. Figure 6: Road Network for the Eastern Developmental Region of Nepal 30 To calculate the arc desirability (i.e., capacity) parameters for the arcs in the network, we used the network topology of Figure 6 and found every possible path from each source to sink. Then for each arc, we identi ed every path that included the arc and added the corresponding path's estimated ow to the arc's desirability parameter. Arc desirabilities for each node in the network are given in Table 4. To illustrate how we use all possible source-sink paths to calculate the arc desirabilites, consider arc (1,6) in Table 4 connecting nodes Damak and Itahari (locations can be seen in Figure 6). This arc is present in six paths between source and sink nodes: it is in two paths between Taplejung - Bhedetar, two paths between Khadbari - Bhadrapur, and two paths between Khadbari - Kakarbhitta. When we multiply these numbers with the corresponding ow values from Table 3, we obtain the arc desirability. In this case, arc 16 has a desirability of: 2(3)+2(2)+2(1) = 12. Without any interdiction, the network with arc desirabilities as capacities is a proxy for the amount of tracking that occurs between districts. Table 4: Arc Desirabilities and Pseudo-Utility Ratios Node i Node j Arc # Arc Desirability Interdiction Cost Initial Interdiction Probability Pseudo-Utility Ratio Taplejung Phidim 1 12 2 0.271 1.626 Taplejung Source 2 Uncapacitated N/A 0 0 Phidim Ilam 3 12 2 0.651 3.906 Ilam Phikkal 4 12 2 0.651 3.906 Phikkal Pasupati Nagar 5 0 1 0.374 0 Phikkal Charali 6 12 4 0.651 1.953 Charali Kakarbhitta 7 4 2 0.651 1.302 Charali Birtamod 8 8 1 0.651 5.208 Charali Bhadrapur 9 8 2 0.651 2.604 Kakarbhitta Sink 10 Uncapacitated N/A 0 0 Birtamod Bhadrapur 11 8 1 0.271 2.168 Birtamod Damak 12 12 1 0.271 3.252 Bhadrapur Kechana 13 0 1 0.171 0 Bhadrapur Sink 14 Uncapacitated N/A 0 0 Damak Gaurigunj 15 0 1 0.271 0 Damak Itahari 16 12 2 0.271 1.626 Itahari Biratnagar 17 9 2 0.651 2.9295 Itahari Dharan 18 9 1 0.651 5.859 Itahari Birpur 19 0 1 0.271 0 Biratnagar Rangeli 20 0 1 0.651 0 Biratnagar Sink 21 Uncapacitated N/A 0 0 Dharan Bhedetar 22 9 1 0.271 2.439 Bhedetar Dhankuta 23 9 1 0.198 1.782 Dhankuta Hile 24 9 1 0.198 1.782 Hile Bhojpur 25 0 20 0.651 0 Hile Basantapur 26 9 1 0.171 1.539 Basantapur Tehrathum 27 0 1 0.271 0 Basantapur Chainpur 28 9 1 0.198 1.782 Chainpur Khadbari 29 9 1 0.171 1.539 Khadbari Source 30 Uncapacitated N/A 0 0 Birpur Bhardaha 31 0 1 0.195 0 Bhardaha Rajbiraj 32 0 1 0.271 0 Bhardaha Rupni 33 0 1 0.198 0 Rajbiraj Kunauli 34 0 1 0.271 0 Rajbiraj Rupni 35 0 1 0.271 0 Rupni Kadmaha 36 0 1 0.198 0 Kadmaha Gaighat 37 0 1 0.195 0 Gaighat Khotang 38 0 3 0.271 0 The cost,ck ij, of attempting an interdiction along arc ( i;j) was assumed to be directly proportional to the sum of the node populations ( PopSum ij) and to the distance 31 between the nodes ( Distij) given that covering long distances and monitoring activities involving large populations could be more costly. In this case study, we assume that the cost of interdiciton does not vary over time (i.e., ck ij=cij;8k2K) and equals cij=PopSum ijDistij: After calculating the cost for attempted interdicitons along each arc, the cost values were scaled to be between 1 and 20 (Table 4). Finally, each arc also has an associated probability of being successfully inter- dicted. While robust data to inform these parameter values does not exist, we estimate the initial interdiction success probabilities, p0, as a function of node population. This is based on Farrell et al. (2010), which surveyed law enforcement's perception of human tracking in their local area and concluded that agencies with human tracking train- ing were more prepared to address human tracking. Their ndings also indicate that, in general, the percentage of law enforcement personnel that have human tracking training is positively correlated with the population of the jurisdiction (Table 5). As such, we have assigned arc ( i;j) an interdiction probability equal to the training per- centage corresponding to the sum of the node iandjpopulations (see Table 4). Table 5: Population Probability Matrix Population Size Training as Probability Proxy 4,999 and below 12.4% 5,000-9,999 17.1% 10,000-24,999 19.5% 25,000-49,999 19.8% 50,000-74,999 17.1% 75,000-99,999 37.4% 100,000-249,999 27.1% 250,000 and above 65.1% See Farrell et al. (2010) for the full table. For this network, a heatmap of the expected pseudo-utility ratios that are used in the repair operation is given in Figure 7. Darker edges denote the arcs with higher expected pseudo-utility ratios. Since the arc capacity parameter is estimated iteratively by considering all paths through the network, the network structure e ects the arc's 32 Figure 7: Heatmap for the expected pseudo-utility ratios capacity and consequently e ects the pseudo-utility ratios. The corresponding pseudo- utility values are presented in Table 4. We acknowledge that the parameter estimation methods described in this section are a simplistic way to calculate how a tracker and an interdictor operate on the network, yet it serves the purpose of testing how the model behaves and algorithm works given that robust human tracking data is scarce. If more sophisticated and accurate ways to quantitatively measure these parameters are found, our model can be used with the updated parameters without needing to make fundamental changes to the modelling formulation. 5.2 Findings Since the parameters needed to implement this model remain an open research question in the human tracking eld, we solved instances with varying budgets and probability update rates for a two-stage model. We assume the budget remains the same in each stage. Since, GAs are not guaranteed to provide an optimal solution, we assessed the GA's performance for low budget instances that we were able to solve to optimality through enumeration. Starting with a budget of 3 and increasing the budget by 1 until it 33 was computationally infeasible for us to compute the optimal solution by enumeration. Table 6 shows the min-max ows at stage 1 (MMF1) and min-max ow at stage 2 (MMF2) under the optimal interdictions and the best results from 100 runs of the GA with budgets equalling 3, 4 and 5. The results indicate that the GA with a repair function is able to converge to optimal in 100 experiments for each setting regardless of the value of the update rate , which can be observed in Figure 8. Figure 8 also shows that MGA was able to nd the optimal solutions in most of the experiments. Budgets larger than 5 were prohibitively costly to calculate through enumeration. Although a provably optimal solution was not obtained for a budget of 10, we provide a population diversity graph in the Appendix to illustrate the diversity of the solutions when the algorithm terminated. We also present the performance of the GA and the MGA in the Nepal network just as we did for the grid networks in Figure 8 and notice a similar result: the MGA performs better than the GA and performance decreases with increasing budget. Figure 8: GA and Modi ed GA Performance on Nepal Network 5.2.1 Interdictors Becoming More Successful From Table 6, we can observe that when the success update parameter  0, it is best to follow the same interdiction strategy for both stages. This makes sense because the rst stage problem is minimizing the tracker's desirability of operating on the network subject to a budget constraint that is consistent in both stages. Since the prob- ability updates are positive (i.e.,  0), a successful interdiction will further increase 34Table 6: Results under Optimal Policy and GA Budget = 3 RateOptimal Solution GA SolutionMMF Di erence1st Int. MMF1 2nd Int. MMF2 Total MMF 1st Int. MMF1 2nd Int. MMF2 Total MMF 1.00 3,18 7.329 3,18 2.558 9.887 3,18 7.329 3,18 2.558 9.887 0.000 0.75 3,18 7.329 3,18 3.751 11.080 4,18 7.329 4,18 3.751 11.080 0.000 0.50 3,18 7.329 3,18 4.943 12.272 3,18 7.329 3,18 4.943 12.272 0.000 0.25 3,18 7.329 3,18 6.136 13.465 3,18 7.329 3,18 6.136 13.465 0.000 0.00 3,18 7.329 3,18 7.329 14.658 4,18 7.329 4,18 7.329 14.658 0.000 -0.25 3,18 7.329 4,18 8.283 15.612 3,18 7.329 4,18 8.283 15.612 0.000 -0.50 3,18 7.329 4,18 9.236 16.565 4,18 7.329 3,18 9.236 16.565 0.000 -0.75 3,18 7.329 4,18 10.190 17.519 3,18 7.329 4,18 10.190 17.519 0.000 -1.00 3,18 7.329 4,22 10.749 18.078 4,22 10.749 3,18 7.329 18.078 0.000 Budget = 4 RateOptimal Solution GA SolutionMMF Di erence1st Int. MMF1 2nd Int. MMF2 Total MMF 1st Int. MMF1 2nd Int. MMF2 Total MMF 1.00 3,18,22 6.478 3,18,22 2.044 8.522 3,18,22 6.478 3,18,22 2.044 8.522 0.000 0.75 3,18,22 6.478 3,18,22 3.077 9.555 3,18,22 6.478 3,18,22 3.077 9.555 0.000 0.50 3,18,22 6.478 3,18,22 4.160 10.638 3,18,22 6.478 3,18,22 4.160 10.638 0.000 0.25 3,18,22 6.478 3,18,22 5.294 11.771 3,18,22 6.478 3,18,22 5.294 11.771 0.000 0.00 3,18,22 6.478 3,18,22 6.478 12.956 3,18,22 6.478 4,18,22 6.478 12.956 0.000 -0.25 3,18,22 6.478 4,18,22 7.248 13.726 4,18,22 6.478 3,18,22 7.248 13.726 0.000 -0.50 3,18,22 6.478 4,18,22 8.053 14.531 3,18,22 6.478 4,18,22 8.053 14.531 0.000 -0.75 3,18,23 6.707 4,18,22 8.563 15.270 3,18,24 6.707 4,18,22 8.563 15.270 0.000 -1.00 3,18,23 6.707 4,18,22 9.258 15.965 3,18,23 6.707 4,18,22 9.258 15.965 0.000 Budget = 5 RateOptimal Solution GA SolutionMMF Di erence1st Int. MMF1 2nd Int. MMF2 Total MMF 1st Int. MMF1 2nd Int. MMF2 Total MMF 1.00 3,4,18 4.603 3,4,18 1.274 5.877 3,4,18 4.603 3,4,18 1.274 5.877 0.000 0.75 3,4,18 4.603 3,4,18 1.990 6.593 3,4,18 4.603 3,4,18 1.990 6.593 0.000 0.50 3, 4, 18 4.603 3,4,18 2.784 7.386 3,4,18 4.603 3,4,18 2.784 7.386 0.000 0.25 3, 4, 18 4.603 3,4,18 3.654 8.257 3,4,18 4.603 3,4,18 3.654 8.257 0.000 0.00 3,4,18 4.603 3,4,18 4.603 9.205 3,4,18 4.603 3,4,18 4.603 9.205 0.000 -0.25 3,4,18 4.603 3,4,18 6.578 11.181 3,4,18 4.603 3,4,18 6.578 11.181 0.000 -0.50 3,18,22,23 6.024 4,18,22,24 7.288 13.313 4,18,22,28 6.024 3,18,22,23 7.288 13.313 0.000 -0.75 1,3,18 6.194 4,18,22,23 7.697 13.891 1,3,18 6.194 4,18,22,24 7.697 13.891 0.000 -1.00 1,3,18 6.194 4,18,22,23 8.254 14.449 1,3,18 6.194 4,18,22,24 8.254 14.449 0.000 Budget = 10 RateOptimal Solution GA SolutionMMF Di erence1st Int. MMF1 2nd Int. MMF2 Total MMF 1st Int. MMF1 2nd Int. MMF2 Total MMF 1.00 NA NA NA NA NA 3,4,8,18,22,23,26,28 2.683 3,4,8,12,18,22,23,28 0.419 3.102 NA 0.75 NA NA NA NA NA 3,4,8,18,22,23,26,28 2.683 3,4,8,12,18,22,23,26 0.844 3.526 NA 0.50 NA NA NA NA NA 3,4,8,18,22,23,24,28 2.643 3,4,8,12,18,22,23,28 1.362 4.005 NA 0.25 NA NA NA NA NA 3,4,6,18,22 2.800 3,4,8,12,18,22,23,24 2.174 4.974 NA 0.00 NA NA NA NA NA 3,4,8,18,22,23,24,28 2.643 3,4,8,18,22,23,24,28 2.643 5.577 NA -0.25 NA NA NA NA NA 3,4,8,18,22,23,24,28 2.643 3,4,12,18,22,23,24,28 4.121 6.764 NA -0.50 NA NA NA NA NA 3,6,18,22,23,24 2.934 3,4,18,22,23,24,26,28 4.084 7.018 NA -0.75 NA NA NA NA NA 3,4,8,9,18,22,24 2.885 3,6,18,22,23,28 5.820 8.705 NA -1.00 NA NA NA NA NA 3,6,8,18,22,23 3.298 3,4,18,22,23,24,26,28 5.740 9.038 NA 35 the likelihood of successfully interdicting the same arc in future stages. Therefore, the optimal rst stage policy becomes even more attractive in the second stage. This is also observed in Figure 9, which illustrates how the rst and second stage objective functions behave as the success rate parameter  varies. It illustrates that since successful interdictions become even more successful in future stages when 0<, the tracker's desire to operate on the network decreases in the second stage. Figure 9: Optimally interdicted ow under budget = 5 5.2.2 Trackers Adapting However, in the case where the tracker is learning from the interdictions and adapting accordingly (i.e.,  <0), interdicting di erent arcs for each stage might yield a better total expected min-max ow over the planning horizon than following the same strategy for both stages since successfully interdicted arcs become less successful in future stages. In the case of  <0, as the budget increases and the  gets closer to 1, the optimal strategy is to be less aggressive in the rst stage, relative to the cases where  is higher. This results in the trade o of allowing more ow through the network in the rst stage in order to preserve some e ective interdictions for the next stage. We can observe this by noticing that the optimal rst stage interdiction decision when  = 1 allows more tracking ow than when  = 0:5 for budgets greater than or equal to 4. (This can be seen from both Table 6 and Figure 9.) This means that even though there exist interdiction decisions that would decrease the tracking in Stage 1 more, these decisions would produce a worse outcome in the second stage and allow for a greater amount of tracking to occur overall. 36 Since the optimal rst and second stage interdiction decisions are the same when 0< but may di er when  <0, we investigate how much of a di erence not following the optimal interdiction strategy would make when  <0. We do this by assuming the interdictor is not changing strategies and continues to implement the initial stage's best interdiction policy assuming the success change rate is 0, when in actuality it is negative. Observations under this problem instance showed that acknowledging the ability of the tracker to adapt and change the interdiction strategy accordingly can reduce the total expected maximum minimum ow by up to 40%, depending on the rate and the interdiction budget (see Table 7). Figure 9 also illustrates that when  <0 and trackers learn from successful interdictions, the network becomes more desirable for trackers to operate on over time. However, it is important to note that while the network becomes more desirable to trackers in the second stage as compared to the rst, it is still less desirable than a network that was never interdicted. That is, even though interdictions become less successful over time, it is still bene cial to pursue interdictions rather than not doing anything. Similar patterns are observed for other budget values. 6 Conclusion and Future Work This paper introduces a multi-stage stochastic network interdiction model with decision-dependent success probabilities to aid in anti-human tracking disruption ef- forts. The tracker's movement throughout a physical network is captured using a maximum ow problem where the traditional arc capacity parameters are rede ned to be a proxy for the desirability of a tracker to operate along the arc. An interdictor| which could include law enforcement, healthcare personnel, non-pro t organizations, service providers, or policy makers|attempts to disrupt the tracking network by in- terdicting arcs. To capture the uncertain nature of interdiction attempts, we assume there is a positive probability that an interdiction attempt may be unsuccessful. We also consider that the success probability is a function of prior interdiction decisions and may change over time as trackers or interdictors learn more information about the network. In other words, the expertise and knowledge we aim to utilize in this model are tracking estimations over a region, estimations about the probability of success for the tracking interdiction, and how this probability will change based on previous actions in the same region. To solve the resulting nonlinear model, we developed a GA and Modi ed GA that uses expected pseudo-utility ratios in its repair operation. 37Table 7: Optimal Interdictions vs Fixed Interdictions Budget = 3 RateOptimal Solution Assume 1st Stage Solution = 2nd Stage SolutionMMF Di erence % MMF Di erence1st Int. MMF1 2nd Int. MMF2 Total MMF 2nd Int. MMF2 Total MMF -0.25 3,18 7.329 4,18 8.283 15.612 3,18 9.554 16.883 1.271 8.1 -0.50 3,18 7.329 4,18 9.236 16.565 3,18 11.779 19.108 2.543 15.4 -0.75 3,18 7.329 4,18 10.190 17.519 3,18 14.004 21.333 3.814 21.8 -1.00 3,18 7.329 4,22 10.749 18.078 3,18 16.229 23.558 5.480 30.3 Budget = 4 RateOptimal Solution Assume 1st Stage Solution = 2nd Stage SolutionMMF Di erence % MMF Di erence1st Int. MMF1 2nd Int. MMF2 Total MMF 2nd Int. MMF2 Total MMF -0.25 3,18,22 6.4778 4,18,22 7.248 13.726 3,18,22 8.520 14.997 1.271 9.3 -0.50 3,18,22 6.4778 4,18,22 8.053 14.531 3,18,22 10.596 17.074 2.543 17.5 -0.75 3,18,22 6.7071 4,18,22 8.563 15.270 3,18,22 12.708 19.415 4.145 27.1 -1.00 3,18,22 6.7071 4,18,22 9.258 15.965 3,18,22 14.855 21.562 5.597 35.1 Budget = 5 RateOptimal Solution Assume 1st Stage Solution = 2nd Stage SolutionMMF Di erence % MMF Di erence1st Int. MMF1 2nd Int. MMF2 Total MMF 2nd Int. MMF2 Total MMF -0.25 3,4,18 4.6026 3,4,18 6.578 11.181 3,4,18 6.578 11.181 0.000 0.0 -0.50 3,4,18 6.0244 4,18,22,24 7.288 13.313 3,4,18 8.823 14.848 1.535 11.5 -0.75 3,4,18 6.1941 4,18,22,23 7.697 13.891 3,4,18 11.338 17.532 3.641 26.2 -1.00 3,4,18 6.1941 4,18,22,23 8.254 14.449 3,4,18 14.122 20.316 5.867 40.6 38 The two-stage version of our model was tested on a case study of a tracking network in the Eastern Development Region of Nepal. Results indicate that the traf- cker's ability to adapt to previous interdictions is a driving factor in determining the optimal interdiction policy over time. If the tracking operation is unable to adapt to disruptions such that the interdictor becomes more successful at interdicting as time progresses, the optimal interdiction strategy is to interdict the same arcs in the rst and second stage. However, if the tracker learns from successful interdictions, thereby reducing the e ectiveness of future interdictions along the same arcs, it is often optimal to interdict di erent arcs in the rst and second stages. One valid concern regarding the applicability of the present model is the avail- ability of data it requires, given the hidden/covert nature of human tracking. In many communities, there is currently a lack of data and understanding about track- ing ows. However, more communities are starting to understand the value of collecting data related to human tracking operations and operational knowledge of tracking is increasing. Thus, this model highlights the bene t of collecting such data so that decision-makers can utilize this knowledge to develop e ective interdiction plans in a cost restrained environment. To the best of our knowledge, our model is the rst network interdiction model tailored to disrupting physical human tracking networks. As such, we acknowledge that there are multiple limitations of our model; human tracking network structures and operating dynamics largely remain an open research question, which limits the input data available for network interdiction models. In light of this gap, we have generated estimates of model parameters based on the current human tracking literature. It is our hope that this model serves as illustration of the types of practice and policy insights that can be obtained if more robust human tracking data was available and provides motivation for interdisciplinary research to collect such data. There are many nuances of human tracking that motivate the need for further extensions of our model to capture the growing knowledge of human tracking networks. As an example, we are currently working on extending the present model to incorporate collaboration and information sharing among multiple anti-tracking stakeholders each seeking to disrupt a tracker's operation. Another extension can address the sequential nature of the interdictor and traf- cker decisions. In the current problem, the interdictor makes a decision and only after observing the outcome of this decision does the tracker determine how to maximize 39 their ow through the network. This assumption is somewhat limiting as trackers and interdictors often do not have full knowledge of each others actions and do not alternate making decisions. As such, network interdiction literature related to dynamic games in which players do not have static strategies could be incorporated into the current model (Lunday & Sherali, 2010; Fischetti et al., 2018; Zhang et al., 2018). Furthermore, loosening the assumption that a tracker optimizes their use of the network should also be considered; in reality, the tracker might take random or partially informed actions on the network. In conclusion, network interdiction models are uniquely positioned to aid in disrupting human tracking networks. To e ectively use this methodology, additional research is needed to obtain robust data to serve as input into the network interdiction models and current network interdiction theory must continue to evolve to capture the nuances of human tracking. Acknowledgements This work was supported in part by the National Science Foundation under Grant No. 1838315. The opinions expressed in the paper do not necessarily re ect the views of the National Science Foundation.