论文部分内容阅读
物流配送路径优化,即车辆路径问题(Vehicle Routing Problem, VRP),是当今物流配送优化中关键的一环,也是电子商务活动不可缺少的内容,一直是近二十多年来的研究热点。运输路线是否合理直接影响到配送速度、成本和效益。选取恰当的车辆路径,不仅可以加快对客户需求的响应速度,提高服务质量,还可以增强客户对物流环节的满意度,降低服务商运作成本。本文在认真分析国内外VRP研究的基础上,建立了一种基于单边硬时间窗的物流配送路径优化模型(ST-VRP),提出单边硬时间窗的车辆路径问题,即在不违背车辆容量,最大路径时间等约束条件的前提下,合理规划运输时的车辆路径安排,以尽可能小的成本满足客户对货物和服务时间的要求。首先介绍了课题的研究背景、意义及VRP问题的研究现状,分析了物流配送VRP问题的构成要素及分类,总结和比较了以往解决VRP问题的算法及存在的缺点,最后将遗传算法(Genetic Algorithm ,GA)和免疫系统的思想相结合,提出一种免疫遗传改进算法用以解决ST-VRP问题。该算法依据抗原与抗体的亲和度以及抗体之间的亲和度进行评价和选择,通过抗体之间的促进和抑制作用,提高最优点附近的搜索效率;通过记忆细胞的作用,有效地减小了陷入局部最优点的可能,提高了全局搜索能力。基于基本免疫遗传算法(Immune Genetic Algorithm ,IGA)解决ST-VRP问题的解决方案,提出对基本免疫遗传算法的三个重要的改进策略:第一,针对以往免疫遗传算法基于单种群的缺陷,算法一旦达到平衡状态则种群不会再有大的变化从而难以寻求全局最优,将分布式遗传算法(Distributed Genetic Algorithm,DGA)的思想引入到免疫遗传算法中,提出多种群策略和迁移算子策略,从而有效提高了算法的搜索范围,防止算法出现“早熟”现象;第二,在新抗体产生的过程中,为了进一步提高选择算子的选优能力,在传统轮盘赌选择算子的基础上提出一种基于排序的多轮轮盘赌选择算子,在提高了选择算子的选优能力的同时有效地减少了随机性所产生的误差;随后将此算子与最佳个体保存法的思想相结合,进一步提出了无回放的基于排序的多轮轮盘赌选择算子,达到了既能够选出最好个体又能够保证种群多样性的效果;第三,针对基于信息熵亲和力计算方法适用于二进制编码问题但不适用于实数编码问题的缺点,以及基于矢量距离的亲和力计算方法忽略了VRP问题编码中弧信息的缺点,提出一种新的基于对等弧的亲和力计算方法,该方法针对ST-VRP问题编码特征能够更有效地保证种群内抗体的多样性。在本文的最后给出了用改进的免疫遗传算法解决物流配送ST-VRP问题的详细流程,并应用Java语言编程实现了新算法。通过将新算法的实验数据与遗传算法以及基本免疫遗传算法相比较,显示出本算法在解决物流配送ST-VRP问题方面的优越性,达到了保持群体多样性、克服早熟收敛、加快搜索速度、提高算法全局搜索能力的效果。