.png){kind=icon}
.png){kind=icon}
Return
Estimating optimal objective values for the TSP, VRP, and other combinatorial problems using randomization
.png){kind=icon}
PRE
AI
DOI：10.1111/itor.13260.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Approximation of the optimal tour length in a Euclidean traveling salesman problem (TSP) has been studied by many researchers. In a previous study, we used the standard deviation in random tour lengths to approximate the optimal tour length in both Euclidean and non-Euclidean TSPs and we obtained good estimates. In this paper, we show that the strong power-law relationship between the standard deviation in random feasible solution values and the optimal solution value also holds for other Euclidean and near-Euclidean combinatorial optimization problems like the minimum spanning tree (MST) and maximum weight matching (MWM) problems. We then enhance the estimation ability of the model by considering a second predictor: the mean in random feasible solution values. Experimental results show that by using the mean, standard deviation, and randomization, we can accurately predict the optimal solution values for the TSP, MST, MWM, and the capacitated vehicle routing problem (VRP).
Keywords:
combinatorial optimization
traveling salesman problem
vehicle routing problem
regression
Journal
IF:
2.9
Papers:
1.8K
Citations:
3.7K