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

经典蚁群算法不能直接用于求解多配送中心车辆路径安排问题(Multiple Depot Vehicle Routing Problem,MDVRP),为了解决这一问题,设计了蚂蚁转移策略和可行解构造方法.蚂蚁转移时,先为蚂蚁指定暂时配送中心,在转移过程中当遇到配送中心时,再确定永久配送中心.蚁群构造路径结束后,在满足车辆数和容量限制的条件下,随机选择优化后的若干只蚂蚁遍历路径,基于"节约最小"、"增加最小"和"就近插入"的原则,删除重复需求点并插入缺少的需求点,使之成为可行解.为了提高算法的性能,引入了K邻域规则限制蚂蚁的转移目标,使用2-Opt方法优化蚁群遍历路径和可行解,并设计了信息素更新方法.对标准测试数据集的测试表明,算法有效求解了MDVRP.

A Hybrid Ant Colony Algorithm for Multiple Depot Vehicle Routing Problem

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" and "nearest insertion".Thus a solution of MDVRP was constructed.In order to improved algorithm's performance,K-neighbor was used to confine ants' transfer objects,and ants' paths and solutions were optimized by 2-Opt,and pheromone update policy was designed.The algorithm was tested on two standard data sets,and the results showed that the algorithm is an efficient one to solve MDVRP.