改进的遗传算法在物流管理中的应用

《改进的遗传算法在物流管理中的应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、物；赢平台改进的遗传髯法在物流管理巾的应用一雷亮杨波重庆科技学院电子信息工程学院[摘要】本文针对传统的双种群遗传算法用于求解最优化问题时常采用固定染色体交叉概率和染色体变异概率，容易出现早熟、收敛速度较慢的问题，提出新的双种群遗传算法，并成功地运用到车辆路径问题的研究。[关键词]物流管理车辆路径问题遗传算法求解物流管理中车辆路径问题．遗传算法是被研究得最多的这样就相应地提高了群体中表现优良的个体的P和P．使得一种。但标准遗传算法(GeneticAlgorithm简称GA)易陷入局部极他们不会处于一种近乎停

2、滞不前的状态。因此．自适应的P和P值解．出现“早熟收敛现象能够提供相对某个解的最佳P和P。改进后的染色体交叉算子和一变异算子在保证群体多样性的同时．保证遗传算法的收敛性。、问题的描述及数学模型物流配送路径优化问题一般可以这样描述从某物流配送中三求解车辆路径问题心最多用K辆配送车向L个客户送货。每辆车载重为b《k=1．2，为便于比较．本实验仍采用的经典测试集。用上述改进的双3⋯．．K)，每个客户货物需求量为d(i=1．2．⋯．L)，客户i种群遗传算法．对一个有8个客户和1个配送中心．两辆车{容6到客户j之间

3、的距离为C假设忽略体积因素在满足各客户配量均为8吨)的配送系统的车辆路径问，题进行求解．已知各客户送需求且不超载的情况下。确定合适的车辆数，以及如何安排行的需求和各客户¨㈩之表1客户间距离及㈩各客户弼求量表车路线，使得总的运输成本最低。问的距离如表1(其QOl2345678设nk为第k辆车所包含的客户数(若n=0表示未启用第k辆中0表示配送中心)．OO467．592010l68车)．用集合R表示第k条路径其中的元素r表示客户『．在路径要求合理安排车辆I4O6．5‘lO5，。5IIlO266．5O7．5IO

4、lO，．S7。57。5k中的顺序为i(不包含物流中心)。令r。=r=O表示物流中心．的行驶路线，使总的37．547．5OIOS99l5则有如下的车辆路径问题的数学模型。运距最短49lOlOlOOlO7S7l5lOmj”埘(绝))用2×8个互不5205lO，IOO797l5，I，^廿重复的1到16的自然6lO7．5，．5975707lO蚍芝d，’⋯·数构成一条染色体，7l6ll7．597：59，OIO0<-§￡，k=l2，，IZ表示一种车辆路径88lO7．Sl5IO7．5lOIOO安排方案。随机产生需求量l

5、2l2l422∑=￡．10个这样的染色体构成初始种群。利用自适应染色体交叉算子和尺}={rhl，'H∈{lt2，3．⋯r上}Ii=1,2·t，珂)变异算子．采用不同的初始种群，经过上机运行10次．进化50尺nRk0，V≠k代和100代得到路径长度与传统的双种群遗传算法的结果对比如表2所示。表3是得到最优解67．5所需的进化代数对比。其中．咖一I)：l：实验符号表示：GA传统的双种群遗传算法。上式中不等式(2}保证每条路径上的各客户的总需求量不超过NewGA本文提出的新双种群遗传算法此条路径配送车容量．不等

6、式(3)表明每条路径服务的客户数不表2两种遗传算法的运行结果超过总客户数，等式(4)要求每个客户都得到车辆的配送服务．等安I盘蒎数t234S6'l9lOAver式{5)表示每条路径的客户组成．等式(6)则限制每个客户的需求o^∞．2秘。3，b64曲，8，l7172们锚．9曲．52仅能由一车辆来完成．代N0^68．869．4秘07啦lall68．8凹．96。．8秘．47069。二改进的双种群遗传算法1OOo^∞'2的．468‘267．36S7mS6．，秘．4醴．3秘．92传统的双种群遗传算法．交叉概率、变异

7、概率固定不变，容代NeWo^髓．，69．16"／．S6搴67．5酾．2秘．26，．9秘．16，_5髓2易出现过早收敛而仅得到局部最优解的现象我们采用自适应遗表3得到最优解67．5所{Il}要的进化代数对比传算法中交叉概率和变异概率能自适应调节的特点．将双种群遗实验捩薮l23456'S9lO^W传算法中交叉概率P，和变异概率P一按如下公式进行自适应调整．o^62嚣932454loo魏222407n6使算法寻优速度加快而且不易陷入局部最优解。NeⅣG^6ll托5l静"／6，窖923o∞26o98L从表2和表3

8、可以看出．改进后的双种群遗传算法搜索到全P，_一{8}局最优解的效率要比传统的双种群遗传算法高能够快速的求得l最优解，是求解车辆路径问题的一种有效算法。l7-=7-～。)"L物流配送系统中的车辆路径问题具有减少运输成本、提高经尸一tP．A⋯(9)济效益的重要作用．对该问题的研究有多种解决方法。本文提出一种改进的双种群遗传算法求解VRP，通过自适应调整染色体交其中，f⋯代表群体中最大适应度；f⋯代表每代群体的平均适叉概率和染色体