New Perspectives on the Optimal Placement of Detectors for Suicide Bombers using Metaheuristics††thanks: This work issupported by the Spanish Ministerio de Economía and European FEDER underProjects EphemeCH (TIN2014-56494-C4-1-P) andDeepBIO (TIN2017-85 (2024)

∎

¹¹institutetext: C. Cotta ²²institutetext: J.E. Gallardo ³³institutetext: ETSI Informática, Universidad de Málaga, Campus de Teatinos, 29071 Málaga (Spain)
Tel.: +34 952137158 / +34 952132795
Fax: +34 952131397
³³email: {ccottap,pepeg}@lcc.uma.es

Carlos Cotta José E. Gallardo

(Received: date / Accepted: date)

Abstract

We consider an operational model of suicide bombing attacks –an increasingly prevalent formof terrorism– against specific targets, and the use of protective countermeasures based on the deploymentof detectors over the area under threat. These detectors have to be carefully located in order tominimize the expected number of casualties or the economic damage suffered, resulting in ahard optimization problem for which different metaheuristics have been proposed. Rather than assumingrandom decisions by the attacker, the problemis approached by considering different models of the latter, whereby he takes informeddecisions on which objective must be targeted and through which path it has to be reached basedon knowledge on the importance or value of the objectives or on the defensive strategy of the defender(a scenario that can be regarded as an adversarial game). We consider four different algorithms,namelya greedy heuristic, a hill climber, tabu search and an evolutionary algorithm, and study theirperformance on a broad collection of problem instances trying to resemble different realistic settingssuch as a coastal area, a modern urban area, and the historic core of an old town. It is shown thatthe adversarial scenario is harder for all techniques, and that the evolutionary algorithm seems toadapt better to the complexity of the resulting search landscape.

Keywords:

Suicide Bombing Optimal Detector Placement Greedy Heuristics Metaheuristics Decision Making

^†^†journal: Natural Computing

1 Introduction

The threat of international terrorism has been present for many decades now, but ever sincethe collapse of the Eastern bloc in the late 1980s and the subsequent end of the Cold War it has emergedas the major factor of instability and social disruption at a global scale, be it directly asa consequence of terrorist actions or indirectly as a result of the countermeasures requiredto prevent the former and the impact of these in our daily lives (not to mention themilitary operations targeting terrorist groups and regimes supporting them, which inthemselves contribute both to local turmoil and social unrest). Indeed, the newinternational environment arising from the end of the Atlantic/Easternbloc dialectic (e.g., easier and increased communications and travel, larger citizen mobility,etc.) and the technical advances that took place in the end of the 20th century were readilyexploited by terror groups to bring their criminal actions to a new level. As a response,democratic nations have typically engaged in a counterterrorist policy which can be describedwithin the framework of the 4Dstrategy (Central Intelligence Agency, 2003): Defeat (proactively attack the structure of terrorist organizations), Deny(precludethe access to any kind of support –political, financial, etc.– and resources for undergoingterrorist attacks), Diminish (minimize the underlying conditions that serve as a breedingground for the emergence of terrorists groups) and Defend (protect the society,the citizens and their interests).

We are particularly concerned here with the last of the four Ds, namelythe defensive component. This constitutes a challenge in light of thenon-conventional means used by terrorists to conduct their infamousactions. Most conspicuously, suicide bombings have established themselvesas a particularly important menace (Chicago Project on Security and Terrorism(2016), CPOST), given their lethality (they causeabout four time more casualties than other kinds of terrorist attacks(Rand Corporation, 2009; Edwards etal, 2016)), simplicity (their nature makes escaping logisticsand equipment for remote operation unneeded), and effectiveness ininstilling fear and cause social disruption (Hoffman, 2003).Defense from this kind of attacks (and from any other of terroristattack for that matter) is a highly cross-disciplinary endeavor that can beapproached from many points of views. One of them is undoubtedlythe understanding of these actions, not just of the means but also ofthe motivations. While the later can be contentious in nature, it canbe nevertheless approached at a meta-level, focusing not just on theprecise motivations but on the framework in which these motivationssubstantiate into actions. In this sense, there are two main schoolsof thought: the psychological-sociological and the political-rational approach(Ganor, 2011). While the former focus on social group dynamics and the psychologicalprofile of individuals, the latter views terrorism as a rational methodof operation for pursuing concrete political goals. Without denying theinterest of the former (which can be useful for, e.g., detecting radicalizationof particular individuals or understanding their activity patterns –see (Lara-Cabrera etal, 2017; Leistedt, 2016; Tutun etal, 2017)),the latter can be particularly interesting from a tactical point of view, that is,when it comes to implementing measures to make attacks unsuccessful. Indeed,many details of a terrorist attack can be dictated by rational calculationsand cost-benefit analysis, much like it would be done by a military staffor a corporate board (Blomberg etal, 2004).

In line with the previous line of reasoning, both the actions of the terroristsand the countermeasures taken to neutralize the former can be regarded asaimed to optimize (in different senses, obviously) some utility function, such asthe number of civilian casualties or the economic damage caused in theinfrastructures. Thisapproach has been precisely considered in some works in the literature. Thus,Nie etal (2007) considered –followingthe seminal work by Kaplan and Kress (2005)– the case of an area under threat of a suicidebombing attack and the deployment of some kind of sensors (tailored to detect traces ofexplosives in their proximity (Gares etal, 2016)) in order to protect specific known targets. To thisend, they proposed a branch-and-bound (BnB) algorithm and a greedy constructiveheuristic to determine the location of these sensors so as tominimize the casualties. This same approach was also appliedby Yan and Nie (2016) to a scenario involving maritime targets underthreat of small vessels. Following these results, Cotta and Gallardo (2017)approached the problem from the point of view of metaheuristics, showing thatthese could outperform the greedy heuristic and tackle problem scenariosuntenable for BnB.

One of the central tenets of these works was a simplistic assumptionon the strategy of the terrorist (whom we should refer to in the following asattacker) whereby the target would be randomly selected. In somesense, this could capture a total-ignorance scenario in which the defensiveforces (the defender in the following) are oblivious to the attacker’sstrategy and so is the attacker with respect to the importance of each targetor the defender’s strategy. We here challenge this assumption and considerother scenarios in this regard, and how these impact the resultingoptimization task for the greedy heuristic and several metaheuristics.Before presenting these algorithms and the experimental setup,let us firstly describe in detail the underlying problem, and how the strategyfor decision-taking is established. This is done in nextsection.

2 Definition of the Problem

As anticipated in the previous section, the main point under scrutiny in this work is thestrategy followed by the attacker in order to select a target. Before describing how wehave modelled the latter, let us firstly describe the basic setting of the model considered.

2.1 Basic Setting

Our goal is to protect a given area under threat, strategically placing detectors insome points in order to detect and neutralize attackers. To this end, we assume thisarea is discretized into a rectangular grid ${A}=\{A_{ij}\}_{m\times n}$ . This discretizationallows to determine which portions of the area (to which we shall refer to in the followingas map) are walkable (or from a more general point of view, accessible)and which ones are inaccessible. The former representopen spaces through which the attacker can pass and in which we could also place adetector. As to the latter, they represent any physical obstruction (walls, buildings, streetfurniture, etc.) that cannot be traversed by the attacker. Some positions in the map willalso represent objectives or targets, that is, sensitive points in which a certain numberof individuals are present and that may be subject to attack. Access to the map is done throughspecific positions or entrances, which are typically placed in the boundaries of the grid(but that could in principle be placed anywhere on the grid – think for example in anunderground passage or metro entrance). Given a certain entrance and a certainobjective, the attacker is assumed to follow a shortest path between these twopoints (Nie etal, 2007; Kim etal, 2016), using the center of grid cells aspotential waypoints, and avoiding any path intersecting with a blocked (i.e., inaccessible)cell of the grid – see (Cotta and Gallardo, 2017) for a brief discussion on these assumptions.In this context, it is easy to construct a weighted graph from a given map, in which verticesrepresent grid positions, edges indicate direct accessibility (i.e., the attacker could walkbetween these two points in a straight line without intersecting an obstacle), and edgeweights correspond to distances. This graph can in turn be used to compute shortest pathsfrom entrances to objectives, e.g., using Dijkstra’s algorithm or any other suitable method.

$\varepsilon$	number of entrances	$e_{i}$	the $i$ -th entrance
$\phi$	number of objectives	$o_{j}$	the $j$ -th objective
$\delta$	number of detectors	$d_{k}$	the $k$ -th detector
$v$	speed of the attacker	$t_{n}$	time required to neutralize
$\eta$	detector’s instantaneous detection rate	$\theta$	probability of neutralization
$P_{ij}$	the path between entrance $e_{i}$ and objective $o_{j}$	$\bar{P}_{ij}$	portion of $P_{ij}$ in which neutralization is still possible.
$l_{ijk}$	portion of $\bar{P}_{ij}$ inside the detection radius of detector $d_{k}$	$p_{ijk}$	probability of $d_{k}$ detecting the attacker through $\bar{P}_{ij}$
$\tilde{D}_{ij}$	probability of non-detection along $P_{ij}$	$C_{j}$	population at objective $o_{j}$
$W_{ij}$	expected number of casualties for $P_{ij}$	$\gamma_{ij}$	probability that the attacker picks $P_{ij}$

New Perspectives on the Optimal Placement of Detectors for Suicide Bombers using Metaheuristics††thanks: This work issupported by the Spanish Ministerio de Economía and European FEDER underProjects EphemeCH (TIN2014-56494-C4-1-P) andDeepBIO (TIN2017-85727-C4-1-P).††thanks: This document is a preprint of Cotta, C., Gallardo, J.E. New perspectives on the optimal placement of detectors for suicide bombers using metaheuristics. Nat Comput 18, 249–263 (2019). https://doi.org/10.1007/s11047-018-9710-1 (1)

As mentioned before, the defense strategy is to place some detectors $d_{1},\dots,d_{\delta}$ on the map. Each of these detectors is characterized by a detection radius $\tau$ , meaning thatany attacker path intersecting the circle of radius $\tau$ centered at the detector is prone to fire an alarmthat would elicit a neutralization response. Both events, alarm firing and neutralization are notdeterministic in order to capture detector reliability and neutralization effectiveness respectively.More precisely, the alarm is fired with a probability that will be larger the longer the section of the pathincluded in this detection circle, and the subsequent neutralization attempt will be successfulwith some probability $\theta$ . This can be formalized as follows (see Table1 foran overview of the notation used): let $P_{ij}$ be the shortest pathbetween the $i$ -th (out of $\varepsilon$ ) entrance $e_{i}$ and the $j$ -th (out of $\phi$ ) objective $o_{j}$ ;if the attacker was too close to the objective within this path, no neutralization would be possible(he would reach the target before the enforcing agents could get to him), so let $\bar{P}_{ij}$ bethe portion of the path $P_{ij}$ in which neutralization is still possible (assuming the attacker moves atspeed $v$ and that $t_{n}$ seconds are required to neutralize him (Kaplan and Kress, 2005), this amountsto detracting a segment of length $vt_{n}$ from the end of $P_{ij}$ ). For each detector $d_{k}$ , let $l_{ijk}$ be the portion of $\bar{P}_{ij}$ subject to detection by $d_{k}$ (see Figure1 for an illustration), an event that will take place with probability

p_{ijk}=1-\exp(-\eta l_{ijk})

(1)

where $\eta>0$ is the detector’s instantaneous detection rate. Following (Nie etal, 2007), detectorswork independently of one another, and therefore the totalprobability of non-detection $\tilde{D}_{ij}$ for path $P_{ij}$ is

\tilde{D}_{ij}=\prod_{k=1}^{\delta}(1-p_{ijk})=\prod_{k=1}^{\delta}\exp(-\eta l%_{ijk})=\exp(-\eta\sum_{k=1}^{\delta}l_{ijk})

(2)

In this case (non-detection) or in case the attacker is detected but not effectivelyneutralized (something that willhappen with probability $1-\theta$ ), the attacker will reachthe objective $o_{j}$ causing a number of casualties $C_{j}$ . Thus,the expected number ofcasualties $W_{ij}$ for this particular path will be

W_{ij}=\tilde{D}_{ij}C_{j}+(1-\tilde{D}_{ij})(1-\theta)C_{j}=C_{j}\left[\tilde%{D}_{ij}\theta+(1-\theta)\right]

(3)

The total expected number of casualties will take into account allpossible paths $P_{ij}$ the attacker can take, that is, betweenany entrance $e_{i}$ and objective $o_{j}$ . To estimate this, let $\gamma_{ij}$ be the probability the attacker chose a particular path $P_{ij}$ . Then,

W=\sum_{i=1}^{\varepsilon}\sum_{j=1}^{\phi}\gamma_{ij}W_{ij}

(4)

Next section will consider different scenarios depending on the particular modelizationof values $\gamma_{ij}$ , which capture the strategy used by the attacker to selecta particular course of action.

2.2 Tackling Decision Making

The choice of values $\gamma_{ij}$ can be used to prioritize some targets and paths above others, and hence embodiesthe decision-making process done by the attacker. In previous works, i.e., (Nie etal, 2007; Yan and Nie, 2016; Cotta and Gallardo, 2017),a very simple approach was considered, namely that the attacker would pick with constant uniform probability any of these paths, thatis,

\gamma_{ij}=\frac{1}{\varepsilon\phi}.

(5)

This can be regarded as a completely blind strategy in which the attacker isfully oblivious to both the damage that can be inflicted by targeting a particular objective or by the potential countermeasurestaken by the defenders, and hence can be arguably considered as unrealistic. To tackle this issue, let us consider moreinformed strategies that take the previous points into account.

Let us firstly focus on the importance of each of the objectives. From the point of view of the attacker this is capturedby values $C_{j}$ that indicate the population at objective $o_{j}$ (but that in a more general context could be also used to modelany other feature of objectives whereby their targeting would be valuable for the attacker). An objective-aware strategy wouldthus preferably pick objectives of higher value over those with lower value. This can be done in a variety of ways, bothfrom a qualitative point of view (considering the actual values $C_{j}$ or only their relative importance as in, e.g., their positionin a ranked list) and from a quantitative point of view (given a certain prioritization index, how these are mapped to actualprobabilities, thus determining how much preference is given to any objective). As a first step, in this work we have considereda strategy based on using the actual values $C_{j}$ and defining a proportional selection scheme based on these, i.e.,

\gamma_{ij}=\frac{C_{j}}{\varepsilon\sum_{k=1}^{\phi}C_{k}}

(6)

Thus, any objective $o_{j}$ will be targeted with a probability $p_{j}=\sum_{i=1}^{\varepsilon}\gamma_{ij}=C_{j}/C$ , where $C=\sum_{k=1}^{\phi}C_{k}$ is the combined value of all objectives, i.e., $p_{j}\propto C_{j}$ , being all paths to thisobjective equiprobable (again, more sophisticated strategies could be thought of here, but we initially assume this forsimplicity).

Going one step beyond, let us consider awareness by the attacker of the presence of detectors. A game-theory perspectivewould be possible here, by considering that the attacker would select values $\gamma_{ij}$ to maximize his benefit (theinflicted damage) given whatever knowledge he has about the position of the detectors (or more generally about the strategyused by the defender to place these), and the defender would in turn place the detectors to minimize his loss given the knowledgehe has about the attacker strategy. If we define $W[\Gamma,\Delta]$ to be the total number of casualties implied by a particular collection $\Gamma$ of values $\gamma_{ij}$ and a particular placement $\Delta$ of the detectors (i.e., a version of Equation4 parameterized by $\Gamma$ and $\Delta$ ), we can see that the solution $(\Gamma^{*},\Delta^{*})$ given by

	$\displaystyle\Gamma^{*}$	$\displaystyle=$	$\displaystyle\underset{\Gamma}{\operatorname{arg\,max}}{\left(W[\Gamma,\Delta%^{}]\right)}$		(7)
	$\displaystyle\Delta^{*}$	$\displaystyle=$	$\displaystyle\underset{\Delta}{\operatorname{arg\,min}}{\left(W[\Gamma^{},%\Delta]\right)}$		(8)

defines a Nash equilibrium state: given a certain location $\Delta^{*}$ of the detectors, any different choice of values $\gamma_{ij}$ would result is less damage (i.e., a loss for the attacker), and conversely given the attacker’s strategy any other placement of thedetectors would result in larger damage (i.e., a loss for the defender). Notice however that we are adopting here the position of thedefender, and in principle it is not realistic to assume perfect knowledge of the attacker (although we can assume as a worst case scenario that the attackerhas indeed this knowledge about the defender). Thus, if we place detectors at positions given by $\Delta$ , we can assume that the attacker wouldpick $\Gamma$ to inflict the highest damage as indicated by Equation7. It then follows that we should pick

\Delta^{\circ}=\underset{\Delta}{\operatorname*{arg\,min}}{\left(\underset{%\Gamma}{\max}(W[\Gamma,\Delta])\right)}

(9)

In order to compute the term inside the outer parentheses in the previous equation we could exploit the fact that $W[\Gamma,\Delta]$ is linearin values $\gamma_{ij}$ and solve a linear program given by

\max W[\Gamma,\Delta]=\max\sum_{i=1}^{\varepsilon}\sum_{j=1}^{\phi}\gamma_{ij}%W[\Delta]_{ij}

(10)

subject to

	$\displaystyle\sum_{i=1}^{\varepsilon}\sum_{j=1}^{\phi}\gamma_{ij}$	$\displaystyle=$	$\displaystyle 1$		(11)
	$\displaystyle 0\leqslant\gamma_{ij}$	$\displaystyle\leqslant$	$\displaystyle 1\qquad\forall i\in\{1,\dots,\varepsilon\},j\in\{1,\dots,\phi\}$		(12)

where $W[\Delta]_{ij}$ is the value given by Equation3 parameterized by $\Delta$ . We do not need to use a linear programmingsolver though, since the solution to Equation10 can be shown to be

\gamma_{ij}=\begin{cases}1&W[\Delta]_{ij}=\underset{i^{\prime}j^{\prime}}{\max%}{(W[\Delta]_{i^{\prime}j^{\prime}})}\\0&{\rm otherwise}\end{cases}

(13)

i.e., the probability would be concentrated on the path that leads to the largest expected number of casualties (which we shall termthe critical path) given thecurrent distribution $\Delta$ of detectors.This follows easily from the fact that $W[\Gamma,\Delta]$ is a convex combination of values $W[\Delta]_{ij}$ . Let $i^{\circ},j^{\circ}$ be the indicescorresponding to the critical path (i.e, $\gamma_{i^{\circ}j^{\circ}}=1,\gamma_{ij}=0$ otherwise).The resulting value of Equation10 for this solution would be $W[\Delta]_{i^{\circ}j^{\circ}}$ , which by virtue of Equation13 is no smallerthan any other $W[\Delta]_{ij}$ , $i,j\neq i^{\circ},j^{\circ}$ . Thus, for any other alternative solution with $\gamma_{i^{\circ}j^{\circ}}=1-\alpha$ , $0<\alpha\leqslant 1$ ,we would have the objective function decreased by $\alpha W[\Delta]_{i^{\circ}j^{\circ}}$ and increased at most by $\alpha W[\Delta]_{i^{\prime}j^{\prime}}$ where $W[\Delta]_{i^{\prime}j^{\prime}}$ is the second largest expected number of casualties, and hence the resulting value of the objectivefunction would be reduced.

Computing the global minimum as per Equation9 is not trivial, and will be dealt with in next section via heuristic approaches.Let us anyway assume that we have found this $\Delta^{\circ}$ , and let $\Gamma[\Delta^{\circ}]$ be the corresponding path probabilities followingEquation13. We can see that in purity the state given by $(\Gamma[\Delta^{\circ}],\Delta^{\circ})$ is not a Nash equilibrium point: if $\Delta^{\circ}$ isfixed it is certainly the case that the attacker would not benefit from picking different path probabilities as shown before; however,taking these path probabilities as fixed, the defender could in general reduce the damage by relocating the detectors so as to have bettercoverage of the critical path. This may result in this path no longer being the critical path, hence implying the attacker would pick adifferent $\Gamma$ ; therefore, in general there may not be a Nash equilibrium. At any rate, this point $(\Gamma[\Delta^{\circ}],\Delta^{\circ})$ does indeed capture some kind of equilibrium, were we toassume that the attacker knows the defender’s strategy, namely that the worst-case casualties are to be minimized without taking any risksand vice versa, i.e., thedefender knows the attacker will act accordingly to maximize his goals, each one being also aware of their own strategy being known bythe opponent.

3 Materials and Methods

In light of the problem setting defined in the previous section, we need to solvethe problem from the perspective of the defender by defining the locationof each of the detectors. This will be done by using different (meta)heuristic approachesas shown below. In all cases, the objective will be minimizing Equation4, namelythe expected number of casualties $W[\Gamma,\Delta]$ . As shown before, this quantity depends on thelocation of the detectors $\Delta$ (which is the actual degree of freedom of the formula, that is,the part of the equation that will be decided by the optimization algorithm) and thepath probabilities $\Gamma$ (which will be given by any of the two scenarios depicted before,that is, fixed and known in advance to be proportional to the importance of each objective,or variable and known to correspond to the critical path implied by the current locationof detectors). Next we will provide more details about the algorithms considered forthis optimization endeavor, as well as about the benchmark we have used to test these.

3.1 Algorithmic Approaches

In this section we describe different algorithmic approaches that we have considered in order to tackle the problem, namely a Greedy Algorithm, a Local Search Procedure, a Tabu Search Metaheuristic and an Evolutionary Algorithm.

In all cases, the computational cost needed to evaluate a solution can be significantly reduced if some preprocessing is done over the problem instance being considered before starting the optimization process itself. This preprocessing is the same for all the algorithms and thus affects in the same way their performances.More precisely, a cache memory has been precomputed corresponding to the length of the segment of a path that would be detected in case a detector were placed at a specific cell in the map. These intersecting lengths are independently stored for each possible path going from one of the entrances in the map to one of the objectives. Besides, a dominance memory ${\Delta}=\{\Delta_{ij}\}_{m\times n}$ is also used to prune to some extent the search space that should be explored in order to optimize an specific instance. The implementations of both of these memories are more precisely described in (Cotta and Gallardo, 2017) and we refer the reader to that work for full details.

3.2 Greedy Algorithm

The algorithm described in this section (denoted as Greedy) corresponds to the one originally proposed by Nie etal (2007). This algorithm is a constructive method hence it places on the map the $\delta$ detectors one after the other. The extension of the current partial solution is done by adding on each step the detector which leads to a better local extension.

Input: $\delta$ (number of detectors to be placed)

1 $\mathit{candidates}:=\{(r,c)\ |\ 1\leqslant r\leqslant m,1\leqslant c\leqslantn%,A_{rc}$ is unblocked $,\Delta_{r,c}<\delta\}$ ;

2 $\mathit{sol}:=\varnothing$ ;

3while $\mathit{length}(\mathit{sol})<\delta$ do

4 $\mathit{fitness}^{*}:=\infty$ ;

5 $\mathit{detector}^{*}:=\mathrm{null}$ ;

6for $d\in\mathit{candidates}$ do

7 $\mathit{tentative}:=\mathit{sol}+\{d\}$ ;

8if $\mathit{value}(\mathit{tentative})<\mathit{fitness}^{*}$ then

9 $\mathit{detector}^{*}:=d$ ;

3.3 Hill Climbing

We also consider a Hill Climbing (HC) Local Search algorithm. In contrast to constructive methods –such as the Greedy method described above– which work with a partial solution, these algorithms work with a complete solution during the optimization process (Aarts and Lenstra, 1997; Hoos and Stützle, 2005). A crucial concept here is that of neighborhood which refers to the set of solutions which can be obtained from current one by modifying one part of the solution. The algorithm starts from a complete solution that should be constructed somehow. Subsequently, solutions in the neighborhood of the current one are examined and evaluated and a move towards one of these is performed in case the quality of such solution improves the current one. This process will be repeated until no solution in the neighborhood of the current one provides any improvement. At this point, a local optimum to the problem has been found and is returned. The whole process can be iterated starting from different initial solutions until the allowed execution time is exhausted, returning the best found solution at the end.

The pseudo-code for this procedure is shown in Algorithm2. $sol$ stands for a complete solution, implemented as avector of different locations for placing the detectors. The algorithm explores the neighborhood of the current solution by substituting one detector locationin the current solution by each of the unused candidate locations for the problem instance( $\textsc{Replace}(\mathit{sol},i,d)$ denotes the solution that is obtained by replacing the $i$ -thdetector in solution $\mathit{sol}$ by the alternative detector $d$ – see line 7). Then the best modified solution is selected (lines 8-11). If this selected solution is better than the current one, a move is done towards the new solution (line 9) and an improvement has been achieved (line 10). Starting from this improved solution, the same procedure is done for the remaining detectors, and this process is repeated until a local optimum is reached, i.e., when no further improvement is possible.

Input: $\mathit{sol}$ (a collection with the coordinates of $\delta$ detectors)

1 $\mathit{candidates}:=\{(r,c)\ |\ 1\leqslant r\leqslant m,1\leqslant c\leqslantn%,A_{rc}$ is unblocked $,\Delta_{rc}<\delta\}$ ;

2 $\mathit{improvement}:=\mathrm{true}$ ;

3while $\mathrm{improvement}$ do

4 $\mathit{improvement}:=\mathrm{false}$ ;

5for $i:=1$ to $\mathit{length}(\mathit{sol})$ do

6for $d\in(\mathit{candidates}\setminus\{d\,|\,d\in\mathit{sol}\})$ do

7 $\mathit{tentative}:=\textsc{Replace}(\mathit{sol},i,d)$ ;

8if $\mathit{value}(\mathit{tentative})<\mathit{value}(\mathit{sol})$ then

9 $\mathit{sol}:=\mathit{tentative}$ ;

10 $\mathit{improvement}:=\mathrm{true}$ ;

12 end if

14 end for

16 end for

18 end while

19return $\mathit{sol}$ ;

3.4 Tabu Search

Tabu Search (TS) is a metaheuristicoriginally proposed by Glover (1989, 1990) that has beensuccessfully used for the resolution of different combinatorial optimization problems. The key idea in TS is to use a memory data structure in order to keep track of the previous history of the search. This memory is referred to asthe Tabu List, as moves towards solutions included in this list areforbidden. This memory serves the purpose of avoidingrevisiting recently explored solutions, thus allowing the algorithm to avoid to a certain extent the possibility of getting trapped in cycles during the search process. At each iteration, the search moves towards the best solution in the neighborhood of allowed moves. Since all improving solutions may be forbidden, moves towards solutions worse than the current one may be performed and this is the mechanism allowing the algorithm to escapefrom local optima. As keeping all visited solutions in a list is not memory efficient, an usual alternative consists of using a datastructure keeping track of attributes of recently visited solutions, and forbidding moves towards solutions with those sameattributes for some iterations (the so called tabu tenure).

Our implementation of a TS algorithm is shown in Algorithm3. A solution corresponds to a vector with $\delta$ locations. The neighborhood of a solution consists of all solutions that can be obtained from that one by moving one of its detectors to another location not included in the solution. As tabu structure, we use a matrix ${T}=\{T_{ij}\}_{m\times n}$ so that $T_{ij}$ records tabu information for doing a move consisting in placing a detector at cell $i\times j$ in the map. $\mathit{sol}$ is the solution currently being explored and $\mathit{best}$ is the best solution found so far. The algorithm repeats the following process, with a limit on the number of iterations to perform in case no improved solution is attained:

•
All moves leading to solutions in the neighborhood of the current one which are not currently tabu are considered and those producing solutions with the best value are collected into $\mathit{bestMoves}$ set (lines 5-18). Additionally, if one solution in the neighborhood is better than the best one found so far (the so named aspiration criteria), this solution is also considered even if the corresponding move were forbidden by the tabu memory.
•
Then, one specific move among the best ones is randomly chosen (line 19) and performed (line 20). Recall that a move displaces one detector to a new position. Trying to move one detector to this same position is set as tabu for a number of iterations (line 21).
•
Finally, if the new solution is the best one found so far, it is recorded and an improvement is acknowledged (lines 23-24). Otherwise, we record that this iteration was unable to achieve any improvement (line 26).

Just like in the case of Hill Climbing algorithm, the whole process is repeated several times until the allowed execution time is exhausted, and the best solution found is returned at the end.

Input: $\mathit{sol}$ (a collection with the coordinates of $\delta$ detectors)

1 $\mathit{candidates}:=\{(r,c)\ |\ 1\leqslant r\leqslant m,1\leqslant c\leqslantn%,A_{rc}$ is unblocked $,\Delta_{rc}<\delta\}$ ;

2 $\mathit{best}:=\mathit{sol}$ ;

3 $\mathit{noImprovement}:=0$ ;

4while $\mathit{noImprovement}<\mathit{maxIters}$ do

3.5 Evolutionary Algorithm

An Evolutionary Algorithm (EA) (Eiben and Smith, 2003) is a optimizationprocedure inspired by the biological evolution of species. These algorithms are population based ones which means that a pool of solutions is maintained during the optimization process. This population of solutions is initialized somehow before entering the evolutionary loop in which solutions go through different processes such as reproduction, recombination, mutation and replacement. At the end of the evolutionary loop, the best solution found during the execution of the algorithm is returned.

Algorithm4 shows the specific incarnation of the EA that we have used. $\mathit{pop}$ is the population of non-repeated $\mathit{popSize}$ individuals, each one being a full solution to the problem. Like in previous heuristics, the search space explored by the EAis restricted to non-blocked cells in themap minus those that are dominated by at least $\delta$ cells.Each individual in the population of solutions is initialized randomly as a vector of $\delta$ different locations for placing each detector. These locations are randomly chosen in an uniform way among all possible ones (lines 1-4). Then, the following process corresponding to the evolutionary loop is repeated, until the maximum allowed execution time for the algorithm is exhausted:

•
With probability of selection $p_{X}$ , two individuals acting as parents are selected from the population (lines 7-9). The specific algorithm used for each selection is binary tournament selection in which, after picking two individuals at random, the best one is selected. Now, these individuals go through recombination in order to produce a new one. For this purpose, letus consider the set comprising the union of detector placementsincluded in to be recombined individuals. A new individual, constituting the offspring for thisgeneration, is then defined by sampling in a uniform way $\delta$ elements (i.e., detector placements) from this previous set.
•
Otherwise (i.e. with probability $1-p_{X}$ ) recombination is not performed and a random individual of currentpopulation is selected as the offspring (line 11).
•
Each detector location in the the offspring is mutated with probability $p_{m}$ . More precisely, with such probability the corresponding detector is replaced with another one notincluded in the solution (line 13). The resulting individual is evaluated (line 14).
•
As to replacement, the worst individual currently included in the population is replaced by the offspring (line 15).

Finally, when the execution time limit is reached, the best individual found along this whole process is returned as a solution.

Input : $\mathit{popSize}$ (population size)

$p_{X}$ (recombination probability)

$p_{m}$ (mutation probability)

1 for $i:=1$ to $\mathit{popSize}$ do

2 $\mathit{pop}_{i}:=$ RandomIndividual $()$ ;

3Evaluate( $\mathit{pop}_{i}$ );

5 end for

6whileallowed runtime not exceededdo

7ifrecombination is performed( $p_{X}$ )then

8 $parent_{1}:=$ Select( $\mathit{pop}$ );

9 $parent_{2}:=$ Select( $\mathit{pop}$ );

10 $\mathit{offspring}:=$ Recombine( $parent_{1}$ , $parent_{2}$ );

12else

13 $\mathit{offspring}:=$ Select( $\mathit{pop}$ );

15 end if

16 $\mathit{offspring}:=$ Mutate( $p_{m},\mathit{offspring}$ );

17Evaluate( $\mathit{offspring}$ );

18 $\mathit{pop}:=$ Replace( $\mathit{pop}$ , $\mathit{offspring}$ );

20 end while

21return best solution found;

3.6 Problem Instances

In order to test the algorithms described in the previous section in a broad set of conditions,we have generated problem instances that try to resemble different real-world scenarios. To be precise,we have considered the following three classes of maps:

•
harbour: these problem instances represent a coastal area that may be subject to amaritime attack by a small vessel, cf. (Yan and Nie, 2016). These maps featurea large inner open area (representing a water mass such as a lake or asheltered body of sea) typically comprising several scattered islands,surrounded by a complex coastline with some straits from which the attackercan enter the threat area. See Figure2a.
•
newtown: these problem instances represent a modern urban area in which streets runin straight lines creating a grid (Manhattan or Barcelona’s Expansion District beingprominent examples). These maps feature streets of different width running atright angles, as well as a number of plazas of different sizes scattered acrossthe map. See Figure2b.
•
oldtown: these problem instances represent the historic core of an old town. As such,the street plan features a much more decentralized and flexible structure. Streetstypically originate at plazas and run in different directions and angles withrespect to each other, bifurcating as they get farther from the plazas. See Figure2c.

For each of these three problem classes, we have defineda map generator in order to create a number of instances of the desired characteristics, hence contributing to thediversity of the benchmark. Next we will describe in more detail the generation procedure for each map class.

3.6.1 Coastal Area

These maps are created in two phases. In the first phase a exponentially decaying diffusion mechanism is used to grow theinner water mass: we start at the center of the lattice with a value $p=1$ ; with this probability we set the current position tounblocked and move to each of the four neighbors in a von Neumann topology (i.e., North, East, South, West), having thisprobability decay by a different factor $\{\beta_{i}\}_{1\leqslant i\leqslant 4}$ , that depends on the direction, and repeating theprocess from each of them. When the diffusion stops, we proceed with the second phase in which the map is smoothed outby using a cellular automaton which has each lattice cell change to the most repeated state among itself and its neighbors.This process is run until convergence or after a maximum number of iterations has been performed.

Once the above is done, objectives are placed on positions along the coastline. To do so, a random unblocked position isselected, and a random walk (using the von Neumann connectivity mentioned before) is performed until a blocked positionis found. This position is then unblocked and defined as an objective. The process is repeated as many times as objectivesneed to be placed. The entrances are randomly selected among the unblocked positions on the borders of the map.

3.6.2 Modern Urban Area

These maps are also created in two phases: in the first one the street grid is created, and in the second one a numberof plazas are added to the map. In order to tackle the first part, we consider values $\{p_{i}\}_{0\leqslant i}$ , representingthe probability of having a street of width $i$ (the value $p_{0}$ corresponding to the situation of not having a street atall). Using these, we traverse the columns of the maps deciding whether we include a North-South street and if so of whichwidth. In case a street of width $w$ is placed, we jump $w+1$ columns to the right and repeat the procedure until allcolumns have been processed. The whole process is then repeated by traversing rows of the maps in order to placeWest-East streets.

The second phase involves placing some plazas on the map. This is controlled by parameter $n_{p}$ indicating thenumber of plazas and values $\{q_{i}\}_{\min_{p}\leqslant i}$ representing the probability of having a square plaza of a certainside length, where $\min_{p}$ indicates the minimum side length admissible. The generator would iterate $n_{p}$ timesa process of determining the size of a plaza using probabilities $\{q_{i}\}$ and then deciding a suitable location given this size.As in the previous scenario, the entrances are randomly selected among the unblocked positions on the borders of the map.As to the objectives, these are placed in random unblocked positions of the map.

3.6.3 Old Historic Town

These maps are created by iterating $n_{p}$ (a parameter that just like in the previous scenario indicates a numberof plazas to be located on the map) times a basic procedure. This procedure consists of determining the size of a plaza(using a collection of values $\{q_{i}\}_{\min_{p}\leqslant i}$ as in the newtownscenario), placing it in on the map, and thenhaving four streets depart from each of the sides of the plaza. These streets do not run at right angles though: theyare laid out having a certain slope between $\pm 1$ (a diagonal street) and $\pm\max_{s}$ (closer to horizontal or vertical).The width of the street is set to $w$ and as the street runs out from the plaza it can branch along the way into a smaller (width $w-1$ )street with probability $p_{b}$ . These branched-out streets can in turn branch into smaller lanes in a recursive way, thustrying to resemble the complex and more convoluted network of small streets and lanes in the historic core of old towns.

Much like it was done in harbourand newtown, the entrances are randomly selected among the unblocked positionson the borders of the map. As to the objectives, these are placed in random unblocked positions of the map as in newtown.

4 Experimental Results

In order to evaluate the performance of the algorithms we have followeda problem generator approach (DeJong etal, 1997), wherebyrather than running each algorithm multiple times on the same problem instance, theyare run once on a different problem instance each time, thus allowing to obtain a morerepresentative measure of performance across the whole set of possible instances,and avoiding (or at the very least diminishing the impact of) any spurious matchbetween a specific instance and a specific algorithm. More precisely, all algorithmshave been run twenty five times on each of the three problem classes,namely harbour,newtownand oldtown, for the twoattacker scenarios (i.e., proportional selection of objectives and worst-case equilibrium)using the same seventy five problem instances in all cases.

The maps considered have been generated on a grid of size $64\times 64$ . In allcases, the number of entrances $\varepsilon$ and the number of objectives $\phi$ are independently chosen uniformly at random between 10 and 15. A 10% region aroundthe borders of the maps is kept free of objectives to avoid any of these being locatedextremely close to an entrance, something which could be regarded as a pathological case.As to scenariodependent parameters, in the case of harbour, the decay parameters $\{\beta_{i}\}$ were randomly picked between 0.98 and 0.99 and checked to empirically ensure thatthe diffusion barely reached the borders of the map.The dimension of each cell in the map was of 200m $\times$ 200m and the detection radius for the detectors was set to $\tau=500m$ . Regarding newtown, each map has arandom number of plazas $n_{p}$ between 3 and 6, whose side length can range between 4 and13 ( $\{q_{i}\}_{4\dots 13}=1/10$ ). Street widths are selected using values $\{p_{i}\}_{0\dots 3}=\{0.5,0.25,0.15,0.1\}$ . Finally,oldtownmaps also comprise a random number of plazas $n_{p}$ between 3 and 6, whosesizes range from 6 up to 15 ( $\{q_{i}\}_{6\dots 15}=1/10$ ). The maximum slope of streets is 1/5 of the map side length,they have initial width $w=3$ , and can branch with probability $p_{b}=0.02$ . For these instances representing different town configurations, the dimension of each cell in the map was of 5m $\times$ 5m and the detection radius for the detectors was set to $\tau=20m$ .

We have considered that minimum time required to neutralize an attacker is $t_{n}=10$ s. In the case of newtownand oldtowninstances, this means that effective neutralization is not possible if the distance of the attacker to the objective is less than 10m, which corresponds to assuming that the attacker moves at a speed $v=1$ m/s. In the case of harbourinstances, we have assumed a moving speed for the vessels $v=20$ m/s and thus the maximum distance to the objective for being able to abort the attack is 200m.As to the detector’s instantaneous detection rates, we have used a value of $\eta=0.06$ for the newtownand oldtowninstances and $\eta=0.006$ forthe harbourinstances, thus assuming that detectors are less reliable in the later case.For the probability of effectively neutralizing a detected attacker, we used $\theta=0.6$ in all cases. Additionally, in order to estimate the expected number of casualties for an objective cell $\{C_{j}\}_{1\dots\phi}$ , we used the same procedure defined by Cotta and Gallardo (2017) which is in turn based onEquation 2 in (Kaplan and Kress, 2005). This equation presumes that the number of fragments produced after the explosion tends to $\infty$ and that these fragments and individuals around the target area are spatially distributed according to a Poisson process. We have used the same parameters for this equation as those proposed by Nie etal (2007), except for the population densities near each objective cell, which were set as a constant therein but which we have modelled as a random variable instead, with the aim of considering more diverse instances. For newtown and oldtowninstances thisis chosen from a normal distribution ${\mathcal{N}(0.4,0.1)}$ persons / ${\mathrm{m}}^{2}$ , whereas in the case of harbourinstances, we take ${\mathcal{N}(9\cdot 10^{7},1.8\cdot 10^{6})}$ (these latter values do not really stand for an expected number of civilian casualties but instead represent the economical cost resulting from damaging the corresponding objective).Overall, all parameters have been picked to have generated instances resemblerealistic scenarios, as described in the literature (Kaplan and Kress, 2005; Nie etal, 2007; Yan and Nie, 2016), while providing diversity thanks to their range of variability.

Regarding the parameters used for the different algorithms, the following settings were used for the EA: population size $\mathit{popSize}=100$ individuals, probability of crossover $p_{X}=0.9$ and probability of mutation $p_{m}=1/\delta$ .The tenure value for the TS algorithm was a random number of iterations in $[\delta\dots 2\delta]$ . All algorithmswere run for 30 seconds on each instance (the hardware platform used was a cluster of Intel Xeon E7-4870 2.4 GHz processors with 2GB of RAM running under SUSE Linux Enterprise Server 11 operating system).

The results are depicted in Figures3–4. In the two scenarios,the three iterative approaches largely outperform the greedy algorithm. In most cases, the latterseems to experience a peak of difficulty when the number of detectors is about the same magnitudeas the number of objectives. This can be explained by the fact that for a low number of detectorsthe number of options are limited and the greedy selection is often reasonably close to more finelyadjusted solutions, whereas for a large number of detectors these can be spread to cover most pathswithout not so much difficulty (thus leaving the middle regime between these two extremesas the most complex one).

This said, it is much more interesting to note the difference between the two scenarios. Notice firstlyhow the range of deviations for all algorithms is larger in the worst-case equilibrium scenario. It isnot difficult to see that this latter scenario is indeed harder from an optimization point of view, due tothe complex structure of the search landscape in this case: the quality of a solution is dictated by thecritical path given the current location of detectors; hence, the optimization algorithm will attemptto gradually increase the coverage of this critical path but in doing so (i) it will have to take care ofnot leaving uncovered other paths to objectives of higher sensitivity, and (ii) eventually the criticalpath may turn to be a different one (recall the discussion in Section2.2) causing anabrupt discontinuity in the direction of the optimization process. This differs from the proportionalselection scenario, in which the objective function is a weighted combination whose coefficientsare fixed, and hence can be optimized in a more smoothly way. Furthermore, notice how the searchlandscape is prone to have mesas in the worst-case equilibrium scenario, given the fact that as longas the coverage of the critical path does not change and the coverage of other paths does not changeenough for the critical path to be a different one, the value of the objective function will be the same.This may affect all algorithms, and in particular the greedy algorithm (see the insets in Figure5),which will face the need to pick a choice among a large number of seemingly equivalent options.

$i$	algorithm	$z$ -statistic	$p$ -value	adjusted $p$ -value
1	EA	3.38e $+$ 00	3.66e $-$ 04	3.66e $-$ 04
2	TS	4.56e $+$ 00	2.51e $-$ 06	5.01e $-$ 06
3	Greedy	9.22e $+$ 00	1.49e $-$ 20	4.46e $-$ 20

$i$	algorithm	$z$ -statistic	$p$ -value	adjusted $p$ -value
1	HC	1.64e $+$ 00	5.02e $-$ 02	5.02e $-$ 02
2	TS	3.29e $+$ 00	5.08e $-$ 04	1.02e $-$ 03
3	Greedy	8.22e $+$ 00	1.05e $-$ 16	3.16e $-$ 16

As a result of the previous considerations, there is a difference between the relative behavior ofthe different iterative algorithms in each of the two scenarios. In the first one (proportional selection),HC is significantly better than the other algorithms (Quade test $p$ -value $\approx 0$ , Holm test resultsshown in Table2). However, in the worst-case equilibrium scenario the EA providesbetter results (Quade test $p$ -value $\approx 0$ , Holm test resultsshown in Table3). Indeed, if we perform a head-to-head comparison betweenHC and EA in this latter scenario by means of a signrank test, we observe that the EA is significantly better with $p$ -value = 0.0057.Quite interestingly, if we break down the analysis by map class, we find that HC is negligibly andnon-significantly better than EA in the harbourclass ( $p$ -value = 0.7422), and that the EA issignificantly better than HC in newtownand oldtown( $p$ -values of 0.0098 and 0.0020 respectively).As a matter of fact, the quantitative difference between the algorithms is clear if we observe the distributionof deviations from the best known solutions (Figure5): the difference in favorof HC is much smaller in the proportional selection scenario when compared to the difference infavor of EA in the worst-case equilibrium scenario. Clearly, the more complex nature of the searchlandscape is better dealt with via the diversification of a population-based approach than the strongintensification of the HC algorithm considered.

Figure6shows an example of the solutions provided by either algorithm ona newtownmap for the worst-case equilibrium scenario. The solutions provided by each algorithmare structurally different. The greedy approach tends to place the detectors in the vicinity of the objectives.The local search approaches seem to have found solutions in which detectors are usually placed close toentrances, but with some detectors being placed next to objectives as well. Finally the EA has also favoredlocations close to entrances in order to cover a large number of paths; however, it has also identified a fewcrossroads that seem to be important in order to maximize coverage of many paths. Notice how foreach of these solutions, the resulting critical path is different in each case.

5 Conclusions and Future Work

Counterterrorism is a multidimensional endeavor that spreads along many entangled fronts. One of them isundoubtedly the tactical defense against targeted attacks, from which suicide bombings constitute a heinousdistinguished example. While low-rank individuals engaged in international terrorism groups may be often fanaticized andhence can have motivations that challenge rational analysis (or motivations that, while rational, can be directedtowards other personal or social goals than those of the terror group as a whole (Abrahms, 2008)),their actions are often dictated by or inspired by theguidelines emanating from the upper levels of a command hierarchy, more prone to engage in analyticalconsiderations of cost-effectiveness in pursue of their criminal goals. As a matter of fact, the assessment ofthe situation would not qualitatively change if rather than considering a suicide attacker embarked on ano-return mission we consider the case of an unmanned attack using a drone or any other suitablevehicle (Patterson and Patterson, 2010), a scenario slanted towards purely tactical considerations. In any case,assuming this operational context provides at the very least a worst-case scenario upon which a better informed,more down-to-earth strategy could be built with the help ofadequate intelligence. The availability of cogent tools to aid in the analysis of these scenarios can thus bemost helpful. In this sense, we have considered in this work the use of different heuristic approaches todetermine the most appropriate deployment of sensors so as to detect perpetrators of bombing attacks ina given threat area, aiming to minimize the number of casualties or economic damages. Modeling thissituation as an adversarial game in which the attacker is cognizant of the location of these detectors andtries to target the most cost-effective objective turns out to pose a challenging optimization task. Among thealgorithms considered and tested on a variety of problem scenarios, an evolutionary algorithm turns outto be quite effective. It is however remarkable that a simple hill climber performs reasonably well on someinstances, suggesting that an eventual hybridization of both methods into a memetic approach (Neri etal, 2012)might be very promising.

Future work will be actually directed in the direction of hybridizing methods, aiming to exploit their synergy.Pushing the limits of the resulting techniques (in terms of, e.g., the size of the maps, the number of objectives,etc.) would be of paramount interest. Also, it is conceivable to consider in the context described in this workextensions of the underlying model including different types of detectors, cf. (Yan and Nie, 2016), or evenintroducing a dynamic component in the configuration of the ground map.

References

Aarts and Lenstra (1997)Aarts EHL, Lenstra JK (1997) Local Search in Combinatorial Optimization. JohnWiley & Sons
Abrahms (2008)Abrahms M (2008) What terrorists really want: Terrorist motives andcounterterrorism strategy. International Security 32(4):78–105
Blomberg etal (2004)Blomberg SB, Hess GD, Weerapana A (2004) An economic model of terrorism.Conflict Management and Peace Science 21(1):17–28
Central Intelligence Agency (2003)Central Intelligence Agency (2003) National strategy for combating terrorism.https://www.cia.gov/news-information/cia-the-war-on-terrorism/Counter˙Terrorism˙Strategy.pdf,[Accessed 31 January 2018]
Chicago Project on Security and Terrorism(2016) (CPOST)Chicago Project on Security and Terrorism (CPOST) (2016) Suicide attackdatabase (April 19, 2016 release). [Data File]. Retrieved fromhttp://cpostdata.uchicago.edu/
Cotta and Gallardo (2017)Cotta C, Gallardo JE (2017) Metaheuristic approaches to the placement ofsuicide bomber detectors. Journal of HeuristicsDOI10.1007/s10732-017-9335-z
DeJong etal (1997)DeJong KA, Potter MA, Spears WM (1997) Using problem generators to explore theeffects of epistasis. In: Bäck T (ed) Proceedings of the 7thInternational Conference on Genetic Algorithms, Morgan Kaufmann, pp 338–345
Edwards etal (2016)Edwards D, McMenemy L, Stapley S, Patel H, Clasper J (2016) 40 years ofterrorist bombings – a meta-analysis of the casualty and injury profile.Injury 47(3):646–652
Eiben and Smith (2003)Eiben AE, Smith JE (2003) Introduction to Evolutionary Computing.SpringerVerlag
Ganor (2011)Ganor B (2011) Trends in modern international terrorism. In: Weisburd D, FeuchtT, Hakimi I, Mock L, Perry S (eds) To Protect and To Serve. Policing in anAge of Terrorism, Springer, New York, pp 11–42
Gares etal (2016)Gares KL, Hufziger KT, Bykov SV, Asher SA (2016) Review of explosive detectionmethodologies and the emergence of standoff deep UV resonance raman.Journal of Raman Spectroscopy 47(1):124–141
Glover (1989)Glover F (1989) Tabu search-part I. ORSA Journal of Computing 1:190–206
Glover (1990)Glover F (1990) Tabu search-part II. ORSA Journal of Computing 2:4–32
Hoffman (2003)Hoffman B (2003) The logic of suicide terrorism. The Atlantic.http://www.theatlantic.com/magazine/archive/2003/06/the-logic-of-suicide-terrorism/302739/,[Accessed 2 July 2016]
Hoos and Stützle (2005)Hoos H, Stützle T (2005) Stochastic Local Search. Foundations andApplications. Morgan Kaufmann
Kaplan and Kress (2005)Kaplan EH, Kress M (2005) Operational effectiveness of suicide-bomber-detectorschemes: A best-case analysis. Proceedings of the National Academy ofSciences of the United States of America 102(29):10399–10404
Kim etal (2016)Kim M, Batta R, He Q (2016) Optimal routing of infiltration operations. Journalof Transportation Security 9(1):87–104
Lara-Cabrera etal (2017)Lara-Cabrera R, González-Pardo A, Benouaret K, Faci N, Benslimane D,Camacho D (2017) Measuring the radicalisation risk in social networks. IEEEAccess 5:10892–10900
Leistedt (2016)Leistedt SJ (2016) On the radicalization process. Journal of Forensic Sciences61(6):1588–1591
Neri etal (2012)Neri F, Cotta C, Moscato P (eds) (2012) Handbook of Memetic Algorithms,Studies in Computational Intelligence, vol 379. Springer-Verlag, BerlinHeidelberg
Nie etal (2007)Nie X, Batta R, Drury CG, Lin L (2007) Optimal placement of suicide bomberdetectors. Military Operations Research 12(2):65–78
Patterson and Patterson (2010)Patterson MR, Patterson SJ (2010) Unmanned systems: An emerging threat towaterside security: Bad robots are coming. In: 2010 International WaterSideSecurity Conference, IEEE Press, pp 1–7
Rand Corporation (2009)Rand Corporation (2009) RAND database of worldwide terrorism incidents.[Data File] http://smapp.rand.org/rwtid/search˙form.php
Tutun etal (2017)Tutun S, Khasawneh MT, Zhuang J (2017) New framework that uses patterns andrelations to understand terrorist behaviors. Expert Systems with Applications78:358–375
Yan and Nie (2016)Yan X, Nie X (2016) Optimal placement of multiple types of detectors under asmall vessel attack threat to port security. Transportation Research Part E:Logistics and Transportation Review 93:71–94

New Perspectives on the Optimal Placement of Detectors for Suicide Bombers using Metaheuristics††thanks: This work is supported by the Spanish Ministerio de Economía and European FEDER under Projects EphemeCH (TIN2014-56494-C4-1-P) and DeepBIO (TIN2017-85 (2024)

Abstract

Keywords:

1 Introduction

2 Definition of the Problem

2.1 Basic Setting

2.2 Tackling Decision Making

3 Materials and Methods

3.1 Algorithmic Approaches

3.2 Greedy Algorithm

3.3 Hill Climbing

3.4 Tabu Search

3.5 Evolutionary Algorithm

3.6 Problem Instances

3.6.1 Coastal Area

3.6.2 Modern Urban Area

3.6.3 Old Historic Town

4 Experimental Results

5 Conclusions and Future Work

References

References