Sensor placement in active multistatic sonar networks

The idea of deploying noncollocated sources and receivers in multistatic sonar networks (MSNs) has emerged as a promising area of opportunity in sonar systems. This article is one of the first to address point coverage problems in MSNs, where a number of points of interest have to be monitored in order to protect them from hostile underwater assets. We consider discrete “definite range” sensors as well as various diffuse sensor models. We make several new contributions. By showing that the convex hull spanned by the targets is guaranteed to contain optimal sensor positions, we are able to limit the solution space. Under a definite range sensor model, we are able to exclude even more suboptimal solutions. We then formulate a nonlinear program and an integer nonlinear program to express the sensor placement problem. To address the nonconvex single‐source placement problem, we develop the Divide Best Sector (DiBS) algorithm, which quickly provides an optimal source position assuming fixed receivers. Starting with a basic implementation of DiBS, we show how incorporating advanced sector splitting methods and termination conditions further improve the algorithm. We also discuss two ways to use DiBS to find multiple source positions by placing sensors iteratively or simultaneously. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 287–304, 2017     

A forward network simplex algorithm for solving multiperiod network flow problems

An optimization model which is frequently used to assist decision makers in the areas of resource scheduling, planning, and distribution is the minimum cost multiperiod network flow problem. This model describes network structure decision-making problems over time. Such problems arise in the areas of production/distribution systems, economic planning, communication systems, material handling systems, traffic systems, railway systems, building evacuation systems, energy systems, as well as in many others. Although existing network solution techniques are efficient, there are still limitations to the size of problems that can be solved. To date, only a few researchers have taken the multiperiod structure into consideration in devising efficient solution methods. Standard network codes are usually used because of their availability and perceived efficiency. In this paper we discuss the development, implementation, and computational testing of a new technique, the forward network simplex method, for solving linear, minimum cost, multiperiod network flow problems. The forward network simplex method is a forward algorithm which exploits the natural decomposition of multiperiod network problems by limiting its pivoting activity. A forward algorithm is an approach to solving dynamic problems by solving successively longer finite subproblems, terminating when a stopping rule can be invoked or a decision horizon found. Such procedures are available for a large number of special structure models. Here we describe the specialization of the forward simplex method of Aronson, Morton, and Thompson to solving multiperiod network network flow problems. Computational results indicate that both the solution time and pivot count are linear in the number of periods. For standard network optimization codes, which do not exploit the multiperiod structure, the pivot count is linear in the number of periods; however, the solution time is quadratic.     

Decomposing inventory routing problems with approximate value functions

We present a time decomposition for inventory routing problems. The methodology is based on valuing inventory with a concave piecewise linear function and then combining solutions to single‐period subproblems using dynamic programming techniques. Computational experiments show that the resulting value function accurately captures the inventory's value, and solving the multiperiod problem as a sequence of single‐period subproblems drastically decreases computational time without sacrificing solution quality. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Aircraft routing under the risk of detection

The deterministic problem for finding an aircraft's optimal risk trajectory in a threat environment has been formulated. The threat is associated with the risk of aircraft detection by radars or similar sensors. The model considers an aircraft's trajectory in three‐dimensional (3‐D) space and represents the aircraft by a symmetrical ellipsoid with the axis of symmetry directing the trajectory. Analytical and discrete optimization approaches for routing an aircraft with variable radar cross‐section (RCS) subject to a constraint on the trajectory length have been developed. Through techniques of Calculus of Variations, the analytical approach reduces the original risk optimization problem to a vectorial nonlinear differential equation. In the case of a single detecting installation, a solution to this equation is expressed by a quadrature. A network optimization approach reduces the original problem to the Constrained Shortest Path Problem (CSPP) for a 3‐D network. The CSPP has been solved for various ellipsoid shapes and different length constraints in cases with several radars. The impact of ellipsoid shape on the geometry of an optimal trajectory as well as the impact of variable RCS on the performance of a network optimization algorithm have been analyzed and illustrated by several numerical examples. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

A selective newsvendor approach to order management

