On the Model and Optimization Algorithm for Dynamic Team Orienteering Problem

您当前的位置：

首页 >

文章列表页 >

On the Model and Optimization Algorithm for Dynamic Team Orienteering Problem

更新时间：2025-07-09

- On the Model and Optimization Algorithm for Dynamic Team Orienteering Problem
- Vol. 45, Issue 6, Pages: 1-6+54(2011)
- 作者机构：
  
  西安交通大学机械制造与系统工程国家重点实验室,西安,710049
- 作者简介：
- 基金信息：
- DOI：
  CLC： TP301.6
- Online First：10 June 2011，
  
  Published：2011
- 稿件说明：
移动端阅览
On the Model and Optimization Algorithm for Dynamic Team Orienteering Problem[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.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Decentralized and Hierarchical Ant Colony Optimization and Its Application to Phase Change Image Sequences Segmentation

Novel Ant Colony Optimization Algorithm Based on Order Optimization

Numerical Simulation of the Energy Conversion Process in Thermoacoustic Engines with Different Stack Materials

Windage Loss and Flow Characteristics in Impeller Back Gaps of sCO2 Radial Inflow Turbines

Knowledge Graph Representation Learning Driven by Semantic Discrimination and Subgraph Integration

Related Author

冯祖仁 1

李进 1

冯远静 4

张兆军 1

冯祖仁 1

Related Institution

西安交通大学系统工程研究所

西安交通大学机械制造系统工程国家重点实验室

Systems Engineering Institute, Xi'an Jiaotong University

State Key Laboratory for Manufacturing Systems Engineering, Xi'an Jiaotong University

⁰