| 分支定价割平面法求解带时间窗和人力分配的车辆路径问题 |
| |
| 引用本文： | 苏欣欣,伊廷刚,秦虎. 分支定价割平面法求解带时间窗和人力分配的车辆路径问题[J]. 交通运输工程与信息学报, 2021, 19(4): 75-86. DOI: 10.19961/j.cnki.1672-4747.2021.04.016 |
| |
| 作者姓名： | 苏欣欣 伊廷刚 秦虎 |
| |
| 作者单位： | 华中科技大学,管理学院,武汉430074;联勤保障部队供应局,武汉430000 |
| |
| 摘 要： | 本文研究了带时间窗和人力分配的车辆路径问题,并提出用分支定价割平面法来求其最优解.分支定价割平面法首先根据Dantzig-Wolfe分解技术将问题的数学模型分解为基于路径的主问题模型和求最短路径的子问题模型,然后利用列生成和标签算法在主问题和子问题之间进行迭代,并使用割平面法调整可行区域来求得主问题的最优松弛解,最后采用基于车辆数目和弧的分支策略获取原问题的整数解.算法中加入了两种加速策略:双向标签算法和递减搜索空间法.通过对多组算例进行测试,验证了模型和算法的准确性,并分析了患者数目和车辆数目对结果的影响,也说明了割平面法具有提高算法效率的作用.最后,对大规模算例进行测试的结果也为实际应用提供了理论依据.
|
| 关 键 词： | 车辆路径问题 人力分配 分支定价割平面法 救护车 列生成 |
Branch-and-Price-and-Cut Algorithm for the Manpower Allocation and Vehicle Routing Problem with Time Windows |
| |
| SU Xin-xin,YI Ting-gang,QIN Hu. Branch-and-Price-and-Cut Algorithm for the Manpower Allocation and Vehicle Routing Problem with Time Windows[J]. Journal of Transportation Engineering and Information, 2021, 19(4): 75-86. DOI: 10.19961/j.cnki.1672-4747.2021.04.016 |
| |
| Authors: | SU Xin-xin YI Ting-gang QIN Hu |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 万方数据 等数据库收录！ |
|