Consider a supplier offering a product to several potential demand sources, each with a unique revenue, size, and probability that it will materialize. Given a long procurement lead time, the supplier must choose the orders to pursue and the total quantity to procure prior to the selling season. We model this as a selective newsvendor problem of maximizing profits where the total (random) demand is given by the set of pursued orders. Given that the dimensionality of a mixed‐integer linear programming formulation of the problem increases exponentially with the number of potential orders, we develop both a tailored exact algorithm based on the L‐shaped method for two‐stage stochastic programming as well as a heuristic method. We also extend our solution approach to account for piecewise‐linear cost and revenue functions as well as a multiperiod setting. Extensive experimentation indicates that our exact approach rapidly finds optimal solutions with three times as many orders as a state‐of‐the‐art commercial solver. In addition, our heuristic approach provides average gaps of less than 1% for the largest problems that can be solved exactly. Observing that the gaps decrease as problem size grows, we expect the heuristic approach to work well for large problem instances. © 2008 Wiley Periodicals, Inc. Naval Research Logistics 2008     

A generalized assignment model for dynamic supply chain capacity planning

We consider a generalization of the well‐known generalized assignment problem (GAP) over discrete time periods encompassed within a finite planning horizon. The resulting model, MultiGAP, addresses the assignment of tasks to agents within each time period, with the attendant single‐period assignment costs and agent‐capacity constraint requirements, in conjunction with transition costs arising between any two consecutive periods in which a task is reassigned to a different agent. As is the case for its single‐period antecedent, MultiGAP offers a robust tool for modeling a wide range of capacity planning problems occurring within supply chain management. We provide two formulations for MultiGAP and establish that the second (alternative) formulation provides a tighter bound. We define a Lagrangian relaxation‐based heuristic as well as a branch‐and‐bound algorithm for MultiGAP. Computational experience with the heuristic and branch‐and‐bound algorithm on over 2500 test problems is reported. The Lagrangian heuristic consistently generates high‐quality and in many cases near‐optimal solutions. The branch‐and‐bound algorithm is also seen to constitute an effective means for solving to optimality MultiGAP problems of reasonable size. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012     

Optimal motion planning in rapid‐fire combat situations with attacker uncertainty

This article provides a modeling framework for quantifying cost and optimizing motion plans in combat situations with rapid weapon fire, multiple agents, and attacker uncertainty characterized by uncertain parameters. Recent developments in numerical optimal control enable the efficient computation of numerical solutions for optimization problems with multiple agents, nonlinear dynamics, and a broad class of objectives. This facilitates the application of more realistic, equipment‐based combat models, which track both more realistic models, which track both agent motion and dynamic equipment capabilities. We present such a framework, along with a described algorithm for finding numerical solutions, and a numerical example.     

斜拉桥监测系统传感器位置的寻优

分析了传感器系统尤其是传感器布点位置在桥梁结构健康监测中的重要性,对桥梁结构传感器优化布点作了详细的分类及论述。分析了遗传算法的特点和优点,并将其与传统优化算法作了比较。利用遗传算法研究了宁波招宝山独塔不对称斜拉桥健康监测系统中传感器的最优布点问题。结果表明,用遗传算法进行传感器最优布点具有结果稳定可靠,收敛迅速的特点,能够满足系统的要求。     

An asymptotically optimal greedy heuristic for the multiperiod single‐sourcing problem: The cyclic case

The dynamics of the environment in which supply chains evolve requires that companies frequently redesign their logistics distribution networks. In this paper we address a multiperiod single‐sourcing problem that can be used as a strategic tool for evaluating the costs of logistics network designs in a dynamic environment. The distribution networks that we consider consist of a set of production and storage facilities, and a set of customers who do not hold inventories. The facilities face production capacities, and each customer's demand needs to be delivered by a single facility in each period. We deal with the assignment of customers to facilities, as well as the location, timing, and size of inventories. In addition, to mitigate start and end‐of‐study effects, we view the planning period as a typical future one, which will repeat itself. This leads to a cyclic model, in which starting and ending inventories are equal. Based on an assignment formulation of the problem, we propose a greedy heuristic, and prove that this greedy heuristic is asymptotically feasible and optimal in a probabilistic sense. We illustrate the behavior of the greedy heuristic, as well as some improvements where the greedy heuristic is used as the starting point of a local interchange procedure, on a set of randomly generated test problems. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 412–437, 2003     

随机动态规划的混合算法研究

针对随机条件下动态规划模型的主要特点,运用智能算法混合编程理论,设计了一种探索多阶段决策问题的智能混合算法.该算法首先将问题转化成一族同类型的一步决策子问题,然后利用随机模拟和遗传算法,依据训练样本形成的训练神经元网络,在单步决策中寻求最优策略和最优目标值,逐个求解,再据初始状态逆序求出最优策略序列和最优目标值.仿真结果表明,该算法具有一定的通用性,初始设计点可以随机产生,其计算精度不因函数的非线性强弱而受影响,对目标和约束的限制较少,可应用于多种形式的随机多阶段决策优化问题,较好地满足了随机动态规划模型求解和优化的要求.     

