物流遗传算法

1基于遗传算法的物流配送路径优化问题研究郎茂祥（北方交通大学交通运输学院，北京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表示配送中心，则可建立如下物流配送路径优化问题的数学模型：KkikrrrrnnsignddZkkkknkiik11)]([min0)1(（1）s.t.nQqkkiikr12（2）kikrrrrDnnsignddkkkknkiik)(10)1(（3）Lnk0（4）LnKkk1（5）},...,2,1,,...,2,1|{kkikikniLrrR（6）21kkRR21kk（7）其他011)(kknnsign（8）上述模型中，（1）式为目标函数；（2）式保证每条路径上各需求点的需求量之和不超过汽车的载重量；（3）式保证每条配送路径的长度不超过汽车一次配送的最大行驶距离；（4）式表明每条路径上的需求点数不超过总需求点数；（5）式表明每个需求点都得到配送服务；（6）式表示每条路径的需求点的组成；（7）式限制每个需求点仅能由一辆汽车送货；（8）式表示当第k辆汽车服务的客户数≥1时，说明该辆汽车参加了配送，则取sign(nk)=1，当第k辆汽车服务的客户数1时，表示未使用该辆汽车，因此取sign(nk)=0。33物流配送路径优化问题的遗传算法3.1遗传算法的基本要素遗传算法是一种“生成+检测”的迭代搜索算法。该算法以群体中的所有个体为操作对象，每个个体对应研究问题的一个解。选择、交叉和变异是遗传算法的三个主要操作算子。该算法包括以下6个基本要素：（1）编码。由于遗传算法不能直接处理解空间的数据，因此，必须通过编码将它们表示成遗传空间的基因型串结构数据。（2）初始群体生成。由于遗传算法是一种群体型搜索方法，所以必须为遗传操作准备一个由若干个体组成的初始群体，每个个体都应通过随机方法产生，并分别对应研究问题的一个解。（3）适应度评估。遗传算法在搜索过程中一般不需要其他外部信息，仅用适应度来评估个体的优劣，并以其作为遗传操作的依据。（4）选择。选择操作是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙，个体的适应度越高，其被选择的机会就越大。（5）交叉。它是遗传算法中最主要的操作，一般分两步进行，一是对群体中的个体进行随机配对；二是在配对个体中，随机设定交叉处，使配对个体彼此交换部分信息。（6）变异。即按一定的概率改变个体的基因链。变异操作同样是随机进行的，其目的是挖掘群体中个体的多样性，克服遗传操作可能限于局部解的弊端。3.2物流配送路径优化问题的遗传算法的构造针对物流配送路径优化问题的特点，作者构造了求解该问题的遗传算法。（1）编码方法的确定。根据物流配送路径优化问题的特点，作者采用了简单直观的自然数编码方法，用0表示配送中心，用1、2、···、L表示各需求点。由于在配送中心有K辆汽车，则最多存在K条配送路径，每条配送路径都始于配送中心，也终于配送中心，为了在编码中反映车辆配送的路径，作者巧妙地采用了增加K-1个虚拟配送中心的方法，分别用L+1、L+2、···、L+K-1表示。这样，1、2、···、L+K-1这L+K-1个互不重复的自然数的随机排列就构成一个个体，并对应一种配送路径方案。例如，对于一个有7个需求点，用3辆汽车完成配送任务的问题，则可用1、2、···、9（8、9表示配送中心）这9个自然数的随机排列，表示物流配送路径方案。如个体129638547表示的的配送路径方案为：路径1：0-1-2-9（0），路径2：9（0）-6-3-8（0），路径3：8（0）-5-4-7-0，共有3条配送路径；个体5738942164表示的配送路径方案为：路径1：0-5-7-3-8（0），路径2：9（0）-4-2-1-6-0，共有2条配送路径。（2）初始群体的确定。随机产生一种1~L+K-1这L+K-1个互不重复的自然数的排列，即形成一个个体。设群体规模为N，则通过随机产生N个这样的个体，即形成初始群体。（3）适应度评估。对于某个个体所对应的配送路径方案，要判定其优劣，一是要看其是否满足配送的约束条件；二是要计算其目标函数值（即各条配送路径的长度之和）。本文根据配送路径优化问题的特点所确定的编码方法，隐含能够满足每个需求点都得到配送服务及每个需求点仅由一辆汽车配送的约束条件，但不能保证满足每条路径上各需求点需求量之和不超过汽车载重量及每条配送路线的长度不超过汽车一次配送的最大行驶距离的约束条件。为此，对每个个体所对应的配送路径方案，要对各条路径逐一进行判断，看其是否满足上述两个约束条件，若不满足，则将该条路径定为不可行路径，最后计算其目标函数值。对于某个个体j，设其对应的配送路径方案的不可行路径数为Mj（Mj=0表示该个体对应一个可行解），其目标函数值为Zj，则该个体的适应度Fj可用下式表示：Fj=1/（Zj+Mj×G）（9）式中，G为对每条不可行路径的惩罚权重，可根据目标函数的取值范围取一个相对较大的正数。（4）选择操作。将每代群体中的N个个体按适应度由大到小排列，排在第一位的个体性能最优，将它复制一个直接进入下一代，并排在第一位。下一代群体的另N-1个个体需要根据前代群体的N个个体的适应度，采用赌轮选择法[4]产生。具体地说，就是首先计算上代群体中所有个体适应度的总和（ΣFj），再计算每个个体的适应度所占的比例（Fj/ΣFj），以此作为其被选择的概率。这样选择方法既可保证最优个体生存至下一代，又能保证适应度较大的个体以较大的机会进入下一代。（5）交叉操作。对通过选择操作产生的新群体，除排在第一位的最优个体外，另N-1个个体要按交叉概率Pc进行配对交叉重组。本文采用了一种类似OX法[2]的交叉方法，现举例说明之：①随机在父代个体中选择一个交配区域，如两父代个体及交配区域选定为：A=47|8563|921，B=83|4691|257；②将B的交配区域加到A的前面，A的交配区域加到B的前面，得：A’=4691|478563921，B’=8563|834691257；③在A’、B’中自交配区域后依次删除与交配区相同的自然数，得到最终的两个体为：A”=469178532，B”=856349127。与其他交叉方法相比，这种方法在两父代个体相同的情况下仍能产生一定程度的变异效果，这对维持群体的多样化特性有一定的作用。5（6）变异操作。由于在选择机制中采用了保留最佳样本的方式，为保持群体内个体的多样化，本文采用了连续多次对换的变异技术，使个体在排列顺序上的有较大变化。变异操作是以概率Pm发生的，一旦变异操作发生，则用随机方法产生交换次数J，对所需变异操作的个体的基因进行J次对换（对换基因的位置也是随机产生的）。4实验计算与结果分析作者根据上述遗传算法编制了C语言程序，并对文献[3]列出的一个某配送中心使用2辆汽车对8个需求点进行送货的物流配送路径优化问题实例进行了实验计算。设汽车的载重量为8t，每次配送的最大行驶距离为40km，配送中心与各需求点之间、各需求点相互之间的距离及各需求点的需求量见表1。表1配送中心与需求点之间的距离及各需求点的需求量表dij(km)ji01234567800467.5920101681406.541057.51110266.507.510107.57.57.537.547.501059915491010100107.57.5105205105100797.56107.57.597.570710716117.597.59701088107.515107.510100qj(t)--12121422根据上述实例的特点，作者在实验计算中采用了以下参数：群体规模取20，交叉概率和变异概率分别取0.95和0.05，进化代数取50，变异时基因换位次数取5，对不可行路径的惩罚权重取100km。对上述问题，利用计算机随机求解10次，得到的计算结果见表2。表2物流配送路径优化问题的遗传算法计算结果计算次序12345678910配送总距离Z/km727276.57067.57073.57571.569从表中数据可以看出，10次运行得到的结果均优于节约法所得的结果79.5km。而且第5次还得到了该问题的最优解67.5km，其对应的配送路径方案为：路径1：0-4-7-6-0；路径62：0-2-8-5-3-1-0。可见，利用遗传算法可以方便有效地求得物流配送路径优化问题的最优解或近似最优解（或称满意解）。5结论（1）在物流配送业务中，合理确定配送路径是提高服务质量、降低配送成本、增加经济效益的重要手段。由于物流配送路径优化问题是一个NP难题，因此，采用启发式算法求解是一个重要的研究方向。（2）本文在建立物流配送路径优化问题的数学模型的基础上，构造了求解物流配送路径优化问题的遗传算法。实验计算结果表明，遗传算法是一种性能优良的启发式搜索方法，利用该方法可以方便有效地求得物流配送路径优化问题的最优解或满意解。（3）本文所构造的进行物流配送路径优化的遗传算法，包括巧妙设计的个体编码方法、个体适应值的计算方法以及选择、交叉和变异算子，对解决类似的组合优化问题具有一定的参考价值。