Discrete particle swarm optimization for the team orienteering problem

被引：27

作者：

Muthuswamy S. ^{[1
]}

Lam S.S. ^{[2
]}

机构：

[1] Department of Technology, Northern Illinois University, De Kalb

[2] Systems Science and Industrial Engineering Department, State University of New York, Binghamton

来源：

Memetic Computing | 2011年 / 3卷 / 4期

关键词：

Discrete particle swarm optimization; Meta-heuristics; Reduced variable neighborhood search; Team orienteering problem;

D O I：

10.1007/s12293-011-0071-x

中图分类号：

学科分类号：

摘要：

Orienteering problem is a well researched routing problem which is a generalization of the traveling salesman problem. Team orienteering problem (TOP) is the extended version of the orienteering problem with more than one member in the team. In this paper the first known discrete particle swarm optimization (DPSO) algorithm has been developed for 2, 3 and 4-member TOP. In the DPSO meta-heuristic novel methods have been introduced for the initial particle generation process. Reduced variable neighborhood search and 2-opt were applied as the local search tools. The efficacy of the algorithm was tested using seven commonly used benchmark problem sets ranging in size from 21 to 102 nodes. The results of the DPSO algorithm were compared against seven other heuristic algorithms that have been developed for TOP. It was concluded that the developed DPSO algorithm for the TOP is competitive and robust across the benchmark problem sets. © 2011 Springer-Verlag.

引用

页码：287 / 303

页数：16

共 32 条

[1]

Anghinolfi D., Paolucci M., A new discrete particle swarm optimization approach for the single-machine total weighted tardiness scheduling problem with sequence-dependent setup times, Eur J Oper Res, 193, 1, pp. 73-85, (2009)

[2]

Archetti C., Hertz A., Speranza M.G., Metaheuristics for the team orienteering problem, J Heuristics, 13, pp. 49-76, (2007)

[3]

Bouly H., Dang D., Moukrim A., A memetic algorithm for the team orienteering problem, 4OR, 8, 1, pp. 49-70, (2010)

[4]

Boussier S., Feillet D., Gendreau M., An exact algorithm for team orienteering problems, 4OR, 5, pp. 211-230, (2007)

[5]

Butt S.E., Cavalier T.M., A heuristic for the multiple tour maximum collection problem, Comput Oper Res, 21, 1, pp. 101-111, (1994)

[6]

Butt S., Ryan D., An optimal solution procedure for the multiple path maximum collection problem using column generation, Comput Oper Res, 26, pp. 427-441, (1999)

[7]

Chao I.M., Golden B.L., Wasil E.A., The team orienteering problem, Eur J Oper Res, 88, pp. 464-474, (1996)

[8]

Dallard H., Lam S., Kulturel-Konak S., A particle swarm optimization approach to the orienteering problem, Proc Ind Eng Res Conf Orlando, FL, (2006)

[9]

Dallard H., Lam S., Kulturel-Konak S., Solving the orienteering problem using attractive and repulsive particle swarm optimization, Int Conf Inf Reuse Integration Las Vegas, NV, (2007)

[10]

Golden B.L., Levy L., Vohra R., The orienteering problem, Navig Res Log, 34, pp. 307-318, (1987)

← 1 2 3 4 →