基于遗传算法的配送路线优化研究

论文摘要

随着物流业在我国的不断发展以及物流专业化水平的不断提高,我国物流配送业近年来也得到了迅速的发展。在物流配送活动中,配送车辆路线优化问题是配送合理化的核心问题,时间窗约束在配送路线优化过程中具有举足轻重的作用。因此对带时间窗的车辆路线问题进行研究具有一定的理论价值和现实意义。本文对单站点、非满载带时间窗城市物流配送的车辆路线问题进行了研究。首先从城市物流入手,分析了城市物流的特点和分类属性及车辆路线问题的主要应用领域。在基本车辆路线问题模型的基础上建立了带时间窗车辆路线问题的数学模型。对带时间窗的车辆路线问题设计了改进的遗传算法。论文采用自然数编码的方法,初始群体的生成采用混合方式,即部分随机生成、部分根据初始解生成,选择策略采用轮盘赌选择法和截断选择法相结合的方法,用改进的边重组法代替常用的PMX、OX、CX交叉法。根据设定的终止条件,最终取得满意解。最后,通过C++实现了算法,用Solomon测试数据里C101中25个客户集的数据进行验证,并与不同算法所得解进行对比,其求解结果和计算时间都有明显改进。本文所得结果,在基于遗传算法求解城市物流配送车辆路径问题领域和物流系统的开发中具有一定的参考价值。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 引言
• 1.2 课题的提出及研究意义
• 1.3 VRPTW 国内外研究现状分析及待解决的问题
• 1.3.1 国外关于VRPTW 问题的发展及研究现状
• 1.3.2 国内关于VRPTW 问题的发展及研究现状
• 1.3.3 国内外研究中待解决的问题
• 1.4 本课题的研究内容和研究方法
• 第二章 城市物流配送中带时间窗的车辆路径问题研究
• 2.1 城市物流特征及发展城市物流意义
• 2.1.1 城市物流
• 2.1.2 城市物流特征
• 2.1.3 发展城市物流的意义
• 2.2 车辆路线问题
• 2.2.1 车辆路线问题简介
• 2.2.2 车辆路线问题分类
• 2.3 一般车辆路线问题模型
• 2.4 车辆路线问题的求解算法
• 2.4.1 组合优化问题
• 2.4.2 计算复杂性
• 2.4.3 精确优化方法
• 2.4.4 启发式方法（Heuristics）
• 2.5 车辆路径问题及带时间窗的车辆路径问题的应用
• 2.6 小结
• 第三章 遗传算法的理论基础及应用
• 3.1 遗传算法的产生及思想
• 3.2 遗传算法的数学基础
• 3.2.1 模式定理
• 3.2.2 Walsh 模式变换及欺骗问题
• 3.2.3 隐含并行性
• 3.2.4 算法的收敛性
• 3.3 遗传算法的特点及其应用
• 3.3.1 遗传算法的特点
• 3.3.2 遗传算法的应用
• 3.4 遗传算法的研究现状
• 3.5 遗传算法的基本步骤
• 3.6 小结
• 第四章 遗传算法在带时间窗的车辆路径问题中的运用
• 4.1 带时间窗的车辆路径问题模型
• 4.2 遗传算法求解带时间窗的车辆路径问题
• 4.2.1 染色体的编码与解码
• 4.2.2 初始群体的生成
• 4.2.3 适应度函数
• 4.2.4 选择策略
• 4.2.5 交叉概率、变异概率
• 4.2.6 交叉算子
• 4.2.7 变异算子
• 4.2.8 算法终止规则
• 4.3 算法试验分析
• 4.4 小结
• 结论与展望
• 1.论文结论
• 2.论文展望
• 参考文献
• 攻读硕士研究生期间发表的论文
• 致谢