摘要：本文考虑以完成时间最小为目标的车辆路径问题的蚁群算法，首先给出以完成时间最小为目标的车辆路径问题，然后通过求解有向图的弧-最短路给出求解给定客户排列的最优分割的方法，从而把该问题转化为寻找最优客户排列的问题，然后给出求解该问题的蚁群算法，最后给出求解算例。
关键词：车辆路径问题，蚁群算法，弧-最短路问题，完成时间
引言
车辆路径问题在交通和物流配送领域有着非常重要的应用，因而是人们研究的热点问题，并已经取得了很多研究成果[1]。车辆路径问题是个NP-hard问题[2]，因而人们主要考虑求解该问题的启发式算法或进化算法，禁忌搜索算法、遗传算法、模拟退火算法和蚁群算法都被用来求解该问题，[3]给出了有关工作的综述。
蚁群算法是由Colorni和Dorigo等人提出的一类模拟蚁群行为的模拟进化算法[4]，其是解决许多组合优化问题的有效算法。同样蚁群算法也被用来求解车辆路径问题[5]，一般的蚁群算法在求解车辆路径问题上不如禁忌搜索算法结果好，[6]给出蚁群算法的两种有效改进方法，提高了蚁群算法在求解车辆路径问题上的计算效果。
车辆路径问题根据其问题不同可以分成很多类型，人们研究比较多的有能力约束的车辆路径问题（CVRP）、带时间窗口的车辆路径问题(VRPTW)、多发点的车辆路径问题(MDVRP)、动态车辆路径问题(DVRP)等。文[7]研究了关于以平衡车辆使用时间为目标的车辆路径问题（记为BTVRP），并且提出一个有效的启发式算法。该类问题与其他车辆路径问题不同之处在于其追求的目标是在现有车辆能力下，以车辆使用时间的差最小。当车辆使用时间的差达到最小时，各个车辆的使用时间也可能都很大。而实践中由许多问题要求以最快的时间满足需求，诸如快餐外卖、特快专递、应急物资发放等情况，此时缩短完成服务时间的重要性远大于减少服务费用或车辆运行时间的差距的重要性。由于每个客户的完成服务时间不同，只有当最后一个客户得到服务时整个任务才算完成，因而本文考虑利用蚁群算法求解只有一个发货点、以完成时间最短为目标的车辆路径问题。
本文给出以完成时间最短为目标的车辆路径问题的蚁群算法，首先第2节给出完成时间最短的车辆路径问题，然后第3节给出给定客户排列的最优车辆分割方法，第4节给出求解该问题的蚁群算法，最后第5节给出计算实例。