基于遗传算法的物流配送路径优化研究

1用单亲遗传算法求解配送车辆调度问题的研究郎茂祥（北京交通大学交通运输学院，北京100044）摘要：论文建立了物流配送车辆调度问题的数学模型，并针对传统遗传算法对复杂问题搜索效率低，易陷入“早熟收敛”的缺点，构建了求解物流配送车辆调度问题的单亲遗传算法，并进行了实验计算。计算结果表明，用单亲遗传算法求解物流配送车辆调度问题，可以取得比传统遗传算法更优的结果。关键词：物流配送；车辆调度问题；单亲遗传算法；遗传算法StudyonthePartheno-GeneticAlgorithmforPhysicalDistributionVehicleSchedulingProblemLANGMao-xiang，HUSi-ji（SchoolofTrafficandTransportation，NorthernJiaotongUniversity，Beijing100044，China）Abstract：Thispaperestablishedthemodelofphysicaldistributionvehicleschedulingproblem.Onthebasisofanalyzingtheshortcomingsoftraditionalgeneticalgorithminlowsearchingefficiencyand“ImmatureConvergence”,thispaperestablishedapartheno-geneticalgorithmforsolvingphysicaldistributionvehicleschedulingproblemandmadesomeexperimentalcomputations.Thecomputationalresultshaddemonstratedthatthepartheno-geneticalgorithmhadhigheroptimizingefficiencyandqualitythantraditionalgeneticalgorithminsolvingphysicaldistributionvehicleschedulingproblem.Keywords：physicaldistribution;vehicleschedulingproblem;pertheno-geneticalgorithm;geneticalgorithm1引言随着市场经济的发展和物流专业化水平的提高，物流配送业得到了迅速发展。在物流配送业务中，配送车辆调度问题的涉及面较广，对企业提高服务质量、降低物流成本的影响也较大。在现实生产和生活中，邮政投递问题、公共汽车调度问题、电力调度问题、管道铺设问题、计算机网络拓扑设计问题等都可以抽象为物流配送车辆调度问题。因此，研究物流配送车辆调度问题具有重要的理论和现实意义。物流配送车辆调度问题作为一个NP难题，随着客户数量的增加，可选的车辆路径方案数量将以指数速度急剧增长。因此，用启发式算法求解该问题就成为人们研究的一个重要方向。求解物流配送车辆调度问题的方法很多，常用的有旅行商法、动态规划法[1]、节约法[2]、扫描法[3]、分区配送算法[4]、方案评价法[5]等。遗传算法的出现为求解物流配送车辆调度问题提供了新的工具。Berthold、Malmborg、Ochi、姜大立、李大卫、李军、谢秉磊、张涛等人都曾利用遗传算法求解物流配送车辆调度问题[6-15]，并取得了一些研究成果。作者也尝试采用新的编码方法和遗传算子构造了求解物流配送车辆调度问题的遗传算法，并对文献[9]中的例题进行了实验计算，计算结果表明，虽然利用传统遗传算法能够方便地求得问题的近似最优解，但也暴露出其存在对复杂问题搜索效率低，易陷入“早熟收敛”[16]的缺点。为了提高优化效率和质量，作者构造了求解物流配送车辆调度问题的单亲遗传算法，通过实验计算，取得比传统遗传算法更好的计算结果。22物流配送车辆调度问题的数学模型物流配送车辆调度问题可以描述为：从某物流中心用多台配送车辆向多个客户送货，每个客户的位置和货物需求量一定，每台配送车辆的载重量一定，其一次配送的最大行驶距离一定，要求合理安排车辆配送路线，使目标函数得到优化，并满足以下条件：（1）每条配送路径上各客户的需求量之和不超过配送车辆的载重量；（2）每条配送路径的长度不超过配送车辆一次配送的最大行驶距离；（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.nQqkkiikr1（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。3物流配送车辆调度问题的单亲遗传算法3.1单亲遗传算法简介单亲遗传算法[17]是对传统遗传算法的一种改进，它不使用传统遗传算法中常用的交叉3算子，对某个个体的遗传操作只在该条染色体上进行，即只通过单个个体繁殖后代。对于采用自然数编码的个体，单亲遗传算法常用的遗传操作算子有：基因换位算子、基因倒位算子和基因移位算子等，使用这些算子可完全实现PMX、CX、OX等传统交叉算子[18]的功能。由于单亲遗传算法不使用交叉算子，即使群体中的个体完全相同，也不影响遗传迭代的进行，从而摆脱了对群体多样性的要求，能克服“早熟收敛”问题。使用单亲遗传算法求解问题，也需要从任一初始群体出发，通过选择、染色体重组等遗传操作，使群体一代一代地进化到搜索空间中越来越好的区域。单亲遗传算法包括编码、初始群体生成、适应性评估、选择和染色体重组5个基本要素。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台车辆配送。（2）初始群体的确定。随机产生一种1~L+K-1这L+K-1个互不重复的自然数的排列，即形成一个个体。设群体规模为N，则通过随机产生N个这样的个体，即形成初始群体。（3）适应度评估。对于某个个体所对应的配送路径方案，要判定其优劣，一是要看其是否满足配送的约束条件；二是要计算其目标函数值（即各条配送路径的长度之和）。本文根据配送路径选择问题的特点所确定的编码方法，隐含能够满足每个需求点都得到配送服务及每个需求点仅由一台车辆配送的约束条件，但不能保证满足每条路径上各需求点需求量之和不超过汽车载重量及每条配送路线的长度不超过汽车一次配送的最大行驶距离的约束条件。为此，对每个个体所对应的配送方案，要对各条路径逐一进行判断，看其是否满足上述两个约束条件，若不满足，则将该条路径定为不可行路径，最后计算其目标函数值。对于某个个体j，设其对应的配送路径方案的不可行路径数为Mj（Mj=0表示该个体是一个可行解），其目标函数值为Zj，则该个体的适应度Fj，可用下式表示：Fj=1/（Zj+Mj×Pw）（9）式中，Pw为对每条不可行路径的惩罚权重（该权重可根据目标函数的取值范围取一个相对较大的正数）。（4）选择操作。将每代群体中的N个个体按适应度由大到小排列，排在第一位的个体性能最优，将它复制一个直接进入下一代，并排在第一位。下一代群体的另N-1个个体需要根据前代群体的N个个体的适应度，采用赌轮选择法产生。具体地说，就是首先计算上代群体中所有个体适应度的总和（ΣFj），再计算每个个体的适应度所占的比例（Fj/ΣFj），以此作为其被选择的概率。这样选择方法既可保证最优个体生存至下一代，又能保证适应度较大的个体以较大的机会进入下一代。（5）染色体重组。对通过选择操作产生的新群体，除排在第一位的最优个体外，另N-1个个体要运用单亲遗传算子进行染色体重组。本文选用多点基因换位算子实现染色体重组，现举例说明其操作过程：①根据预先确定的最大基因换位次数（Nc），取随机数k（1≤k≤Nc）。本例中设Nc=4，k=2。②在染色体上随机选取k对基因，并交换其位置。本例中设原染色体为A=478563921，随机产生的第一对交换基因位为2和5，则基因换位后染色体变为A’=468573921；随机产生的第二对交换基因位为3和8，再次实施基因换位后染色体变为4A”=462573981。③判断实施多点基因换位后，个体的适应值是否增加，若增加，则用换位后的个体取代原个体，进入下一代，否则原个体直接进入下一代。本例中设A”的适应值大于A的适应值，则A”进入下一代。（6）终止准则。采用进化指定代数的终止准则。4实验计算与结果分析作者用C语言分别编制了物流配送车辆调度问题的传统遗传算法程序和单亲遗传算法程序，并对文献[9]中某配送中心使用2台车辆对8个需求点送货的问题进行了实验计算（计算时在原问题的基础上增加了车辆一次配送的最大行驶距离为40km的约束条件）。实验中采用了以下参数：群体规模为20，进化代数为50，传统遗传算法的交叉概率和变异概率分别取0.95和0.05，单亲遗传算法的最大基因换位次数取4。将两种算法的计算机程序分别随机运行10次，得到的计算结果（即配送路径总长度）见表1。表1物流配送车辆调度问题的传统遗传算法和单亲遗传算法计算结果的比较计算次序12345678910传统遗传算法的计算结果Z/km727276.57067.57073.57571.569单亲遗传算法的计算结果Z/km6967.5707067.56967.5726971.5从表1可以看出，传统遗传算法和单亲遗传算法的10次计算结果均优于节约法的结果79.5km，而且单亲遗传算法得到的结果更优，10次计算中，单亲遗传算法有3次得到了问题的最优解67.5km，还有3次得到了问题的次优解69km，而传统遗传算法仅1次得到了最优解，1次得到了次优解。这充分说明，单亲遗传算法可以克服传统遗传算法的“早熟收敛”问题，具有良好的搜索效率