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

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个需求点的需求量dk(i)dk(2) 从需求点k到k的运距d0k 配送中央到需求点k的运距no第i个配送中央的第j辆车配送的需求点个数,nj=0表示未使用第j辆车R -第i个配送中央的第j辆车配送的路径年 第i个配送中央的第j辆车配送的第k个需求点,叫 表示配送中央 Nqk k i n口-1 其中,口表示不大于括号内数字的最大整数Q假设以配送路径最短为目标函数,那么可以建立如下配送路径的优化模型：M InijminZdr人dr.f nj1rij k 1 1 ijk r

6、ij 0ijnij Ji 1 j 1 k 1J上述模型中：(1)式为目标函数；(2)式保证每条路径上各客户的货物需求量之和不超 过配送车辆的载重量；(3) 式说明每条路径上的客户数不超过总客户数；(4)式说明每 个客户都得到配送效劳；(5)式表示每条路径的客户的组成；(6)式限制每个客户仅能由 一台配送车辆送货；(7)式表示当第i个配送中央的第j辆车效劳的客户数?1时,说明该 台车参加了配送,那么取f (体)=1 ,当第i个配送中央的第j辆车效劳的客户数 1时,表 示未使用该台车辆,因此取f (小)=0.3遗传算法设计3.1 编码方法确实定和初始种群的产生根据多物流配送中央路径优化问题的特点,

7、作者提出了一种配送中央和需求点直接 排列的编码方法.这种表示方法是直接生产N 1N间的互不重复的自然数给这Nt需求 点编码,再生产 咿-M-1之间的互不重复的负整数给这 册配送中央编码. 把这M-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子路径2：配送中央 3 需求点3 需求点4需求点5配送中央 3其中,-2、-5和两个-1都是无效基因.这种染色体结构子路径内部是有序的,子路径中需求点1和2交换位置,会使目标函数值改变；而子路径之间是无序的,假设子路径1和2交换位置,却不会改变目标函数值.3.2 适应度评估方法确

9、实定.适应度函数同目标函数有关,要求非负,通过变换目标函数得到适应度函数：fk bz / Zk.其中,b为常数,z为初始群体中最好的染色体配送距离,zk为当前染 色体对应的配送距离.3.3 选择操作.本文采用如下最正确个体保存与赌轮选择相结合的选择策略：将每代群体中的n介个体按适应度由大到小排列,排在第一位的个体性能最优,将它复制一个直接进入下一代,并排在 第一位；下一代群体的另m - 1个个体需要根据前代群体的n介个体的适应度,采用赌轮选 择法产生,具体地说,就是首先计算上代群体中所有个体适应度的总和2Fj ,再计算每个个体的适应度所占的比例Fj/ 2 Fj (j = 1 ,2 , ?,m)

10、,以此作为其被选择的概率.上述选择方法既可保证最优个体生存至下一代,又能保证适应度较大的个体以较大的时机进 入下一代.3.4 交叉操作对通过选择操作产生的新群体,除排在第一位的最优个体外,另m- 1个个体要按交叉概 率Pc进行配对交叉重组.本文采用类 O点实施交叉操作,其操作过程为：如果染色体交 叉点处的两个基因都为负数,那么直接用基于序的交叉进行运算；如果染色体交叉点处的 基因不全为负数,那么将交叉点左移(右移),直到左右两个交叉点处的基因都为负数,再 进行运算.如：父代 1: -1 , -4, | 1, 2, | -1, -2, -3, 3, 4, 5, -5父代2: -5 ,-1,3,1

11、 , 5, -2 , | -4 , 4,| 2, -1 , -3I I内为匹配段,经过最大保存交叉运算后形成子代 1: -1, 1, -4,4,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 终止准那么采用最正

12、确个体保存指定代数的终止准证,即假设某个体在连续假设干代都是最正确个体, 说明该个体是很好的个体,那么停止操作.4 仿真实验本文用matlab编制了多物流配送中央路径优化问题的遗传算法计算程序.算例：有 两个配送中央各两辆配送车向9个需求点配送,配送车的载重量均是10吨.配送中央(编 号为-1和-2)与需求点之间以及需求点相互之间的距离 dkdg、9个客户的需求量qk均见卜表1.要求安排合理的配送路线,使得总的配送路径最短根据算例的特点,在用遗传算法对其求解时采用了一下参数：种群规模取25,进化代数取100,交叉概率取0.9,变异概率取0.01 ,对不可行路径的惩罚权重取100km对算 例求解

13、10次,所得的计算结果见表2.表1算例的条件表dk(1)k(2) (km) k -1 _-2_12 3 4 5 6 7 89k(1)-1-2123456789qk (t)010 6 12 4 10 4 6 10 130 12 8 12 4 6 80 13 5 11 8 90 15 10 10 80 10 6.5 103 780413101191051410 812 78 412 100 100.23396116表2算例的遗传算法计算结果计算次序1 2 3 4 5 6 7 8 9 10配送总距离(km)67 64 68 70 64 68 64 6768 64首次搜索到最终解的代数43 38 36

14、 42 53 57 4951 48 52由表2可以看出：用遗传算法对算例的10次求解中,有4次得到了问题的最优解64km (其对应的配送路径方案为：路径1:-1,1,3,-1; 路径2: -1, 5, 6, 9,-1;路径3: -2,4, 7,-2;路径4: -2, 2, 8, -2) , 6次得到了问题的近似最优解,这种方法求解多物 流配送中央路径优化问题明显的优于把多个配送中央问题通过任务分派转化为单物流配 送中央问题求解.5 结束语(1)本文建立了一个多物流配送中央模型,并基于多物流配送中央配送的特点,设计了 求解算法.由于每个配送中央需要派出多少车次是不确定的,文章通过采用无效基因很

15、好的解决了这个由于各配送中央需要派出多少车次不确定引起的对个体无法编码的问 题.这样就可以把多个物流配送中央配送优化问题用一个数学模型来求解,这种方法要 优于把需求点预先划分给各个配送中央,以转化为单物流配送中央求解的方法.(2)遗传算法是模拟生物遗传学的规律的算法,但是,在生物体内的基因是存在无效基 因的,而目前使用的遗传算法编码的基因都是有效的.因此,无效基因的概念的提出是 遗传算法的一次开展,拓宽了遗传算法适用范围,也使得遗传算法更接近生物遗传的规 律.本文设计个体的编码方法对解决类似的组合优化问题具有一定的参考价值.(3)个体中增加了无效基因,就等于在更大的空间内寻优.这样一来就加大了

16、寻优的难度,需要迭代更多的代数才能寻得最优解或近似最优解.如何降低迭代次数以尽快寻得 最优解或近似最优解,有待进一步研究.参考文献1 张俊伟,王 勃,马范援.多仓库多配送点的物流配送算法J . 计算机工 程,2022 ,31 (21) :192 - 194.2 Skok M , Skrlec D , Krajcar S. The genetic algorithm methodfor multiple depot capacitated vehicle routing problem solving C/ / The Fourth International Conference on Kno

17、wled ge -based Intelligent Engineering Systems & Allied Technologies.Brighton ,U K: U K Press , 2000 :520 - 526.3 Filipec 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 ：320 - 328.4 魏百鑫,史海波.基于整车配送的多仓库开路VRPTM题的研究与实现J .信 息与限制,2022 ,34 :350 - 355.5李大卫,王