# Estimating the Tour Length for the Close Enough Traveling Salesman Problem
## 1 Introduction  
Operations researchers have long been interested in estimating the length of tours and routes in the traveling salesman problem (TSP) and the vehicle routing problem (VRP). One of the earliest papers by [PERSON] et al. [1] developed analytically derived formulas for the TSP. [PERSON] and [PERSON] [2], [PERSON] and [PERSON] [3], and [PERSON] and [PERSON] [4] improved these formulas by using empirically estimated parameters. [PERSON] and [PERSON] [5] constructed interval estimates of the optimal solution value. [PERSON] [6] and [PERSON] et al. [7] used parameters for the shape of the area covering the customers and the depot, the distance between customers, and the coordinates of the customers. [PERSON] and [PERSON] [8] estimated the optimal tour length for 17 TSP instances using the square root of the number of cities and the variability of tour lengths. [PERSON] et al. [9] developed empirically based regression models for estimating the travel distance in the TSP, in the capacitated VRP with time windows, and in the multi-region, multi-depot pickup and delivery problem. As pointed out by [PERSON] et al. [9], carriers and logistics companies may need to solve a large number of routing problems which might require a significant computational effort. Approaches that generate fast, accurate estimates for the travel distance are highly desirable in practice for a wide range of real-world routing problems. These estimates can be used by companies to make strategic, tactical, and operational decisions quickly [9]. In this paper, we construct empirically based regression models for estimating the tour length in the Close Enough Traveling Salesman Problem (CETSP). In the TSP, a salesman must visit the exact customer location. In the CETSP, a customer has a service region and is considered visited when the salesman visits any point in the customer's service region. The CETSP arises in practical applications including utility meter reading at residential locations using radio frequency identification and using drones for aerial surveillance. Inanother application, during multi-visit drone routing [10] it becomes important to quickly assess whether the duration to cover a region of interest would exceed a drone's battery life. In the CETSP, a service region is assumed to be a circular disk centered at the customer location with a specified radius. The objective is to visit all customers in the shortest distance traveled starting and ending at the depot. The TSP is a special case of the CETSP when all radii of the circular disks are zero, making the CETSP at least as difficult to solve as the TSP. In order to solve an instance of the CETSP, it is not enough to determine the sequence in which the customers are visited. We must also determine the locations at which these customers are visited within their respective service regions. In Figure 1, we show an instance of a CETSP with 12 customers denoted by \(C_{1},\ldots,C_{12}\) and a depot denoted by \(C_{0}\). The service region is specified by a circle centered at the customer's location. A feasible CETSP tour is shown by the solid lines with arrows. The tour passes through at least one point in the service region of each customer. If a tour passes through an overlap of several disks, all customers that define those disks are served. A Steiner zone is an overlap of disks. If a Steiner zone is contained in at most \(k\) disks, it has degree \(k\). For example, the location of each of customers \(C_{1}\), \(C_{6}\), \(C_{8}\), and \(C_{11}\) is within a degree 1 Steiner zone. Similarly, the location of each of customers \(C_{3}\), \(C_{4}\), \(C_{5}\), \(C_{9}\), and \(C_{12}\) is within a degree 2 Steiner zone. Whereas, the location of each of customers \(C_{2}\), \(C_{7}\), and \(C_{10}\) is within a degree 3 Steiner zone. For more details on Steiner zones, see [PERSON] et al. [11]. Figure 1: An instance of a CETSP with 12 customers [11]. Progress in computational integer programming has been remarkable over the past 30 years; see [PERSON] et al.