The gradual covering problem

In this paper we investigate the gradual covering problem. Within a certain distance from the facility the demand point is fully covered, and beyond another specified distance the demand point is not covered. Between these two given distances the coverage is linear in the distance from the facility. This formulation can be converted to the Weber problem by imposing a special structure on its cost function. The cost is zero (negligible) up to a certain minimum distance, and it is a constant beyond a certain maximum distance. Between these two extreme distances the cost is linear in the distance. The problem is analyzed and a branch and bound procedure is proposed for its solution. Computational results are presented. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

Algorithms for solving the conditional covering problem on paths

Consider the conditional covering problem on an undirected graph, where each node represents a site that must be covered by a facility, and facilities may only be established at these nodes. Each facility can cover all sites that lie within some common covering radius, except the site at which it is located. Although this problem is difficult to solve on general graphs, there exist special structures on which the problem is easily solvable. In this paper, we consider the special case in which the graph is a simple path. For the case in which facility location costs do not vary based on the site, we derive characteristics of the problem that lead to a linear‐time shortest path algorithm for solving the problem. When the facility location costs vary according to the site, we provide a more complex, but still polynomial‐time, dynamic programming algorithm to find the optimal solution. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

A cover based competitive facility location model with continuous demand

In this paper we propose and solve a competitive facility location model when demand is continuously distributed in an area and each facility attracts customers within a given distance. This distance is a measure of the facility's attractiveness level which may be different for different facilities. The market share captured by each facility is calculated by two numerical integration methods. These approaches can be used for evaluating functional values in other operations research models as well. The single facility location problem is optimally solved by the big triangle small triangle global optimization algorithm and the multiple facility problem is heuristically solved by the Nelder‐Mead algorithm. Extensive computational experiments demonstrate the effectiveness of the solution approaches.     

An integer decomposition algorithm for solving a two‐stage facility location problem with second‐stage activation costs

We study a stochastic scenario‐based facility location problem arising in situations when facilities must first be located, then activated in a particular scenario before they can be used to satisfy scenario demands. Unlike typical facility location problems, fixed charges arise in the initial location of the facilities, and then in the activation of located facilities. The first‐stage variables in our problem are the traditional binary facility‐location variables, whereas the second‐stage variables involve a mix of binary facility‐activation variables and continuous flow variables. Benders decomposition is not applicable for these problems due to the presence of the second‐stage integer activation variables. Instead, we derive cutting planes tailored to the problem under investigation from recourse solution data. These cutting planes are derived by solving a series of specialized shortest path problems based on a modified residual graph from the recourse solution, and are tighter than the general cuts established by Laporte and Louveaux for two‐stage binary programming problems. We demonstrate the computational efficacy of our approach on a variety of randomly generated test problems. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

舰船维修器材保障点选址决策模型及算法

传统的最大覆盖选址模型没有考虑对服务半径外的需求点的满足和服务时间的响应,而在舰船维修器材保障中,不论需求点到保障点的距离是否大于服务半径,都应对其进行保障服务,且在保障过程中要满足保障时间控制在不影响舰船正常维修任务时间内。针对此问题,运用广义最大覆盖选址模型和时间满意度函数,构建基于时间满意的广义最大覆盖选址模型,并运用一种混合算法———基于遗传模拟退火算法的BP算法对模型进行求解。最后,运用该算法对实例进行了分析计算,计算结果验证了该算法的有效性。     

Single-lane bridge serving two-lane traffic

This paper presents a mathematical model of a single-lane bridge serving two-way traffic in alternating directions (with an FIFO rule observed within each directional queue). While the bridge serves cars moving in one direction, cars approaching from the opposite direction wait in a queue at its foot. When cars in the current direction finish crossing the bridge, it begins serving cars from the other direction, if any are present. A newly-arrived car finding an empty bridge mounts it immediately. Several cars moving in the same direction may occupy the bridge simultaneously. The crossing speed is assumed to be constant, and the arrival processes in both directions are assumed to be independent, homogeneous Poisson processes. A generalization of the alternating-priority models [1, 2] is developed to arrive at the Laplace-Stieltjes transform and the expected value of the flow time (the time interval between the moments of arrival at the bridge and departure from it) for steady state conditions. The results are discussed and some examples are presented graphically.     

Values for optimum reject allowances

