Abstract
The Team Orienteering Problem (TOP) is a variant of the vehicle routing problem. Given a set of vertices, each one associated with a score, the goal of TOP is to maximize the sum of the scores collected by a fixed number of vehicles within a certain prescribed time limit. More particularly, the Team Orienteering Problem with Time Windows (TOPTW) imposes the period of time of customer availability as a constraint to assimilate the real world situations. In this paper, we present a memetic algorithm for TOPTW based on the application of split strategy to evaluate an individual. The effectiveness of the proposed MA is shown by many experiments conducted on benchmark problem instances available in the literature. The computational results indicate that the proposed algorithm competes with the heuristic approaches present in the literature and improves best known solutions in \(101\) instances.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Archetti, C., Hertz, A., Speranza, M.G.: Metaheuristics for the team orienteering problem. J. Heuristics 13(1), 49–76 (2007)
Bouly, H., Dang, D.C., Moukrim, A.: A memetic algorithm for the team orienteering problem. 4OR 8(1), 49–70 (2010)
Chao, I.M., Golden, B., Wasil, E.A.: The team orienteering problem. Eur. J. Oper. Res. 88, 464–474 (1996)
Cordeau, J.F., Gendreau, M., Laporte, G.: A tabu search heuristic for periodic and multi-depot vehicle routing problems. Networks 30(2), 105–119 (1997)
Dang, D.-C., Guibadj, R.N., Moukrim, A.: A PSO-based memetic algorithm for the team orienteering problem. In: Di Chio, C., et al. (eds.) EvoApplications 2011, Part II. LNCS, vol. 6625, pp. 471–480. Springer, Heidelberg (2011)
Dang, D.C., Guibadj, R.N., Moukrim, A.: An effective pso-inspired algorithm for the team orienteering problem. Eur. J. Oper. Res. 229(2), 332–344 (2013)
Golden, B., Levy, L., Vohra, R.: The orienteering problem. Nav. Res. Logistics 34, 307–318 (1987)
Kantor, M.G., Rosenwein, M.B.: The orienteering problem with time windows. J. Oper. Res. Soc. 43(6), 629–635 (1992)
Labadie, N., Mansini, R., Melechovský, J., Calvo, R.W.: The team orienteering problem with time windows: An lp-based granular variable neighborhood search. Eur. J. Oper. Res. 220(1), 15–27 (2012)
Labadie, N., Melechovský, J., Calvo, R.W.: Hybridized evolutionary local search algorithm for the team orienteering problem with time windows. J. Heuristics 17(6), 729–753 (2011)
Lin, S.W., Yu, V.F.: A simulated annealing heuristic for the team orienteering problem with time windows. Eur. J. Oper. Res. 217(1), 94–107 (2012)
Montemanni, R., Gambardella, L.: Ant colony system for team orienteering problems with time windows. Found. Comput. Decis. Sci. 34(4), 287–306 (2009)
Moscato, P.: Memetic algorithms: a short introduction. In: New Ideas in Optimization, pp. 219–234. McGraw-Hill Ltd., Maidenhead (1999)
Potvin, J.Y., Kervahut, T., Garcia, B.L., Rousseau, J.M.: The vehicle routing problem with time windows part i: Tabu search. INFORMS J. Comput. 8(2), 158–164 (1996)
Prins, C.: A simple and effective evolutionary algorithm for the vehicle routing problem. Comput. Oper. Res. 31(12), 1985–2002 (2004)
Prins, C., Labadie, N., Reghioui, M.: Tour splitting algorithms for vehicle routing problems. Int. J. Prod. Res. 47(2), 507–535 (2009)
Righini, G., Salani, M.: Decremental state space relaxation strategies and initialization heuristics for solving the orienteering problem with time windows with dynamic programming. Comput. Oper. Res. 36(4), 1191–1203 (2009)
Sadykov, R., Vanderbeck, F.: Bin packing with conflicts: a generic branch-and-price algorithm (2012). (preprint accepted for publication in INFORMS Journal on Computing)
Solomon, M.M.: Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper. Res. 35(2), 254–265 (1987)
Souffriau, W., Vansteenwegen, P., Vanden Berghe, G., Van Oudheusden, D.: A path relinking approach for the team orienteering problem. Comput. Oper. Res. 37(11), 1853–1859 (2010)
Tang, H., Miller-Hooks, E.: A tabu search heuristic for the team orienteering problem. Comput. Oper. Res. 32, 1379–1407 (2005)
Tarjan, R.E.: Graph theory and gaussian elimination. Technical report, Stanford University (1975)
Tricoire, F., Romauch, M., Doerner, K.F., Hartl, R.F.: Heuristics for the multi-period orienteering problem with multiple time windows. Comput. Oper. Res. 37, 351–367 (2010)
Tsiligirides, T.: Heuristic methods applied to orienteering. J. Oper. Res. Soc. 35(9), 797–809 (1984)
Vansteenwegen, P., Souffriau, W., Van Oudheusden, D.: The orienteering problem: a survey. Eur. J. Oper. Res. 209(1), 1–10 (2011)
Vansteenwegen, P., Souffriau, W., Vanden Berghe, G., Van Oudheusden, D.: Iterated local search for the team orienteering problem with time windows. Comput. Oper. Res. 36(12), 3281–3290 (2009)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Guibadj, R.N., Moukrim, A. (2014). Memetic Algorithm with an Efficient Split Procedure for the Team Orienteering Problem with Time Windows. In: Legrand, P., Corsini, MM., Hao, JK., Monmarché, N., Lutton, E., Schoenauer, M. (eds) Artificial Evolution. EA 2013. Lecture Notes in Computer Science(), vol 8752. Springer, Cham. https://doi.org/10.1007/978-3-319-11683-9_15
Download citation
DOI: https://doi.org/10.1007/978-3-319-11683-9_15
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-11682-2
Online ISBN: 978-3-319-11683-9
eBook Packages: Computer ScienceComputer Science (R0)