EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

185. Estimating Optimal Split Delivery Vehicle Routing Problem Solution Values

Invited abstract in session TC-29: Exact Algorithms and Formulations for Network Optimization Problems, stream Combinatorial Optimization.

Tuesday, 12:30-14:00
Room: 157 (building: 208)

Authors (first author is the speaker)

1. Shuhan Kou
2. Bruce Golden
Decision & Information Technologies, University of Maryland
3. Luca Bertazzi
Dept. of Economics and Management, University of Brescia

Abstract

Motivated by Basel and Willemain’s (2001) work on estimating optimal tour lengths in the Traveling Salesman Problem (TSP), we identify an intrinsic relationship between the distribution of the feasible solution space and the optimal solution value in combinatorial optimization problems. Our goal is to use regression modeling to estimate optimal solution values. We begin with a model that uses standard deviation as a predictor and we explain why this makes sense. We study TSP instance sets, both Euclidean and non-Euclidean. Next, we add the mean and the minimum in order to obtain very high quality results. We extend our experiments to include more than 10,000 vehicle routing problem (VRP) instances. Again, we obtain excellent results. Finally, we focus on the more difficult Split Delivery Vehicle Routing Problem (SDVRP) by combining the mean and standard deviation predictors with two topological features. In testing on 95 diverse benchmark instances from the literature, our regression model successfully estimates the optimal SDVRP solution value to within about 3%, on average.

Keywords

Status: accepted


Back to the list of papers