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

Abstract The majority of research in the continuous approximation paradigm has emphasized routing problems, such as the travelling salesman problem and the vehicle routing problem. This article instead focuses on continuous approximation formulas for problems involving location, specifically the ‐medians, ‐dispersion, and generalized minimum spanning tree problems. We contribute bounds for constants that describe the growth rate of the cost of these problems as the number of demand points becomes large, and conduct computational experiments that verify that they provide a good approximation in practice.

We give a fast and simple factor 2.74 approximation algorithm for the problem of choosing the k medians of the continuum of demand points defined by a convex polygon C. Our algorithm first surrounds the input region with a bounding box, then subdivides the bounding box into subregions with equal area. Simulation results on the convex hulls of the 50 states in the United States show that the practical performance of our algorithm is within 10% of the optimal solution in the vast majority of cases.

Autonomous vehicles (or drones) are very frequently used for servicing a geographic region in numerous applications. Given a geographic territory and a set of n fixed vehicle depots, we consider the problem of designing service districts so as to balance the workload of a collection of vehicles which service this region. We assume that the territory is a connected polygonal region, i.e. a simply connected polygon containing a set of simply connected obstacles. We give a fast algorithm, based on an infinite-dimensional optimization formulation, that divides the territory into compact, connected sub-regions, each of which contains a vehicle depot, such that all regions have equal area. We also show how we can use this algorithm to find better locations of the vehicle depots.

We consider the problem of dividing a geographic region into subregions so as to minimize the maximum workload of a collection of facilities over that region. We assume that the cost of servicing a demand point is a monomial function of the distance to its assigned facility and that demand points follow a continuous probability density. We show that, when our objective is to minimize the maximum workload of all facilities, the optimal partition consists of a collection of circular arcs that are induced by a multiplicatively weighted Voronoi diagram. When we require that all subregions have equal area, the optimal partition consists of a collection of hyperbolic or quartic curves. We show that, for both problems, the dual variables correspond to “prices” for a facility to serve a demand point, and our objective is to determine a set of prices such that the entire region is “purchased” by the facilities, i.e., that the market clears. This allows us to solve the partitioning problem quickly without discretizing the service region.

We consider an uncapacitated stochastic vehicle routing problem in which vehicle depot locations are fixed, and client locations in a service region are unknown but are assumed to be independent and identically distributed samples from a given probability density function. We present an algorithm for partitioning the service region into subregions so as to balance the workloads of all vehicles when the service region is simply connected and point-to-point distances follow some “natural” metric, such as any Lp norm. This algorithm can also be applied to load balancing of other combinatorial structures, such as minimum spanning trees and minimum matchings.

Previous work has developed algorithms for finding an equitable convex partition that partitions the plane into n convex pieces each containing an equal number of red and blue points. Motivated by a vehicle routing heuristic, we look at a related problem where each piece must contain one point and an equal fraction of the area of some convex polygon. We first show how algorithms for solving the older problem lead to approximate solutions for this new equitable convex partition problem. Then we demonstrate a new algorithm that finds an exact solution to our problem in O ( N n log N ) time or operations, where n is the number of points, m the number of vertices or edges of the polygon, and N := n + m the sum.