Aişe Zülal ŞEVKLİ, Fatih Erdoğan SEVİLGEN

Discrete particle swarm optimization for the team orienteering problem

In this paper, a novel discrete particle swarm optimization (PSO) algorithm is proposed to solve the team orienteering problem (TOP). Discrete evaluation is achieved by redefining all operators and operands used in PSO. To obtain better results, a strengthened PSO, which improves both exploration and exploitation during the search process, is employed. Our algorithm achieves the best known solutions in a short time compared to previous heuristics for the TOP.

Anahtar Kelimeler:

Particle swarm optimization, reduced variable neighborhood search, team orienteering problem, vehicle routing problem with profits

Discrete particle swarm optimization for the team orienteering problem

Keywords:

Particle swarm optimization, reduced variable neighborhood search, team orienteering problem, vehicle routing problem with profits,

PDF

___

I. Chao, B. Golden, E. Wasil, “Theory and methodology – the team orienteering problem”, European Journal of Operations Research, Vol. 88, pp. 464-474, 1996.
S. Boussier, D. Feillet, M. Gendreau, “An exact algorithm for team orienteering problems”, 4OR, Vol. 5, pp. 211-230, S. Butt, D. Ryan, “An optimal solution procedure for the multiple tour maximum collection problem using column generation”, Computers & Operations Research, Vol. 26, pp. 427-441, 1999.
H. Bouly, D.C. Dang, A. Moukrim, “A memetic algorithm for the team orienteering problem”, Lecture Notes in Computer Science, Vol. 4974, pp. 649-658, 2008.
L. Ke, C. Archetti, Z. Feng, “Ants can solve the team orienteering problem”, Computers & Industrial Engineering, Vol. 54, pp. 648-665, 2008.
C. Archetti, A. Hertz, M.G. Speranza, “Metaheuristics for the team orienteering problem”, Journal of Heuristics, Vol. 13, pp. 49-76, 2007.
H. Tang, E. Miller Hooks, “A tabu search heuristic for the team orienteering problem”, Computers & Operations Research, Vol. 32, pp. 1379-1407, 2005.
P. Vansteenwegen, W. Souﬀriau, G.V. Berghe, D.V. Oudheusden, “A guided local search metaheuristic for the team orienteering problem”, European Journal of Operational Research, Vol. 196, pp. 118-127, 2009.
Z. Sevkli, E. Sevilgen, “StPSO: Strengthened particle swarm optimization”, Turkish Journal of Electrical Engineer- ing & Computer Sciences, Vol. 18, pp. 1095-1114, 2010.
R.C. Eberhard, J. Kennedy, “New optimizer using particle swarm theory”, Proceedings of the Sixth International Symposium on Micro Machine and Human Science, Nagoya, Japan, pp. 39-43, 1995.
K. Rameshkumar, R.K. Suresh, K.M. Mohanasundaram, “Discrete particle swarm optimization (DPSO) algorithm for permutation ﬂowshop scheduling to minimize makespan”, ICNC, Vol. 3, pp. 572-581, 2005.
C.J. Liao, C.T. Tseng, P. Luarn, “A discrete version of particle swarm optimization for ﬂowshop scheduling problems”, Computers & Operations Research, Vol. 34, pp. 3099-3111, 2007.
M.F. Tasgetiren, Y.C. Liang, M. Sevkli, G. Gencyilmaz, “Particle swarm optimization algorithm for makespan and total ﬂowtime minimization in permutation ﬂowshop sequencing problem”, European Journal of Operational Research, Vol. 177, pp. 1930-1947, 2007.
N. Mladenovic, P. Hansen, “Variable neighborhood search”, Computers & Operations Research, Vol. 24, pp. 1097- , 1997.