论文部分内容阅读
现代物流产业是国民经济的支柱产业和新的经济增长点,是流通业的物质基础,是企业的第三利润源泉。作为现代物流中一项重要内容,车辆路径调度问题(Vehicle Routing Problems,简称VRP)一直是影响企业经济效益的一个重要方面。通过各种有效手段,不断优化车辆路径调度,将给企业带来巨大的经济效益。目前对车辆路径调度问题的研究,都基于一个基本条件:已知路径信息中没有或很少有冗余信息,也即车辆最后的结果是遍历所有城市。然而现实的车辆路径调度问题中,路径冗余信息是经常存在的,特别是包含城市较多的较大区域内的车辆路径调度,很难预先排除所有一定不会经过的城市。对于这样一类问题,目前相关研究开展的还不多。本文以车辆路径调度问题为主线,在对国内外现有研究成果及技术发展脉络进行系统总结的基础上,提出了一类复杂的车辆路径调度问题:非遍历VRP。在分析比较当前流行的启发式优化算法的基础上,对人工蚁群算法进行了有效的改进,提出了一种新型的启发式优化算法:聪明蚁群算法。并通过一系列仿真实验证明了其用于求解非遍历VRP的有效性。最后,对非遍历VRP的多路扩展问题:非遍历MVRP(Multi Vehicle Routing Problems,简称MVRP)做了初步探讨,并改进聪明蚁群算法,对非遍历MVRP做了初步求解尝试。本文的主要创新研究成果包括:(1) 基于物流运输企业车辆路径调度实际,提出了一类非遍历、重复路径、带时间窗的复杂车辆路径调度问题,对相关领域的研究成果进行了综述,分析了传统优化算法求解这类复杂车辆路径调度问题的困难所在,分析了求解这类问题的算法应具有的特点。(2) 针对约束复杂,难以建立数学模型的优化问题,提出了一种结构化求解方法。这种方法借鉴模块化程序设计思想,将优化命题的求解过程分成几个关联模块,具有良好的通用性和可扩展性。(3) 针对本文提出的车辆路径调度问题,在人工蚁群算法的基础上,通过引入蚂蚁在搜索前及在搜索过程中对食物方位能大致确定的概念,提出了一类新型的启发式优化算法:聪明蚁群算法。该方法既继承了人工蚁群算法不依赖初始解的特点,又克服了非遍历及路径重复带来的易陷入局部最优问题。仿真实验证明了该算法在求解该类车辆路径调度问题的有效性。