多物流配送中心路径优化问题及其遗传算法

1、多物流配送中心路径优化问题及其遗传算法廖成林柳茂森(重庆大学经济与工商管理学院，重庆，400030)摘要：论文建立了多物流配送中心路径优化问题的数学模型，并针对该问题的特点构造出求解该 问题的遗传算法，把多物流配送中心路径优化问题综合起来用一个数学模型求解。本文提出了无效基 因的概念，从而不局限于使得个体中每个基因都必须表达出来，因此增强了编码的灵活性。仿真实验 证明了该方法的有效性和可操作性。关键词：无效基因遗传算法物流配送1引言物流配送是物流管理中一个极其重要的环节，它是指按用户的订货要求，在配送中心进行分 货、配货，并将配好的货物及时送交收货人的活动。物流配送主要研究车辆调度及路径安排问

2、题。近 年来，国内外学者对物流配送问题进行了大量的研究，这些研究主要 集中在单物流配送中心的车辆调 度及路径安排方面。由于配送路径优化问题是一个NP难题，因此，研究者大都使用启发式算法和 智能算法或者是在智能算法优化过程中加入优化策略以构造混合智能算法来求解物流配送问题。但 是，目前国内外对多个物流配送中心的物流配送问题的研究成果很少，而且现有研究成果大都是把多 个配送中心问题通过任务分派转化为单物流配送中心问题来研究3】，使用这种方法把需求点预先划 分给各个 配送中心，在求解过程中再作适当的调整，这种方法其实只是单物流配送中心优化的简单 组合，通常只能求得近似最优配送方案。魏百鑫等4 针对整

3、车配送需求点分散特征，解决了多仓库 的整车配送问题，但并不是一个通用的解决多物流中心配送问题的方法。由于遗传算法具有良好的全局寻优性能，并且对不要求搜索空间具是连续的，这正符合该问题的 特点和要求。因此本文亦采用遗传算法求解。本文基于整体路径最优由多个物流配送中心同时服务多个需求点建立一个通用的多物流配送中心 的配送模型，并给出求解算法。单物流配送中心路径优化问题可以事先确定需要派出的车次，但是多 物流配送中心路径优化问题中，每个配送中心需要派出多少车次是不确定的，因此，无法用常规的方 法确定染色体的长度。为解决基因编码的问题，本文提出了无效基因的概念。所谓无效基因就是在一 次基因表达的过程中

4、不作表达的基因。但是，在交叉过程中无效基因处可以被选为交叉点，交叉后无 效基因可能转化为有效基因。因此，有些基因时而是有效基因时而是无效基因，因而无效基因在不清 楚有些基因是否表达较好的时候起到缓冲作用。2模型的建立 多物流配送路径优化问题可描述为：从多个配送中心用多辆配送车向多个需求点送 货，每个需求点的位置和需求量一定，要求安排合理的配送路线，使得目标函数最优或接近最优。为 了研究的方便且具有实际意义，做以下假设：(1)每条配送路径上各需求点的需求量之和不超过配送车的载重量；(2)每个需求点都必须满足，且只能由一辆配送车送货。本文的各种符号及其含义做如下说明： M配送中心的个数 i配送中心

5、的下标j配送车辆的下标k需求点的下标N需求点的个数L第i个配送中心的配送车的个数Q 第i个配送中心的第j辆车的载重量qk-第k个需求点的需求量dgdg从需求点k到k的运距&内一.配送中心到需求点k的运距no- 第i个配送中心的第j辆车配送的需求点个数，ny=O表示未使用第j辆车R -第i个配送中心的第j辆车配送的路径你 第i个配送中心的第j辆车配送的第k个需求点，国表示配送中心Nqkn J1其中，口表示不大于括号内数字的最大整数Q若以配送路径最短为目标函数，则可以建立如下配送路径的优化模型：M Li njminZd. dr 寸 f 门打1ij k 1 1 ijkij Oijniji 1 j 1

