Stochastic network interdiction optimization via capacitated network reliability modeling and probabilistic solution discovery

This paper introduces an evolutionary optimization approach that can be readily applied to solve stochastic network interdiction problems (SNIP). The network interdiction problem solved considers the minimization of the cost associated with an interdiction strategy such that the maximum flow that can be transmitted between a source node and a sink node for a fixed network design is greater than or equal to a given reliability requirement. Furthermore, the model assumes that the nominal capacity of each network link and the cost associated with their interdiction can change from link to link and that such interdiction has a probability of being successful. This version of the SNIP is for the first time modeled as a capacitated network reliability problem allowing for the implementation of computation and solution techniques previously unavailable. The solution process is based on an evolutionary algorithm that implements: (1) Monte-Carlo simulation, to generate potential network interdiction strategies, (2) capacitated network reliability techniques to analyze strategies’ source-sink flow reliability and, (3) an evolutionary optimization technique to define, in probabilistic terms, how likely a link is to appear in the final interdiction strategy. Examples for different sizes of networks are used throughout the paper to illustrate the approach.     

Algorithms for discrete and continuous multicommodity flow network interdiction problems

We consider a network interdiction problem on a multicommodity flow network, in which an attacker disables a set of network arcs in order to minimize the maximum profit that can be obtained from shipping commodities across the network. The attacker is assumed to have some budget for destroying (or “interdicting”) arcs, and each arc is associated with a positive interdiction expense. In this paper, we examine problems in which interdiction must be discrete (i.e., each arc must either be left alone or completely destroyed), and in which interdiction can be continuous (the capacities of arcs may be partially reduced). For the discrete problem, we describe a linearized model for optimizing network interdiction that is similar to previous studies in the field, and compare it to a penalty model that does not require linearization constraints. For the continuous case, we prescribe an optimal partitioning algorithm along with a heuristic procedure for estimating the optimal objective function value. We demonstrate on a set of randomly generated test data that our penalty model for the discrete interdiction problem significantly reduces computational time when compared to that consumed by the linearization model.     

Models for nuclear smuggling interdiction

We describe two stochastic network interdiction models for thwarting nuclear smuggling. In the first model, the smuggler travels through a transportation network on a path that maximizes the probability of evading detection, and the interdictor installs radiation sensors to minimize that evasion probability. The problem is stochastic because the smuggler's origin-destination pair is known only through a probability distribution at the time when the sensors are installed. In this model, the smuggler knows the locations of all sensors and the interdictor and the smuggler “agree” on key network parameters, namely the probabilities the smuggler will be detected while traversing the arcs of the transportation network. Our second model differs in that the interdictor and smuggler can have differing perceptions of these network parameters. This model captures the case in which the smuggler is aware of only a subset of the sensor locations. For both models, we develop the important special case in which the sensors can only be installed at border crossings of a single country so that the resulting model is defined on a bipartite network. In this special case, a class of valid inequalities reduces the computation time for the identical-perceptions model.     

All-terminal network reliability optimization via probabilistic solution discovery

This paper presents a new algorithm that can be readily applied to solve the all-terminal network reliability allocation problems. The optimization problem solved considers the minimization of the network design cost subject to a known constraint on all-terminal reliability by assuming that the network contains a known number of functionally equivalent components (with different performance specifications) that can be used to provide redundancy. The algorithm is based on two major steps that use a probabilistic solution discovery approach and Monte Carlo simulation to generate the quasi-optimal network designs. Examples for different sizes of all-terminal networks are used throughout the paper to illustrate the approach. The results obtained for the larger networks with unknown optima show that the quality of the solutions generated by the proposed algorithm is significantly higher with respect to other approaches and that these solutions are obtained from restricted solution search space. Although developed for all-terminal reliability optimization, the algorithm can be easily applied in other resource-constrained allocation problems.     

Port-of-entry safety via the reliability optimization of container inspection strategy through an evolutionary approach

Up to now, of all the containers received in USA ports, roughly between 2% and 5% are scrutinized to determine if they could cause some type of danger or contain suspicious goods. Recently, concerns have been raised regarding the type of attack that could happen via container cargo leading to devastating economic, psychological and sociological effects. Overall, this paper is concerned with developing an inspection strategy that minimizes the total cost of inspection while maintaining a user-specified detection rate for “suspicious” containers. In this respect, a general model for describing an inspection strategy is proposed. The strategy is regarded as an (n+1)-echelon decision tree where at each of these echelons, a decision has to be taken, regarding which sensor to be used, if at all. Second, based on the general decision-tree model, this paper presents a minimum cost container inspection strategy that conforms to a pre-specified user detection rate under the assumption that different sensors with different reliability and cost characteristics can be used. To generate an optimal inspection strategy, an evolutionary optimization approach known as probabilistic solution discovery algorithm has been used.     

