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

柯良军; 尚可; 冯祖仁

您当前的位置：

首页 >

文章列表页 >

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

更新时间：2025-07-09

- 动态团队定向问题的模型及其优化算法
- On the Model and Optimization Algorithm for Dynamic Team Orienteering Problem
- 西安交通大学学报 2011年45卷第6期页码：1-6+54
- 作者机构：
  
  西安交通大学机械制造与系统工程国家重点实验室,西安,710049
- 作者简介：
- 基金信息：
  
  : 2011-01-04. 作者简介: 柯良军(1976-),男,副教授. 基金项目: 国家自然科学基金资助项目(60905044);教育部博士点基金资助项目(20090201120042);国家重点基础研究发展规划资助项目(2007CB311000)
- DOI：
  中图分类号： TP301.6
- 网络首发：2011-06-10，
  
  纸质出版：2011
- 稿件说明：
移动端阅览
柯良军, 尚可, 冯祖仁. 动态团队定向问题的模型及其优化算法[J]. 西安交通大学学报, 2011,45(6):1-6+54.

On the Model and Optimization Algorithm for Dynamic Team Orienteering Problem[J]. 2011, 45(6): 1-6+54.
柯良军, 尚可, 冯祖仁. 动态团队定向问题的模型及其优化算法[J]. 西安交通大学学报, 2011,45(6):1-6+54. DOI：

On the Model and Optimization Algorithm for Dynamic Team Orienteering Problem[J]. 2011, 45(6): 1-6+54. DOI：

摘要

针对物流配送系统优化设计中关键难题之一的团队定向问题

提出了一种部分顾客需求动态到达的动态团队定向问题

并建立了该问题的模型.采用把规划周期分成一系列时间段的策略

将动态问题转化成一系列的静态子问题求解.提出了一种蚁群算法

其特点是利用上一时间段的信息来加速算法寻优能力

并用一种基于分支定价的离线精确性算法来求解动态团队定向问题.实验结果表明

与基于分支定价的离线精确性算法相比

所提出的蚁群算法能在1 ks内求解4个测试算例

并且在2个算例中得到的最好解优于离线精确性算法的解.

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 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.

关键词

Keywords

references

BUTT S E, CAVALIER T M. A heuristic for the multiple path maximum collection problem[J]. Computers and Operations Research, 1994, 21(1):101-111.

CHAO I M, GOLDEN B L, WASIL E A. The team orienteering problem[J]. European Journal of Operational Research, 1996, 88(3): 464-474.

BUTT S, RYAN D. An optimal solution procedure for the multiple path maximum collection problem using column generation[J]. Computer and Operations Research, 1999, 26(4):427-441.

BOUSSIER S, FEILLET D, GENDREAU M. An exact algorithm for team orienteering problems[J]. 4OR:A Quarterly Journal of Operations Research, 2007, 5(3): 211-230.

TANG Hao, MILLER-HOOKS E. A tabu search heuristic for the team orienteering problem[J]. Computers and Operations Research, 2005, 32(6):1379-1407.

ARCHETTI C, HERTZ A, SPERANZA M G. Metaheuristics for the team orienteering problem[J]. Journal of Heuristics, 2007, 13(1):49-76.

KE Liangjun, ARCHETTI C, FENG Zuren. Ants can solve the team orienteering problem[J]. Computers and Industrial Engineering, 2008, 54(3):648-665.

VANSTEENWEGEN P, SOURIAU W, OUDHEUSDEN D. The orienteering problem: a survey[J]. European Journal of Operational Research, 2011, 209(1):1-10.

CHEN Zhilong, XU Hang. Dynamic column generation for dynamic vehicle routing with time windows [J]. Transportation Science, 2006, 40(1):74-88.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

分散、递阶蚁群算法及其在相变序列图像分割中的应用

采用序优化的改进蚁群算法

混合电解槽阵列协同的风光耦合制氢系统双层多目标优化

超临界二氧化碳向心透平轮背间隙内风阻损失及流动特性研究

EBSILON软件在热电联产系统优化中的应用综述