EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
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:00Room: 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
- Combinatorial Optimization
- Graphs and Networks
- Vehicle Routing
Status: accepted
Back to the list of papers