一类求解带时间窗的团队定向问题的改进蚁群算法  

Improved Ant Colony Optimization Approach for the Team Orienteering Problem with Time Windows

作　　者：柯良军[1] 章鹤[1] 尚可[1] 冯祖仁[1] 

机构地区：[1]西安交通大学机械制造与系统工程国家重点实验室,西安710049

出　　处：《计算机科学》2012年第4期214-216,共3页Computer Science

基　　金：国家重点基础研究发展计划(2007CB311000);国家自然科学基金(60905044);教育部博士点基金(20090201120042);博士后特别基金(201003675)资助

摘　　要：带时间窗的团队定向问题是一类重要的物流配送路径优化问题,其优化目标是制定最优可行车辆路线,在规定的时间窗内服务一组顾客,以获得最大的总收益。提出了一类改进蚁群算法,用以求解该问题。为了提高解构造质量与效率,使用一种快速的方法来确定动态候选链表,并且利用串行法和贪婪法构造解。与迭代局部搜索相比,所提算法能够在12s内得到更好的解。Team orienteering problem with time windows is one of the most important logistic distribution routing optimization problems.The optimization objective of this problem is to plan the optimal feasible routes in which the total reward is maximized while a set of customers can be served in the given time windows.An improved ant colony optimization approach was developed to deal with this problem.In order to construct better and faster solutions,the proposed algorithm uses a fast method to determine dynamic candidate list.Moreover,it adopts the sequence method and the greedy method to construct solutions.Compared with iterated local search,the proposed algorithm can obtain better results within 12 seconds.

关 键 词：启发式算法 团队定向问题 蚁群优化 时间窗 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]