物流配送中车辆路径算法分析与研究

论文摘要

现代物流作为一种先进的组织方式和管理技术,通过降低流通费用,缩短流通时间,可以整合企业价值链、延伸企业的控制能力,加快企业资金周转。因此,随着社会的发展,作为第三利润的源泉,物流的重要性逐渐显现出来,越来越受到各个行业的重视。上到政府下到企业都纷纷探讨如何提高物流利润,使其成为一个重要的发展行业。通过分析研究人们发现配送成本在物流的各项成本当中占有相当高的比重,因此,对配送中心而言,合理的优化配送路径不仅可以简化配送程序、减少配送频率;而且更重要的是可以降低配送费用,从而带来更大的效益,因此配送路径的优化选择引起了各界人士的注意。本论文的研究就是围绕物流配送路径优化问题而展开的,通过分析目前国内外物流配送路径优化问题的研究现状,指出国内在路径优化方面存在的问题,提出本文所要解决的问题。本文首先对车辆路径问题进行分析,并具体介绍了一些重要的求解算法。然后,在对现有车辆路径问题求解算法进行分析的基础上,本文选择利用遗传算法求解VRP问题。根据对遗传算法基本原理及其存在缺陷的分析,提出了两种方法对遗传算法的进行改进。随后介绍了遗传算法基于自然数编码的编码理论,并且对遗传操作进行了具体介绍;重点研究了有时间窗约束的车辆路径问题的求解方法,提出了一种自适应混合遗传算法求解此类问题,并且通过对一个具体实例的分析,验证了此算法的可行性及优良的寻优能力。另外,由于实际中出现的往往是一些非确定性信息,如模糊信息等,研究确定性车辆路径问题的有效方法不一定能有效解决模糊车辆路径问题,因此本文对具有模糊预约时间的VRP问题进行了分析,对模糊车辆调度问题进行了初步探讨,提出了两种求解此问题的方法,并且提出一种新型的遗传操作的设计,最后对一个算例进行计算,提出引入用户主观决策的算法输出设计。最后,对论文的主要工作进行了总结,并对未来研究加以展望。希望本次课题的研究能对未来物流的实际应用能提供一些思路和方法。

论文目录

• 摘要
• ABSTRACT
• 第一章 引言
• 1.1 物流
• 1.1.1 物流的概念及发展
• 1.1.2 物流的结构
• 1.2 物流配送
• 1.2.1 物流配送的概念
• 1.2.2 我国物流配送的发展现状
• 1.3 物流网络规划
• 1.3.1 定位—运输路线安排问题LRP
• 1.3.2 LRP和LA、VRP的比较及相互关系
• 1.4 VRP研究动态及水平
• 1.5 本文研究的主要内容
• 第二章 车辆路径问题研究
• 2.1 VRP问题描述
• 2.2 一般VRP模型
• 2.2.1 模型中的决策变量
• 2.2.2 模型中参数的含义
• 2.2.3 车辆优化调度数学模型
• 2.3 VRP的分类
• 2.4 基本求解算法
• 2.4.1 精确算法
• 2.4.2 启发式算法
• 2.5 基本问题分析
• 2.5.1 两点间最短路问题
• 2.5.2 中国邮递员问题
• 2.5.3 旅行商问题TSP
• 2.6 一类车辆路径问题的求解算法
• 2.6.1 先安排线路后分组的方法
• 2.6.2 先分组后安排线路的方法
• 2.6.3 节约/插入算法
• 2.6.4 改进/交换算法
• 2.6.5 基于数学规划的算法
• 第三章 遗传算法原理及改进
• 3.1 遗传算法的发展过程及其特点
• 3.1.1 遗传算法的起源和发展
• 3.1.2 遗传算法的特点及其应用
• 3.2 标准遗传算法
• 3.2.1 遗传算法的基本原理
• 3.2.2 遗传算法基本操作介绍
• 3.3 标准遗传算法的早熟现象
• 3.4 遗传算法的改进
• 3.4.1 遗传算法参数的改进
• 3.4.2 混合遗传算法
• 3.5 本章小结
• 第四章 改进遗传算法求解车辆路径问题
• 4.1 遗传算法求解车辆路径问题
• 4.1.1 自然数编码理论
• 4.1.2 遗传操作介绍
• 4.2 改进的遗传算法求解具有时间窗约束的车辆路径问题
• 4.2.1 时间窗约束VRP介绍
• 4.2.2 遗传算法求解的几个重要步骤
• 4.2.3 自适应混合遗传算法设计
• 4.2.4 仿真实验及结果分析
• 4.3 模糊车辆路径问题
• 4.3.1 具有模糊预约时间的VRP问题介绍
• 4.3.2 多目标模糊VRP模型的建立
• 4.3.3 改进的遗传算法求解模糊预约时间车辆路径问题
• 4.3.4 仿真实验及结果分析
• 4.4 本章小结
• 第五章 总结与展望
• 5.1 总结
• 5.2 进一步的研究方向
• 致谢
• 参考文献
• 硕士就读期间发表的论文