×

zbMATH — the first resource for mathematics

A population algorithm based on randomized tabu thresholding for the multi-commodity pickup-and-delivery traveling salesman problem. (English) Zbl 06988111
Summary: The multi-commodity pickup-and-delivery traveling salesman problem (m-PDTSP) is a variant of the classic traveling salesman problem with pickup and delivery. It arises from a number of real-life applications where a capacitated vehicle services a set of customers that provide or require certain amounts of different commodities. In this paper, we present a simple but highly effective population based algorithm for m-PDTSP (denoted as PRTTA) that uses a randomized tabu thresholding algorithm for local improvement. Extensive experiments on a large set of benchmark instances show that the proposed approach competes very favorably with the existing methods from the literature.
MSC:
90B Operations research and management science
Software:
irace; SPOT
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bennell, J. A.; Dowsland, K. A., A tabu thresholding implementation for the irregular stock cutting problem, Int. J. Prod. Res., 37, 18, 4259-4275, (1999) · Zbl 0949.90606
[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] Boese, K. D.; Kahng, A. B.; Muddu, S., A new adaptive multi-start technique for combinatorial global optimizations, Oper. Res. Lett., 16, 2, 101-113, (1994) · Zbl 0812.90126
[4] Castelino, D.; Stephens, N., Tabu thresholding for the frequency assignment problem, Meta-Heuristics, 343-359, (1996), Springer US · Zbl 0877.90060
[5] 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
[6] Glover, F., Tabu thresholding: improved search by nonmonotonic trajectories, ORSA J. Comput., 7, 4, 426-442, (1995) · Zbl 0843.90097
[7] Gouveia, L.; Ruthmair, M., Load-dependent and precedence-based models for pickup and delivery problems, Comput. Oper. Res., 63, 56-71, (2015) · Zbl 1349.90087
[8] Hagen, L. W.; Kahng, A. B., Combining problem reduction and adaptive multistart: a new technique for superior iterative partitioning, IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 16, 7, 709-717, (1997)
[9] Hernández-Pérez, H.; Rodrguez-Martín, I.; Salazar-González, J. J., A hybrid GRASP/VND heuristic for the one-commodity pickup-and-delivery traveling salesman problem, Comput. Oper. Res., 36, 5, 1639-1645, (2009) · Zbl 1177.90343
[10] 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
[11] Hernández-Pérez, H.; Salazar-González, J. J., The one-commodity pickup-and-delivery travelling salesman problem, Combinatorial Optimization-Eureka, You Shrink!, 89-104, (2003), Springer Berlin Heidelberg · Zbl 1024.90057
[12] Hernández-Pérez, H.; Salazar-González, J. J., Heuristics for the one-commodity pickup-and-delivery traveling salesman problem, Transp. Sci., 38, 2, 245-255, (2004)
[13] Hernández-Pérez, H.; Salazar-González, J. J., The one-commodity pickup-and-delivery traveling salesman problem: inequalities and algorithms, Networks, 50, 4, 258-272, (2007) · Zbl 1146.90056
[14] Hernández-Pérez, H.; Salazar-González, J. J., The multi-commodity one-to-one pickup-and-delivery traveling salesman problem, Eur. J. Oper. Res., 196, 3, 987-995, (2009) · Zbl 1176.90055
[15] Hernández-Pérez, H.; Salazar-González, J. J., The multi-commodity pickup-and-delivery traveling salesman problem, Networks, 63, 1, 46-59, (2014) · Zbl 1338.90340
[16] 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)
[17] Martí, R.; Resende, M. G.; Ribeiro, C. C., Multi-start methods for combinatorial optimization, Eur. J. Oper. Res., 226, 1, 1-8, (2013) · Zbl 1292.90257
[18] 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
[19] Moscato, P., Memetic algorithms: a short introduction, New Ideas in Optimization, 219-234, (1999), McGraw-Hill Ltd. UK
[20] Mosheiov, G., The travelling salesman problem with Pick-up and delivery, Eur. J. Oper. Res., 79, 2, 299-310, (1994) · Zbl 0815.90135
[21] Öncan, T., Milp formulations and an iterated local search algorithm with tabu thresholding for the order batching problem, Eur. J. Oper. Res., 243, 1, 142-155, (2015) · Zbl 1346.90165
[22] Rodríguez-Martín, I.; Salazar-González, J. J., The multi-commodity one-to-one pickup-and-delivery traveling salesman problem: a matheuristic, Network Optimization, 401-405, (2011), Springer Berlin, Heidelberg · Zbl 1345.90078
[23] Rodríguez-Martín, I.; Salazar-González, J. J., A hybrid heuristic approach for the multi-commodity one-to-one pickup-and-delivery traveling salesman problem, J. Heuristics, 18, 6, 849-867, (2012) · Zbl 1365.90293
[24] Valls, V.; Martí; Lino, P., A tabu thresholding algorithm for arc crossing minimization in bipartite graphs, Ann. Oper. Res., 63, 2, 233-251, (1996) · Zbl 0851.90132
[25] Valls, V.; Pérez, M. A.; Quintanilla, M. S., A modified tabu thresholding approach for the generalised restricted vertex colouring problem, Meta-Heuristics, 537-553, (1996), Springer Boston, MA · Zbl 0877.90081
[26] Vigo, D.; Maniezzo, V., A genetic/tabu thresholding hybrid algorithm for the process allocation problem, J. Heuristics, 3, 2, 91-110, (1997) · Zbl 1071.90586
[27] Wang, X.; Tang, L., A population-based variable neighborhood search for the single machine total weighted tardiness problem, Comput. Oper. Res., 36, 6, 2105-2110, (2009) · Zbl 1179.90163
[28] Wang, Y.; Lü, Z.; Glover, F.; Hao, J. K., Probabilistic GRASP-tabu search algorithms for the UBQP problem, Comput. Oper. Res., 40, 12, 3100-3107, (2013) · Zbl 1348.90557
[29] Zhao, F.; Li, S.; Sun, J.; Mei, D., Genetic algorithm for the one-commodity pickup-and-delivery traveling salesman problem, Comput. Indus. Eng., 56, 4, 1642-1648, (2009)
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.