动态威胁环境下单无人机测向定位航迹优化算法

为解决单架无人机在动态战场环境下的测向定位问题,提出了一种基于动态窗口法的单机测向定位航迹优化算法。以最大化Fisher信息矩阵行列式为测向定位评价准则,在由动态探测雷达和静/动障碍构成的动态战场环境中,基于动态窗口法思想,将测向定位航迹优化评价准则由传统的单步最优原则扩展到对多步预测航迹的评价,同时考虑雷达探测和静/动障碍环境对预测航迹的影响,通过滚动时域方法控制无人机最优航向。仿真结果表明,所提方法能够使无人机在有效逃避雷达探测威胁以及规避环境中静/动障碍的条件下保证对目标的高精度测向定位,为解决动态战场环境下的单架无人机测向定位问题提供了新思路。     

Path optimization for the resource‐constrained searcher

We formulate and solve a discrete‐time path‐optimization problem where a single searcher, operating in a discretized three‐dimensional airspace, looks for a moving target in a finite set of cells. The searcher is constrained by maximum limits on the consumption of one or more resources such as time, fuel, and risk along any path. We develop a specialized branch‐and‐bound algorithm for this problem that uses several network reduction procedures as well as a new bounding technique based on Lagrangian relaxation and network expansion. The resulting algorithm outperforms a state‐of‐the‐art algorithm for solving time‐constrained problems and also is the first algorithm to solve multi‐constrained problems. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Optimal FCFS allocation rules for periodic‐review assemble‐to‐order systems

In Assemble‐To‐Order (ATO) systems, situations may arise in which customer demand must be backlogged due to a shortage of some components, leaving available stock of other components unused. Such unused component stock is called remnant stock. Remnant stock is a consequence of both component ordering decisions and decisions regarding allocation of components to end‐product demand. In this article, we examine periodic‐review ATO systems under linear holding and backlogging costs with a component installation stock policy and a First‐Come‐First‐Served (FCFS) allocation policy. We show that the FCFS allocation policy decouples the problem of optimal component allocation over time into deterministic period‐by‐period optimal component allocation problems. We denote the optimal allocation of components to end‐product demand as multimatching. We solve the multi‐matching problem by an iterative algorithm. In addition, an approximation scheme for the joint replenishment and allocation optimization problem with both upper and lower bounds is proposed. Numerical experiments for base‐stock component replenishment policies show that under optimal base‐stock policies and optimal allocation, remnant stock holding costs must be taken into account. Finally, joint optimization incorporating optimal FCFS component allocation is valuable because it provides a benchmark against which heuristic methods can be compared. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 158–169, 2015     

基于改进人工蜂群算法的漏磁缺陷轮廓重构

漏磁缺陷重构是指由检测到的漏磁信号重构缺陷轮廓及参数,是实现漏磁反演的关键。将局部最优解和全局最优解引入到人工蜂群算法(Artificial Bee Colony Algorithm,ABC)中,提出了一种基于改进人工蜂群算法的缺陷重构模型。在该模型中,径向基函数神经网络作为前向模型求解漏磁信号,改进人工蜂群算法用于求解反演问题中的优化问题。将改进人工蜂群算法和基本人工蜂群算法作为反演算法进行了比较,实验结果表明,改进人工蜂群反演算法精度较高,速度较快,同时对实测信号具有鲁棒性,是一种有效可行的漏磁反演新方法。     

Dynamic inventory management with cash flow constraints

In this article, we consider a classic dynamic inventory control problem of a self‐financing retailer who periodically replenishes its stock from a supplier and sells it to the market. The replenishment decisions of the retailer are constrained by cash flow, which is updated periodically following purchasing and sales in each period. Excess demand in each period is lost when insufficient inventory is in stock. The retailer's objective is to maximize its expected terminal wealth at the end of the planning horizon. We characterize the optimal inventory control policy and present a simple algorithm for computing the optimal policies for each period. Conditions are identified under which the optimal control policies are identical across periods. We also present comparative statics results on the optimal control policy. © 2008 Wiley Periodicals, Inc. Naval Research Logistics 2008     

