An Analysis of Several Heuristics for the Traveling Salesman Problem
The DOI matches its Crossref record; 14 of the 14 references it cites were found in a registry or an index.
Abstract
Several polynomial time algorithms finding “good,” but not necessarily optimal, tours for the traveling salesman problem are considered. We measure the closeness of a tour by the ratio of the obtained tour length to the minimal tour length. For the nearest neighbor method, we show the ratio is bounded above by a logarithmic function of the number of nodes. We also provide a logarithmic lower bound on the worst case. A class of approximation methods we call insertion methods are studied, and these are also shown to have a logarithmic upper bound. For two specific insertion methods, which we call nearest insertion and cheapest insertion, the ratio is shown to have a constant upper bound of 2, and examples are provided that come arbitrarily close to this upper bound. It is also shown that for any $n\geqq 8$, there are traveling salesman problems with n nodes having tours which cannot be improved by making $n/4$ edge changes, but for which the ratio is $2(1-1/n)$.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“While pioneering approaches for in situ sequencing154,155, transcriptome in vivo analysis156, and multiplex FISH157–159 of single-cell RNA are emerging (see also a recent review160), their throughput and accessibility to the research community have not yet matched those of more established protocols.”
From Revealing the vectors of cellular identity with single-cell genomics (2016) · cites this paper as [154]
Citations
Cites
Reducibility among Combinatorial Problems
Karp, R. M. (1972) · Complexity of Computer Computations · doi:10.1007/978-1-4684-2001-2_9 · Cited by 11,511
On the shortest spanning subtree of a graph and the traveling salesman problem
Kruskal, J. B. (1956) · Proceedings of the American Mathematical Society · doi:10.1090/s0002-9939-1956-0078686-7 · Cited by 5,088
Shortest Connection Networks And Some Generalizations
Prim, R. C. (1957) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1957.tb01515.x · Cited by 4,565
Floyd, R. W. (1962) · Communications of the ACM · doi:10.1145/367766.368168 · Cited by 3,998
An Effective Heuristic Algorithm for the Traveling-Salesman Problem
Lin, S., & Kernighan, B. W. (1973) · Operations Research · doi:10.1287/opre.21.2.498 · Cited by 3,821
Computer Solutions of the Traveling Salesman Problem
Lin, S. (1965) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1965.tb04146.x · Cited by 1,986
A Method for Solving Traveling-Salesman Problems
Croes, G. A. (1958) · Operations Research · doi:10.1287/opre.6.6.791 · Cited by 1,570
The Traveling Salesman Problem: A Survey
Bellmore, M., & Nemhauser, G. L. (1968) · Operations Research · doi:10.1287/opre.16.3.538 · Cited by 411
A Heuristic Approach to Solving Travelling Salesman Problems
Karg, R. L., & Thompson, G. L. (1964) · Management Science · doi:10.1287/mnsc.10.2.225 · Cited by 210
Reiter, S., & Sherman, G. (1965) · Journal of the Society for Industrial and Applied Mathematics · doi:10.1137/0113056 · Cited by 112
Research works printed but not linked: 1
- Sartaj Sahni, Teofilo Gonzales, P -complete problems and approximate solutions, 15th Annual Symposium on Switching and Automata Theory (Univ. New Orleans, New Orleans, La., 1974), IEEE Comput. Soc., Long Beach, Calif., 1974, 28–32 MR0416113 (54:4189) · doi:10.1109/swat.1974.22
Cited by
Items 101–200 of 1,000
Online graph exploration: New results on old and new algorithms
Megow, N., Mehlhorn, K., & Schweitzer, P. (2012) · Theoretical Computer Science · doi:10.1016/j.tcs.2012.06.034 · Cited by 89
Multi-objective Meta-heuristics for the Traveling Salesman Problem with Profits
Jozefowiez, N., Glover, F., & Laguna, M. (2008) · Journal of Mathematical Modelling and Algorithms · doi:10.1007/s10852-008-9080-2 · Cited by 86
Operational estimators for the length of a traveling salesman tour
Chien, T.-H. (1992) · Computers & Operations Research · doi:10.1016/0305-0548(92)90002-m · Cited by 86
The Traveling Salesman Problem with Backhauls
Gendreau, M., Hertz, A., & Laporte, G. (1996) · Computers & Operations Research · doi:10.1016/0305-0548(95)00036-4 · Cited by 85
Visualizing synaptic plasticity in vivo by large-scale imaging of endogenous AMPA receptors
Graves, A. R., Roth, R. H., Tan, H. L., Zhu, Q., Bygrave, A. M., Lopez-Ortega, E., Hong, I., Spiegel, A. C., Johnson, R. C., Vogelstein, J. T., et al. (2021) · eLife · doi:10.7554/elife.66809 · Cited by 84
Monochromatic and Bichromatic Reverse Top-k Queries
Vlachou, A., Doulkeridis, C., Kotidis, Y., & Nørvåg, K. (2011) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2011.50 · Cited by 83
The traveling salesman problem with delivery and backhauls
Anily, S., & Mosheiov, G. (1994) · Operations Research Letters · doi:10.1016/0167-6377(94)90016-7 · Cited by 82
Design and Operational Concepts of High-Coverage Point-to-Point Transit System
Cortés, C. E., & Jayakrishnan, R. (2002) · Transportation Research Record Journal of the Transportation Research Board · doi:10.3141/1783-22 · Cited by 80
Sustainable last-mile distribution with autonomous delivery robots and public transportation
Maio, A. D., Ghiani, G., Laganà, D., & Manni, E. (2024) · Transportation Research Part C Emerging Technologies · doi:10.1016/j.trc.2024.104615 · Cited by 79
Optimal Clustering of Railroad Track Maintenance Jobs
Peng, F., & Ouyang, Y. (2013) · Computer-Aided Civil and Infrastructure Engineering · doi:10.1111/mice.12036 · Cited by 78
Planning the sequence of tasks for harvesting robots
Kurtser, P., & Edan, Y. (2020) · Robotics and Autonomous Systems · doi:10.1016/j.robot.2020.103591 · Cited by 77
A tabu search heuristic for a routing problem arising in servicing of offshore oil and gas platforms
Gribkovskaia, I. V., Laporte, G., & Shlopak, A. (2007) · Journal of the Operational Research Society · doi:10.1057/palgrave.jors.2602469 · Cited by 77
Improving variable neighborhood search to solve the traveling salesman problem
Hore, S., Chatterjee, A., & Dewanji, A. (2018) · Applied Soft Computing · doi:10.1016/j.asoc.2018.03.048 · Cited by 77
A bound for the Steiner tree problem in graphs
Plesník, J. (1981) · Czech digital mathematics library · Cited by 77
Heuristics for the traveling repairman problem with profits
Dewilde, T., Cattrysse, D., Coene, S., Spieksma, F. C. R., & Vansteenwegen, P. (2013) · Computers & Operations Research · doi:10.1016/j.cor.2013.01.003 · Cited by 75
Survey of Methods of Solving TSP along with its Implementation using Dynamic Programming Approach
Chauhan, C., Gupta, R., & Pathak, K. (2012) · International Journal of Computer Applications · doi:10.5120/8189-1550 · Cited by 75
Collaborated Tasks-driven Mobile Charging and Scheduling: A Near Optimal Result
Wu, T., Yang, P., Dai, H., Xu, W., & Xu, M. (2019) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom.2019.8737509 · Cited by 73
Kuo, R. J., & Shih, C.-H. (2007) · Computers & Mathematics with Applications · doi:10.1016/j.camwa.2006.03.043 · Cited by 72
A model for a multi-size inland container transportation problem
Funke, J., & Kopfer, H. (2016) · Transportation Research Part E Logistics and Transportation Review · doi:10.1016/j.tre.2016.02.010 · Cited by 72
Bandaru, S., & Deb, K. (2016) · CRC Press eBooks · doi:10.1201/9781315183176-12 · Cited by 72
Online Graph Exploration with Advice
Dobrev, S., Kráľovič, R., & Μάρκου, Ε. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-31104-8_23 · Cited by 70
Dynamic vehicle routing for online B2C delivery
DU, T. C.-T., Li, E. Y., & Chou, D. (2004) · Omega · doi:10.1016/j.omega.2004.03.005 · Cited by 70
On-line steiner trees in the Euclidean plane
Alon, N., & Azar, Y. (1993) · Discrete & Computational Geometry · doi:10.1007/bf02573969 · Cited by 70
Machine Learning for Data-Driven Last-Mile Delivery Optimization
Özarık, S. S., da Costa, P., & Florio, A. M. (2023) · Transportation Science · doi:10.1287/trsc.2022.0029 · Cited by 68
Improving the Efficiency of Stochastic Vehicle Routing: A Partial Lagrange Multiplier Method
Cao, Z., Guo, H., Zhang, J., Niyato, D. T., & Fastenrath, U. (2015) · IEEE Transactions on Vehicular Technology · doi:10.1109/tvt.2015.2480964 · Cited by 68
A Hybrid Swarm Intelligence Algorithm for Vehicle Routing Problem With Time Windows
Shen, Y., Liu, M., Yang, J., Shi, Y., & Middendorf, M. (2020) · IEEE Access · doi:10.1109/access.2020.2984660 · Cited by 67
A Framework and Benchmark for Deep Batch Active Learning for RegressionPreprint
Holzmüller, D., Zaverkin, V., Kästner, J., & Steinwart, I. (2022) · arXiv (Cornell University) · doi:10.48550/arxiv.2203.09410 · Cited by 67
Castillo, V. E., Bell, J. E., Mollenkopf, D. A., & Stank, T. P. (2021) · Journal of Business Logistics · doi:10.1111/jbl.12288 · Cited by 68
A hybrid scatter search for the probabilistic traveling salesman problem
Liu, Y.-H. (2005) · Computers & Operations Research · doi:10.1016/j.cor.2005.11.008 · Cited by 66
Boldon, B., Deo, N., & Kumar, N. (1996) · Parallel Computing · doi:10.1016/0167-8191(95)00010-0 · Cited by 66
Liu, W., Lin, C., Chiu, C., Tsao, Y.-S., & Wang, Q. (2014) · Sustainability · doi:10.3390/su6074658 · Cited by 65
Disaster relief routing under uncertainty: A robust optimization approach
Li, Y., & Chung, S. H. (2018) · IISE Transactions · doi:10.1080/24725854.2018.1450540 · Cited by 64
Chung, K.-H., Ko, C. S., Shin, J. Y., Hwang, H., & Kim, K. H. (2007) · Computers & Industrial Engineering · doi:10.1016/j.cie.2007.06.017 · Cited by 64
The value of integrating order picking and vehicle routing decisions in a B2C e-commerce environment
Moons, S., Braekers, K., Ramaekers, K. M., Caris, A., & Arda, Y. (2019) · International Journal of Production Research · doi:10.1080/00207543.2019.1566668 · Cited by 63
Emergent cooperative goal-satisfaction in large-scale automated-agent systems
Shehory, O. M., Kraus, S., & Yadgar, O. (1999) · Artificial Intelligence · doi:10.1016/s0004-3702(99)00018-1 · Cited by 63
A GP Hyper-Heuristic Approach for Generating TSP Heuristics
Duflo, G., Kieffer, E., Brust, M. R., Danoy, G., & Bouvry, P. (2019) · IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum · doi:10.1109/ipdpsw.2019.00094 · Cited by 62
The use of dynamic programming in genetic algorithms for permutation problems
Yagiura, M., & Ibaraki, T. (1996) · European Journal of Operational Research · doi:10.1016/0377-2217(94)00301-7 · Cited by 62
Large Language Models as End-to-end Combinatorial Optimization Solvers
Jiang, X., Wu, Y., Li, M., Cao, Z., & Zhang, Y. (2025) · neural information processing systems · doi:10.52202/085713-5495 · Cited by 61
BEE COLONY OPTIMIZATION WITH LOCAL SEARCH FOR TRAVELING SALESMAN PROBLEM
Wong, L., Low, M. Y. H., & Chong, C. S. (2010) · International Journal of Artificial Intelligence Tools · doi:10.1142/s0218213010000200 · Cited by 61
Models and algorithms for a two-stage production process
Sherali, H. D., Sarin, S. C., & Kodialam, M. S. (1990) · Production Planning & Control · doi:10.1080/09537289008919291 · Cited by 60
Trading off Charging and Sensing for Stochastic Events Monitoring in WRSNs
Sun, Y., Lin, C., Dai, H., Wang, P., Wang, L., Wu, G., & Zhang, Q. (2021) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2021.3122130 · Cited by 59
A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem
van Bevern, R., & Slugina, V. (2020) · Historia Mathematica · doi:10.1016/j.hm.2020.04.003 · Cited by 58
Cuts, Primal Heuristics, and Learning to Branch for the Time-Dependent Traveling Salesman ProblemPreprint
Hansknecht, C., Joormann, I., & Stiller, S. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1805.01415 · Cited by 58
A Bi-Level Framework for Learning to Solve Combinatorial Optimization on GraphsPreprint
Wang, R., Hua, Z., Liu, G., Zhang, J., Yan, J., Feng, Q., Yang, S., Zhou, J., & Yang, X. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2106.04927 · Cited by 58
Algorithms for a stochastic selective travelling salesperson problem
Tang, H., & Miller-Hooks, E. D. (2004) · Journal of the Operational Research Society · doi:10.1057/palgrave.jors.2601831 · Cited by 56
The pickup and delivery traveling salesman problem with first-in-first-out loading
Erdoğan, G., Cordeau, J., & Laporte, G. (2008) · Computers & Operations Research · doi:10.1016/j.cor.2008.05.005 · Cited by 56
An Efficient Evolutionary Algorithm for Subset Selection with General Cost Constraints
Bian, C., Feng, C., Qian, C., & Yu, Y. (2020) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v34i04.5726 · Cited by 55
A survey on deep learning-based algorithms for the traveling salesman problem
Sui, J., Ding, S., Huang, X., Yu, Y., Liu, R., Xia, B., Ding, Z., Xu, L., Zhang, H., Yu, C., et al. (2024) · Frontiers of Computer Science · doi:10.1007/s11704-024-40490-y · Cited by 54
Pareto Evolutionary Algorithm Hybridized with Local Search for Biobjective TSP
Kumar, R., & Singh, P. K. (2007) · Studies in computational intelligence · doi:10.1007/978-3-540-73297-6_14 · Cited by 54
Review of Stochastic Dynamic Vehicle Routing in the Evolving Urban Logistics Environment
Mardešić, N., Erdelić, T., Carić, T., & Ðurasević, M. (2023) · Mathematics · doi:10.3390/math12010028 · Cited by 53
Dynamic vehicle routing problem with drone resupply for same-day delivery
Pina-Pardo, J. C., Silva, D. F., Smith, A. E., & Gatica, R. A. (2024) · Transportation Research Part C Emerging Technologies · doi:10.1016/j.trc.2024.104611 · Cited by 53
Hilgert, T., Kagerbauer, M., Schuster, T., & Becker, C. (2016) · Transportation research procedia · doi:10.1016/j.trpro.2016.12.068 · Cited by 53
Home health care logistics management problems: a critical review of models and methods
Gutiérrez, E. V., & Holguín, C. J. V. (2013) · Revista Facultad de Ingeniería Universidad de Antioquia · doi:10.17533/udea.redin.17222 · Cited by 53
Approximation Algorithms and Metaheuristics
Gonzalez, T. F. (2014) · Chapman & Hall/CRC eBooks · doi:10.1201/9780429171529-12 · Cited by 53
Integrated task sequencing and path planning for robotic remote laser welding
Kovács, A. (2015) · International Journal of Production Research · doi:10.1080/00207543.2015.1057626 · Cited by 52
Inventory Routing for Bike Sharing Systems
Brinkmann, J., Ulmer, M. W., & Mattfeld, D. C. (2016) · Transportation research procedia · doi:10.1016/j.trpro.2016.12.091 · Cited by 52
Competitive concurrent distributed queuing
Herlihy, M. P., Tirthapura, S., & Wattenhofer, R. P. (2001) · ACM Symposium on Principles of Distributed Computing (PODC) · doi:10.1145/383962.384001 · Cited by 52
Bee Colony Optimization with local search for traveling salesman problem
Wong, L., Low, M. Y. H., & Chong, C. S. (2008) · IEEE International Conference on Industrial Informatics (INDIN) · doi:10.1109/indin.2008.4618252 · Cited by 51
Recognizing Local and Global Structural Motifs at the Atomic Scale
Gasparotto, P., Meißner, R. H., & Ceriotti, M. (2018) · Journal of Chemical Theory and Computation · doi:10.1021/acs.jctc.7b00993 · Cited by 53
DDL: Empowering Delivery Drones With Large-Scale Urban Sensing Capability
Chen, X., Wang, H., Cheng, Y., Fu, H., Liu, Y., Dang, F., Liu, Y., Cui, J., & Chen, X. (2024) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2024.3427371 · Cited by 50
A Geo-Aware and VRP-Based Public Bicycle Redistribution System
Lin, J. H., & Chou, T. (2012) · International Journal of Vehicular Technology · doi:10.1155/2012/963427 · Cited by 50
Near Optimal Charging Schedule for 3-D Wireless Rechargeable Sensor Networks
Lin, C., Yang, W. J., Dai, H., Li, T., Wang, Y., Wang, L., Wu, G., & Zhang, Q. (2021) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2021.3137308 · Cited by 50
Transgenetic algorithm for the Traveling Purchaser Problem
Goldbarg, M. C., Bagi, L. B., & Goldbarg, E. F. G. (2008) · European Journal of Operational Research · doi:10.1016/j.ejor.2008.10.027 · Cited by 49
Huang, Y., Shen, X., & You, X. (2021) · Applied Soft Computing · doi:10.1016/j.asoc.2021.107085 · Cited by 48
Solving a real-world package delivery routing problem using quantum annealers
Osaba, E., Villar-Rodríguez, E., & Asla, A. (2024) · Scientific Reports · doi:10.1038/s41598-024-75572-1 · Cited by 47
Placido, A. D., Archetti, C., & Cerrone, C. (2022) · Computers & Operations Research · doi:10.1016/j.cor.2022.105831 · Cited by 47
The traveling purchaser problem with budget constraint
Mansini, R., & Tocchella, B. (2008) · Computers & Operations Research · doi:10.1016/j.cor.2008.09.001 · Cited by 47
Eguía, I., Racero, J., Guerrero, F., & Lozano, S. (2013) · SIMULATION · doi:10.1177/0037549713491590 · Cited by 46
On-line network optimization problems
Kalyanasundaram, B., & Pruhs, K. R. (1998) · Lecture notes in computer science · doi:10.1007/bfb0029573 · Cited by 46
On the solutions of stochastic traveling salesman problems
Leipälä, T. (1978) · European Journal of Operational Research · doi:10.1016/0377-2217(78)90044-9 · Cited by 46
An approximation algorithm for the asymmetric travelling salesman problem with distances one and two
Vishwanathan, S. (1992) · Information Processing Letters · doi:10.1016/0020-0190(92)90103-3 · Cited by 46
Vehicle routing in the 1-skip collection problem
Archetti, C., & Speranza, M. G. (2004) · Journal of the Operational Research Society · doi:10.1057/palgrave.jors.2601743 · Cited by 46
Kong, X., & Schunn, C. D. (2007) · Cognitive Systems Research · doi:10.1016/j.cogsys.2007.06.002 · Cited by 45
Optimizing Auto-Carrier Loading
Agbegha, G., Ballou, R. H., & Mathur, K. (1998) · Transportation Science · doi:10.1287/trsc.32.2.174 · Cited by 45
Ramírez-Villamil, A., Montoya‐Torres, J. R., Jaegler, A., & Cuevas-Torres, J. M. (2023) · Computers & Industrial Engineering · doi:10.1016/j.cie.2023.109604 · Cited by 44
Reoptimization of minimum and maximum traveling salesman's tours
Ausiello, G., Escoffier, B., Monnot, J., & Paschos, V. T. (2008) · Journal of Discrete Algorithms · doi:10.1016/j.jda.2008.12.001 · Cited by 44
A bidirectional graph neural network for traveling salesman problems on arbitrary symmetric graphs
Hu, Y., Zhang, Z., Yao, Y., Huyan, X., Zhou, X., & Lee, W. S. (2020) · Engineering Applications of Artificial Intelligence · doi:10.1016/j.engappai.2020.104061 · Cited by 44
BIRCHSCAN: A sampling method for applying DBSCAN to large datasets
Ventorim, I. D. M., Luchi, D., Rodrigues, A. L., & Varejão, F. M. (2021) · Expert Systems with Applications · doi:10.1016/j.eswa.2021.115518 · Cited by 44
Lin, C., Guo, C., Dai, H., Wang, L., & Wu, G. (2019) · IEEE International Conference on Distributed Computing Systems (ICDCS) · doi:10.1109/icdcs.2019.00068 · Cited by 43
Ancău, M. (2007) · Computers & Industrial Engineering · doi:10.1016/j.cie.2007.12.008 · Cited by 42
DENDIS: A new density-based sampling for clustering algorithm
Ros, F., & Guillaume, S. (2016) · Expert Systems with Applications · doi:10.1016/j.eswa.2016.03.008 · Cited by 42
Zhu, X., Li, J., & Zhou, M. (2019) · IEEE Internet of Things Journal · doi:10.1109/jiot.2019.2899155 · Cited by 42
Dynamic Analysis of the Arrow Distributed Protocol
Herlihy, M. P., Kühn, F., Tirthapura, S., & Wattenhofer, R. P. (2006) · Theory of Computing Systems · doi:10.1007/s00224-006-1251-9 · Cited by 42
Reordering rows for better compression: Beyond the lexicographic order
Lemire, D., Kaser, O., & Gutarra, E. (2012) · ACM Transactions on Database Systems · doi:10.1145/2338626.2338633 · Cited by 42
On the nearest neighbor rule for the metric traveling salesman problem
Hougardy, S., & Wilde, M. (2014) · Discrete Applied Mathematics · doi:10.1016/j.dam.2014.03.012 · Cited by 41
Hyperseed: Unsupervised Learning With Vector Symbolic Architectures
Osipov, E., Kahawala, S., Haputhanthri, D., Kempitiya, T., Silva, D. D., Alahakoon, D., & Kleyko, D. V. (2022) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2022.3211274 · Cited by 41
Greedy heuristics with regret, with application to the cheapest insertion algorithm for the TSP
Hassin, R., & Keinan, A. (2007) · Operations Research Letters · doi:10.1016/j.orl.2007.05.001 · Cited by 41
PREACO: A fast ant colony optimization for codebook generation
Tsai, C., Tseng, S.-P., Yang, C., & Chiang, M. (2013) · Applied Soft Computing · doi:10.1016/j.asoc.2013.01.017 · Cited by 41
Fischer, A., Fischer, F., Jäger, G., Keilwagen, J., Molitor, P., & Große, I. (2013) · Discrete Applied Mathematics · doi:10.1016/j.dam.2013.09.011 · Cited by 41
Schneider, J. J. (2002) · Future Generation Computer Systems · doi:10.1016/s0167-739x(02)00106-1 · Cited by 41
Lin, C., Hao, S., Yang, W. C., Wang, P., Wang, L., Wu, G., & Zhang, Q. (2022) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2022.3220927 · Cited by 40
Discrete Mayfly Algorithm for spherical asymmetric traveling salesman problem
Zhang, T. Y., Zhou, Y., Zhou, G., Deng, W., & Luo, Q. (2023) · Expert Systems with Applications · doi:10.1016/j.eswa.2023.119765 · Cited by 40
Liu, Y.-H. (2007) · European Journal of Operational Research · doi:10.1016/j.ejor.2007.08.023 · Cited by 40
USING ITERATED TABU SEARCH FOR THE TRAVELING SALESMAN PROBLEM
Misevičius, A. (2004) · Information Technology And Control · doi:10.5755/j01.itc.32.3.11858 · Cited by 40
CALM: Co-evolution of Algorithms and Language Model for Automatic Heuristic Design
Huang, Z., Wu, W., Wu, K., Wang, J., & Lee, W. (2026) · International Conference on Learning Representations · doi:10.48550/arxiv.2505.12285 · Cited by 40
Şevkli, A. Z., & Güler, B. (2017) · Applied Soft Computing · doi:10.1016/j.asoc.2017.04.045 · Cited by 39
A new approach for solving large traveling salesman problem using evolutionary ant rules
Tsai, C.-F., & Tsai, C.-W. (2003) · International Joint Conference on Neural Networks (IJCNN) · doi:10.1109/ijcnn.2002.1007746 · Cited by 39
Chen, C.-L., Wu, J., Lin, Y.-T., Fu, L., & Chen, M.-Y. (2014) · IEEE/ASME Transactions on Mechatronics · doi:10.1109/tmech.2014.2313351 · Cited by 38
Effectiveness of Local Search for Geometric Optimization
Cohen-Addad, V., & Mathieu, C. (2015) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.socg.2015.329 · Cited by 38
Reoptimization of Minimum and Maximum Traveling Salesman’s Tours
Ausiello, G., Escoffier, B., Monnot, J., & Paschos, V. T. (2006) · Lecture notes in computer science · doi:10.1007/11785293_20 · Cited by 37
Metadata
- Authors
- Rosenkrantz, D. J., Stearns, R. E., & Lewis, II
- Affiliations
- General Electric (United States) (US)
- Venue
- SIAM Journal on Computing
- Published
- 1977-09
- Volume
- 6
- Issue
- 3
- Pages
- 563-581
- ISSN
- 0097-5397 (ISSN-L)
- 1095-7111
- OpenAlex
- W2956015669
- Cited by
- 837
- References
- 14
- Citations by year
- 2026: 39 · 2025: 40 · 2024: 46 · 2023: 42 · 2022: 33 · 2021: 45 · 2020: 34 · 2019: 36 · 2018: 32 · 2017: 31 · 2016: 25 · 2015: 25 · 2014: 32 · 2013: 29 · 2012: 23
- FWCI
- 2.91
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- SIAM Journal on Computing (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Engineering › Industrial and Manufacturing Engineering › Vehicle Routing Optimization Methods
- Physical Sciences › Computer Science › Computer Graphics and Computer-Aided Design › Computational Geometry and Mesh Generation
- Keywords
- traveling salesman problem, approximation algorithms, polynomial-time heuristic, nearest neighbor algorithm, insertion method, logarithmic approximation ratio, worst-case analysis
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.