详情

原文传递带时间窗车辆路径问题及其算法研究

论文题名：	带时间窗车辆路径问题及其算法研究
关键词：	车辆路径问题;时间窗;时差插入检测法;非代际克隆选择算法
摘要：	带时间窗的车辆路径问题(VehicleRoutingProblemwithTimeWindows，VRPTW)是对物流配送管理的核心问题——配送车辆调度的问题抽象，其是在基本VRP基础上添加了时间窗约束衍生而来的，可以将VRPTW描述为:使车辆从站点出发服务用户，完成用户需求后仍返回站点，规定每个用户只能被一辆车服务且仅服务一次，且对用户的服务必须在用户事先指定的时间窗内进行，问题的优化目标是如何选择适当的路径，使得在满足以上约束条件的情况下，完成全部需求花费的总成本最小或总利润最大。实践中许多运输管理问题均可抽象为VRPTW，如银行运钞车调度、邮政配送问题、工厂废弃物回收问题、校车问题、JIT生产调度等。本文围绕三类带时间窗车辆路径问题（基本的带时间窗车辆路径问题、带时间窗的取送货问题、带工作时间与时间窗的开放式车辆路径问题）展开研究，主要研究内容如下: 　　对带时间窗车辆路径问题的插入检测法进行了深入研究。主要作了以下三个方面的工作:一是对求解VRP的插入检测法进行了定义与分类，并对求解VRPTW插入检测法的已有研究成果进行梳理总结;二是对前推值插入检测法原理进行了数学证明，分析该插入检测法的计算复杂度表明:前推值插入检测法与传统的基于时间窗约束条件的插入检测法计算复杂度相当。三是提出了时差的概念及时差插入检测法，证明了该检测法的充要条件，分析其计算复杂度表明:其计算复杂度优于前推值插入检测法及传统的基于时间窗约束条件的插入检测法。仿真测试结果显示:时差插入检测法与前推值插入检测法一样有效，而前者的检测速度优于后者。　　对带时间窗车辆路径问题的插入启发式算法进行了深入研究。在介绍三种经典插入启发式算法的启发原理基础上，提出了时差插入启发式算法，介绍了时差插入启发式算法的启发规则，算法构架，仿真测试了该算法的最佳参数组合，比较该算法与三种经典插入启发式算法的求解质量表明:该算法的求解质量优于Solomon的插入启发式算法。　　对带时间窗取送货问题的深入研究。提出了求解带时间窗取送货问题的非代际遗传算法。相比于基本遗传算法，该算法有以下特点:一是采用基于个体的搜索机制，该机制能更好的保留优异个体与种群的多样性。二是改进编码方法，设计了包含最早完成时间、最迟开始时间的整数编码方法，该方法不仅能表示客户编号，而且能表示车辆在客户处的到达顺序，还能在变异、交叉过程及初始解生成过程中运用时差插入检测法。三是设计了适用于带时窗取送货问题的非对称匹配交叉、对称匹配交叉、线路交叉以及R1变异与R2变异等算子。仿真测试表明该算法比已有报道的求解带时间窗取送货问题的其它算法求解质量高。　　最后是对带工作时间与时间窗的开放式车辆路径问题及其克隆选择算法的研究。主要作了以下工作:一是提出了带工作时间与时间窗的开放式车辆路径问题，建立该问题的混合整数规划模型;二是提出了求解该问题的非代际免疫克隆选择算法，算法改进的原有克隆选择算法的克隆选择方法，并针对问题特点，设计了适用于该问题的R3变异算子。仿真测试表明该问题模型是有效的，且该算法在合理的时间内能求得满意解。
作者：	潘立军
专业：	交通运输工程
导师：	符卓
授予学位：	博士
授予学位单位：	中南大学
学位年度：	2012
正文语种：	中文