Email this article 
Open Access
Subscription or Fee Access
Solving the Capacitated Team Orienteering Problem with Time Windows Through Variable Neighborhood Search
(*) Corresponding author
DOI: https://doi.org/10.15866/irecos.v10i11.7919
Abstract
This paper presents a variable neighborhood search algorithm for the capacitated team orienteering problem with time windows (CTOPTW). In CTOPTW, a set of customers is given; each customer has a demand, a profit, a service time and a time window. The objective is to design a set of vehicle routes that maximizes the total collected profit, while satisfying the time windows, the vehicle capacity and the maximum duration constraints for each route. To deal with the CTOPTW, a variable neighborhood search algorithm is developed. This algorithm uses three neighborhood structures to explore the solution space. Our computational results show that the developed heuristic algorithm is competitive comparing to existing heuristic algorithms in the literature. New best solutions on large test instances were achieved.
Copyright © 2015 Praise Worthy Prize - All rights reserved.
Keywords
References
Liu, S., Zhou, J., Lei, J., A kind of new algorithm to solve the multi-objective traveling salesman, (2013) International Review on Computers and Software (IRECOS), 8 (1), pp. 267-270.
Vangeri, A., Hebbal, S.S., Route optimization of automated warehouse with the aid of modified genetic algorithms (MGA), (2014) International Review of Mechanical Engineering (IREME), 8 (4), pp. 667-679.
Sayoti, F., Riffi, M.E., Random-keys golden ball algorithm for solving traveling salesman problem, (2015) International Review on Modelling and Simulations (IREMOS), 8 (1), pp. 84-89.
http://dx.doi.org/10.15866/iremos.v8i1.5302
S. Boussier, D. Feillet, M. Gendreau, An Exact Algorithm for the Team Orienteering Problems, 4OR, Vol. 5, n. 3, pp. 211-230, 2007.
http://dx.doi.org/10.1007/s10288-006-0009-1
M. Keshtkaran, K. Ziarati, A. Bettinelli, D. Vigo, Enhanced exact solution methods for the team orienteering problem, International Journal of Production Research, 2015.
http://dx.doi.org/10.1080/00207543.2015.1058982
C. Archetti, A. Hertz, M.G. Speranza, Metaheuristics for the Team Orienteering Problem, Journal of Heuristics, Vol. 13, n. 1, pp. 49-76, 2007.
http://dx.doi.org/10.1007/s10732-006-9004-0
P. Vansteenwegen, W. Souffriau, G.V. Berghe, D.V. Oudheusden, A Guided Local Search Metaheuristic for the Team Orienteering Problem, European Journal of Operational Research, Vol. 196, n. 1, pp. 118-127, 2009.
http://dx.doi.org/10.1016/j.ejor.2008.02.037
S.-W. Lin, Solving the Team Orienteering Problem using Effective Multi-Start Simulated Annealing, Applied Soft Computing, Vol. 13, n. 2, pp. 1064-1073, 2013.
http://dx.doi.org/10.1016/j.asoc.2012.09.022
C. Archetti, D. Feillet, A. Hertz, M.G. Speranza, The Capacitated Team Orienteering Problem and Profitable Tour Problem, Journal of the Operational Research Society, Vol. 60, pp. 831-842, 2009.
http://dx.doi.org/10.1057/palgrave.jors.2602603
C.D. Tarantilis, F. Stavropoulou, P.P. Repoussis, The Capacitated Team Orienteering Problem: A Bi-level Filter-and-Fan Method, European Journal of Operational Research, Vol. 224, n. 1, pp. 65-78, 2013.
http://dx.doi.org/10.1016/j.ejor.2012.07.032
Z. Luo, B. Cheang, A. Lim, W. Zhu, An Adaptive Ejection Pool with Toggle-Rule Diversification approach for the Capacitated Team Orienteering Problem, European Journal of Operational Research, Vol. 229, n. 3, pp. 673-682, 2013.
http://dx.doi.org/10.1016/j.ejor.2012.12.020
G. Righini, M. Salani, Decremental Sate Space Relaxation Strategies and Initialization Heuristics for Solving the Orienteering Problem with Time Windows with Dynamic Programming, Computers and Operations Research, Vol. 36, n. 4, pp. 1191-1203, 2009.
http://dx.doi.org/10.1016/j.cor.2008.01.003
J. Karbowska-Chilinska, P. Zabielski, Genetic Algorithm with Path Relinking for the Orienteering Problem with Time Windows, Fundamenta Informaticae - Concurrency Specification and Programming 2013 (CS&P’13), Vol. 135, n. 4, pp. 419-431, 2014.
R. Montemanni, L.M. Gambardella, An Ant Colony System for Team Orienteering Problem with Time Windows, Foundations of Computing and Decision Sciences, Vol. 34, n. 4, pp. 287-306, 2009.
http://dx.doi.org/10.1109/isccs.2011.95
P. Vansteenwegen, W. Souffriau, G.V. Berghe, D.V. Oudheusden, Iterated Local Search for the Team Orienteering Problem with Time Windows, Computers and Operations Research, Vol. 36, n. 12, pp. 3281-3290, 2009.
http://dx.doi.org/10.1016/j.cor.2009.03.008
N. Labadie, R. Mansini, J. Melechovský, R.W. Calvo, The Team Orienteering Problem with Time Windows: An LP-based Granular Variable Neighborhood Search, European Journal of Operational Research, Vol. 220, n. 1, pp. 15-27, 2012.
http://dx.doi.org/10.1016/j.ejor.2012.01.030
S.-W. Lin V.F. Yu, A Simulated Annealing Heuristic for the Team Orienteering Problem with Time Windows, European Journal of Operational Research, Vol. 217, n. 1, pp. 94-107, 2012.
http://dx.doi.org/10.1016/j.ejor.2011.08.024
C. Tunchan, An Artificial Bee Colony Algorithm Approach for the Team Orienteering Problem with Time Windows, Computers and Industrial Engineering, Vol. 74, pp. 270-290, 2014.
http://dx.doi.org/10.1016/j.cie.2014.06.004
Q. Hu, A. Lim, An Iterative Three-Component Algorithm for the Team Orienteering Problem with Time Windows, European Journal of Operational Research, Vol. 232, n. 2, pp. 276-286, 2014.
http://dx.doi.org/10.1016/j.ejor.2013.06.011
A. Garcia, P. Vansteenwegen, W. Souffriau, O. Arbelaitz, M.T. Linaza, Solving Multi-Constrained Team Orienteering Problems to generate tourist routes, 2009.
W. Souffriau, P. Vansteenwegen, G.V. Berghe, D.V. Oudheusden, The Multi-Constraint Team Orienteering Problem with Multiple Time Windows, Transportation Science, Vol. 47, n. 1, pp. 53-63, 2013.
http://dx.doi.org/10.1287/trsc.1110.0377
D. Gavalas, C. Konstantopoulos, K. Mastakas, G. Pantziou, A Survey on Algorithmic Approaches for Solving Tourist Trip Design Problems, Journal of Heuristics, Vol. 20, n. 3, pp. 291-328, 2014.
http://dx.doi.org/10.1007/s10732-014-9242-5
Aghezzaf, B., El Fahim, H., The Multi-Constraint Team Orienteering Problem with Time Windows in the Context of Distribution Problems: a Variable Neighbourhood Search Algorithm, Proceedings of the IEEE International Conference on Logistics and Operations Management (GOL) (Pages: 155-160 Year of Publication: 2014 ISBN: 978-1-4799-4651-8).
http://dx.doi.org/10.1109/gol.2014.6887433
Y. Marinakis, Multiple Phase Neighborhood Search-GRASP for the Capacitated Vehicle Routing Problem, Expert Systems with Applications, Vol. 39, n. 8, pp. 6807-6815, 2012.
http://dx.doi.org/10.1016/j.eswa.2012.01.015
Y. Xiao, Q. Zhao, I. Kaku, N. Mladenovic, Variable Neighborhood Simulated Annealing for Capacitated Vehicle Routing Problems, Engineering Optimization, Vol. 46, n. 4, pp. 562-579, 2014.
http://dx.doi.org/10.1080/0305215x.2013.791813
J. Jin, T.G. Crainic, A. Løkketangen, A Cooperative Parallel Metaheuristic for the Capacitated Vehicle Routing Problem, Computers & Operations Research, Vol. 44, pp. 33-41, 2014.
http://dx.doi.org/10.1016/j.cor.2013.10.004
W.Y. Szeto, Y. Wu, S.C. Ho, An Artificial Bee Colony Algorithm for the Capacitated Vehicle Routing Problem, European Journal of Operational Research, Vol. 215, n. 1, pp. 126-135, 2011.
http://dx.doi.org/10.1016/j.ejor.2011.06.006
Taha, A., Hachimi, M., Moudden, A., Adapted bat algorithm for capacitated vehicle routing problem, (2015) International Review on Computers and Software (IRECOS), 10 (6), pp. 610-619.
http://dx.doi.org/10.15866/irecos.v10i6.6512
E. Teymourian, V. Kayvanfar, GH.M. Komaki, M. Zandieh, Enhanced Intelligent Water Drops and Cuckoo Search Algorithms for Solving the Capacitated Vehicle Routing Problem, Information Sciences, 2015.
http://dx.doi.org/10.1016/j.ins.2015.11.036
B. Yu, Z. Hang, B. Yao, A Hybrid Algorithm for Vehicle Routing Problem with Time Windows, Expert Systems with Applications, Vol. 38, n. 1, pp. 435-441, 2011.
http://dx.doi.org/10.1016/j.eswa.2010.06.082
Wang, Y., Research on the vehicle routing problem with time windows by cellular ant algorithm, (2013) International Review on Computers and Software (IRECOS), 8 (1), pp. 390-395.
L. Tan, F. Lin, H. Wang, Adaptive Comprehensive Learning Bacterial Foraging Optimization and its Application on Vehicle Routing Problem with Time Windows, Neurocomputing, Vol. 151, n. 3, pp. 1208-1215, 2015.
http://dx.doi.org/10.1016/j.neucom.2014.03.082
J. Luo, X. Li, Ming-ron Chen, A Novel Hybrid Shuffled frog Leaping Algorithm for Vehicle Routing Problem with Time Windows, Information Sciences, Vol. 316, pp. 266-292, 2015.
http://dx.doi.org/10.1016/j.ins.2015.04.001
E.T. Yassen, M. Ayob, M.Z. Ahmed Nazari, N.R. Sabar, Meta-Harmony Search Algorithm for the Vehicle Routing Problem with Time Windows, Information Sciences, Vol. 325, pp. 140-158, 2015.
http://dx.doi.org/10.1016/j.ins.2015.07.009
N. Azi, M. Gendreau, J-Y. Potvin, An Exact Algorithm for a Vehicle Routing Problem with Time Windows and Multiple Use of Vehicles, European Journal of Operational Research, Vol. 202, n. 3, pp. 756-763, 2010.
http://dx.doi.org/10.1016/j.ejor.2009.06.034
R. Macedo, C. Alves, J.M.V. Carvalho, F. Clautiaux, S. Hanafi, Solving the Vehicle Routing Problem with Time Windows and Multiple Routes Exactly Using a Pseudo-Polynomial Model, European Journal of Operational Research, Vol. 214, n. 3, pp. 536-545, 2011.
http://dx.doi.org/10.1016/j.ejor.2011.04.037
F. Hernandez, D. Feillet, R. Giroudeau, O. Naud, A New Exact Algorithm to Solve the Multi-Trip Vehicle Routing Problem with Time Windows and Limited Duration, 4OR, Vol. 12, n. 3, PP. 235-259, 2014.
http://dx.doi.org/10.1007/s10288-013-0238-z
F. Hernandez, D. Feillet, R. Giroudeau, O. Naud, Branch-and-Price Algorithms for the Solution of the Multi-Trip Vehicle Routing Problem with Time Windows, European Journal of Operational Research, Vol. 249, n. 2, pp. 551-559, 2015.
http://dx.doi.org/10.1016/j.ejor.2015.08.040
J.-F. Cordeau, M. Gendreau, G. Laporte, A Tabu Search Heuristic for Periodic and Multi-Depot Vehicle Routing Problems, Networks, Vol. 30, n. 2, pp. 105-119, 1997.
http://dx.doi.org/10.1002/(sici)1097-0037(199709)30:2%3C105::aid-net5%3E3.0.co;2-g
Refbacks
- There are currently no refbacks.
Please send any question about this web site to info@praiseworthyprize.com
Copyright © 2005-2024 Praise Worthy Prize
