分支定价割平面法求解带时间窗和人力分配的车辆路径问题

本文研究了带时间窗和人力分配的车辆路径问题,并提出用分支定价割平面法来求其最优解。分支定价割平面法首先根据Dantzig-Wolfe分解技术将问题的数学模型分解为基于路径的主问题模型和求最短路径的子问题模型,然后利用列生成和标签算法在主问题和子问题之间进行迭代,并使用割平面法调整可行区域来求得主问题的最优松弛解,最后采用基于车辆数目和弧的分支策略获取原问题的整数解。算法中加入了两种加速策略:双向标签算法和递减搜索空间法。通过对多组算例进行测试,验证了模型和算法的准确性,并分析了患者数目和车辆数目对结果的影响,也说明了割平面法具有提高算法效率的作用。最后,对大规模算例进行测试的结果也为实际应用提供了理论依据。

一种多阶段对抗博弈的合成火力分配方法

如何进行贴近实际的合成火力分配是一个极具挑战性的课题。考虑到实际作战任务的多阶段特性,提出了一种新的回合制对抗策略及博弈模型,并设计了高效的确切解算法。红方对抗策略的首要目标设计为每一回合均最大化蓝方的损失,且最小化己方的损失。其次,针对战术目标的优先级问题,引入了权重系数分别表示蓝方和红方不同兵力的重要性,其值越高代表其被打击或保护的优先级越高。此外,首次引入了表征红方对自身损失敏感程度的超参数,其值小即对损失不敏感,意味着可采取较激进的战术。针对相应的整数线性规划模型,设计了分支定价算法。实验结果不仅表明了数学建模的正确性与合理性,而且验证了分支定价法相较于遗传算法的优越性。对抗策略设计、优先级量化方案以及损失敏感程度度量的合理性也得到了充分验证。此外,该新颖的对抗博弈模型及算法部分表现出了与传统兰彻斯特作战模型的一致性;而可调节的损失敏感参数,使得模型具有较好的兵力分配的灵活性,在达成战役目的的前提下,可实现兵力的阶段性投入并避免某一阶段无某一类型兵力可用的情况。