多车场多车型最快完成车辆路径问题的变异蚁群算法  

Mutation ant colony algorithm for multiple-depot multiple-types vehicle routing problems with shortest finish time

作　　者：马建华[1] 房勇[2] 袁杰[1] 

机构地区：[1]山东财经大学信息管理学院,济南250014 [2]中国科学院数学与系统科学研究院,北京100190

出　　处：《系统工程理论与实践》2011年第8期1508-1516,共9页Systems Engineering-Theory & Practice

基　　金：国家自然科学基金(70601027);山东省高校人文社会科学研究计划(J09WJ07-1)

摘　　要：一般车辆路径问题的目标是总路程或总费用最小,而在应急管理或特殊配送中要求以最快的速度完成配送任务,该文研究了以最快完成为目标的多车场多车型车辆路径问题的变异蚁群算法.首先介绍了多车场多车型最快完成车辆路径问题,然后分别给出求解多车型和单车型问题的车辆分割的动态规划方法,并把单车型问题的动态规划方法和改进的Split方法进行对比,同时利用改进的最大流算法将车辆分配给各车场,从而把该问题转化为寻找最优顾客排列的问题.随后给出了求解该问题的变异蚁群算法,最后给出了计算实例.The objective of the tradition vehicle routing problems is to minimize the total distance or total cost.But in the emergency management or special distribution,the objective is to shorten the finish time. In this paper mutation ant colony algorithm for multiple-depot multiple-types vehicle routing problems with shortest finish time（FTMDMTVRP） is studied.First,FTMDMTVRP is introduced,then divided given customer array to vehicles by using the dynamic programming method for multiple-types problem and single vehicle type problem,and compared dynamic programming method with Split algorithm.And improved max flows algorithm to allocate vehicles to depots is given.So this problem is translated into finding the optimal customer array,next mutation ant colony algorithm for FTMDVRP is given to search the optimal customer array.At last,a computational instance is given.

关 键 词：车辆路径问题 动态规划 Split算法 变异蚁群算法 

分 类 号：F253[经济管理—国民经济]