动态团队定向问题的模型及其优化算法  

On the Model and Optimization Algorithm for Dynamic Team Orienteering Problem

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

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

出　　处：《西安交通大学学报》2011年第6期1-6,54,共7页Journal of Xi'an Jiaotong University

基　　金：国家自然科学基金资助项目(60905044);教育部博士点基金资助项目(20090201120042);国家重点基础研究发展规划资助项目(2007CB311000)

摘　　要：针对物流配送系统优化设计中关键难题之一的团队定向问题,提出了一种部分顾客需求动态到达的动态团队定向问题,并建立了该问题的模型.采用把规划周期分成一系列时间段的策略,将动态问题转化成一系列的静态子问题求解.提出了一种蚁群算法,其特点是利用上一时间段的信息来加速算法寻优能力,并用一种基于分支定价的离线精确性算法来求解动态团队定向问题.实验结果表明,与基于分支定价的离线精确性算法相比,所提出的蚁群算法能在1 ks内求解4个测试算例,并且在2个算例中得到的最好解优于离线精确性算法的解.A dynamic team orienteering problem of partial dynamic arrival customers is studied, and a model of the problem is established to deal with the team orienteering problem, which is one of the most critical problems in the optimization design for logistic distribution system. The dynamic problem is converted into a series of static sub-problems by partitioning the planning horizon into a series of time segments. An ant colony optimization （ACO） based algorithm is proposed to solve the resulting problem. The prominent characteristic of the algorithm is to use the information obtained from the last time segment to enhance the search behavior. An exact offline algorithm based on branch and price is also presented to solve the problem. Experimental results and comparisons with the exact offline algorithm based on the branch and bound show that the proposed ACO-based algorithm can solve four test instances within 1 000 seconds, and that the solutions of two test instances obtained by the proposed ACO-based algorithm are better than those obtained by the exact offline algorithm.

关 键 词：动态团队定向问题 蚁群算法 分支定价 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]