论文部分内容阅读
随着现代市场经济的迅速发展和物流技术专业化水平的提高,物流配送业已经迅猛发展起来,配送成本在整个物流成本中占有较高比例。在客户需求位置已知的条件下,遵循各类约束,安排合理的配送路线,使得配送成本最小化,这是车辆路径问题(Vehicle Routing Problem,简称VRP)所研究的重点。车辆路径问题是一个典型的NP难问题,最早是Dantzig和Ramser于1959年提出的,受到了运筹学、经济学和应用数学等众多领域的广泛关注。近年来,车辆路径问题已经成为国内外学者的研究热点之一,主要集中在运用智能优化算法解决车辆路径问题上,其中遗传算法(Genetic Algorithm,简称GA)擅长解决全局最优化问题,简单通用,具有极强的容错能力和并行处理能力,尤其适用于对目标函数有诸多限制条件的多参数优化问题。目前,国内外研究人员运用遗传算法来求解车辆路径问题,并且取得一定的成果。但由于传统的遗传算法是个大范围、粗粒度的寻优算法,收敛速度慢且容易出现早熟现象,因此运用改进的遗传算法求解车辆路径问题成为研究人员的研究重点。案例推理是一种基于人类问题求解实例的计算模型,来源于Schank的动态存储理论,已经被成功的运用于经验管理、故障诊断和医药医疗等众多领域。CBR的各种应用在美国和欧洲已经得到相当发展,居世界领先。而国内对生产或商业化的CBR系统的研究还留有很大空白,目前主要集中在大学和科研院所的研究应用。本文通过引入案例推理(Case-based Reasoning,简称CBR)技术,模拟人类的思维经验,提出了一种基于案例推理的遗传算法(CBR-GA),结合了遗传算法的优点,有效解决了GA收敛速度慢和容易陷入早熟的问题,对求解VRP问题成效明显。本文主要做了如下工作:(1)结合CBR技术,提出CBR-GA算法,并用4阶欺骗问题验证了算法的可行性;(2)将CBR-GA算法应用于车辆路径问题,以车辆行驶路线的重心之间的距离为可行解的相似判别标准,根据相似度保存不相似的可行解,生成案例库;(3)提出差异化学习交叉算子,重组案例生成最优解决方案。