# Estimating the Tour Length for the Close Enough Traveling Salesman Problem
## 2 Regression Models and Fitness Measures  
The Steiner zone variable neighborhood search (SZVNS) heuristic developed by [PERSON] et al. (2019) finds high-quality solutions to instances of the CETSP. We use SZVNS tour lengths in our regression models to estimate CETSP tour lengths. Our regression model can be represented by \(y_{i}=\hat{\beta}_{1}+\hat{\beta}_{2}\times\mathrm{n}_{i}+\hat{\beta}_{3}\times \mathrm{A}_{i}+\hat{\beta}_{4}\times\mathrm{MinP}_{i}+\hat{\beta}_{5}\times \mathrm{MaxP}_{i}+\hat{\beta}_{6}\times\mathrm{VarP}_{i}+\hat{\beta}_{7}\times \mathrm{SumMinP}_{i}+\hat{\beta}_{8}\times\mathrm{SumMaxP}_{i}+\hat{\beta}_{9 }\times\mathrm{MinM}_{i}+\hat{\beta}_{10}\times\mathrm{MaxM}_{i}+\hat{\beta}_{ 11}\times\mathrm{SumM}_{i}+\hat{\beta}_{12}\times\mathrm{VarM}_{i}+\hat{\beta} _{13}\times(\mathrm{VarX}\times\mathrm{VarY})_{i}+\hat{\beta}_{14}\times \mathrm{AvgR}_{i}+\hat{\beta}_{15}\times\mathrm{SZ}_{i}\), where \(y_{i}=\mathbb{E}(Y_{i})\), \(\hat{\beta}_{k}=\mathbb{E}(\beta_{k})\), \(k\in\{1,\ldots,15\}\), \(i\) denotes a CETSP instance, and \(\mathbb{E}()\) denotes the expected value. The dependent variable \(Y_{i}\) is the tour length generated by the SZVNS heuristic. In Table 1, we give the definitions of the independent variables for the regression model. Nodes represent customers and the depot. The size of an instance is captured by n and A. MinP, MaxP, VarP, SumMinP, and SumMaxP capture the distances between nodes. MinM, MaxM, SumM, and VarM capture the distances to the average node represented by the mean \(x\)-coordinate and the mean \(y\)-coordinate. VarX\(\times\)VarY captures the spread of the instance across the two axes. AvgR captures the mean of the radii of the customer service regions. The service region radius of a depot is always zero. SZ captures the feature of the instance that is exploited by the SZVNS heuristic. AvgR and SZ are used to capture the geometric features unique to the CETSP. These two independent variables would not be used in a regression model that estimates TSP tour lengths. We use the 780 CETSP benchmark instances and their tour lengths produced by the SZVNS heuristic given in [PERSON] et al. (2019). The node locations (depot and the customers) are generated randomly and all customers in an instance have the same radius for the service regions. The instances have 6, 8, 10, 12, 14, 16, 18, 20, 25, or 30 customers. The radii for the customer service regions are 0.25, 0.50, or 1.00. There are 30 instances for each combination of the radius of the customer service regions and the number of customers up to 20. There are 10 instances for each combination of the radius of the customer service regions and the number of customers greater than 20. We use mean percentage error (MPE) and mean absolute percentage error (MAPE) to assess the quality of the approximation of the CETSP tour lengths from the regression model (\(y_{i}\)) with respect to the tour lengths from the SZVNS heuristic (\(Y_{i}\)). MPE and MAPE are defined by \(100\times\left(\sum_{i=1}^{N}\left(Y_{i}-y_{i}\right)/Y_{i}\right)/N\) and \(100\times\left(\sum_{i=1}^{N}\left|\right.Y_{i}-y_{i}\right.\left|\right./Y_{i} \right)/N\), respectively, where \(N\) denotes the number of instances. A value of MPE close to zero indicates that there is almost an equal distribution of instances with tour lengths being overestimated (\(Y_{i}<y_{i}\)) and underestimated (\(Y_{i}>y_{i}\)). The value of MAPE is always non-negative, and a small value indicates that the tour-length estimates are close to the SZVNS tour lengths for most of the instances. We use adjusted R\({}^{2}\), Studentized residuals, [PERSON]'s \(C_{p}\), and Bayesian information criterion (BIC) to assess the quality of the model fits. Residuals (\(Y_{i}-y_{i}\)) have a mean of zero. Studentized residuals are scaled residuals with unit variance. [PERSON]'s \(C_{p}\) and BIC are used in the context of model selection where the goal is to find the best model involving a subset of the independent variables.