Approximation results for min‐max path cover problems in vehicle routing

This article studies a min‐max path cover problem, which is to determine a set of paths for k capacitated vehicles to service all the customers in a given weighted graph so that the largest path cost is minimized. The problem has wide applications in vehicle routing, especially when the minimization of the latest service completion time is a critical performance measure. We have analyzed four typical variants of this problem, where the vehicles have either unlimited or limited capacities, and they start from either a given depot or any depot of a given depot set. We have developed approximation algorithms for these four variants, which achieve approximation ratios of max{3 ‐ 2/k,2}, 5, max{5 ‐ 2/k,4}, and 7, respectively. We have also analyzed the approximation hardness of these variants by showing that, unless P = NP , it is impossible for them to achieve approximation ratios less than 4/3, 3/2, 3/2, and 2, respectively. We have further extended the techniques and results developed for this problem to other min‐max vehicle routing problems.© 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

蚁群算法在车辆巡回保障中的应用研究

应用蚁群算法（ACA）解决车辆巡回保障问题,建立了车辆巡回保障优化数学模型,对轨迹更新规则进行了重新设定,给出了算法的实现步骤。通过算例分析,将计算结果与遗传算法（GA）和粒子群算法（PSO）作了比较,对模型和算法的正确性、高效性和适用性进行了验证。实验结果表明,该算法可以快速、有效求得车辆巡回保障的优化解,得到车辆巡回保障过程中的较优方案。     

一种曲伸式 DFB 光纤激光水听器探头的研究

为了提高 DFB(分布反馈式)光纤激光水听器的声压灵敏度,改善其动态特性,设计了一种曲伸式DFB 光纤激光水听器探头结构.该结构在保持激光器原有优点的同时,通过增大声压作用面积并将压力转化为对激光腔的轴向应变,有效地实现了声压增敏,同时通过机械结构改善了水听器的动态特性.利用有限元软件 ANSYS 对该结构进行了优化设计,加工制作了备构件并对 DFB 光纤激光器进行了封装,制作出长度约80 mm、直径仅6 mm的水听器原型样品并进行了实验研究.实验结果表明,采取该种形式的结构对 DFB光纤激光器进行封装后,探头的声压灵敏度提高了约17.5 dB,在500～1 500 Hz频率范围内具有较平坦的灵敏度响应.     

低速率移动自组织网络安全路由协议

由于移动Ad Hoc网络具有无需基础设施,可以快速部署,很难完全被摧毁等优点,被作为数字化战场通信的优先选择,设计实现了一种适用于低速率移动Ad Hoc网络的安全路由协议——LSRP,它适用于分层架构的低速移动电台自组网,可以在网络资源有限的情况下,防御来自外部和内部两方面的攻击。LSRP协议利用分布式门限RSA签名方案来阻止非授权接入,防范来自网络外部的攻击;利用邻节点信任度评估机制,进行恶意节点检测和剪除,防范来自网络内部的攻击,增强了网络的安全性。     

Asymptotic analysis of periodic policies for the inventory routing problem

In this article, a distribution system is studied where the sum of transportation and inventory costs is to be minimized. The inventory holding cost is assumed to be the same for all retailers. A fixed partition (FP) periodic policy is proposed with tight asymptotic worst‐case performance of 3/2 with respect to the best possible policy. This bound cannot be improved in the class of FP periodic policies. In partition‐based PB policies, the retailers are first partitioned into sets and then the sets are grouped in such a way that sets of retailers within a group are served together at selected times. A PB periodic, policy is presented with tight worst‐case asymptotic performance of with respect to the best possible policy. This latter performance improves the worst‐case asymptotic performance of of the previously best known policy for this problem. We also show that the proposed PB periodic policy has the best worst‐case asymptotic performance within the class of PB policies. Finally, practical heuristics inspired by the analyzed policies are designed and tested. The asymptotic worst–case performances of the heuristics are shown to be the same of those of the analyzed policies. Computational results show that the heuristics suggested are less than 6.4% on average from a lower bound on the optimal cost when 50 or more retailers are involved. © 2013 Wiley Periodicals, Inc. Naval Research Logistics 00: 000–000, 2013     

运用动态规划的智能卫星集群星间通信路由算法

通过建立智能卫星集群网络模型,把智能卫星集群星间通信路由问题转换为时延最短路径问题,进而提出一种求解此问题的智能卫星集群星间通信路由算法.该路由算法采用动态规划策略分阶段规划智能卫星集群两个成员之间的星间通信路由,在每个规划阶段,负责发送数据的智能卫星自主调用一种星间通信路由静态规划算法,以求出其在当前时刻的后继卫星来...     

气体炮法测评抗冲元件的动态特性

提出了一种测评抗冲元件动态特性的方法.通过气体炮发射的炮弹撞击砧块,使之获得一定的初速度,再利用砧块的惯性对抗冲元件施加冲击载荷.使用激光位移传感器和测力钢块分别测量力和位移,解决了特殊情况下数据测量的问题.     

JTIDS自组织组网路由协议及性能分析

文章在分析JTIDS数据链系统消息的基础上,提出了一种支持地面组网的路由协议(JMR),在不改动现有消息内容的前提下,可以实现JTIDS端机间的无中心自组织组网,并对时延、吞吐量、交付率、路由开销等方面性能进行了仿真分析。     

Chord算法及其改进策略

Chord算法因为查找效率高、查找时延可预测、负载均衡及可扩展性强等特点,成为基于分布式哈希表的一种典型的结构化P2P查找算法,并得到了广泛的应用。文章首先介绍了Chord算法的基本原理并对其优缺点进行了分析;然后对Chord算法的不同改进策略进行了对比分类,分析比较了改进后的性能,最后围绕进一步研究和使用Chord算法进行了讨论。     

Outsourcing warranty repairs: Dynamic allocation

In this paper we consider the problem of minimizing the costs of outsourcing warranty repairs when failed items are dynamically routed to one of several service vendors. In our model, the manufacturer incurs a repair cost each time an item needs repair and also incurs a goodwill cost while an item is awaiting and undergoing repair. For a large manufacturer with annual warranty costs in the tens of millions of dollars, even a small relative cost reduction from the use of dynamic (rather than static) allocation may be practically significant. However, due to the size of the state space, the resulting dynamic programming problem is not exactly solvable in practice. Furthermore, standard routing heuristics, such as join‐the‐shortest‐queue, are simply not good enough to identify potential cost savings of any significance. We use two different approaches to develop effective, simply structured index policies for the dynamic allocation problem. The first uses dynamic programming policy improvement while the second deploys Whittle's proposal for restless bandits. The closed form indices concerned are new and the policies sufficiently close to optimal to provide cost savings over static allocation. All results of this paper are demonstrated using a simulation study. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005