求解卸装一体化车辆路径问题的改进导向局部搜索算法.pdf

《求解卸装一体化车辆路径问题的改进导向局部搜索算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第15卷第18期2015年6月科学技术与工程VoJ_15No．18Jun．20151671—1815(2015)18—0066—05ScienceTechnologyandEngineering⑥2015Sci．Tech．Engrg．计算机技术求解卸装一体化车辆路径问题的改进导向局部搜索算法田冉孙林夫’唐慧佳赵进超(西南交通大学信息科学与技术学院，成都610031；郑州轻工业学院计算机与通信工程学院，郑州450002)摘要针对卸装一体化车辆路径问题，提出一种变惩罚函数的导向局部搜索算法(IGLS)。在传统导向局部搜索算法

2、的基础上加入了新的惩罚效用函数，当传统导向局部搜索算法陷入局部最优时，变换惩罚策略后重新搜索，从而扩展搜索的邻域。通过和传统导向局部搜索算法以及TS—GLS算法在不同算例上的仿真结果比较，验证了所提算法在解决卸装一体化车辆路径问题上的有效性和稳定性。关键词卸装一体化车辆路径问题变惩罚函数导向局部搜索惩罚策略中图法分类号TP301；文献标志码A装卸一体化车辆路径问题(vehicleroutingprob．到更好的性能和收敛速度，但缺点是这类算法对初1emwithsimultaneousdeliveryandpickup，V

3、RPSDP)始解和邻域的依赖较大。因此，选择合适的邻域和是车辆路径问题(capacitatedvehicleroutingprob-设计有效的局部最优解逃离策略对算法性能至关lem，VRP)问题的扩展。其普遍存在于邮政、制造、重要。电商等企业的物流运输中，是降低物流成本，提高客在应用传统的导向局部搜索算法解决VRPSDP户满意的关键问题。由于VRPSDP同VRP问题都问题时由于采用的惩罚策略在迭代过程中并无变属于NP难题，因此目前国内外对于VRPSDP的动，就可能导致一些必然经过的长路径被作为惩罚研究主要集中在各种元启发

4、式算法和混合式的启发边而被惩罚，从而导致了算法在逃离局部最优时经算法上，在元启发式算法方面：GajpalY、AiTJ、历了大量的无用计算。因此提出一种新的变惩罚函TasanAS、Alfredo等分别采用蚁群算法、粒子数的导向局部搜索算法(improvedguidedlocal群算法、遗传算法、禁忌搜索算法等来解决这一问search)，采用多惩罚函数从而降低了单一惩罚函数题。在混合启发式算法上，K．Ganesh等提出多阶惩罚有效边的可能性，扩大了邻域搜索范围。同时段的改进混合启发式算法；J．Crispim等提出结合通过反复

5、搜索来减少初始解对算法的影响。最后通禁忌搜索和变邻域下降搜索的混合算法；E．E．Za—过对28个算例的求解，表明了该算法的有效性和稳chariadis等提出导引式局部搜索和禁忌搜索相结定性，为求解装卸一体化车辆路径问题提供了新的合的混合算法。根据使用解的个数，又可将这些启求解思路。发式算法分为两类：基于个体的局部搜索方法(如模拟退火、禁忌搜索、导向局部搜索算法等)和基于1问题描述群体的全局搜索方法(如遗传算法、蚁群算法)。大1．1问题描述量的研究表明基于个体的局部搜索方法往往能够得装卸一体化车辆路径问题可以定义为：设定有

6、向带权图G=(V，A，C)，其中V={iIi=0，1，⋯，2014年12月29日收到国家高技术研究发展计划(863)n}是节点集合，节点0为出发地节点，(1～)为(2013AA040606)和四川省科技支撑计划项目(2014GZ0142)资助第一作者简介：田冉(1981一)，男，河南南阳人，博士研究生。E．客户地节点；A={i，Ii，EV}表示弧集，C=mail：troom@163．com。{c1．(i，)∈A}为权重矩阵，C表示节点i到节通信作者简介：孙林夫(1963一)，男，浙江人，教授。研究方向：云点．的距离。设定

7、每个客户节点i都有卸货需求d制造，云服务平台技术。E—mail：sunlf@vip．sina．com。和装货需求P，运输车辆的最大载货量为Q。VRPS-DP则可以描述为：①每辆车都从0点出发，服务若18期田冉，等：求解卸装一体化车辆路径问题的改进导向局部搜索算法67干客户后返回0点，形成一个解S；②每个客户都仅总的弧长。A为规范化系数，通常取0．01～0．10⋯。被服务一次，而且只能由某一车辆提供服务；③每个通过惩罚具有惩罚特征的解，保证了较好特征的可车辆的载重量都不超过Q；④所有客户的装卸货需行解进行邻域搜索，通过目标

8、函数的不断修改，使得求都不超过Q；⑤总的运输距离s)最小。当前局部极值不再具有局部最优性，从而不断迭代1．2解的可行性定义找到最优解。对于VRPSDP的解S={rI．=1，⋯，k}，其中2．2惩罚效用函数设计r={ili∈[1，n]}，表示车辆的路径，k为解中最由于传统的惩罚效用函数U(S)寻找的是解大的车辆数。对于