Optimal resource allocation and redistribution strategy in military conflicts with Lanchester square law attrition

We address the problem of optimal decision‐making in conflicts based on Lanchester square law attrition model where a defending force needs to be partitioned optimally, and allocated to two different attacking forces of differing strengths and capabilities. We consider a resource allocation scheme called the Time Zero Allocation with Redistribution (TZAR) strategy, where allocation is followed by redistribution of defending forces, on the occurrence of certain decisive events. Unlike previous work on Lanchester attrition model based tactical decision‐making, which propose time sequential tactics through an optimal control approach, the present article focuses on obtaining simpler resource allocation tactics based on a static optimization framework, and demonstrates that the results obtained are similar to those obtained by the more complex dynamic optimal control solution. Complete solution for this strategy is obtained for optimal partitioning of resources of the defending forces. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

作动器最优配置的柔性结构振动主动控制

柔性结构广泛应用于航空航天等领域,为了获得结构的最佳动力学性能,在主动振动控制中作动器或传感器位置优化成为关键。基于结构有限元动力学方程,在状态空间利用系统可控和可观Gramian矩阵考虑结构剩余模态的影响,推导一种新的作动器/传感器优化准则。根据优化准则结合非线性整数规划遗传算法对作动器的位置进行配置。以悬臂板为研究对象,采用基于状态反馈的线性二次型调节器研究悬臂板的振动控制效果。与其他配置方法进行比较,验证了新方法的优越性。     

Capacitated warehouse location model with risk pooling

In this article, we introduce the capacitated warehouse location model with risk pooling (CLMRP), which captures the interdependence between capacity issues and the inventory management at the warehouses. The CLMRP models a logistics system in which a single plant ships one type of product to a set of retailers, each with an uncertain demand. Warehouses serve as the direct intermediary between the plant and the retailers for the shipment of the product and also retain safety stock to provide appropriate service levels to the retailers. The CLMRP minimizes the sum of the fixed facility location, transportation, and inventory carrying costs. The model simultaneously determines warehouse locations, shipment sizes from the plant to the warehouses, the working inventory, and safety stock levels at the warehouses and the assignment of retailers to the warehouses. The costs at each warehouse exhibit initially economies of scale and then an exponential increase due to the capacity limitations. We show that this problem can be formulated as a nonlinear integer program in which the objective function is neither concave nor convex. A Lagrangian relaxation solution algorithm is proposed. The Lagrangian subproblem is also a nonlinear integer program. An efficient algorithm is developed for the linear relaxation of this subproblem. The Lagrangian relaxation algorithm provides near‐optimal solutions with reasonable computational requirements for large problem instances. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

多重优化的分布式无线覆盖探测算法

为满足无线通信网络信号覆盖有效性的实时实地可重复探测的需求,提出一种基于传感器网络的分布式无线覆盖探测算法。通过随机部署于目标区域内的无线传感器节点对无线通信网接收信号强度进行感知和预处理;利用变异函数构造新的BP神经网络目标函数,通过改进粒子群算法优化其初始权值和阈值;利用训练好的网络模型对存在探测盲区的目标区域进行插值估计,并联合传感器节点采集到的数据生成无线通信网络等信号强度线。仿真结果表明,所提算法比其他经典算法具有更高的精度,可有效探测目标区域无线通信网络的信号覆盖情况。     

Annealing adaptive search,cross‐entropy,and stochastic approximation in global optimization

The Annealing Adaptive Search (AAS) algorithm for global optimization searches the solution space by sampling from a sequence of Boltzmann distributions. For a class of optimization problems, it has been shown that the complexity of AAS increases at most linearly in the problem dimension. However, despite its desirable property, sampling from a Boltzmann distribution at each iteration of the algorithm remains a practical challenge. Prior work to address this issue has focused on embedding Markov chain‐based sampling techniques within the AAS framework. In this article, based on ideas from the recent Cross‐Entropy method and Model Reference Adaptive Search, we propose an algorithm, called Model‐based Annealing Random Search (MARS), that complements prior work by sampling solutions from a sequence of surrogate distributions that iteratively approximate the target Boltzmann distributions. We establish a novel connection between MARS and the well‐known Stochastic Approximation method. By exploiting this connection, we prove the global convergence of MARS and characterize its asymptotic convergence rate behavior. Our empirical results indicate promising performance of the algorithm in comparison with some of the existing methods. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011