Industrial situations exist where it is necessary to estimate the optimum number of parts to start through a manufacturing process in order to obtain a given number of completed good items. The solution to this problem is not straightforward when the expected number of rejects from the process is a random variable and when there are alternative penalties associated with producing too many or too few items. This paper discusses various aspects of this problem as well as some of the proposed solutions to it. In addition, tables of optimum reject allowances based on a comprehensive model are presented.     

基于点模式匹配的雷达航迹与航行计划匹配算法

在雷达航迹与航行计划匹配时,针对传统算法对单点信息依赖程度较高,在信息缺失、目标机动等情况下匹配效果差的问题,提出了一种基于滑窗的改进点模式匹配算法。首先,提取了雷达航迹多特征点,利用特征点集弥补单点信息的不足,通过简化匹配分数的计算,降低了点模式匹配复杂度。仿真实验结果表明,改进的点模式匹配算法显著提高了信息缺失、目标机动等情况下的匹配正确率。     

A note on equity across groups in facility location

An equity model between groups of demand points is proposed. The set of demand points is divided into two or more groups. For example, rich and poor neighborhoods and urban and rural neighborhoods. We wish to provide equal service to the different groups by minimizing the deviation from equality among groups. The distance to the closest facility is a measure of the quality of service. Once the facilities are located, each demand point has a service distance. The objective function, to be minimized, is the sum of squares of differences between all pairs of service distances between demand points in different groups. The problem is analyzed and solution techniques are proposed for the location of a single facility in the plane. Computational experiments for problems with up to 10,000 demand points and rectilinear, Euclidean, or general ?_p distances illustrate the efficiency of the proposed algorithm. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

A multifacility capacity expansion model with joint expansion set-up costs

This article describes a multifacility capacity expansion model in which the different facility types represent different quality levels. These facility types are used to satisfy a variety of deterministic demands over a finite number of discrete time periods. Applications for the model can be found in cable sizing problems associated with the planning of communication networks. It is assumed that the cost function associated with expanding the capacity of any facility type is concave, and that a joint set-up cost is incurred in any period in which one or more facilities are expanded. The model is formulated as a network flow problem from which properties associated with optimal solutions are derived. Using these properties, we develop a dynamic programming algorithm that finds optimal solutions for problems with a few facilities, and a heuristic algorithm that finds near-optimal solutions for larger problems. Numerical examples for both algorithms are discussed.     

Manpower modeling in cost effectiveness studies of usaf program to reduce the incidence of heart disease

Planning for a cardiovascular disease reduction program, soon to be initiated by the United States Air Force, has required an evaluation of its expected cost effectiveness. During the course of this evaluation, it was necessary to consider manpower flows and their expected changes in response to the disease reduction program. This paper describes several manpower models that were applied: a simple expected value equilibrium model; a cross-sectional model that considered the length of service of personnel; and a staffing model used to optimize the allocation of paramedics to the many Air Force bases of various sizes. The relevance of these models to the cost effectiveness evaluation is shown but the detailed cost effectiveness results are not presented.     

A capacity-expansion model for two facility types

This paper describes a deterministic capacity-expansion model for two facility types with a finite number of discrete time periods. Capacity expansions are initialed either by new construction or by the conversion of idle capacity from one facility type to the other. Once converted, the capacity becomes an integral part of the new facility type. The costs incurred include construction, conversion, and holding costs. All cost functions are assumed to be nondecreasing and concave. Using a network flow approach, the paper develops an efficient dynamic-programming algorithm to minimize the total costs when the demands for additional capacity are nonnegative in each period. Thereafter, the algorithm is extended for arbitrary demands. The model is applied to a cable-sizing problem that occurs in communication networks, and numerical examples are discussed.     

Analysis of a machine repair problem with an unreliable server and phase type repairs and services

In this paper we study a machine repair problem in which a single unreliable server maintains N identical machines. The breakdown times of the machines are assumed to follow an exponential distribution. The server is subject to failure and the failure times are exponentially distributed. The repair times of the machine and the service times of the repairman are assumed to be of phase type. Using matrix‐analytic methods, we perform steady state analysis of this model. The time spent by a failed machine in service and the total time in the repair facility are shown to be of phase type. Several performance measures are evaluated. An optimization problem to determine the number of machines to be assigned to the server that will maximize the expected total profit per unit time is discussed. An illustrative numerical example is presented. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 462–480, 2003     

