×

zbMATH — the first resource for mathematics

A memetic algorithm for the orienteering problem with mandatory visits and exclusionary constraints. (English) Zbl 1403.90144
Summary: The orienteering problem with mandatory visits and exclusionary constraints (OPMVEC) is to visit a set of mandatory nodes (locations) and some optional nodes, while respecting the compatibility constraint between nodes and the maximum total time budget constraint. It is a variation of the classic orienteering problem that originates from a number of real-life applications. We present a highly effective memetic algorithm (MA) for OPMVEC combining: (i) a dedicated tabu search procedure that considers both feasible and infeasible solutions by constraint relaxation, (ii) a backbone-based crossover, and (iii) a randomized mutation procedure to prevent from premature convergence. Experiments on six classes of 340 benchmark instances from the literature demonstrate highly competitive performance of MA – it reports improved results for 104 instances compared with the existing heuristic approach, while finding matching best-known results for the remaining cases. Additionally, MA can be used to produce a starting point for an exact solver (e.g., CPLEX), leading to an increased number of problem instances that are solved to optimality. We further investigate the contribution of the key algorithmic elements to the success of the proposed approach.
MSC:
90B06 Transportation, logistics and supply chain management
90C35 Programming involving graphs or networks
90C59 Approximation methods and heuristics in mathematical programming
Software:
CPLEX; irace; SPOT
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Arkin, E. M.; Mitchell, J. S.B.; Narasimhan, G., Resource-constrained geometric network optimization, Proceedings of the fourteenth symposium on computational geometry, 307-316, (1998), ACM
[2] Birattari, M.; Yuan, Z.; Balaprakash, P.; Stützle, T., F-race and iterated F-race: an overview, Experimental methods for the analysis of optimization algorithms, 311-336, (2010), Springer Berlin Heidelberg · Zbl 1204.68280
[3] Castro, M.; Sörensen, K.; Vansteenwegen, P.; Goos, P., A memetic algorithm for the travelling salesperson problem with hotel selection, Computers & Operations Research, 40, 7, 1716-1728, (2013) · Zbl 1348.90438
[4] Chen, Y.; Hao, J. K.; Glover, F., A hybrid metaheuristic approach for the capacitated arc routing problem, European Journal of Operational Research, 253, 1, 25-39, (2016) · Zbl 1346.90087
[5] Fischetti, M.; Gonzalez, J. J.S.; Toth, P., Solving the orienteering problem through branch-and-cut, Informs Journal on Computing, 10, 2, 133-148, (1998) · Zbl 1034.90523
[6] Gendreau, M.; Hertz, A.; Laporte, G., A tabu search heuristic for the vehicle routing problem, Management Science, 40, 10, 1276-1290, (1994) · Zbl 0822.90053
[7] Gendreau, M.; Laporte, G.; Semet, F., A branch-and-cut algorithm for the undirected selective traveling salesman problem, Networks, 32, 4, 263-273, (1998) · Zbl 1002.90044
[8] Golden, B. L.; Levy, L.; Vohra, R., The orienteering problem, Naval Research Logistics, 34, 3, 307-318, (1987) · Zbl 0647.90099
[9] Hao, J. K., Memetic algorithms in discrete optimization, In handbook of memetic algorithms, 73-94, (2012), Springer Berlin Heidelberg
[10] Kataoka, S.; Morito, S., An algorithm for single constraint maximum collection problem, Journal of the Operations Research Society of Japan, 31, 4, 515-531, (1988) · Zbl 0665.90092
[11] Laporte, G.; Martello, S., The selective travelling salesman problem, Discrete Applied Mathematics, 26, 2, 193-207, (1990) · Zbl 0695.90098
[12] López-Ibánez, M., Dubois-Lacoste, J., Stützle, T., & Birattari, M. (2011). The irace package, iterated race for automatic algorithm configuration. Technical report tr/iridia/2011-004, Belgium, IRIDIA, Université Libre de Bruxelles.
[13] Manerba, D.; Mansini, R., A branch-and-cut algorithm for the multi-vehicle traveling purchaser problem with pairwise incompatibility constraints, Networks, 65, 2, 139-154, (2015)
[14] Manerba, D.; Mansini, R., The nurse routing problem with workload constraints and incompatible services, IFAC-PapersOnLine, 49, 12, 1192-1197, (2016)
[15] Martí, R.; Duarte, A.; Laguna, M., Advanced scatter search for the MAX-cut problem, Informs Journal on Computing, 21, 1, 26-38, (2009) · Zbl 1243.90227
[16] Mei, Y.; Salim, F. D.; Li, X., Efficient meta-heuristics for the multi-objective time-dependent orienteering problem, European Journal of Operational Research, 254, 2, 443-457, (2016) · Zbl 1346.90745
[17] Minh, T. T.; Hoai, T. V.; Nguyet, T. T.N., A memetic algorithm for waste collection vehicle routing problem with time windows and conflicts, Proceedings of the International conference on computational science and its applications - ICCSA 2013, (2013), Springer Berlin Heidelberg
[18] Minh, T. T.; Hoai, T. V.; Nguyet, T. T.N., A memetic algorithm for waste collection vehicle routing problem with time windows and conflicts, Computational science and its applications - ICCSA 2013, (2013), Springer Berlin Heidelberg
[19] Moscato, P., Memetic algorithms: A short introduction, In new ideas in optimization, 219-234, (1999), McGraw-Hill Ltd. UK
[20] Neri, F.; Cotta, C.; Eiben, A. E.; Smith, J. E.; Oca, M. A.M. D.; Cotta, C., Handbook of memetic algorithms, (2012), Springer Berlin Heidelberg
[21] Palomo-Martínez, P. J.; Salazar-Aguilar, M. A.; Albornoz, V. M., Formulations for the orienteering problem with additional constraints, Annals of Operations Research, 78, 1-43, (2017) · Zbl 1381.90020
[22] Palomo-Martínez, P. J.; Salazar-Aguilar, M. A.; Laporte, G.; Langevin, A., A hybrid variable neighborhood search for the orienteering problem with mandatory visits and exclusionary constraints, Computers & Operations Research, 78, 408-419, (2017) · Zbl 1391.90528
[23] Salazar-Aguilar, M. A.; Langevin, A.; Laporte, G., The multi-district team orienteering problem, Computers & Operations Research, 41, 1, 76-82, (2014) · Zbl 1348.90061
[24] Tricoire, F.; Romauch, M.; Doerner, K. F.; Hartl, R. F., Heuristics for the multi-period orienteering problem with multiple time windows, Computers & Operations Research, 37, 2, 351-367, (2010) · Zbl 1175.90212
[25] Tsiligirides, T., Heuristic methods applied to orienteering, Journal of the Operational Research Society, 35, 9, 797-809, (1984)
[26] Vansteenwegen, P.; Souffriau, W.; Berghe, G. V.; Oudheusden, D. V., The city trip planner: an expert system for tourists, Expert Systems with Applications, 38, 6, 6540-6546, (2011)
[27] Wu, Q.; Hao, J. K., A hybrid metaheuristic method for the maximum diversity problem, European Journal of Operational Research, 231, 2, 452-464, (2013) · Zbl 1317.90338
[28] Zhou, Y.; Hao, J. K.; Duval, B., Opposition-based memetic search for the maximum diversity problem, IEEE Transactions on Evolutionary Computation, 21, 5, 731-745, (2017)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.