模拟退火算法在带时间窗的车辆调度问题中应用

摘要

现代物流作为一种先进的组织方式和管理技术，被广泛认为是企业在降低物资消耗，提高劳动生产率之外的重要利润来源，在国民经济和社会发展中发挥着重要作用。在物流配送系统中，通过科学合理的方法确定运输路线和时间，不仅可以降低运作成本，还可以加快物质配送速度、提高运营效益和保证客户服务水平。 物流配送中的车辆调度问题(VehicleRoutingProblem，简称VRP)是一个NP-hard问题，该问题由Dantzig和Ramser于1959年首次提出。由于很多问题都可以抽象为这一问题，很快便引起运筹学、应用数学、组合数学、图论与网络分析、物流科学、计算机应用等学科的专家以及运输计划制定者的极大重视，并一直是运筹学与组合优化领域的前沿与热点问题。 在已有研究的基础上，本文研究了带时间窗的车辆调度问题(VehicleRoutingProblemwithTimeWindows，简称VRPTW)，该问题可以简单描述为：使车辆从站点出发完成客户的配送需求，在满足容量和时间窗约束下，选择合适的路径，使得完成全部客户的配送需求所需的总的成本最小。本文分析VRPTW所具有的特点以及以往对该问题研究，在此基础上把模拟退火算法用到该问题的求解中。首先采用SWEEP算法构建初始路径，然后通过模拟退火算法求得满意解，在解的改进过程中采用2-interchange技术构建邻域。最后通过实验测试说明该算法能够求解一定规模的VRPTW问题，并对温度下降速度对算法的影响作了分析。

目录

文摘

英文文摘

论文说明：图表目录

声明

致谢

第一章引言

1.1研究背景

1.2车辆调度问题的提出

1.3本文的研究内容

第二章车辆调度问题基本模型与算法

2.1 VRP与TSP的联系

2.2 VRP的研究现状

2.2.1国外对VRP的研究

2.2.2国内对VRP的研究

2.2.3车辆调度问题的分类

2.3车辆调度问题的基本模型与求解算法

2.3.1车辆调度问题的基本模型

2.3.2 VRP常用的求解算法

2.4本章小结

第三章带时间窗车辆调度问题研究

3.1引言

3.2 VRPTW问题建模

3.3 VRPTW问题求解算法

3.3.1初始解算法

3.3.2邻域交换技术

3.3.3亚启发式算法

3.4本章小结

第四章求解VRPTW的两阶段模拟退火算法

4.1约束处理

4.1.1预处理过程中时间窗约束处理

4.1.2节点路径分配时时间窗约束处理

4.2两阶段模拟退火算法

4.2.1初始解算法

4.2.2邻域构造

4.2.3模拟退火算法

4.3实验结果与分析

4.4本章小结

第五章总结与展望

5.1研究总结

5.2研究展望

参考文献

攻读硕士学位期间发表的论文