一种改进的种群增量学习算法求解带软时间窗的车辆路径优化问题  

Improved population-based learning algorithm for solving vehicle routing problem with soft time windows

作　　者：谢勇[1] 胡蓉[1] 钱斌[1] 陈少峰[1] 张桂莲[1] 张笑迪 

机构地区：[1]昆明理工大学信息工程与自动化学院,云南昆明650500

出　　处：《南京理工大学学报》2016年第1期110-116,共7页Journal of Nanjing University of Science and Technology

基　　金：国家自然科学基金(60904081);云南省应用基础研究计划项目(2015FB136);云南省中青年学术和技术带头人后备人才项目(2012HB011);昆明理工工大学学科方向建设项目(14078212)

摘　　要：针对求解带软时间窗车辆路径问题(Vehicle routing problem with soft time windows,VRPSTW),提出一种改进的种群增量学习算法(Improved population-based incremental learning algorithm,IPBIL)优化运输总成本。提出一种新型的3维种群增量学习模型引导算法执行全局搜索,发现解空间中的优质解区域;设计一种基于客户间距离和惩罚成本相关度的交换操作进一步提高解的质量;提出一种关于时间窗问题性质的插入和逆转操作,对优质解区域进行细致搜索。最后,通过仿真实验和算法比较,验证了该文所提出的IPBIL的有效性。An improved population-based incremental learning algorithm, short for IPBIL, is proposed to solve the vehicle routing problem with soft time windows（VRPSTW） for optimizing the total trans- portation cost. A new three-dimensional population incremental learning model is proposed to lead the algorithm to perform global search, find high quality solution region in the solution space. An exchange operation ,which is based on the client distance and the penalty cost correlation degree, is designed to further improve the quality of solutions. An insertion and reverse operation based on the character of the time windows problem is proposed for detailed search in high-quality solution space. Through the simulation experiment and the comparison of algorithms, the proposed IPBIL is verified effectively.

关 键 词：种群增量学习算法 带软时间窗的车辆路径问题 概率模型 优质解区域 运输总成本 有效性 全局搜索 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]