{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T02:51:49Z","timestamp":1774925509363,"version":"3.50.1"},"reference-count":23,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2021,4,12]],"date-time":"2021-04-12T00:00:00Z","timestamp":1618185600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We construct empirically based regression models for estimating the tour length in the Close Enough Traveling Salesman Problem (CETSP). In the CETSP, a customer is considered visited when the salesman visits any point in the customer\u2019s service region. We build our models using as many as 14 independent variables on a set of 780 benchmark instances of the CETSP and compare the estimated tour lengths to the results from a Steiner zone heuristic. We validate our results on a new set of 234 instances that are similar to the 780 benchmark instances. We also generate results for a new set of 72 larger instances. Overall, our models fit the data well and do a very good job of estimating the tour length. In addition, we show that our modeling approach can be used to accurately estimate the optimal tour lengths for the CETSP.<\/jats:p>","DOI":"10.3390\/a14040123","type":"journal-article","created":{"date-parts":[[2021,4,12]],"date-time":"2021-04-12T21:47:33Z","timestamp":1618264053000},"page":"123","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Estimating the Tour Length for the Close Enough Traveling Salesman Problem"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4375-1387","authenticated-orcid":false,"given":"Debdatta","family":"Sinha Roy","sequence":"first","affiliation":[{"name":"Staples Inc., Framingham, MA 01702, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5270-6094","authenticated-orcid":false,"given":"Bruce","family":"Golden","sequence":"additional","affiliation":[{"name":"Robert H. Smith School of Business, University of Maryland, College Park, MD 20742, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4021-3954","authenticated-orcid":false,"given":"Xingyin","family":"Wang","sequence":"additional","affiliation":[{"name":"Engineering Systems and Design, Singapore University of Technology and Design, Singapore 487372, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8397-4809","authenticated-orcid":false,"given":"Edward","family":"Wasil","sequence":"additional","affiliation":[{"name":"Kogod School of Business, American University, Washington, DC 20016, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2021,4,12]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1017\/S0305004100034095","article-title":"The shortest path through many points","volume":"55","author":"Beardwood","year":"1959","journal-title":"Math. Proc. Camb. Philos. Soc."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1057\/jors.1969.101","article-title":"Expected distances in distribution problems","volume":"20","author":"Christofides","year":"1969","journal-title":"J. Oper. Res. Soc."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"662","DOI":"10.1057\/palgrave.jors.2601751","article-title":"Models to estimate average route lengths in different geographical environments","volume":"55","author":"Hindle","year":"2004","journal-title":"J. Oper. Res. Soc."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"588","DOI":"10.1016\/j.ejor.2014.12.020","article-title":"A distribution-free TSP tour length estimation model for random graphs","volume":"243","author":"Cavdar","year":"2015","journal-title":"Eur. J. Oper. Res."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1002\/nav.3800260108","article-title":"Interval estimation of a global optimum for large combinatorial problems","volume":"26","author":"Golden","year":"1979","journal-title":"Nav. Res. Logist. Q."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1016\/0305-0548(92)90002-M","article-title":"Operational estimators for the length of a traveling salesman tour","volume":"19","author":"Chien","year":"1992","journal-title":"Comput. Oper. Res."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1039","DOI":"10.1016\/0305-0548(94)00093-N","article-title":"Estimating the length of the optimal TSP tour: An empirical study using regression and neural networks","volume":"22","author":"Kwon","year":"1995","journal-title":"Comput. Oper. Res."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1023\/A:1011263204536","article-title":"Random tours in the traveling salesman problem: Analysis and application","volume":"20","author":"Basel","year":"2001","journal-title":"Comput. Optim. Appl."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/j.cor.2018.10.008","article-title":"Total distance approximations for routing solutions","volume":"102","author":"Nicola","year":"2019","journal-title":"Comput. Oper. Res."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"104802","DOI":"10.1016\/j.cor.2019.104802","article-title":"Multi-visit drone routing problem","volume":"113","author":"Poikonen","year":"2020","journal-title":"Comput. Oper. Res."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1016\/j.cor.2018.07.023","article-title":"A Steiner zone variable neighborhood search heuristic for the close-enough traveling salesman problem","volume":"101","author":"Wang","year":"2019","journal-title":"Comput. Oper. Res."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"813","DOI":"10.1214\/15-AOS1388","article-title":"Best subset selection via a modern optimization lens","volume":"44","author":"Bertsimas","year":"2016","journal-title":"Ann. Stat."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1287\/ijoc.2013.0574","article-title":"An integer-programming-based approach to the close-enough traveling salesman problem","volume":"26","author":"Behdani","year":"2014","journal-title":"INFORMS J. Comput."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"752","DOI":"10.1287\/ijoc.2016.0711","article-title":"A branch-and-bound algorithm for the close-enough traveling salesman problem","volume":"28","author":"Coutinho","year":"2016","journal-title":"INFORMS J. Comput."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/j.cor.2016.09.003","article-title":"A novel discretization scheme for the close-enough traveling salesman problem","volume":"78","author":"Carrabs","year":"2017","journal-title":"Comput. Oper. Res."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Gulczynski, D., Heath, J., and Price, C. (2006). The close enough traveling salesman problem: A discussion of several heuristics. Perspectives in Operations Research: Papers in Honor of Saul Gass\u2019 80th Birthday, Springer.","DOI":"10.1007\/978-0-387-39934-8_16"},{"key":"ref_17","unstructured":"Dong, J., Yang, N., and Chen, M. (2007). Heuristic approaches for a TSP variant: The automatic meter reading shortest tour problem. Extending the Horizons: Advances in Computing, Optimization, and Decision Technologies, Springer."},{"key":"ref_18","unstructured":"Mennell, W.K. (2009). Heuristics for Solving Three Routing Problems: Close-Enough Traveling Salesman Problem, Close-Enough Vehicle Routing Problem, Sequence-Dependent Team Orienteering Problem. [Ph.D. Thesis, Decision, Operations & Information Technologies, University of Maryland]."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Mennell, W.K., Golden, B., and Wasil, E. (2011). A Steiner-zone heuristic for solving the close-enough traveling salesman problem. Operations Research, Computing, and Homeland Defense, INFORMS.","DOI":"10.1287\/ics.2011.0004"},{"key":"ref_20","unstructured":"Silberholz, J., and Golden, B. (2007). The generalized traveling salesman problem: A new genetic algorithm approach. Extending the Horizons: Advances in Computing, Optimization, and Decision Technologies, Springer."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"1252","DOI":"10.1109\/TKDE.2007.1062","article-title":"On the optimal robot routing problem in wireless sensor networks","volume":"19","author":"Yuan","year":"2007","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/j.ejor.2017.07.024","article-title":"A double-loop hybrid algorithm for the traveling salesman problem with arbitrary neighbourhoods","volume":"265","author":"Yang","year":"2018","journal-title":"Eur. J. Oper. Res."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Sinha Roy, D., Golden, B., Wang, X., and Wasil, E. (2021, April 08). Instances for the Close Enough Traveling Salesman Problem. Data Set. Available online: http:\/\/doi.org\/10.5281\/zenodo.4632436.","DOI":"10.3390\/a14040123"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/4\/123\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T13:35:52Z","timestamp":1760362552000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/4\/123"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,12]]},"references-count":23,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2021,4]]}},"alternative-id":["a14040123"],"URL":"https:\/\/doi.org\/10.3390\/a14040123","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,12]]}}}