多车场车辆路径问题的新型聚类蚁群算法

Study on A Novel Clustering Ant Colony Algorithms for Multi-depots Vehicle Routing Problem

在对多车场带时间窗的车辆路径问题进行详细阐述的基础上,以车辆运输总费用最少为目标函数,建立了问题的数学模型。提出了先采用聚类蚁群算法将多车场带时间窗的车辆路径问题分解为若干个单车场车辆路径问题,然后对各单车场问题应用改进蚁群算法进行优化的求解思路。最后通过一个实例将这种新型聚类蚁群算法与就近分配禁忌搜索算法和K-均值算法的优化能力进行了对比。试验结果表明,该算法对优化多车场带时间窗的车辆路径问题的求解结果是相当令人满意的。

It takes the vehicles transport time costs as the target function on the basis of expounding detail to the multi - depots vehicle routing problem with time windows, builds the mathematic model of the problem. It divides a multi-depots vehicle routing problem with time windows（MDVRTW） into several single-depot vehicle routing problem by using the novel clustering ant colony algorithms （NCACA） first, then＇ applies the improved ant colony algorithms to optimize the single - depot vehicle routing. At last, it presents a case study which contrasts the novel clustering ant colony algorithms （NCACA） to nearest assigning tabu - search algorithms and k - means algorithms in the optimizing ability. The experiment results show that the method in the above- mentioned is very satisfactory.