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

45 6 西 安 交 通 大 学 学 报 Vol45 No6 2011 6 JOURNAL OF XIAN JIAOT ONG UNIV RSIT Y Jun. 2011 , , ( , 710049, ) : 针对物流配送系统优化设计中关键难题之一的团队定向 题, 提出了一种部分顾客需求动 态到达的动态团队定向 题, 并建立了该 题的模型.采用把规划周期分成 一系列时间段的策略, 将动态 题转化成一系列的静态子 题求解. 提出了一种蚁群算法, 其特点是利用上一时间段的信 息来加速算法寻优能力, 并用 一种基于分支定价的离线精确性算法来求解动态团队定向 题. 实验 结果表明, 与基于分支定价的离线精确性算法相比, 所提出的蚁群算法能在 1 ks 内求解4 个测试 算例, 并且在2 个算例中得到的最好解优于离线精确性算法的解. : 动态团队定向 题; 蚁群算法; 分支定价 : TP3016 : A : 0253987X(2011) On the Model and Optimization Algorithm for Dynamic Team Orienteering Problem K Liangjun, SHANG Ke, F NG Zuren ( State Key Laboratory for Manufacturing Systems ngineering, Xian Jiaotong University, Xian 710049, China) Abstract: 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 subproblems by partitioning the planning ho rizon into a series of time segments. An ant colony optimization ( ACO) based algorithm is pro posed to solve the resulting problem. T he 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. xperimental results and comparisons with the exact offline algorithm based on the branch and bound show that the proposed ACObased algorithm can solve four test instances within 1 000 seconds, and that the solutions of two test instances obtained