一种改进人工鱼群算法求解冷链中车辆路径问题

发布时间：2020-12-31 06:57

　　针对一类特殊的多车型车辆路径问题(Heterogeneous Vehicle Routing Problems,HVRP),即冷链中带时间窗与能量消耗的车辆路径问题开展研究.将配送车辆分为了两种:普通车辆与冷藏车辆,目标是在考虑客户满意度的同时将运输总成本最小化,为此建立了新的问题模型,采用了改进的人工鱼群算法对此类问题进行求解.为了使算法更适用于求解离散化的优化问题,对觅食行为和追尾行为进行了改进,改进的追尾行为在一定的概率范围内学习最优解,具备了跳出局部最优解的能力.同时,在改进的人工鱼群算法中结合变异算子和交叉算子,增强了局部搜索和全局搜索能力.最后通过大量的仿真实验证明了该改进算法的有效性. 

【文章来源】：聊城大学学报(自然科学版). 2020年05期

【文章页数】：11 页

【部分图文】：

编码示意图

解码甘特图

在经典的AFS算法中，觅食行为用于为每个选择的解生成邻近解．然而，AFS算法中的觅食行为仅适用于连续优化问题，为了使其适用于求解离散优化问题，提出了一种改进的觅食行为，具体如：Step 1：循环初始解集的每一个解xi，根据“可视范围”确定解的邻域解集．Step 2：如果当前解xi在“可视范围”内随机选择一个解xj,xj如果的目标值比xi优秀，则xi向xj方向移动，即xi与xj进行交叉操作．Step 3：在公告板更新最好解．Step 4：更新xi的尝试次数Try＿number．在改进的觅食行为中，对现有的人工鱼xi采取两种策略：（1）策略I.Step 1：为了生成邻域解，随机选择一种车型，对所选车型随机选择一辆车，然后从中随机选择一个客户，并将其在所选车辆中删除．Step 2：将所选客户插入到同类型的另一辆车中．在策略I中，将客户插入到当前解决方案的时间复杂度为O(n2），假设要重新插入的客户数量为（1/r）×n，其中r为选择的速率，则该策略的时间复杂度为O(n3).(2）策略Ⅱ．Step 1：为了生成邻域解，与策略I相同，随机选择一辆车，然后从所选车辆中随机选择一定数量的客户并将这些客户从当前车辆中删除．Step 2：将选择的客户随机插入到相同车型的其他车辆中．策略Ⅱ中的改进的觅食行为过程如图3．两种觅食启发式在该改进算法中是随机选择使用的．3.4 改进的追尾行为

【参考文献】：
期刊论文
[1]带时间窗车辆路径问题的粒子群算法[J]. 李宁,邹彤,孙德宝.  系统工程理论与实践. 2004(04)

博士论文
[1]一种新型的智能优化方法-人工鱼群算法[D]. 李晓磊.浙江大学 2003



本文编号：2949181