物流遗传算法.docx

基于遗传算法的物流配送路径优化问题研究郎茂祥(北方交通大学交通运输学院,北京100044)摘要:论文在建立物流配送路径优化问题的数学模型的基础上,构造了求解该问题的遗传算法,并进行了实验运算。运算结果表明,用遗传算法进行物流配送路径优化,可以方便有效地求得问题的最优解或近似最优解。关键词:物流配送;遗传算法;优化2物流配送路径优化问题的数学模型物流配送路径优化问题可以描述为:从配送中心(或称物流据点)用多辆汽车向多个需求点(或称顾客)送货,每个需求点的位置和需求量一定,每辆汽车的载重量一定,要求合理安排汽车路线,使总运距最短,并满足以下条件:(1)每条配送路径上各需求点的需求量之和不超过汽车载重量;(2)每条配送路径的长度不超过汽车一次配送的最大行驶距离;(3)每个需求点的需求必须满足,且只能由一辆汽车送货。本文借鉴文献[3]建立的车辆路径问题的数学模型,并通过考虑上述物流配路径优化问题的约束条件和优化目标,建立了物流配送路径优化问题的数学模型。设配送中心有K辆汽车,每辆汽车的载重量为Qk(k=1,2,···,K),其一次配送的最大行驶距离为Dk,需要向L个需求点送货,每个需求点的需求量为qi(i=1,2,···,L),需求点i到j的运距为dij,配送中心到各需求点的距离为d0j(i、j=1,2,···,L),再设nk为第k辆汽车配送的需求点数(nk=0表示未使用第k辆汽车),用集合Rk表示第k条路径,其中的元素rki表示需求点rki在路径k中的顺序为i(不包括配送中心),令rk0=0表示配送中心,则可建立如下物流配送路径优化问题的数学模型:(1).(2)(3)(4)(5)(6)(7)(8)上述模型中,(1)式为目标函数;(2)式保证每条路径上各需求点的需求量之和不超过汽车的载重量;(3)式保证每条配送路径的长度不超过汽车一次配送的最大行驶距离;(4)式表明每条路径上的需求点数不超过总需求点数;(5)式表明每个需求点都得到配送服务;(6)式表示每条路径的需求点的组成;(7)式限制每个需求点仅能由一辆汽车送货;(8)式表示当第k辆汽车服务的客户数≥1时,说明该辆汽车参加了配送,则取sign(nk)=1,当第k辆汽车服务的客户数<1时,表示未使用该辆汽车,因此取sign(nk)=0。“生成+检测”的迭代搜索算法。该算法以群体中的所有个体为操作对象,每个个体对应研究问题的一个解。挑选、交叉和变异是遗传算法的三个主要操作算子。该算法包括以下6个基本要素:(1)编码。由于遗传算法不能直接处懂得空间的数据,因此,必须通过编码将它们表示成遗传空间的基因型串结构数据。(2)初始群体生成。由于遗传算法是一种群体型搜索方法,所以必须为遗传操作准备一个由若干个体组成的初始群体,每个个体都应通过随机方法产生,并分别对应研究问题的一个解。(3)适应度评估。遗传算法在搜索过程中一样不需要其他外部信息,仅用适应度来评估个体的优劣,并以其作为遗传操作的依据。(4)挑选。挑选操作是为了从当前群体中选出优良的个体,使它们有机会作为父代为下一代繁育子孙,个体的适应度越高,其被挑选的机会就越大。(5)交叉。它是遗传算法中最主要的操作,一样分两步进行,一是对群体中的个体进行随机配对;二是在配对个体中,随机设定交叉处,