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/ .