关于基于遗传算法的物流配送路径优化分析

毕业设计计题目 基于于遗传算算法的物物流配送送路径优优化分析析学生姓名 学 号 专 业 班 级 指导教师 二 0 00 九 年 十 月目 录黑体三号居中）（空一行在文中不能出现字样。）摘要宋体小四号。一、引言（问题题的提出出引言或问题的提出只能选一。）行间距1.5倍行。 1二、物流配配送路径径优化问问题的数数学模型型XX根据具体页码标明。三、物流配配送路径径优化问问题的遗遗传算法法XX（一）遗传传算法的的基本要要素 X（二）物流流配送路路径优化化问题的的遗传算算法的构构造X四、实验计计算与结结果分析析 X五、 结论论X参考文献 X致谢 X 摘摘 要要黑体四号字加粗：论文在在建立物物流配送送路径优优化问题题的数学学模型的的基础上上，构造造了求解解该问题题的遗传传算法，并并进行了了实验计计算。计计算结果果表明，用用遗传算算法进行行物流配配送路径径优化，可可以方便便有效地地求得问问题的最最优解或或近似最最优解行间距1.5倍行。 关关键词3-5个：物流配配送；遗遗传算法法；优化化Studyy onn thhe OOptiimizzingg off Phhysiicall Diistrribuutioon RRouttingg Proobleem BBaseed oon GGeneeticc Allgorrithhm Abstrractt：On thee baasiss off esstabblisshinng tthe opttimiizinng mmodeel oon pphyssicaal ddisttribbutiion rouuting proobleem, thiis ppapeer ppressentts a gennetiic aalgooritthm forr soolviing thiis pprobblemm, aand makke ssomee exxperrimeentaal ccalcculaatioons. Thhe eexpeerimmenttal callcullatiion ressultts ddemoonsttrattes thhat thee opptimmal or neaarlyy opptimmal sollutiionss too thhe pphyssicaal ddisttribbutiion rouutinng pprobblemm caan bbe eeasiily obttainned by usiing gennetiic aalgooritthm.Keywoordss：phhysiicall diistrribuutioon；gennetiic aalgooritthm；opttimiizinng 一该文题目为“基于遗传算法的物流配送路径优化研究”、引言四号黑体加粗字（问问题的提提出） 随随着市场场经济的的发展和和物流技技术专业业化水平平的提高高，物流流配送业业得到了了迅猛发发展。物物流配送送是指按按用户的的订货要要求，在在配送中中心进行行分货、配配货，并并将配好好的货物物及时送送交收货货人。在在物流配配送业务务中，存存在许多多优化决决策问题题，本文文讨论其其中的物物流配送送路径优优化问题题，即通通过制定定合理的的配送路路径，快快速而经经济地将将货物送送达用户户手中。配配送路径径的选择择是否合合理，对对加快配配送速度度、提高高服务质质量、降降低配送送成本及及增加经经济效益益都有较较大影响响。 研研究表明明，配送送路径优优化问题题是一个个NP难难题，只只有在需需求点和和路段较较少时，才才能求得得精确解解。因此此，用启启发式算算法求解解该问题题就成为为人们研研究的一一个重要要方向，并并出现了了多种启启发式算算法，如如Claarkee和Wriightt提出的的节约法法，Giilleett和和Milllerr提出的的扫描法法 Z米凯利维茨. 演化程序遗传算法和数据编码的结合M. 北京：科学出版社，2000.等，虽虽然这些些算法为为求解配配送路径径优化问问题提供供了有效效的方法法，但也也存在一一定的问问题，如如节约法法虽然具具有运算算速度快快的优点点，但也也有组合合点零乱乱、边缘缘点难以以组合的的问题，扫扫描法为为非渐进进优化等等。如何何针对物物流配送送路径优优化问题题的特点点，构造造运算简简单、寻寻优性能能优良的的启发式式算法，是是一个值值得深入入研究的的课题。遗传算法的的出现为为求解物物流配送送路径优优化问题题提供了了新的工工具，该该算法是是由美国国的J.Holllannd教授授于19975年年提出的的，它是是一种借借鉴生物物界自然然选择和和自然遗遗传机制制的随机机化搜索索方法。由由于遗传传算法采采用随机机选择，对对搜索空空间无特特殊要求求，无需需求导，具具有运算算简单、收收敛速度度快等优优点，尤尤其适用用于处理理传统搜搜索方法法难于解解决的复复杂和非非线性的的问题，目目前已广广泛应用用于组合合优化、机器学习、自适应控制等领域。本文针对物流配送路径优化问题的特点，构造了求解该问题的遗传算法，通过实验计算，得到了较好的结果。二、物流配配送路径径优化问问题的数数学模型型四号黑体加粗字 物流配送路路径优化化问题可可以描述述为：从从配送中中心（或或称物流流据点）用用多辆汽汽车向多多个需求求点（或或称顾客客）送货货，每个个需求点点的位置置和需求求量一定定，每辆辆汽车的的载重量量一定，要要求合理理安排汽汽车路线线，使总总运距最最短，并并满足以以下条件件：（11）每条条配送路路径上各各需求点点的需求求量之和和不超过过汽车载载重量；（2）每每条配送送路径的的长度不不超过汽汽车一次次配送的的最大行行驶距离离；（33）每个个需求点点的需求求必须满满足，且且只能由由一辆汽汽车送货货。本文文借鉴文文献33建立立的车辆辆路径问问题的数数学模型型，并通通过考虑虑上述物物流配路路径优化化问题的的约束条条件和优优化目标标，建立立了物流流配送路路径优化化问题的的数学模模型。 设配送中心心有K辆辆汽车，每每辆汽车车的载重重量为QQk（k=1，22，KK），其其一次配配送的最最大行驶驶距离为为Dk，需要要向L个个需求点点送货，每每个需求求点的需需求量为为qi（i=1，22，LL），需需求点ii到j的运距距为dij，配配送中心心到各需需求点的的距离为为d0j（ii、j=1，2，L），再再设nk为第kk辆汽车车配送的的需求点点数（nnk=0表表示未使使用第kk辆汽车车），用用集合Rk表示第第k条路径径，其中中的元素素rki表示需需求点rrki在路路径k中的顺顺序为ii（不包包括配送送中心），令令rk0=0表示示配送中中心，则则可建立立如下物物流配送送路径优优化问题题的数学学模型： （1） ss.t. （22） （33） （4） （55） （66） （7） （88）上述模型中中，（11）式为为目标函函数；（22）式保保证每条条路径上上各需求求点的需需求量之之和不超超过汽车车的载重重量；（33）式保保证每条条配送路路径的长长度不超超过汽车车一次配配送的最最大行驶驶距离；（4）式式表明每每条路径径上的需需求点数数不超过过总需求求点数；（5）式式表明每每个需求求点都得得到配送送服务；（6）式式表示每每条路径径的需求求点的组组成；（77）式限限制每个个需求点点仅能由由一辆汽汽车送货货；（88）式表表示当第第k辆汽汽车服务务的客户户数1时，说说明该辆辆汽车参加加了配送送，则取取siggn(nnk)=11，当第第k辆汽汽车服务务的客户户数1时，表表示未使使用该辆辆汽车，因因此取ssignn(nk)=00。三、物流配配送路径径优化问问题的遗遗传算法法四号黑体加粗字（一）遗传传算法的的基本要要素小四号宋体加粗字 遗传算法是是一种“生成+检测”的迭代搜搜索算法法。该算算法以群群体中的的所有个个体为操操作对象象，每个个个体对对应研究究问题的的一个解解。选择择、交叉叉和变异异是遗传传算法的的三个主主要操作作算子。该该算法包包括以下下6个基基本要素素： 1、编码。由由于遗传传算法不不能直接接处理解解空间的的数据，因因此，必必须通过过编码将将它们表表示成遗遗传空间间的基因因型串结结构数据据。 2、初始群群体生成成。由于于遗传算算法是一一种群体体型搜索索方法，所所以必须须为遗传传操作准准备一个个由若干干个体组组成的初初始群体体，每个个个体都都应通过过随机方方法产生生，并分分别对应应研究问问题的一一个解。 3、适应度度评估。遗遗传算法法在搜索索过程中中一般不不需要其其他外部部信息，仅用适应度来评估个体的优劣，并以其作为遗传操作的依据。 4、选择。选选择操作作是为了了从当前前群体中中选出优优良的个个体，使使它们有有机会作作为父代代为下一一代繁殖殖子孙，个个体的适适应度越越高，其其被选择择的机会会就越大大。 5、交叉。它它是遗传传算法中中最主要要的操作作，一般分分两步进进行，一一是对群群体中的的个体进进行随机机配对；二是在在配对个个体中，随随机设定定交叉处处，使配配对个体体彼此交交换部分分信息。 6、变异。即即按一定定的概率率改变个个体的基基因链。变变异操作作同样是是随机进进行的，其其目的是是挖掘群群体中个个体的多多样性，克克服遗传传操作可可能限于于局部解解的弊端端。（二）物流流配送路路径优化化问题的的遗传算算法的构构造小四号宋体加粗字 针对物流配配送路径径优化问问题的特特点，作作者构造造了求解解该问题题的遗传传算法。 1、编码方方法的确确定。根根据物流流配送路路径优化化问题的的特点，作作者采用用了简单单直观的的自然数数编码方方法，用用0表示示配送中中心，用用1、22、LL表示各各需求点点。由于于在配送送中心有有K辆汽汽车，则则最多存存在K条条配送路路径，每每条配送送路径都都始于配配送中心心，也终终于配送送中心，为为了在编编码中反反映车辆辆配送的的路径，作作者巧妙妙地采用用了增加加K-11个虚拟拟配送中中心的方方法，分分别用LL+1、LL+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、初始群群体的确确定。随随机产生生一种11L+K-11这L+K-11个互不不重复的的自然数数的排列列，即形形成一个个个体。设设群体规规模为NN，则通通过随机机产生NN个这样样的个体体，即形形成初始始群体。3、适应度度评估。对对于某个个个体所所对应的的配送路路径方案案，要判判定其优优劣，一一是要看看其是否否满足配配送的约约束条件件；二是是要计算算其目标标函数值值（即各各条配送送路径的的长度之之和）。本本文根据据配送路路径优化化问题的的特点所所确定的的编码方方法，隐隐含能够够满足每每个需求求点都得得到配送送服务及及每个需需求点仅仅由一辆辆汽车配配送的约约束条件件，但不不能保证证满足每每条路径径上各需需求点需需求量之之和不超超过汽车车载重量量及每条条配送路路线的长长度不超超过汽车车一次配配送的最最大行驶驶距离的的约束条条件。为为此，对对每个个个体所对对应的配配送路径径方案，要要对各条条路径逐逐一进行行判断，看看其是否否满足上上述两个个约束条条件，若若不满足足，则将将该条路路径定为为不可行行路径，最最后计算算其目标标函数值值。对于于某个个个体j，设设其对应应的配送送路径方方案的不不可行路路径数为为Mj（Mj=0表示示该个体体对应一一个可行行解），其其目标函函数值为为Zj，则该该个体的的适应度度Fj可用下下式表示示： Fj=1/（Zj+MjG） （99）式中，G为为对每条条不可行行路径的的惩罚权权重，可可根据目目标函数数的取值值范围取取一个相相对较大大的正数数。 4、选择操操作。将将每代群群体中的的N个个个体按适适应度由由大到小小排列，排排在第一一位的个个体性能能最优，将将它复制制一个直直接进入入下一代代，并排排在第一一位。下下一代群群体的另另N-11个个体体需要根根据前代代群体的的N个个个体的适适应度，采采用赌轮轮选择法法4产生。具具体地说说，就是是首先计计算上代代群体中中所有个个体适应应度的总总和（Fj），再再计算每每个个体体的适应应度所占占的比例例（Fjj/Fj），以以此作为为其被选选择的概概率。这这样选择择方法既既可保证证最优个个体生存存至下一一代，又又能保证证适应度度较大的的个体以以较大的的机会进进入下一一代。 5、交叉操操作。对对通过选选择操作作产生的的新群体体，除排排在第一一位的最最优个体体外，另另N-11个个体体要按交交叉概率率Pc进行配配对交叉叉重组。本本文采用用了一种种类似OOX法2的的交叉方方法，现现举例说说明之：随机在在父代个个体中选选择一个个交配区区域，如如两父代代个体及及交配区区域选定定为：AA=477|85563|9211，B=83|46991|2257；将B的的交配区区域加到到A的前前面，AA的交配配区域加加到B的的前面，得得：A=46691|478856339211，B=85563|834469112577；在A、B中自交交配区域域后依次次删除与与交配区区相同的的自然数数，得到到最终的的两个体体为：AA”=466917785332，BB”=855634491227。与与其他交交叉方法法相比，这这种方法法在两父父代个体体相同的的情况下下仍能产产生一定定程度的的变异效效果，这这对维持持群体的的多样化化特性有有一定的的作用。 6、变异操操作。由由于在选选择机制制中采用用了保留留最佳样样本的方方式，为为保持群群体内个个体的多多样化，本本文采用用了连续续多次对对换的变变异技术术，使个个体在排排列顺序序上的有有较大变变化。变变异操作作是以概概率Pmm发生的的，一旦旦变异操操作发生生，则用用随机方方法产生生交换次次数J，对对所需变变异操作作的个体体的基因因进行JJ次对换换（对换换基因的的位置也也是随机机产生的的）。四、实验计计算与结结果分析析四号黑体加粗字 作者根据上上述遗传传算法编编制了CC语言程程序，并并对文献献列出的的一个某某配送中中心使用用2辆汽汽车对88个需求求点进行行送货的的物流配配送路径径优化问问题实例例进行了了实验计计算。设设汽车的的载重量量为8tt，每次次配送的的最大行行驶距离离为400km，配配送中心心与各需需求点之之间、各各需求点点相互之之间的距距离及各各需求点点的需求求量见表表1。表1 配配送中心心与需求求点之间间的距离离及各需需求点的的需求量量表表名在表的正上方dij (km) jji01234567800467.5920101681406.541057.51110266.507.510107.57.57.537.547.501059915491010100107.57.5105205105100797.56107.57.597.570710716117.597.59701088107.515107.510100qj (tt)-12121422根据上述实实例的特特点，作作者在实实验计算算中采用用了以下下参数：群体规规模取220，交交叉概率率和变异异概率分分别取00.95和和0.05，进进化代数数取500，变异异时基因因换位次次数取55，对不不可行路路径的惩惩罚权重重取1000kmm。对上上述问题题，利用用计算机机随机求求解100次，得得到的计计算结果果见表22。表2 物物流配送送路径优优化问题题的遗传传算法计计算结果果计算次序12345678910配送总距离离Z /km727276.57067.57073.57571.569从表中数据据可以看看出，110次运运行得到到的结果果均优于于节约法法所得的的结果779.55km。而而且第55次还得得到了该该问题的的最优解解67.5kmm，其对应应的配送送路径方方案为：路径11：0-4-77-6-0；路路径2：0-22-8-5-33-1-0。可可见，利利用遗传传算法可可以方便便有效地地求得物物流配送送路径优优化问题题的最优优解或近近似最优优解（或或称满意意解）。五、 结论论黑体四号加粗 （一）在物物流配送送业务中中，合理理确定配配送路径径是提高高服务质质量、降降低配送送成本、增增加经济济效益的的重要手手段。由由于物流流配送路路径优化化问题是是一个NNP难题题，因此此，采用用启发式式算法求求解是一一个重要要的研究究方向。 （二）本文文在建立立物流配配送路径径优化问问题的数数学模型型的基础础上，构构造了求求解物流流配送路路径优化化问题的的遗传算算法。实实验计算算结果表表明，遗遗传算法法是一种种性能优优良的启启发式搜搜索方法法，利用用该方法法可以方方便有效效地求得得物流配配送路径径优化问问题的最最优解或或满意解解。（三）本文文所构造造的进行行物流配配送路径径优化的的遗传算算法，包包括巧妙妙设计的的个体编编码方法法、个体体适应值值的计算算方法以以及选择择、交叉叉和变异异算子，对对解决类类似的组组合优化化问题具具有一定定的参考考价值。参考文献仿宋四号加粗居中（空一行）1蔡希希贤，夏夏士智宋体五号字. 物流流合理化化的数量量方法M表示书. 武汉：华中工工学院出出版社，119855.2陈国良良，王煦煦法，庄庄镇泉，王王东生. 遗传传算法及及其应用用M. 北北京：人人民邮电电出版社社，19996.3姜大大立，杨杨西龙，杜杜文，周周贤伟. 车辆辆路径问问题的遗遗传算法法研究J表示杂志. 系系统工程程理论与与实践，119999，（66）：40-44.4Z米凯利利维茨. 演化化程序遗传传算法和和数据编编码的结结合MM. 北京：科学出出版社，220000. 5王江江.车辆辆调度认认知NN.中中国物流流报,220099-122-099: 22此图作为标明图号的格式。图名在图正下方。致 谢谢黑体小三字加粗。这是北京交通大学的一研究生的致谢词。衷心感谢指指导老师师汝宜红红教授对对我的精精心培养养和谆谆谆教诲。本本文是在在导师的的指导下下完成的的，导师师严谨的的治学态态度、渊渊博的学学识和忘忘我的敬敬业精神神给我留留下了难难忘的印印象，并并使我终终生受益益师兄朱朱煜对论论文的思思路提出出了诸多多建设性性的意见见，在论论文的撰撰写过程程中给予予大力的的指导和和鼓励，经经济管理理学院的的李卫东东老师给给与我统统计方面面的大量量帮助，郑凯博士为论文的顺利进展给予极大的支持和关怀，提供了非常有益的建议和资料，在此致以诚挚的谢意! 北京市工商行政管理局信息中心的陈会明主任为物流企业信息提供了有益资料，特表谢意。感谢好友的的苏威、李李萌、以以及宿舍舍同学对对我的关关心和帮帮助，是是他们无无私的支支持和鼓鼓励伴我我完成毕毕业论文文，再次次感谢所所有关心心和帮助助过我的的人们!老师、师兄兄、朋友友所给与与我的一一切，我我将铭刻刻在心，永永志不忘忘！