多配送中心车辆路径安排问题混合蚁群算法  

A Hybrid Ant Colony Algorithm for Multiple Depot Vehicle Routing Problem

作　　者：戴树贵[1,2] 陈文兰 潘荫荣[1] 胡幼华[1] 

机构地区：[1]华东师范大学计算机科学技术系,上海200062 [2]滁州学院计算机科学与技术系,安徽滁州239000

出　　处：《四川大学学报（工程科学版）》2008年第6期154-158,共5页Journal of Sichuan University (Engineering Science Edition)

基　　金：安徽高校省级自然科学基金资助项目(2006KJ253B);安徽高校青年教师资助计划项目(2007jq1191)

摘　　要：经典蚁群算法不能直接用于求解多配送中心车辆路径安排问题(Multiple Depot Vehicle Routing Problem,MDVRP),为了解决这一问题,设计了蚂蚁转移策略和可行解构造方法。蚂蚁转移时,先为蚂蚁指定暂时配送中心,在转移过程中当遇到配送中心时,再确定永久配送中心。蚁群构造路径结束后,在满足车辆数和容量限制的条件下,随机选择优化后的若干只蚂蚁遍历路径,基于"节约最小"、"增加最小"和"就近插入"的原则,删除重复需求点并插入缺少的需求点,使之成为可行解。为了提高算法的性能,引入了K邻域规则限制蚂蚁的转移目标,使用2-Opt方法优化蚁群遍历路径和可行解,并设计了信息素更新方法。对标准测试数据集的测试表明,算法有效求解了MDVRP。To solve Multiple Depot Vehicle Routing Problem(MDVRP) directly,ant s transfer policy and method to construct valid solution were designed.When an ant began transfer,a temporary depot was prearranged to the ant,then the permanent depot was rooted when a depot was met with.After paths were constructed,several ants paths were selected randomly with the restriction of vehicles satisfied,and iterative depots were deleted and absent depots were inserted based on the regulars of "least decrease","least increase"...

关 键 词：多配送中心车辆路径安排问题 混合蚁群算法 2-Opt 可行解构造 

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