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

摘要

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