一种基于改进遗传算法的智能运输调度优化方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN111709559A(43)申请公布日2020.09.25(21)申请号202010474257.6(22)申请日2020.05.29(71)申请人杭州电子科技大学地址310018浙江省杭州市下沙高教园区2号大街(72)发明人徐海涛段凤浦攀(74)专利代理机构杭州君度专利代理事务所(特殊普通合伙)33240代理人朱月芬(51)Int.Cl.G06Q10/04(2012.01)G06Q10/08(2012.01)G06N3/12(2006.01)权利要求书3页说明书6页附图7页(54)发明名称一种基于改进遗传算法的智能运输调度优化方法(57)摘要本发明公开了一种基于改进的遗传算法的智能运输调度优化方法。该方法对遗传算法的几个关键操作进行了改进，加入了精英保留策略和最优近距离的交叉方法，同时，在进行适应度评估时考虑了近距离服务优先规则。精英保留策略将每一代种群中适应度最好的个体直接保留到下一代，避免它被交叉和变异操作破坏。最优近距离的交叉方法可以将种群中距离较近的个体连续排列，加快算法的收敛速度。在进行个体适应度评估时，对违背近距离服务优先规则的个体给予相应的惩罚，增大个体间的差异，从而增加优秀个体被选择的概率。本发明运算速度快，能在给定较短的优化时间的前提下得到较优的优化结果，解决了传统动态调度方法中优化效率低下的问题。CN111709559ACN111709559A权利要求书1/3页1.一种基于改进遗传算法的智能运输调度优化方法，其特征在于包括如下步骤：步骤1、确定时间相关参数，包括最大遗传优化的处理时间、客户列表的更新时间周期、工作时间以及系统接收新订单的截止时间；步骤2、在工作日开始之前，先对前一天还没有处理的所有客户订单进行遗传优化，选择总成本最低的排列顺序，按照所选的排列顺序，依次安排能在第一个更新周期内完成服务的客户对象；步骤3、按照客户列表的更新时间周期更新客户列表，将新接收到的客户对象与还未处理的客户对象作为一个整体，再次运用遗传优化，安排下一个更新周期内需要服务的客户对象；步骤4、判断当前时间是否已到接收新订单的截止时间，如果没有，则跳转到步骤3；若已到达接收新订单的截止时间，则不再接收新的订单；判断所有接收到的订单是否已全部完成，如果全部完成，则程序结束；否则继续进行遗传优化，按照最优方案安排调度。2.根据权利要求1所述的一种基于改进遗传算法的智能运输调度优化方法，其特征在于步骤2、3和4中所述的遗传优化的模型的建立具体如下：2-1.遗传优化模型的假设条件如下：①所有调度车辆采用同一型号；②所有调度车辆必须从车场出发，服务完成后再回到车场；③每个客户只能被一辆车访问，而且只能被访问一次；④任何时刻都需满足容量约束；2-2.遗传优化模型中使用的变量及其含义如下：V表示所有车辆的数量v表示车辆vvi表示车辆v访问的第i个节点qi表示客户i的订单请求；pi,j表示从客户i到客户j的惩罚因子Nv表示车辆v访问的节点数运输车每个节点(包括车场节点和客户节点)向下一个节点转移时，都需要考虑是否违背了近距离优先服务的原则，如果违背这一原则，则需要加入惩罚因子，惩罚因子的设计如下：因此，遗传优化模型的目标函数为：假设每辆车的最大容量是Q，访问的节点对象总数为N，则需要满足约束条件如下:2CN111709559A权利要求书2/3页3.根据权利要求1或2所述的一种基于改进遗传算法的智能运输调度优化方法，其特征在于步骤2、3和4中所述的遗传优化的实现步骤如下：3-1.设定遗传相关参数：种群大小N，选择概率ps，交叉概率pc，变异概率pm，最大的遗传优化时间Tmax，精英选择的比例rate；3-2.初始化种群P0，即随机产生N个可行解，可行解序列是由前一天未处理的客户对象组成；3-3.设定优化时间t为0，种群代数g为0；3-4.计算种群中个体的适应度，按照精英选择比例从种群中选择一定数量的精英个体组成精英群体，同时，采用改进的锦标赛选择策略从种群中选择N个个体构成一个新的种群p1；3-5.用精英群体中的所有个体替换种群p1相应数目最差的几个个体，构成新种群p2；3-6.将改进的混合交叉策略作用于种群p2，形成新种群p3；3-7.将反转变异策略作用于种群p3，形成新种群p4；3-8.用精英群体中的最优个体替换种群p4中适应度最差的个体，形成新种群p5；3-9.更新种群代数g＝g+1，更新种群Pg＝p5；3-10.判断当前系统执行优化的时间t,若超过最大的遗传优化时间，则种群Pg中适应度最优的个体就表示问题的最优解；如果没有超过最大遗传优化时间，则转至步骤3-4。4.根据权利要求3所述的一种基于改进遗传算法的智能运输调度优化方法，其特征在于所述的步骤3-4中改