有时间窗的车辆路径问题的近似算法研究

被引：21

作者：

刘小兰

郝志峰

汪国强

符克强

机构：

[1] 华南理工大学应用数学系

[2] 华南理工大学应用数学系广东　广州

[3] 广东　广州

来源：

计算机集成制造系统 | 2004年 / 07期

基金：

广东省自然科学基金;

关键词：

有时间窗的车辆路径问题; 大规模邻域搜索算法; 初始算法;

D O I：

10.13196/j.cims.2004.07.106.liuxl.019

中图分类号：

TP29 [自动化技术在各方面的应用];

学科分类号：

0811 ; 081101 ; 081102 ;

摘要：

为了克服原有大规模邻域搜索算法不能有效求解时间窗较宽的车辆路径问题的缺陷,介绍了有时间窗的车辆路径问题(VRPTW)的通用数学模型。通过分析各主要变量之间的关系,构造了一种简单、快速的确定性初始算法。通过引入”短路径优先策略”,构造了一种改进的大规模邻域搜索算法,该策略也可嵌入到求解时间窗比较窄的车辆路径问题中,达到加速搜索的目的。试验结果表明,改进的算法可以在较短的时间内有效地求得 VRPTW的优化解,是求解VRPTW的一个较好方案。

引用

页码：825 / 831

页数：7