得所需送货员的人数最少,线路及人员安排情况如下表:表二:模型一人员分配表送货员R123456合计路线L24681、53、7---------总时间(h)4.523.233.224.425.345.7126.44总重量(kg)24.523.524.718.348.245.3184.5总路程(km)88606898100122536综上,可得该模型所构建的路线共需6名送货员,快件完全送完所需总路程为536千米,所需总时间为26.44小时。该模型较简单直观,但也存在不足。在路径选择时,当其中某一点被路线选定后,该点将不作为接下来的任意一条路线的备选送货点,每一条路线均为当前条件下的最优路线,将所有路线组合后不一定是整体送货点的最优路线,即局部最优并非整体最优。为提高工作效率,使所走总路程更短、时间更少,我们对上述模型进行了优化。5.1.3利用顺序插入交叉算子(OIC)优化模型一顺序插入交叉算子是针对TSP问题的特点,在遗传算法的交叉运算过程中设计的三角距离差函数作为评价标准,运用贪婪策略思想,提出的一种新的交叉算子,该算子有效的利用了局部信息,并且能很好的继承父代优秀的基因。顺序插入交叉算子的基本思想是:对于两个待交叉的染色体,将一个作为基本染色体,另一个作为参考染色体,按照在参考染色体中的送货点间的邻接顺序,利用三角距离差函数作为评价标准,运用贪婪策略思想,逐步改变基本染色体的编码顺序,从而使经过交叉得到的两个子代染色体的适应度最高。优化思想:利用顺序插入交叉算子,我们将模型一中每一条进行染色体编码定义,如,将上述染色体看成一个环,染色体的下一个送货点是。定义,设有3个送货点,,,定义三角距离函数G(a,b,c)如下:(5.1.12)其中,表示送货点到送货点的距离。设待交叉的双亲为和,设计交叉算子其求解步骤如下:将父体作为基本染色体,父体作为参考染色体,在中随机找到一个参考城市
全文预览
