A New Upper Bound for the Euclidean TSP Constant

Let Formula: see text be n independent and uniformly distributed random points in a compact region Formula: see text of area 1. Let Formula: see text denote the length of the optimal Euclidean traveling salesman tour that traverses all these points. The classical Beardwood-Halton-Hammersley theorem proves the existence of a universal constant Formula: see text such Formula: see text almost surely, which satisfies Formula: see text. This paper presents a computer-aided proof using numerical quadrature and decision trees that Formula: see text. Although our improvement is still somewhat small, our approach has the advantage that it is primarily limited by computer hardware and is thus amenable to further improvements over time. History: Accepted by Russell Bent, Area Editor for Network Optimization: Algorithms & Applications. Funding: This work was supported by the Office of Naval Research Grants AWD-00008450, N00014-20-S-B001, and N00014-21-1-2208, the California Department of Transportation, and the U.S. Department of Transportation Grant 69A3551747114. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0538 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0538 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .