原文传递
基于聚类分析和遗传算法的带时间窗车辆路径问题研究
| 论文题名： | 基于聚类分析和遗传算法的带时间窗车辆路径问题研究 |
| 关键词： | 车辆路径问题;遗传算法;聚类分析;时间窗 |
| 摘要： | 车辆路径问题(VRP)是物流配送过程中的关键问题之一，随着物流配送行业竞争日益激烈和客户对物流配送时效性要求越来越高，对VRP的研究，尤其是对带时间窗车辆路径问题(VehicleRoutingProblemwithTimewindows，VRPTW)的研究，不仅可以帮助运输企业提高服务水平，为顾客提供快捷、准时、安全、舒适的服务，解决发展电子商务中速递这一“瓶颈”约束，而且有助于企业节约运输成本，改善车辆利用效率，缩短生产周期，加速资金周转，实现资源的合理配置，汲取“第三利润源泉”的财富，因此更加具有实际意义。 本文在认真分析国内外VRP研究现状的基础上，对带时间窗车辆路径问题进行深入分析，考虑道路拥挤程度对配送的影响，引入交通工程学中的道路阻抗系数，进而建立了带时间窗车辆路径问题的的数学模型。针对大规模车辆路径问题的特点，应用两阶段启发式算法求解，首先应用k-means聚类分析对配送网点进行配送区域划分，将大规模的VRP简化成小规模的VRP，降低计算量，提高求解速度；其次结合使用遗传算法，应用一种新颖的染色体编码和交叉方式，改进了传统的遗传算法，使求解过程大大简化，从而为快速、有效地优化带时间窗车辆路径问题创造了有利条件。通过MATLAB编程，有效地实现了对路径的自动寻优。并通过实例，进一步将运算结果与其他优化算法进行比较，证明了本文提出的改进遗传算法在处理路径优化问题上具有明显的优势，在所用配送车数量最小的前提下，可得到一个相对最短的行驶路线，实现总运行成本最低的目的。 |
| 作者： | 林郁丞 |
| 专业： | 交通运输规划与管理 |
| 导师： | 张正雄 |
| 授予学位： | 硕士 |
| 授予学位单位： | 福建农林大学 |
| 学位年度： | 2009 |
| 正文语种： | 中文 |
检索历史
应用推荐
