物流网络路径优化及其算法设计

论文摘要

物流配送路径优化是物流系统优化中关键的一环,如何经济的安排车辆配送路径是物流管理者面临的一个很重要的决策问题,如何设计能够快速得到问题的最优解的高效算法一直是专家们研究的热门问题。文章对物流配送路径优化中最短路径与车辆调度两个基本问题做了探讨,并给出解决问题的有效算法。针对物流配送网络中交通节点与图顶点的相似性,交通路线与图中边的可类比性,文章把地理交通网络模拟成计算机容易操作的数据结构—图。在实际运用中,由于配送中心必须快速响应客户要求,那么就需要实时计算车辆行驶最优路径,这就决定了最短路径问题的实现应该是高效率的。鉴于此,文章选择堆排序对地理网络中没有标记节点进行排序来改进Dijkstra算法以提高算法的执行效率。对于长途配送而言,交通堵塞和道路拥堵状况可以忽略不计,但对于城市配送而言,由于受交通堵塞和各种交通管制的影响,导致配送路径寻优更具复杂性。文章根据城市物流配送特点对Dijkstra算法进行扩展,使之能够根据实时的路况信息不断地调整行驶路线,这样可以有效地解决了这类问题。文章系统分析了遗传算法,并根据车辆路径问题的特点建立了数学模型,提出了一种改进的遗传算法求解车辆路径问题。在算法的求解过程中,构造了一种新的编码方式,能够显著减少编码长度。实验结果表明,本算法可以快速求得最优解,是求解车辆路径问题的一种有效算法。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 课题背景
• 1.2 研究现状
• 1.3 本文主要工作
• 1.3.1 物流配送系统优化中最短路径问题
• 1.3.2 物流配送系统优化中车辆路径问题
• 1.4 本文的结构安排
• 第2章 网络路径优化的图论基础
• 2.1 图与网络一些基本概念及属性
• 2.2 图与网络的存储结构
• 2.2.1 邻接矩阵表示法
• 2.2.2 邻接表法
• 2.2.3 邻接多重表
• 2.2.4 十字链表
• 2.3 图的搜索算法
• 2.3.1 图的遍历
• 2.3.2 广度优先遍历算法
• 2.4 最短路径问题与Dijkstra算法
• 2.4.1 单源最短路径问题
• 2.4.2 Dijkstra算法可行性证明
• 2.5 本章小结
• 第3章 基于扩展Dijkstra算法的物流配送路径优化
• 3.1 物流配送的概念、研究现状及意义
• 3.1.1 物流配送的概念
• 3.1.2 物流配送的研究现状
• 3.1.3 物流配送的意义及作用
• 3.2 Dijkstra算法在物流配送路径中的研究
• 3.2.1 无路障下配送路径优化与改进Dijkstra算法
• 3.2.2 有路障下路径优化与扩展的Dijkstra算法
• 3.3 城市物流配送路径优化问题的Dijkstra算法实现
• 3.3.1 案例分析
• 3.3.2 具有一般意义的解决方案
• 3.4 本章小结
• 第4章 遗传算法
• 4.1 遗传算法的发展
• 4.2 遗传算法的基本流程
• 4.3 遗传算法的实现方法
• 4.3.1 编码
• 4.3.2 适应度函数
• 4.3.3 遗传操作
• 4.3.4 停止准则
• 4.3.5 参数设定
• 4.4 遗传算法的基本理论
• 4.4.1 模式定理
• 4.4.2 隐含并行性
• 4.4.3 收敛问题
• 4.5 遗传算法的性能评估
• 4.6 遗传算法的特点及改进
• 4.6.1 遗传算法的优缺点
• 4.6.2 遗传算法的改进
• 4.7 发展方向
• 4.8 本章小结
• 第5章 车辆路径问题的改进遗传算法研究
• 5.1 车辆路径问题
• 5.1.1 车辆路径问题的定义
• 5.1.2 车辆路径问题特性
• 5.1.3 常见的基本问题
• 5.1.4 车辆路径问题的算法类型
• 5.2 带时间窗约束车辆路径问题的描述及其数学模型
• 5.3 带时间窗约束车辆路径问题的改进遗传算法设计
• 5.3.1 构造解的编码，产生初始群体
• 5.3.2 可行化过程
• 5.3.3 染色体的适应度计算
• 5.3.4 选择操作
• 5.3.5 染色体的交叉
• 5.3.6 染色体的变异
• 5.3.7 最佳染色体的保留
• 5.3.8 结束条件
• 5.4 实例分析
• 5.5 本章小结
• 结论
• 参考文献
• 附录
• 致谢