6、 k 1J上述模型中：（1）式为目标函数；（2）式保证每条路径上各客户的货物需求量之和不超 过配送车辆的载 重量；（3）式表明每条路径上的客户数不超过总客户数；（4）式表明每个客户都得到配送服务；（5）式表示每条路径的客户的组成；（6）式限制每个客户仅能由一台配送车辆 送货；（7）式表示当第i个配送中心的第j辆车服务的客户数1时，说明该台车参加了配送，则取f （n。）=1 ,当第i个配送中心的第j辆车服务的客户数V 1时，表 示未使用该台车辆，因此取f（m） = 0。3遗传算法设计3.1编码方法的确定和初始种群的产生根据多物流配送中心路径优化问题的特点，作者提出了一种配送中心和需求点直接排列的

7、编码方 法。这种表示方法是直接生产N个1N间的互不重复的自然数给这N个需求点编码，再生产M个-M -1之间的互不重复的负整数给这M个配送中心编码。把这Mt-M-1之间的互不重复的负整数各n 个和这Nt 1N间的互不重复的自然数各一个组成一个 长度为n*M+N勺数列，数列的第一个位置随机 排上一个负整数，其余位置随机全排列，即形成一个染色体。随机产生m个这样的个体即可形成种群 规模为m勺初始种群。这样的染色体结构可解释为：（1）从负数对应的配送中心出发向紧接着该负数后面的若干个正数所对应的需求点配送，再回到 该配送中心，形成一条子路径。2）后面未紧接着正数的负数为无效基因，不表示任何意义，但是可

8、以在该基因处进行交叉操 作。若交叉后该负数后面紧接正数，则该负数由无效基因变为有效基因，其意义与（1 ）所述 相同。例如染色体(-1 , -4 , 1, 2,1 ,-2 ,-3 , 3, 4, 5,-5)表示的意义：子路径1 :配送中心4需求点1需求点2配送中心4子路径配送中心3需求点3需求点4需求点5配送中心3其中，-2、-5和两个-1都是无效基因。这种染色体结构子路径内部是有序的，子路径中需求点1和2交换位置，会使目标函数值改变；而子路径之间是无序的，若子路径1和2交换位置，却不会改变目标函数值。3.2 适应度评估方法的确定。适应度函数同目标函数有关，要求非负，通过变换目标函数得到适应度

9、函数：fk bz / Zk。其中，b为常数，z为初始群体中最好的染色体配送距离，zk为当前染 色体对应的配送 距离3.3 选择操作。本文采用如下最佳个体保留与赌轮选择相结合的选择策略：将每代群体中的m个个体按适应度由大到小排列，排在第一位的个体性能最优，将它复制一个直接进入下一代,并排在第一位;下一 代群体的另m.1个个体需要根据前代群体的仃个个体的适应度，采用赌轮选择法产生，具体地说，就是首先计算上代群体中所有个体适应度的总和工Fj,再计算每个个体的适应度所占的比例Fj/工Fj (j = 1 ,2 , ?,m),以此作为其被选择的概率。上述选择方法既可保证最优个体生存至下一代，又能保证适应度

10、较大的个体以较大的机会进入下一代。3.4 交叉操作对通过选择操作产生的新群体，除排在第一位的最优个体外，另m.1个个体要按交叉概 率Pc进行配 对交叉重组。本文采用类。眩实施交叉操作，其操作过程为：如果染色体交叉点处的两个基因都为负 数，则直接用基于序的交叉进行运算；如果染色体交叉点处的基因不全为负数，则将交叉点左移(右 移)，直到左右两个交叉点处的基因都为负数，再进行运算.如：父代 1：-1, -4,I1,2,I,-2,-3, 3, 4,5,-5父代 2:-5,3,1,5,-2 ,I-4 ,4, I 2, -1 ,-3I I内为匹配段，经过最大保留交叉运算后形成子代 1：-1,1,-4,4,

