基于免疫遗传算法物流配送车辆路径优化问题研究.pdfVIP

Issue 第15卷专辑 中国管理科学 V01．15，Special Chinese of Science 2007 Journal 2007年10月 Management October， 文章编号：1003—207(2007)zk一0432—05 基于免疫遗传算法的物流配送车辆路径 优化问题研究 李 军 (天津职业大学经济与管理学院，天津 300402) 摘要：物流配送车辆的优化调度问题是近年来物流研究中的一个热点也是一个难点，传统的优化方法往往难以 解决这类问题。本文提出一种新型免疫遗传算法进行物流配送车辆路径问题的优化规划。在遗传进化过程中，借 鉴生物免疫机制对每个种群的染色体进行免疫算子操作，这些算子包括接种疫苗、各基因座多样性调整以及免疫 选择。以运输费用最小为优化目标建立了物流配送车辆路径优化问题的数学模型，利用免疫遗传算法求得优化 解，并通过具体实例以及免疫遗传算法与标准遗传算法运算结果的比较，验证了本文免疫遗传算法的有效性和优 越性。 关键词：物流配送；车辆路径问题；免疫遗传算法 中图分类号：C931 文献标识码：A 收敛，局部有哪些信誉好的足球投注网站能力差，进化过程中不能很好的利用 1 引言 系统信息，进化后期易出现震荡现象等，因此不能保 Problem，简称证最大概率收敛到全局最优解。 车辆路径问题(VehicleRouting VRP)是指为服务于已知的一组顾客的一个车队，设 近年来出现的免疫算法借鉴生物免疫机理，能 计一组开始和结束于一个中心出发点的最小费用路 充分利用最优个体及系统的信息，且能有效保持种 径。每个顾客只能被服务一次，而且，一个车辆服务 群多样性，在优化过程中，吸取了已有优化算法的有 的顾客数不能超过它的能力¨1。VRP由于其特有益思想，将随机有哪些信誉好的足球投注网站和确定性的变化结合在一起，减 的魅力以及其与运筹学理论研究和现代物流实际生 小了随机因素对算法本身的影响，能较好的消除不 成熟收敛及震荡现象一]。本文在标准遗传算法 产生活的紧密联系，自1959年由Dantzig和Ramser Genetic 首次提出后，很快就吸引了全世界无数的科学家、工 (Simple (Immune 程师和管理学者为之探索，先后涌现出了一大批解 Algorithm)的基础上，设计了求解物流配 送车辆路径优化问题的一种免疫遗传算法(Immune 决VRP问题的启发式、亚启发式算法，如Clark和 Genetic Wright提出的节约法怛1，Gillett和Miller提出的 息熵来实现对种群多样性的调整，以更准确、快速的 Sweep算法[3J，Lin提出的2一opt和3一opt交换算 法H1等以及近年来出现的遗传算法(Genetic反映系统进化过程，应用系统的启发式信息实现种 Algo-