原文传递
一种求解带时间窗和容量约束的车辆路线问题有效的蚁群算法
| 论文题名： | 一种求解带时间窗和容量约束的车辆路线问题有效的蚁群算法 |
| 关键词： | 蚁群算法;车辆路径;容量约束;时间窗;最近邻近算法 |
| 摘要： | 带时间窗和容量约束的车辆路线问题(VRPTW)是在物流业中发生的一个重要问题。这个问题的目标是在不破坏客户时间窗要求和车辆不超载的情况下，以最小的成本代价，寻找一个最好的车辆配置方案，满足一些地域上分散的客户的搭载要求。同时，这些客户都有各自特定数量的货物需求，而且必须在预先定义的时间窗口之内对该客户的进行服务。在本文中，成功将蚁群算法(ACS)应用于解决带时间窗和容量约束的车辆路线问题。具体的算法实现是：(1)首先由一代蚂蚁按蚁群算法进行测试，尝试发现解决VRPTW问题的理想合适的车辆数目；(2)在上述确定的车辆数目限制下，实现车辆总的运行时间尽可能短。经典测试用例的实验结果证明了，蚁群算法应用到VRPTW上，与其他已经存在的解决VRPTW的算法相比，在解决问题的质量和计算速度上都具有很强的竞争性，是解决VRPTW问题较好的启发式搜索算法之一。 |
| 作者： | 姚友寿 |
| 专业： | 计算机软件与理论 |
| 导师： | 张军 |
| 授予学位： | 硕士 |
| 授予学位单位： | 中山大学 |
| 学位年度： | 2006 |
| 正文语种： | 中文 |
检索历史
应用推荐