A bi-level network interdiction model for solving the hazmat routing problem

In the current work, we considered the problem of hazardous material distribution where the distributer chooses the routes on the network, and a regulatory agency controls the behaviour of the distributer to traverse the specified routes. In these circumstances, the distributer sets to select some routes to minimise the total distributing costs. Mostly, this occurs due to selecting risky arcs in which more individuals are exposed to risk. To prevent this and increase the capability to deal with the risk of hazardous material transportation through roads, the regulatory agency obliges carriers to traverse through the most secure arcs, though imposing more distribution costs. The problem is modelled as a bi-level routing problem. The bi-level model is difficult to solve and may be ill-posed. Two meta-heuristic algorithms are proposed to solve the bi-level model, and some randomly generated problems are applied to show the applicability and efficiency of the proposed algorithms.     

有限资源下最大可靠性网络流中断模型

提出了最大可靠性网络流中断模型。此模型是在给定的网络图中,通过在边上设置监测点来阻止给定两个顶点之间的网络流量,同时考虑所设置监测点失效的可能,在给定的资源限制下,最大化中断网络流的可能性,即给定起点和终点的网络图,在资源有限的情况下,选择一些边设置监测点使得从起点到终点的所有路都包含尽可能多的已被设置中断点的边。在给定图中,两点之间的路的条数是图的规模的指数次幂,为此将此模型转化为双层整数规划模型,鉴于双层整数规划模型在一般情况下是不可解的,通过探讨下层整数规划问题与其线性规划松弛之间的关系以及线性规划对偶理论来解此双层整数规划模型。本文不仅将该模型约束的个数从图的规模的指数次幂降到一次幂,同时也提供了一种解双层整数规划问题的方法。     

Reliability-oriented multi-resource allocation in a stochastic-flow network

A stochastic-flow network consists of a set of nodes, including source nodes which supply various resources and sink nodes at which resource demands take place, and a collection of arcs whose capacities have multiple operational states. The network reliability of such a stochastic-flow network is the probability that resources can be successfully transmitted from source nodes through multi-capacitated arcs to sink nodes. Although the evaluation schemes of network reliability in stochastic-flow networks have been extensively studied in the literature, how to allocate various resources at source nodes in a reliable means remains unanswered. In this study, a resource allocation problem in a stochastic-flow network is formulated that aims to determine the optimal resource allocation policy at source nodes subject to given resource demands at sink nodes such that the network reliability of the stochastic-flow network is maximized, and an algorithm for computing the optimal resource allocation is proposed that incorporates the principle of minimal path vectors. A numerical example is given to illustrate the proposed algorithm.     

Human–machine function allocation: a functional modelling approach

Function allocation between humans and systems is an important factor regarding safety, reliability and efficiency of industrial processes. One should allocate functions in order to maximise the operator's situation understanding and ability to handle unexpected events. Functional models can be used to study function allocation in a process control environment, because they explicitly describe functions and tasks of both the plant and the operator. The Halden Reactor Project is currently engaged in such a project called function allocation methods (FAME), aimed specifically at the work in a nuclear power plant control room. This paper describes the main features of the approach, and discusses how functional modelling can be used to address the issue of how much information is necessary for the operator, and thereby give a basis for how functions should be allocated.     

Constrained multi-objective optimization using constrained non-dominated sorting combined with an improved hybrid multi-objective evolutionary algorithm

Constrained multi-objective optimization problems (cMOPs) are complex because the optimizer should balance not only between exploration and exploitation, but also between feasibility and optimality. This article suggests a parameter-free constraint handling approach called constrained non-dominated sorting (CNS). In CNS, each solution in a population is assigned a constrained non-dominated rank based on its constraint violation degree and Pareto rank. An improved hybrid multi-objective optimization algorithm called cMOEA/H for solving cMOPs is proposed. Additionally, a dynamic resource allocation mechanism is adopted by cMOEA/H to spare more computational efforts for those relatively hard sub-problems. cMOEA/H is first compared with the baseline algorithm using an existing constraint handling mechanism, verifying the advantages of the proposed constraint handling mechanism. Then cMOEA/H is compared with some classic constrained multi-objective optimizers, experimental results indicating that cMOEA/H could be a competitive alternative for solving cMOPs. Finally, the characteristics of cMOEA/H are studied.     

