Decomposition-based approximation algorithms for the one-warehouse multi-retailer problem with concave batch order costs

We study the one-warehouse multi-retailer problem under deterministic dynamic demand and concave batch order costs, where order batches have an identical capacity and the order cost function for each facility is concave within the batch. Under appropriate assumptions on holding cost structure, we obtain lower bounds via a decomposition that splits the two-echelon problem into single-facility subproblems, then propose approximation algorithms by judiciously recombining the subproblem solutions. For piecewise linear concave batch order costs with a constant number of slopes we obtain a constant-factor approximation, while for general concave batch costs we propose an approximation within a logarithmic factor of optimality. We also extend some results to subadditive order and/or holding costs.     

不确定环境下无人机区域目标搜索及载荷参数影响

针对不确定环境下无人机区域搜索问题,建立了实时探测更新的搜索方法,提出了机载光电载荷参数优化配置策略。建立了基于二维离散网格的无人机区域搜索模型,采用概率地图描述目标信息的实时获取与更新;引入不确定度指标、目标网格的重访和网格探测次数控制,建立搜索目标函数;建立了基于粒子群算法的搜索路径滚动优化方法;通过对任务区域平均探测时间步数和误判概率的估计分析,建立了机载光电载荷参数优化配置策略。使用蒙特卡洛方法验证了区域搜索方法的有效性和光电载荷参数配置对搜索效率、误判概率的影响。     

Heuristics for the location of inspection stations on a network

This article considers the preventive flow interception problem (FIP) on a network. Given a directed network with known origin‐destination path flows, each generating a certain amount of risk, the preventive FIP consists of optimally locating m facilities on the network in order to maximize the total risk reduction. A greedy search heuristic as well as several variants of an ascent search heuristic and of a tabu search heuristic are presented for the FIP. Computational results indicate that the best versions of the latter heuristics consistently produce optimal or near optimal solutions on test problems. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 287–303, 2000     

一种基于目标的雷达对抗侦察策略

传统的电子战接收系统的搜索方式主要针对参数完全未知的敌方信号,通过在频域、空域等各维度进行大范围的逐段重复搜索可在较长时间内获得较好的侦察效果,但不适合短时间内对特定目标群的搜索和验证。针对电子战接收机存在的盲目侦察接收、与作战目标结合不紧密等问题,提出了一种基于作战目标的侦察策略,能够智能引导超外差接收机进行搜索截获,有效提升了超外差接收机对重点目标的实时截获与准确识别能力。     

VNS和SA相结合的指挥控制资源部署

针对指挥控制资源部署问题,引入任务复杂度来定义决策实体的工作负载,并建立以最小化决策实体工作负载的均方根为目标的优化模型。针对传统的层次聚类法容易陷入局部最优,提出了一种变邻域搜索(Variable Neighborhood Search,VNS)和模拟退火(Simulated Annealing,SA)相结合的具有全局性的求解方法,使用VNS进行全局寻优,使用SA对VNS中的邻域进行局部寻优。最后通过一个联合作战案例的平台调度方案,验证了所提方法的优越性。     

SpaceWire网络混合路由机制设计

针对星上系统总线多元性导致的星载网络接口和协议不能标准化的发展瓶颈,基于SpaceWire总线协议,通过将静态路由(时间触发)与动态路由(事件触发)机制结合,实现了控制数据和载荷数据共用网络。静态路由完全遵循SpaceWire-D协议,在保证确定性传输的同时,通过启发式调度算法首次实现了多时间窗并行调度,并提出利用最大公约数法设计时间窗,以提高网络吞吐量;动态路由通过对随机事件和载荷数据分配优先级,实现传输路径冲突时对紧急任务的优先处理。在OPENT中搭建网络系统仿真模型,对所提出的路由机制进行了仿真。实验结果表明,静态路由时段网络吞吐量较现有调度算法有明显提高,动态路由实现了紧急事件优先传输。     

风对反潜巡逻机应召搜索延迟时间的影响研究

为了定量分析风对反潜巡逻机应召搜索延迟时间的影响,根据飞行气象学中风对飞行的影响描述以及实际需求,建立了反潜巡逻机飞往潜艇初始概略位置的航路模型。研究结果证明了模型的正确性,并通过仿真分析了反潜巡逻机的航速和航向、风速和风向的变化对延迟时间的影响。结果表明风对延迟时间的影响是不能忽略的,为反潜巡逻机航路的优化、应召搜索效能的提高提供了决策依据。     

A cooperative game in search theory

Search theory originates from the military research efforts of WWII. Most researchers of that period modeled their search games in noncooperative games, where players are enemies or compete against each other. In this article, we deal with a cooperative search game, where multiple searchers behave cooperatively. First we describe several search problems and discuss the possibility of a coalition or cooperation among searchers. For the cooperative search game, we define a function named quasi‐characteristic function, which gives us a criterion similar to the so‐called characteristic function in the general coalition game with transferable utility. The search operation includes a kind of randomness with respect to whether the searchers can detect a target and get the value of the target. We also propose a methodology to divide the obtained target value among members of the coalition taking account of the randomness. As a concrete problem of the cooperative search game, we take the so‐called search allocation game, where searchers distribute their searching resources to detect a target in a cooperative way and the target moves in a search space to evade the searchers. Lastly, we discuss the core of the cooperative search allocation game. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

区域目标搜索中基于改进RRT的UAV实时航迹规划

在线自主航迹规划是无人机(Unmanned Aerial Vehicles,UAV)执行区域目标搜索任务的有效保证.针对UAV区域搜索中航迹规划的实时性要求,提出了一种固定搜索模式和动态搜索模式相结合的UAV自主航迹规划框架.在快速扩展随机树(RRT)方法的基础上,通过改进随机扩展树的节点选择和引入启发式信息,提出了基于改进RRT的UAV实时搜索航迹规划算法,该算法能够有效降低在线航迹规划的时间代价和扩展节点数.仿真实验结果验证了本文方法的有效性.     

直升机吊放声纳搜索方法效能研究

利用直升机吊放声纳对潜艇目标进行搜索,是航空反潜作战的重要环节.引入蒙特卡罗法对吊放声纳搜潜方法进行效能评估,以概率和统计理论方法得出其搜索概率作为评定吊放声纳搜潜方法效能的指标.对三种吊放声纳搜潜方法进行了效能仿真.通过计算机模拟对三种方法对潜艇目标的搜索概率进行比较,结果表明采用蒙特卡罗法对吊放声纳搜潜方法进行效能评估是可行有效的.