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     

目标通视性检测建模与仿真

在战斗机对地攻击选择武器投放位置以及巡航导弹选择地标点时,必须验证其选择位置的合理性,因此通视性检测是战斗机对地攻击规划的关键技术之一。提出了一种目标通视性检测的建模方法,分析了地形遮蔽盲区构成因素,给出了数字地图处理方法,建立了地形遮蔽盲区计算模型及发现目标概率模型,实现了目标的通视性检测,并进行了仿真验证。该模型为战斗机对地攻击选择武器投放位置和验证导弹地标点选择合理性提高了方法。     

X射线脉冲星的波形及其对光子接收的影响

建立了X射线脉冲星的X射线传播模型,在狭义相对论框架下研究了X射线脉冲星的波形及其对光子接收的影响。计算表明:脉冲星发出的X射线位于螺旋形的波带内,波带各处的厚度不同;波带上各同相点与脉冲星的距离不相等,不同倾角处的探测器接收到的脉冲的时长不相同。     

一种地形分析结果的多层次表示及量化方法

为了适应作战仿真智能实体的分层次路径规划,提出了一种地形分析结果的多层次表示及量化方法。根据全局路径规划与局部路径规划的概念和数字高程模型的多尺度表示模型,建立了地形坡度分析和可视性分析结果的多层次表示方法和量化公式。结合坡度计算和可视性计算公式,运用该方法实现了一个具体数字高程模型的多层次量化,分析了方法的有效性和可行性。试验结果表明：该方法可以实现分析结果的多层次表示,满足分层路径规划对地形分析的要求。     

VORONOI图的无人机航路快速初始规划

在分析VORONOI图的性质与威胁代价函数的基础上,针对航路的初始规划提出了一种先局部优化后进行全局优化的算法,从而避免在航路全局优化时陷入局部极小点的危险.通过对一个简单算例的分析,阐述了这种规划方法的合理性和快速性,给出了其对应的伪代码.它可对其他各种航路规划算法的边界条件进行初始预处理,快速确定初始可选航路集的解,缩短航路规划的时间;针对某阵地航路规划的仿真结果表明了该算法的有效性,初始的航路集有效地避开了威胁配置较密集的地方,同时尽量以较短的航路接近目标.     

计算机控制抛光中基于等面积增长螺旋线的加工路径

目前计算机控制抛光工艺中使用的阿基米德螺旋线路径,存在加工工件中心区域时工件转速过快的缺点.为了克服该缺点,分析了螺旋线路径加工的特点,分析表明工件的瞬时转速取决于加工点的驻留时间密度和螺旋线的面积增长速率.据此,提出了一种新的螺旋线作为抛光路径,该螺旋线的面积增长速率恒定,因此也称为等面积增长螺旋线.利用该螺旋线路径,加工转速趋于恒定,可降低加工中心区域的转速,从而降低对机床运动性能的要求,降低设备成本和加工成本.实验结果证实,阿基米德螺旋线路径加工中心区域容易产生过加工问题,加工精度较低;等面积增长螺旋线路径加工可避免中心区域过加工问题,获得较高的加工精度.     

一种应用于移动机器人的路径跟踪控制方法

针对移动机器人的路径跟踪复杂性问题,设计了一种易于实现的控制系统,其中的跟踪策略改进了传统的视线导航算法,使机器人光滑趋近到期望路径,控制器的设计采用基于模糊逻辑的变速度控制和角速度滑模控制,减小了角速度的抖振,并使控制具有一定的智能化特点.实验结果表明,设计的控制系统即可以保证路径跟踪的精度,同时避免了运动控制的不稳定性.     

接地双层介质上平面螺旋天线的数值分析与实验结果

本文对接地双层介质结构上的阿基米德平面螺旋天线进行了研究。以接地双层结构上水平赫芝偶极子Ｓｏｍｍｅｒｆｅｌｄ型积分的格林函数为基础,用矩量法求解积分方程,从而确定出螺旋天线臂上的电流分布。用渐近法估计Ｓｏｍｍｅｒｆｅｌｄ积分得到远区电场的解析表达式,由此计算出输入阻抗、方向图、功率增益和轴比。这些参数值对于双层结构上印刷线天线的优化设计具有重要指导意义。实验结果证明了数值方法的正确性     

分段线性凸费用网络流的两个算法

本文讨论了分段线性凸费用网络流问题,推广了线性费用网络流中的负回路方法和最小费用路方法,从而得到了求分段线性凸费用网络的最小费用流的两个算法。     

复杂环境下基于多目标粒子群的DWA路径规划算法

针对机器人在障碍物分布密集的复杂环境中运行时,动态窗口法(dynamic window approach,DWA)易出现避障失败或规划不合理的情况,提出一种基于多目标粒子群优化算法(multi-objective particle swarm optimization,MOPSO)的改进DWA规划算法。在建立多障碍物环境覆盖模型的基础上,提出一种障碍物密集度的判断方法;优化DWA算法中的子评价函数;利用改进的MOPSO算法实现DWA权重系数的动态调整,将权重系数的自适应变化问题转化为多目标优化问题;根据路径规划的要求将安全距离和速度作为优化目标,并使用改进的MOPSO算法对相应的多目标优化模型进行优化求解。仿真结果表明,该算法使机器人有效地通过障碍〖BHDWG8,WK10YQ,DK1*2,WK1*2D〗〖XCLXY.TIF;%129%129〗听语音 聊科研与作者互动 物密集区的同时兼顾了运行的安全性和速度,具有更好的路径规划效果。