An integer programming model for the weekly tour scheduling problem

We study a workforce planning and scheduling problem in which weekly tours of agents must be designed. Our motivation for this study comes from a call center application where agents serve customers in response to incoming phone calls. Similar to many other applications in the services industry, the demand for service in call centers varies significantly within a day and among days of the week. In our model, a weekly tour of an agent consists of five daily shifts and two days off, where daily shifts within a tour may be different from each other. The starting times of any two consecutive shifts, however, may not differ by more than a specified bound. Furthermore, a tour must also satisfy constraints regarding the days off, for example, it may be required that one of the days off is on a weekend day. The objective is to determine a collection of weekly tours that satisfy the demand for agents' services, while minimizing the total labor cost of the workforce. We describe an integer programming model where a weekly tour is obtained by combining seven daily shift scheduling models and days‐off constraints in a network flow framework. The model is flexible and can accommodate different daily models with varying levels of detail. It readily handles different days‐off rules and constraints regarding start time differentials in consecutive days. Computational results are also presented. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 607–624, 2001.     

A facility reliability problem: Formulation,properties, and algorithm

Having a robustly designed supply chain network is one of the most effective ways to hedge against network disruptions because contingency plans in the event of a disruption are often significantly limited. In this article, we study the facility reliability problem: how to design a reliable supply chain network in the presence of random facility disruptions with the option of hardening selected facilities. We consider a facility location problem incorporating two types of facilities, one that is unreliable and another that is reliable (which is not subject to disruption, but is more expensive). We formulate this as a mixed integer programming model and develop a Lagrangian Relaxation‐based solution algorithm. We derive structural properties of the problem and show that for some values of the disruption probability, the problem reduces to the classical uncapacitated fixed charge location problem. In addition, we show that the proposed solution algorithm is not only capable of solving large‐scale problems, but is also computationally effective. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Polynomial algorithms for center location on spheres

When locating facilities over the earth or in space, a planar location model is no longer valid and we must use a spherical surface. In this article, we consider the one-and two-center problems on a sphere that contains n demand points. The problem is to locate facilities to minimize the maximum distance from any demand point to the closest facility. We present an O(n) algorithm for the one-center problem when a hemisphere contains all demand points and also give an O(n) algorithm for determining whether or not the hemisphere property holds. We present an O(n³ log n) algorithm for the two-center problem for arbitrarily located demand points. Finally, we show that for general p, the p center on a sphere problem is NP-hard. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44: 341–352, 1997     

舰机协同反潜有利态势初探

为研究舰机协同反潜的典型有利态势,为指挥决策提供依据。首先,依据敌我探测距离、攻击距离的对比,提出了舰机协同反潜有利态势的判断原则;其次,利用该判断原则对三种典型对抗条件下的战场态势进行了深入分析,得到了各种对抗条件下的有利态势;最后,分析了有利态势对作战指挥决策的重要作用,初步提出了基于有利态势的作战指挥决策流程。为进一步研究基于有利态势的舰机协同攻潜辅助决策方案生成奠定了基础。     

助推段反导的动能拦截弹导引律设计

为降低需用过载，对助推段反导的空基动能拦截弹导引律进行分析研究。在建立导引系统模型的基础上，增加修正因子，分析碰撞拦截点处的过载需求；区分有无预测拦截点距离误差的情况，仿真分析了拦截弹道和过载动态响应。仿真结果表明，该导引律能降低需用过载，实现碰撞拦截。     

An algorithm for the solution of a location problem with metric constraints

In many location problems, the solution is constrained to lie within a closed set. In this paper, optimal solutions to a special type of constrained location problem are characterized. In particular, the location problem with the solution constrained to be within a maximum distance of each demand point is considered, and an algorithm for its solution is developed and discussed.     

相参辐射源安全诱偏反辐射导弹研究

相参诱偏技术,相对目前广泛采用的非相参诱偏技术,理论上可将反辐射导弹诱偏至导弹杀伤半径外的安全区域,具有一定的应用前景,其实现难点主要在于相位差的控制。通过两点源反辐射导弹诱偏模型,得出相参辐射源安全诱偏反辐射导弹所需要的相位差,提出利用交互多模-概率数据关联滤波估计的方法对反辐射导弹的位置进行滤波估计以减少相位差误差。仿真试验表明,该方法能有效提高定位精度,减少相位差误差。