×

zbMATH — the first resource for mathematics

A simple and effective metaheuristic for the minimum latency problem. (English) Zbl 1253.90012
Summary: The Minimum Latency Problem (MLP) is a variant of the Traveling Salesman Problem which aims to minimize the sum of arrival times at vertices. The problem arises in a number of practical applications such as logistics for relief supply, scheduling and data retrieval in computer networks. This paper introduces a simple metaheuristic for the MLP, based on a greedy randomized approach for solution construction and iterated variable neighborhood descent with random neighborhood ordering for solution improvement. Extensive computational experiments on nine sets of benchmark instances involving up to 1000 customers demonstrate the good performance of the method, which yields solutions of higher quality in less computational time when compared to the current best approaches from the literature. Optimal solutions, known for problems with up to 50 customers, are also systematically obtained in a fraction of seconds.

MSC:
90-08 Computational methods for problems pertaining to operations research and mathematical programming
90C59 Approximation methods and heuristics in mathematical programming
90C27 Combinatorial optimization
68M10 Network design and communication in computer systems
Software:
TSPLIB
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abeledo, H., Fukasawa, R., Pessoa, A., Uchoa, E., 2010a. The Time Dependent Traveling Salesman Problem: Polyhedra and Algorithm. Tech. Rep. RPEP, vol. 10 no. 15. Universidade Federal Fluminense, Brasil. · Zbl 1269.90064
[2] Abeledo, H.G., Fukasawa, R., Pessoa, A.A., Uchoa, E., 2010b. The time dependent traveling salesman problem: polyhedra and branch-cut-and-price algorithm. In: Proceedings of the 9th International Symposium on Experimental Algorithms, SEA 2010, pp. 202-213. · Zbl 1269.90064
[3] Archer, A., Blasiak, A., 2010. Improved approximation algorithms for the minimum latency problem via prize-collecting strolls. In: Proceedings of the 21th Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 429-447. · Zbl 1288.68100
[4] Archer, A., Williamson, D.P., 2003. Faster approximation algorithms for the minimum latency problem. In: Proceedings of the 40th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 88-96. · Zbl 1094.68699
[5] Arora, S.; Karakostas, G., Approximation schemes for minimum latency problems, SIAM journal on computing, 32, 5, 1317-1337, (2003) · Zbl 1047.68166
[6] Ausiello, G., Leonardi, S., Marchetti-Spaccamela, A., 2000. On salesmen, repairmen, spiders, and other traveling agents. In: Proceedings of the 4th Italian Conference on Algorithms and Complexity, pp. 1-16. · Zbl 0973.90082
[7] Bianco, L.; Mingozzi, A.; Ricciardelli, S., The traveling salesman problem with cumulative costs, Networks, 23, 2, 81-91, (1993) · Zbl 0821.90121
[8] Bigras, L.-P.; Gamache, M.; Savard, G., The time-dependent traveling salesman problem and single machine scheduling problems with sequence dependent setup times, Discrete optimization, 5, 4, 685-699, (2008) · Zbl 1152.90425
[9] Blum, A., Chalasanit, P., Pulleyblankt, B., Raghavan, P., Sudan, M., 1994. The minimum latency problem. In: Proceedings of the 26th Annual ACM Symposium on Theory of Computing, pp. 163-171. · Zbl 1345.90073
[10] Campbell, A.; Vandenbussche, D.; Hermann, W., Routing for relief efforts, Transportation science, 42, 2, 127-145, (2008)
[11] Chaudhuri, K., Godfrey, B., Rao, S., Talwar, K., 2003. Paths, trees, and minimum latency tours. In: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003, pp. 36-45.
[12] Dewilde, T., Cattrysse, D., Coene, S., Spieksma, F.C.R., Vansteenwegen, P., 2010. Heuristics for the traveling repairman problem with profits. In: Proceedings of the 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2010, pp. 34-44. · Zbl 1247.90291
[13] Dongarra, J.J., 2011. Performance of Various Computers using Standard Linear Equations Software. Tech. Rep. CS-89-85. Computer Science Department, University of Tennessee, Knoxville, TN, USA.
[14] Ezzine, I.O., Semet, F., Chabchoub, H., 2010. New formulations for the traveling repairman problem. In: Proceedings of the 8th International Conference of Modeling and Simulation.
[15] Fakcharoenphol, J.; Harrelson, C.; Rao, S., The k-traveling repairmen problem, ACM transactions on algorithms, 3, 4, 40+, (2007) · Zbl 1446.90133
[16] Feo, T.A.; Resende, M.G.C., Greedy randomized adaptive search procedures, Journal of global optimization, 6, 2, 109-133, (1995) · Zbl 0822.90110
[17] Fischetti, M.; Laporte, G.; Martello, S., The delivery man problem and cumulative matroids, Operations research, 41, 6, 1055-1064, (1993) · Zbl 0791.90062
[18] García, A.; Jodrá, P.; Tejel, J., A note on the traveling repairman problem, Networks, 40, 1, 27-31, (2002) · Zbl 1027.90104
[19] Goemans, M.X.; Kleinberg, J.M., An improved approximation ratio for the minimum latency problem, Mathematical programming, 82, 1, 111-124, (1998) · Zbl 0920.90138
[20] Gouveia, L.; Voss, S., A classification of formulations for the (time-dependent) traveling salesman problem, European journal of operational research, 83, 1, 69-82, (1995) · Zbl 0903.90170
[21] Heilporn, G.; Cordeau, J.-F.; Laporte, G., The delivery man problem with time windows, Discrete optimization, 7, 4, 269-282, (2010) · Zbl 1241.90110
[22] Kindervater, G.; Savelsbergh, M., Vehicle routing: handling edge exchanges, (), 337-360 · Zbl 0887.90060
[23] Lourenço, H.; Martin, O.; Stützle, T., Iterated local search, (), 320-353 · Zbl 1116.90412
[24] Lucena, A., Time-dependent traveling salesman problem – the deliveryman case, Networks, 20, 6, 753-763, (1990) · Zbl 0744.90063
[25] Martin, O.; Otto, S.W.; Felten, E.W., Large-step Markov chains for the traveling salesman problem, Complex systems, 5, 3, 299-326, (1991) · Zbl 0736.90063
[26] Méndez-Dı´az, I.; Zabala, P.; Lucena, A., A new formulation for the traveling deliveryman problem, Discrete applied mathematics, 156, 17, 3223-3237, (2008) · Zbl 1155.90471
[27] Mladenović, N.; Hansen, P., Variable neighborhood search, Computers & operations research, 24, 11, 1097-1100, (1997) · Zbl 0889.90119
[28] Nagarajan, V., Ravi, R., 2008. The directed minimum latency problem. In: Proceedings of the 11th International Workshop, APPROX 2008, and 12th International Workshop, RANDOM 2008 on Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques, pp. 193-206. · Zbl 1159.68674
[29] Ngueveu, S.; Prins, C.; Wolfler Calvo, R., An effective memetic algorithm for the cumulative capacitated vehicle routing problem, Computers & operations research, 37, 11, 1877-1885, (2010) · Zbl 1188.90037
[30] Picard, J.-C.; Queyranne, M., The time-dependent traveling salesman problem and its application to the tardiness problem in one-machine scheduling, Operations research, 26, 1, 86-110, (1978) · Zbl 0371.90066
[31] Reinelt, G., TSPLIB - a traveling salesman problem library, INFORMS journal on computing, 3, 4, 376-384, (1991) · Zbl 0775.90293
[32] Ribeiro, G.; Laporte, G., An adaptive large neighborhood search heuristic for the cumulative capacitated vehicle routing problem, Computers & operations research, 39, 3, 728-735, (2012) · Zbl 1251.90057
[33] Sahni, S.; Gonzalez, T., P-complete approximation problems, Journal of the ACM, 23, 3, 555-565, (1976) · Zbl 0348.90152
[34] Salehipour, A.; Sörensen, K.; Goos, P.; Bräysy, O., Efficient GRASP+VND and GRASP+VNS metaheuristics for the traveling repairman problem, 4OR: A quarterly journal of operations research, 9, 2, 189-209, (2011) · Zbl 1221.90077
[35] Savelsbergh, M., Local search in routing problems with time windows, Annals of operations research, 4, 1, 285-305, (1985)
[36] Sitters, R., 2002. The minimum latency problem is NP-hard for weighted trees. In: Proceedings of the 9th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2002, pp. 230-239. · Zbl 1049.90531
[37] Subramanian, A.; Drummond, L.M.A.; Bentes, C.; Ochi, L.S.; Farias, R., A parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery, Computers & operations research, 37, 11, 1899-1911, (2010) · Zbl 1188.90041
[38] Tsitsiklis, J.N., Special cases of traveling salesman and repairman problems with time windows, Networks, 22, 3, 263-282, (1992) · Zbl 0819.90124
[39] Van Eijl, C.A., 1995. A Polyhedral Approach to the Delivery Man problem. Tech. Rep. COSOR 95-19. Eindhoven University of Technology.
[40] Vidal, T., Crainic, T., Gendreau, M., Prins, C., 2011. A Unifying View on Timing Problems and Algorithms. Tech. Rep. CIRRELT.
[41] Wu, B.Y.; Huang, Z.-N.; Zhan, F.-J., Exact algorithms for the minimum latency problem, Information processing letters, 92, 6, 303-309, (2004) · Zbl 1173.68832
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.