动态多目标车辆路径问题的算法研究

作     者：钱艳婷 

作者单位：天津理工大学 

学位级别：硕士

导师姓名：王鹏涛

授予年度：2011年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 08[工学] 070105[理学-运筹学与控制论] 0701[理学-数学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：动态需求 多目标 混合算法 车辆路径问题 需求预测 灰色马尔科夫模型 

摘      要：近年来,随着社会市场竞争的日趋激烈,尤其是经济的飞速发展、多样化的社会运输交通工具、复杂性、多变性的交通运输网络,使得物流配送管理及其优化越来越受到整个社会各方面的关注。这些都促使了车辆路径问题的发展,也为车辆路径问题(Vehicle Routing Problem,VRP)的研究提供了广泛的现实基础,其中,实时处理车辆路径问题的应用研究,由于现代通信及其信息技术的发展成果而成为可能。 被称为“运筹学领域最为成功的研究之一的车辆路径问题(VRP)是理论和实践结合最为紧密的研究课题方向之一。现在,许多研究车辆路径问题的工作大部分都是集中在静态问题上,而对有动态需求变化方面的车辆路径问题的的研究很少。然而,随着社会和科学信息技术的发展,人们更希望在物流运输配送管理上能够实时的满足他们的需求。这样,就使得动态需求方面的车辆路径问题成为热点。因此,在对实际配送(尤其是动态需求)车辆路径问题的研究意义重大。 论文主要研究工作及成果有以下几个方面: 1.提出了动态需求VRP的多目标求解问题以及动态需求VRP的优化策略,采用基于灰色与马尔可夫链组合模型的需求预测方法将未知的信息转换成已知的信息,从而将动态问题转换为静态问题,重点研究基于优先预测的动态需求信息车辆路径问题的建模和相应的混合算法的策略问题,对于提高物流配送管理的工作效率和经济利益具有重大的现实意义和实用价值。 2.引入时间段和关键点的概念,建立了基于时间段和关键点的动态问题的优化策略,通过动态问题的静态化处理将动态车辆路径问题转化成若干静态子问题来进行求解,从而为动态车辆路径问题的求解提供新的优化策略。 3在将动态问题分解成若干静态子问题进行求解(即通过设立时间段和关键点),实现动态问题的静态化处理的基础上。最后,设计两种混合算法分别是基于预测优化策略和动态问题静态化处理的优化机制的基础上进行模型的求解,最后通过仿真实验论证,该混合算法可以提高效率。 a.基于遗传算法的混合算法,通过遗传算法的改进,在变异操作中加入禁忌搜索算法,利用遗传算法得到一个较好的初始解,提高解的质量,避免陷入“早熟的现象,并提出新颖的编码方式和交叉操作;并且在算法后期加入爬山算法,补充遗传算法局部搜索能力不足的缺陷。 b.基于禁忌搜索算法的混合算法,通过节约法得到的初始解,为禁忌搜索算法提供较好的初始解,从而提高整个混合算法的收敛速度。