11、2,-1 ,-2,-3, 3,5 , -5子代 2:-5,-1,3,5,-2, -4,1 ,2,-1 , 4, -33.5 变异操作由于在选择机制中采用了保留最佳个体的方式，为保持群体内个体的多样化，本文采用连续多次对 换的变异技术，使个体在排列顺序上有较大的变化。变异操作是以概率Pm发生的，一旦变异操作发 生，则用随机方法产生交换次数J ,对所需变异操作的个体的基因进行J次对换(对换基因的位置也是 随机产生的)。3.6 终止准则采用最佳个体保留指定代数的终止准证，即若某个体在连续若干代都是最佳个体，说明该个体是 很好的个体，则停止操作。4仿真实验本文用matlab编制了多物流配送中心路径优化

12、问题的遗传算法计算程序。算例：有 两个配送中心各两辆配送车向9个需求点配送，配送车的载重量均是10吨。配送中心(编号为和-2)与需求点 之间以及需求点相互之间的距离dgdg、9个客户的需求量qk均见 下表1。要求安排合理的配送路线， 使得总的配送路径最短。根据算例的特点，在用遗传算法对其求解时采用了一下参数：种群规模取25,进化代数取100, 交叉概率取0.9，变异概率取0。，对不可行路径的惩罚权重取100km对算例求解10次，所得的计 算结果见表2。dk k (2)(km)-1-2123456789qk (t)表1算例的已知条件表k(2) -121 2 3 4 5 6 7 89106124

13、100 12812460 135 114688 90 15 10 10 80 10 6.5-|00 3 70500-34 4 2310 134913 1010511 141081278412 100 10023396116表2算例的遗传算法计算结果计算次序1 2 34567 8 9 10配送总距离(km)67 64 68 70 64 68 64 6768 64首次搜索到最终解的代数43 38 36 42 53 57 4951 48 52由表2可以看出：用遗传算法对算例的10次求解中，有4次得到了问题的最优解64km (其对应的配送路径方案为：路径1：路径2 ： -1，5，6，9，;路径3 ：

14、-2，4, 7, -2 ;路径4 ：2，2，8，-2)，6次得到了问题的近似最优解，这种方法求解多物流配送中心路 径优化问题明显的优于把多个配送中心问题通过任务分派转化为单物流配送中心问题求解。5结束语(1)本文建立了一个多物流配送中心模型，并基于多物流配送中心配送的特点，设计了求解算法。由于 每个配送中心需要派出多少车次是不确定的，文章通过采用无效基因很 好的解决了这个由于各配送中 心需要派出多少车次不确定引起的对个体无法编码的问题。这样就可以把多个物流配送中心配送优化 问题用一个数学模型来求解，这种方法要 优于把需求点预先划分给各个配送中心，以转化为单物流配 送中心求解的方法。(2)遗传算

15、法是模拟生物遗传学的规律的算法，但是，在生物体内的基因是存在无效基因的，而目前使 用的遗传算法编码的基因都是有效的。因此，无效基因的概念的提出是遗传算法的一次发展，拓宽了 遗传算法适用范围，也使得遗传算法更接近生物遗传的规律。本文设计个体的编码方法对解决类似的 组合优化问题具有一定的参考价值。(3)个体中增加了无效基因，就等于在更大的空间内寻优。这样一来就加大了寻优的难度，需要迭代更多的代数才能寻得最优解或近似最优解。如何降低迭代次数以尽快寻得最优解或近似 最优解，有待进一步研究。参考文献1 张俊伟,王 勃,马范援.多仓库多配送点的物流配送算法J ,计算机工 程2005 ,31 (21) :1

16、92 - 194. 2 Skok M , Skrlec D , Krajcar S. The genetic algorithm methodfor multipledepot capacitated vehicle routing problem solving C/ / The FourthInternational Conference on Knowled ge -based Intelligent EngineeringSystems & Allied Technologies.Brighton ,U K: U K Press , 2000 :520 - 526.3 Filipec

17、M, Skrlec D , Krajcar S. Genetic algorithm approachfor multiple depot capacitated vehicle routing problem solvingwith heuristic improvements built - inJ .International Jour2nal of Modeling and Simulation , 2000,20 (4) :320 - 328.4 魏百鑫，史海波.基于整车配送的多仓库开路VRPTW问题的研究与实现J L信 息与控制,2005 ,34 :350 - 355.5李大卫，王莉