×

zbMATH — the first resource for mathematics

Hybrid evolutionary search for the traveling repairman problem with profits. (English) Zbl 1453.90179
Summary: The Traveling Repairman Problem with Profits is a node routing problem, where a repairman visits a subset of nodes of a weighted graph in order to maximize the collected time-dependent profits. In this work, we present the first population-based hybrid evolutionary search algorithm for solving the problem that combines: (i) a randomized greedy construction method for initial solution generation, (ii) a dedicated variable neighborhood search for local optimization, (iii) two crossover operators for solution recombination with an adaptive rule for crossover selection. Computational results on six sets of 120 benchmark instances from the literature demonstrate that the proposed algorithm achieves a high performance – it improves the best-known results (new lower bounds) for 39 instances, while matching the best-known results for the remaining cases. We investigate several main algorithmic ingredients to understand their impacts on the performance of the algorithm.
MSC:
90C35 Programming involving graphs or networks
90C59 Approximation methods and heuristics in mathematical programming
Software:
CBMix; irace; SPOT
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Avci, M.; Avci, M. G., A GRASP with iterated local search for the traveling repairman problem with profits, Comput. Industr. Eng., 113, 323-332 (2017)
[2] Bruni, M. E.; Beraldi, P.; Khodaparasti, S., A heuristic approach for the k-traveling repairman problem with profits under uncertainty, Electron. Notes Discrete Math., 69, 221-228 (2018)
[3] Bang, B. H.; Nghia, N. D., Improved genetic algorithm for minimum latency problem, Proceedings of the 2010 Symposium on Information and Communication Technology (pp. 9-15) (2010), ACM
[4] 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 (pp. 311-336) (2010), Springer Berlin Heidelberg · Zbl 1204.68280
[5] Blum, A.; Chalasani, P.; Coppersmith, D.; Pulleyblank, B.; Raghavan, P.; Sudan, M., The minimum latency problem, Proceedings of the 26th Annual ACM Symposium on Theory of Computing (pp. 163-171) (1994), ACM · Zbl 1345.90073
[6] Ban, H. B.; Nguyen, K.; Ngo, M. C.; Nguyen, D. N., An efficient exact algorithm for minimum latency problem, J. PI, 1, 10, 1-8 (2013)
[7] Beraldi, P.; Bruni, M. E.; Laganà, D.; Musmanno, R., The risk-averse traveling repairman problem with profits, Soft. Comput., 1-15 (2018) · Zbl 1418.90066
[8] Bruni, M. E.; Beraldi, P.; Khodaparasti, S., A fast heuristic for routing in post-disaster humanitarian relief logistics, Transp. Res. Procedia, 30, 304-313 (2018)
[9] Bruni, M. E.; Brusco, L.; Ielpa, G.; Beraldi, P., The risk-averse profitable tour problem, International Conference on Operations Research and Enterprise Systems (2019)
[10] Campos, V.; Martí, R.; Sánchez-Oro, J.; Duarte, A., GRASP with path relinking for the orienteering problem, J. Oper. Res. Soc., 65, 12, 1800-1813 (2014)
[11] Chen, Y.; Hao, J. K.; Glover, F., A hybrid metaheuristic approach for the capacitated arc routing problem, Eur. J. Oper. Res., 253, 1, 25-39 (2016) · Zbl 1346.90087
[12] Coene, S.; Spieksma, F. C., Profit-based latency problems on the line, Oper. Res. Lett., 36, 3, 333-337 (2008) · Zbl 1152.90533
[13] Carrabs, F.; Cordeau, J. F.; Laporte, G., Variable neighborhood search for the pickup and delivery traveling salesman problem with LIFO loading, INFORMS J. Comput., 19, 4, 618-632 (2007) · Zbl 1241.90103
[14] Dewilde, T.; Cattrysse, D.; Coene, S.; Spieksma, F. C.; Vansteenwegen, P., Heuristics for the traveling repairman problem with profits, Comput. Oper. Res., 40, 7, 1700-1707 (2013) · Zbl 1348.90634
[15] 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) · Zbl 1317.90114
[16] Ekici, A.; Retharekar, A., Multiple agents maximum collection problem with time dependent rewards, Comput. Industr. Eng., 64, 4, 1009-1018 (2013)
[17] Erkut, E.; Zhang, J., The maximum collection problem with time-dependent rewards, Nav. Res. Logist., 43, 5, 749-763 (1996) · Zbl 0864.90041
[18] Erdoǧan, G.; Laporte, G., The orienteering problem with variable profits, Networks, 61, 2, 104-116 (2013) · Zbl 1269.90123
[19] Fischetti, M.; Gonzalez, J. J.S.; Toth, P., Solving the orienteering problem through branch-and-cut, INFORMS J. Comput., 10, 2, 133-148 (1998) · Zbl 1034.90523
[20] Fakcharoenphol, J.; Harrelson, C.; Rao, S., The k-traveling repairmen problem, ACM Trans. Algorithms (TALG), 3, 4, 40 (2007) · Zbl 1446.90133
[21] Feillet, D.; Dejax, P.; Gendreau, M., Traveling salesman problems with profits, Transp. Sci., 39, 2, 188-205 (2005)
[22] Goemans, M.; Kleinberg, J., An improved approximation ratio for the minimum latency problem, Math. Program., 82, 1-2, 111-124 (1998) · Zbl 0920.90138
[23] Peng, L.; Liu, S.; Liu, R.; Wang, L., Effective long short-term memory with differential evolution algorithm for electricity price prediction, Energy, 162, 1301-1314 (2018)
[24] Hansen, P.; Mladenović, N.; Todosijević, R.; Hanafi, S., Variable neighborhood search: basics and variants, EURO J. Comput. Optim., 5, 3, 423-454 (2017) · Zbl 1390.90586
[25] Hao, J. K., Memetic algorithms in discrete optimization, (Neri; etal., Handbook of Memetic Algorithms (pp. 73-94) (2012), Springer Berlin Heidelberg)
[26] Hernández-Pérez, H.; Rodríguez-Martín, I.; Salazar-González, J. J., A hybrid heuristic approach for the multi-commodity pickup-and-delivery traveling salesman problem, Eur. J. Oper. Res., 251, 1, 44-52 (2016) · Zbl 1346.90124
[27] Jarboui, B.; Derbel, H.; Hanafi, S.; Mladenović, N., Variable neighborhood search for location routing, Comput. Oper. Res., 40, 1, 47-57 (2013) · Zbl 1349.90091
[28] Kellegöz, T.; Toklu, B.; Wilson, J., Comparing efficiencies of genetic crossover operators for one machine total weighted tardiness problem, Appl. Math. Comput., 199, 2, 590-598 (2008) · Zbl 1140.90402
[29] Kuo, Y.; Wang, C. C., A variable neighborhood search for the multi-depot vehicle routing problem with loading cost, Expert Syst. Appl., 39, 8, 6949-6954 (2012)
[30] López-Ibáñez, M.; Dubois-Lacoste, J.; Cáceres, L. P.; Birattari, M.; Stützle, T., The irace package: iterated racing for automatic algorithm configuration, Oper. Res. Perspect., 3, 43-58 (2016)
[31] Lin, S.; Kernighan, B. W., An effective heuristic algorithm for the traveling-salesman problem, Oper. Res., 21, 2, 498-516 (1973) · Zbl 0256.90038
[32] Lu, Y.; Benlic, U.; Wu, Q., A memetic algorithm for the orienteering problem with mandatory visits and exclusionary constraints, Eur. J. Oper. Res., 268, 1, 54-69 (2018) · Zbl 1403.90144
[33] Luo, Z.; Qin, H.; Lim, A., Branch-and-price-and-cut for the multiple traveling repairman problem with distance constraints, Eur. J. Oper. Res., 234, 1, 49-60 (2014) · Zbl 1305.90408
[34] Martí, R.; Duarte, A.; Laguna, M., Advanced scatter search for the max-cut problem, INFORMS J. Comput., 21, 1, 26-38 (2009) · Zbl 1243.90227
[35] Mladenović, N.; Hansen, P., Variable neighborhood search, Comput. Oper. Res., 24, 11, 1097-1100 (1997) · Zbl 0889.90119
[36] Mladenović, N.; Urošević, D.; Ilić, A., A general variable neighborhood search for the one-commodity pickup-and-delivery travelling salesman problem, Eur. J. Oper. Res., 220, 1, 270-285 (2012) · Zbl 1253.90200
[37] Moscato, P., Memetic algorithms: A short introduction, New Ideas in Optimization (pp. 219-234) (1999), McGraw-Hill Ltd.: McGraw-Hill Ltd. UK
[38] Neri, F.; Cotta, C.; Moscato, P., Handbook of Memetic Algorithms (2012), Springer Berlin Heidelberg
[39] Or, I., Traveling salesman-type combinational problems and their relation to the logistics of blood banking (1976), USA: Northwestern University, PhD thesis
[40] Prins, C.; Bouchenoua, S., A memetic algorithm solving the VRP, the CARP and general routing problems with nodes, edges and arcs, Recent Advances in Memetic Algorithms (2005), Springer Berlin Heidelberg
[41] Salehipour, A.; Sörensen, K.; Goos, P.; Bräysy, O., Efficient GRASP+VND and GRASP+VNS metaheuristics for the traveling repairman problem, 4OR, 9, 2, 189-209 (2011) · Zbl 1221.90077
[42] Silva, M. M.; Subramanian, A.; Vidal, T.; Ochi, L. S., A simple and effective metaheuristic for the minimum latency problem, Eur. J. Oper. Res., 221, 3, 513-520 (2012) · Zbl 1253.90012
[43] Vansteenwegen, P.; Souffriau, W.; Van Oudheusden, D., The orienteering problem: a survey, Eur. J. Oper. Res., 209, 1, 1-10 (2011) · Zbl 1205.90253
[44] Wu, B. Y., Polynomial time algorithms for some minimum latency problems, Inf. Process. Lett., 75, 5, 225-229 (2000) · Zbl 1339.68125
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.