物流专业毕业设计样本

毕业设计题目基于遗传算法的物流配送路径优化分析学生姓名学号专业班级指导教师二00九年十月目录（空一行）摘要………………………………………………………………ⅰ一、引言（问题的提出）…………………………………………1二、物流配送路径优化问题的数学模型……………………………X三、物流配送路径优化问题的遗传算法……………………………X（一）遗传算法的基本要素………………………………………X（二）物流配送路径优化问题的遗传算法的构造……………………X四、实验计算与结果分析…………………………………………X五、结论…………………………………………………………X参考文献…………………………………………………………X致谢………………………………………………………………X摘要：论文在建立物流配送路径优化问题的数学模型的基础上，构造了求解该问题的遗传算法，并进行了实验计算。计算结果表明，用遗传算法进行物流配送路径优化，可以方便有效地求得问题的最优解或近似最优解。关键词：物流配送；遗传算法；优化StudyontheOptimizingofPhysicalDistributionRoutingProblemBasedonGeneticAlgorithmAbstract：Onthebasisofestablishingtheoptimizingmodelonphysicaldistributionroutingproblem,thispaperpresentsageneticalgorithmforsolvingthisproblem,andmakesomeexperimentalcalculations.Theexperimentalcalculationresultsdemonstratesthattheoptimalornearlyoptimalsolutionstothephysicaldistributionroutingproblemcanbeeasilyobtainedbyusinggeneticalgorithm.Keywords：physicaldistribution；geneticalgorithm；optimizing一、引言（问题的提出）随着市场经济的发展和物流技术专业化水平的提高，物流配送业得到了迅猛发展。物流配送是指按用户的订货要求，在配送中心进行分货、配货，并将配好的货物及时送交收货人。在物流配送业务中，存在许多优化决策问题，本文讨论其中的物流配送路径优化问题，即通过制定合理的配送路径，快速而经济地将货物送达用户手中。配送路径的选择是否合理，对加快配送速度、提高服务质量、降低配送成本及增加经济效益都有较大影响。研究表明，配送路径优化问题是一个NP难题，只有在需求点和路段较少时，才能求得精确解。因此，用启发式算法求解该问题就成为人们研究的一个重要方向，并出现了多种启发式算法，如Clarke和Wright提出的节约法，Gillett和Miller提出的扫描法①等，虽然这些算法为求解配送路径优化问题提供了有效的方法，但也存在一定的问题，如节约法虽然具有运算速度快的优点，但也有组合点零乱、边缘点难以组合的问题，扫描法为非渐进优化等。如何针对物流配送路径优化问题的特点，构造运算简单、寻优性能优良的启发式算法，是一个值得深入研究的课题。遗传算法的出现为求解物流配送路径优化问题提供了新的工具，该算法是由美国的J.Holland教授于1975年提出的，它是一种借鉴生物界自然选择和自然遗传机制的随机化搜索方法。由于遗传算法采用随机选择，对搜索空间无特殊要求，无需求导，具有运算简单、收敛速度快等优点，尤其适用于处理传统搜索方法难于解决的复杂和非线性的问题，目前已广泛应用于组合优化、机器学习、自适应控制等领域。本文针对物流配送路径优化问题的特点，构造了求解该问题的遗传算法，通过实验计算，得到了较好的结果。二、物流配送路径优化问题的数学模型物流配送路径优化问题可以描述为：从配送中心（或称物流据点）用多辆汽车向多个需求点（或称顾客）送货，每个需求点的位置和需求量一定，每辆汽车的载重量一定，要求合理安排汽车路线，使总运距最短，并满足以下条件：（1）每条配送路径上各需求点的需求量之和不超过汽车载重量；（2）每条配送路径的长度不超过汽车一次配送的最大行驶距离；（3）每个需求点的需求必须①Z·米凯利维茨.演化程序——遗传算法和数据编码的结合[M].北京：科学出版社，2000.满足，且只能由一辆汽车送货。本文借鉴文献[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。三、物流配送路径优化问题的遗传算法（一）遗传算法的基本要素遗传算法是一种“生成+检测”的迭代搜索算法。该算法以群体中的所有个体为操作对象，每个个体对应研究问题的一个解。选择、交叉和变异是遗传算法的三个主要操作算子。该算法包括以下6个基本要素：1、编码。由于遗传算法不能直接处理解空间的数据，因此，必须通过编码将它们表示成遗传空间的基因型串结构数据。2、初始群体生成。由于遗传算法是一种群体型搜索方法，所以必须为遗传操作准备一个由若干个体组成的初始群体，每个个体都应通过随机方法产生，并分别对应研究问题的一个解。3、适应度评估。遗传算法在搜索过程中一般不需要其他外部信息，仅用适应度来评估个体的优劣，并以其作为遗传操作的依据。4、选择。选择操作是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙，个体的适应度越高，其被选择的机会就越大。5、交叉。它是遗传算法中最主要的操作，一般分两步进行，一是对群体中的个体进行随机配对；二是在配对个体中，随机设定交叉处，使配对个体彼此交换部分信息。6、变异。即按一定的概率改变个体的基因链。变异操作同样是随机进行的，其目的是挖掘群体中个体的多样性，克服遗传操作可能限于局部解的弊端。（二）物流配送路径优化问题的遗传算法的构造针对物流配送路径优化问题的特点，作者构造了求解该问题的遗传算法。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条配送路径；个体573894216表示的配送路径方案为：路径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。与其他交叉方法相比，这种方法在两父代个体相同的情况下仍能产生一定程度的变异效果，这对维持群体的多样化特性有一定的作用。6、变异操作。由于在选择机制中采用了保留最佳样本的方式，为保持群体内个体的多样化，本文采用了连续多次对换的变异技术，使个体在排列顺序上的有较大变化。变异操作是以概率Pm发生的，一旦变异操作发生，则用随机方法产生交换次数J，对所需变异操作的个体的基因进行J次对换（对换基因的位置也是随机产生的）。四、实验计算与结果分析作者根据上述遗传算法编制了C语言程序，并对文献列出的一个某配送中心使用2辆汽车对8个需求点进行送货的物流配送路径优化问题实例进行了实验计算。设汽车的载重量为8t，每次配送的最大行驶距离为40km，配送中心与各需