基于Sweep和主动禁忌的多时窗VRPPD设计  

Design for VRPPD with multi-time window based on Sweep and reactive tabu

作　　者：朱玲玲[1] 程学云[1] 魏晓宁[1] 吴宽仁[2] 

机构地区：[1]南通大学计算机科学与技术学院,江苏南通226019 [2]南京大学计算机科学与技术系,江苏南京211102

出　　处：《计算机工程与设计》2013年第9期3279-3283,共5页Computer Engineering and Design

基　　金：国家自然科学基金项目(60211227);广西教育厅科研基金项目(201204LX513);南通市自然科学基金项目(BK2011070);南通大学自然科学基金项目(03040850)

摘　　要：针对多时窗装卸车辆路线问题(vehicle routing problem with pickups and deliveries,VRPPD),提出了一种基于Sweep算法和主动禁忌算法的多时窗VRPPD问题求解方法。定义了多时窗VRPPD问题的数学模型;通过改进的Sweep算法获取初始解,设计了候选解结构、适应度函数、4种邻域操作以及邻域操作需满足的车辆容量约束和时间窗约束方程,采用主动禁忌算法自适应地修改禁忌长度以增强算法的全局寻优能力;定义了具体的多时窗VRPPD求解算法。实验结果表明,该方法能有效地解决多时间窗VRPPD问题;与其它方法相比,该方法具有全局搜索能力强和收敛速度快的优点。Aiming at solving VRPPD problem （vehicle routing problem with pickups and deliveries） with multi-time window, a method is proposed based on Sweep algorism and reactive tabu algorism. Firstly, the mathematical model for VRPPD problem with multi-time window is defined. Then the improved sweep algorism is used to get the initial solution, the candidate solution structure, fitness function, four neighborhood operations and the vehicle constraint and multi-window constraint are designed, the tabu table length is modified automatically by reactive tabu algorism. Finally, the algorism for solving VRPPD problem with multi-time window is defined. The experiment shows the method can solve the VRPPD problem with multi-time window effectively, and compared with the other methods it has the strong search ability and rapid convergence rate.

关 键 词：装卸车辆路线问题 适应度 容量约束 多时间窗 禁忌算法 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]