论文部分内容阅读
车辆路径问题(VRP)是物流配送末端的一项重要内容,而现代物流产业的飞速发展为车辆路径问题的研究提供了宽阔的应用空间。随着我国经济的高速增长,市场竞争的日益加剧,产业升级的不断加快,越来越多的企业把提高物流效率、降低物流成本作为提升本企业核心竞争能力的重要手段。目前对于VRP的研究多是基于确定性信息,在市场需求瞬息万变的现代社会,与配送相关的信息往往呈现某种统计规律,随机车辆路径问题(SVRP)专注于此类情况的研究。因此,对随机车辆路径问题的研究具有重要的学术意义和实用价值。本文针对随机需求的车辆路径问题进行研究,建立了带时间窗的和基于模糊预约时间的多目标问题模型,并设计了不同的混合量子进化算法对上述模型进行求解。纵观全文,本文的主要工作如下:(1)建立带时间窗的随机需求车辆路径问题(VRPSDTW)的数学模型,设计了一种基于免疫算子的混合量子进化算法(IQEA)对上述问题求解。针对车辆路径问题的特点,提出了一种基于整数排序的量子编码方式,并通过引用“虚拟客户点”的概念将多车配送简化为单车配送。采用概率选择最优解和动态旋转角度提高算法的精细搜索能力。引入免疫算子,保留优秀量子基段,避免出现倒退现象。对多组实例的仿真和与其他算法的对比,结果表明IQEA能获得90%以上的最优解,接种概率越大所得结果越精确,而且加入免疫算子的IQEA收敛速度更快。(2)在VRPSDTW的基础上,建立了基于模糊预约时间的多目标问题模型,针对该模型设计了一种量子进化算法(QEA)与粒子群算法(PSO)分段优化的方法对其进行求解。分别利用QEA搜索空间大和PSO快速收敛的特性,在进化的初始阶段使用QEA获得具有一定规模的非劣解集,并设计了一种转化方案将离散编码转化为连续编码,进而使用PSO的进化机制快速搜索最终的Pareto最优解。提出了一种自适应网格算法,通过自适应的改变网格密度保持Pareto最优解的多样性和均匀性。仿真结果表明,该方法不仅能获得足够数量的Pareto解,而且与其他算法的对比结果也显示该方法在解的均匀性、多样性以及收敛速度等方面都具有绝对优势。(3)在上述工作的基础上,搭建了随机车辆调度验证平台,对本文中的模型和算法进行检验,并结合GIS,通过Web页面直观展现出来。