Deterministic global optimization approach to steady-state distribution gas pipeline networks

Natural gas is normally transported through a vast network of pipelines. A pipeline network is generally established either to transmit gas at high pressure from coastal supplies to regional demand points (transmission network) or to distribute gas to consumers at low pressure from the regional demand points (distribution network). In this study, the distribution network is considered. The distribution network differs from the transmission one in a number of ways. Pipes involved in a distribution network are often much smaller and the network is simpler, having no valves, compressors or nozzles. In this paper, we propose the problem of minimizing the cost of pipelines incurred by driving the gas in a distribute non-linear network under steady-state assumptions. In particular, the decision variables include the length of the pipes’ diameter, pressure drops at each node of the network, and mass flow rate at each pipeline leg. We establish a mathematical optimization model of this problem, and then present a global approach, which is based on the GOP primal-relaxed dual decomposition method presented by Visweswaran and Floudas (Global optimization in engineering design. Kluwer book series in nonconvex optimization and its applications. Kluwer, Netherlands, 1996), to the optimization model. Finally, results from application of the approach to data from gas company are presented.     

A mathematical modeling approach to resource allocation for railroad-highway crossing safety upgrades

State Departments of Transportation (S-DOT's) periodically allocate budget for safety upgrades at railroad-highway crossings. Efficient resource allocation is crucial for reducing accidents at railroad-highway crossings and increasing railroad as well as highway transportation safety. While a specific method is not restricted to S-DOT's, sorting type of procedures are recommended by the Federal Railroad Administration (FRA), United States Department of Transportation for the resource allocation problem. In this study, a generic mathematical model is proposed for the resource allocation problem for railroad-highway crossing safety upgrades. The proposed approach is compared to sorting based methods for safety upgrades of public at-grade railroad-highway crossings in Tennessee. The comparison shows that the proposed mathematical modeling approach is more efficient than sorting methods in reducing accidents and severity.     

Sensitivity and uncertainty analysis in optimization programs using an evolutionary approach: a maintenance application

Indirect-Grouping Maintenance Strategy requires the calculation of an optimum (global) according to a minimization program P. However the model on which the optimal is based may be incomplete in the sense that important uncertainties have not been considered. In order to evaluate the effects of the uncertainty of the parameters or how the uncertainty is propagated in the optimization program, the decision-maker needs to evaluate the range of variation of program P.In this work an innovative two step evolutionary approach to analyze uncertainties in Indirect-Grouping Maintenance Strategies is presented. The proposed approach combines the two proven techniques of Cellular Evolutionary Strategies (CES) and Evolutionary Strategies (ES) for the optimization problem. The approach does not guarantee the global optimum, but the experiments show that the results are very close to the real one. The examples presented confirm that the approach produces very good approximations for the range of the minimum when there is uncertainty in the model parameters and can be used as a tool for uncertainty/sensitivity analysis in other areas.     

A simulation-based optimization approach to size manufacturing systems

The problem of sizing the resources of a production system is widely encountered both in the literature and in practice. Simulation is a very useful method to identify the necessary number of resources. However, if there are numerous resources, it can become impossible to make a sound ‘trial-and-error’ analysis with simulation models, so that strategies using simulation optimization appear as an attractive approach. Unfortunately, it is necessary to specify a cost function, and, in practice, it is often very difficult to formalize such a function which is used to determine the number of resources that will minimize this cost. In this article, we propose a different modelling approach, which aims at sizing the resources so as to meet the design specifications. In this respect, we search for the minimum number of resources of each type, while satisfying the performance requirements specified in the design project. As a result, the problem is formulated as a stochastic multi-objective optimization problem with constraints. The approach used here is based on simulation, used in conjunction with a bootstrap approach which accounts for the stochastic aspect of the model, and with regression metamodelling in order to derive an analytical formulation of the constraints together. Different multi-objective optimization methods can then be used to solve the problem. An illustrative example is given.     

Multi-objective hierarchical genetic algorithms for multilevel redundancy allocation optimization

Multilevel redundancy allocation optimization problems (MRAOPs) occur frequently when attempting to maximize the system reliability of a hierarchical system, and almost all complex engineering systems are hierarchical. Despite their practical significance, limited research has been done concerning the solving of simple MRAOPs. These problems are not only NP hard but also involve hierarchical design variables. Genetic algorithms (GAs) have been applied in solving MRAOPs, since they are computationally efficient in solving such problems, unlike exact methods, but their applications has been confined to single-objective formulation of MRAOPs. This paper proposes a multi-objective formulation of MRAOPs and a methodology for solving such problems. In this methodology, a hierarchical GA framework for multi-objective optimization is proposed by introducing hierarchical genotype encoding for design variables. In addition, we implement the proposed approach by integrating the hierarchical genotype encoding scheme with two popular multi-objective genetic algorithms (MOGAs)—the strength Pareto evolutionary genetic algorithm (SPEA2) and the non-dominated sorting genetic algorithm (NSGA-II). In the provided numerical examples, the proposed multi-objective hierarchical approach is applied to solve two hierarchical MRAOPs, a 4- and a 3-level problems. The proposed method is compared with a single-objective optimization method that uses a hierarchical genetic algorithm (HGA), also applied to solve the 3- and 4-level problems. The results show that a multi-objective hierarchical GA (MOHGA) that includes elitism and mechanism for diversity preserving performed better than a single-objective GA that only uses elitism, when solving large-scale MRAOPs. Additionally, the experimental results show that the proposed method with NSGA-II outperformed the proposed method with SPEA2 in finding useful Pareto optimal solution sets.     

Topology optimization of geometrically nonlinear structures using an evolutionary optimization method

The topology optimization using isolines/isosurfaces and extended finite element method (Iso-XFEM) is an evolutionary optimization method developed in previous studies to enable the generation of high-resolution topology optimized designs suitable for additive manufacture. Conventional approaches for topology optimization require additional post-processing after optimization to generate a manufacturable topology with clearly defined smooth boundaries. Iso-XFEM aims to eliminate this time-consuming post-processing stage by defining the boundaries using isovalues of a structural performance criterion and an extended finite element method (XFEM) scheme. In this article, the Iso-XFEM method is further developed to enable the topology optimization of geometrically nonlinear structures undergoing large deformations. This is achieved by implementing a total Lagrangian finite element formulation and defining a structural performance criterion appropriate for the objective function of the optimization problem. The Iso-XFEM solutions for geometrically nonlinear test cases implementing linear and nonlinear modelling are compared, and the suitability of nonlinear modelling for the topology optimization of geometrically nonlinear structures is investigated.     

Decoupled approach to multidisciplinary design optimization under uncertainty

We propose solution methods for multidisciplinary design optimization (MDO) under uncertainty. This is a class of stochastic optimization problems that engineers are often faced with in a realistic design process of complex systems. Our approach integrates solution methods for reliability-based design optimization (RBDO) with solution methods for deterministic MDO problems. The integration is enabled by the use of a deterministic equivalent formulation and the first order Taylor’s approximation in these RBDO methods. We discuss three specific combinations: the RBDO methods with the multidisciplinary feasibility method, the all-at-once method, and the individual disciplinary feasibility method. Numerical examples are provided to demonstrate the procedure. Anukal Chiralaksanakul is currently a full-time lecturer in the Graduate School of Business Administration at National Institute of Development Administration (NIDA), Bangkok, Thailand.     

Linear approximation model network and its formation via evolutionary computation

To overcome the deficiency of ’local model network’ (LMN) techniques, an alternative ’linear approximation model’ (LAM) network approach is proposed. Such a network models a nonlinear or practical system with multiple linear models fitted along operating trajectories, where individual models are simply networked through output or parameter interpolation. The linear models are valid for the entire operating trajectory and hence overcome the local validity of LMN models, which impose the predetermination of a scheduling variable that predicts characteristic changes of the nonlinear system. LAMs can be evolved from sampled step response data directly, eliminating the need for local linearisation upon a pre-model using derivatives of the nonlinear system. The structural difference between a LAM network and an LMN is that the overall model of the latter is a parameter-varying system and hence nonlinear, while the former remains linear time-invariant (LTI). Hence, existing LTI and transfer function theory applies to a LAM network, which is therefore easy to use for control system design. Validation results show that the proposed method offers a simple, transparent and accurate multivariable modelling technique for nonlinear systems.