Opened 13 years ago
Closed 12 years ago
#1561 closed enhancement (done)
Improve VRP implementation
Reported by: | svonolfe | Owned by: | abeham |
---|---|---|---|
Priority: | medium | Milestone: | HeuristicLab 3.3.6 |
Component: | Problems.VehicleRouting | Version: | 3.3.6 |
Keywords: | Cc: |
Description
The VRP implementation in HeuristicLab should be improved, so large-scale instances can be solved.
This includes performance enhancements and the implementation of additional operators.
Change History (15)
comment:1 Changed 13 years ago by svonolfe
comment:2 Changed 13 years ago by svonolfe
Included additional operators in r6448
comment:3 Changed 13 years ago by svonolfe
Improved performance of many VRP operators by optimizing the parameter lookup in r6449
comment:4 Changed 13 years ago by svonolfe
- Status changed from new to accepted
comment:5 Changed 13 years ago by svonolfe
Further improved performance in r6450
comment:6 Changed 13 years ago by svonolfe
Worked on insertion based crossover in r6455
comment:7 Changed 13 years ago by svonolfe
Added possibility to allow infeasible solutions in r6459
comment:8 Changed 13 years ago by svonolfe
- Owner changed from svonolfe to abeham
- Status changed from accepted to reviewing
These changes improve the optimization of large-scale instances.
- Performance improvements (related to parameter lookup)
- Improved visualization of the best found solution
- Additional operators
- Iterative insertion creator
- Insertion based crossover (IBX)
- Lambda interchange local improvement (for VNS)
- Possibility to allow infeasible solutions during the search process for the Potvin operators
I think they should be incorporated in the next release. It would be great if you could review the changes.
comment:9 Changed 13 years ago by abeham
- IBX crossover
- should have a literature reference
- SelectRandomTourBiasedByLength: 1 / (b / c) = c / b. There's no need to normalize the probabilities, just multiply rand with sum and you can save on a for loop.
- CalculateCentroidDistance: ySum and xSum are the same, I assume the y-values are stored in the second column
- I wouldn't use Math.Pow for squaring numbers, inlining the multiplication is likely to be faster
- SelectCityBiasedByNeighborDistance: This doesn't feel right "next = tour.Cities[next];", next is used as an index and as the value of that index. You should put i + 1 as accessor of the array which is clearer to read. Same issue with variable prev.
- Again I don't see the need to normalize the probabilities array after calculating it. If instead you multiply the variable rand with the sum of the probabilities array you've got the same solution. Also since you're using the same code again, it would be good to extract that into an own method.
- FindRouteInsertionPlace: You want to find the minimum detour. Since you're initialising minDetour to 0 instead of double.MaxValue you're actually finding the minimum detour that is also an improvement over the current distance. Is that the desired behavior? I'm just asking.
- This statement if ((!allowInfeasible && feasible) || (allowInfeasible && (!bestFeasible || feasible))) can be written easier as if (feasible || allowInfeasible && !bestFeasible)
- The next if statement is evaluated positively if place == 0, shouldn't that be place < 0 since otherwise place = 0 will never be selected. In general this statement is very complicated to read
- FindRoute uses the Contains method on a list which is very slow (complexity O(N)) if the list is long. Since this method is called in another loop the total complexity is O(N^2 * M) with M being the number of tours. Better you fill a HashSet<int> with all cities, iterate over the tours sequentially and remove them from the set as you encounter them. Afterwards the set will contain only unrouted customers and the complexity is only 2 * O(N).
- Assignments like this should be simplified
like so
bool success = true; if (!RouteUnrouted(child, distMatrix, dueTime, readyTime, serviceTime, demand, capacity, allowInfeasible)) { success = false; }
bool success = RouteUnrouted(child, distMatrix, dueTime, readyTime, serviceTime, demand, capacity, allowInfeasible);
- Statements like this are short enough to be written in one line
if (feasible) bestFeasible = true;
comment:10 Changed 13 years ago by svonolfe
Thanks very much for the comments and for the thorough review.
We will have to take a closer look at the IBX. It works quite well in the optimization process, however we have to verify if it is implemented correctly as it is described in the literature and add a proper reference.
We should probably move this ticket to the 3.3.6 release. For now, I will remove the IBX from the trunk since the release is due tomorrow.
comment:11 Changed 13 years ago by svonolfe
- Milestone changed from HeuristicLab 3.3.5 to HeuristicLab 3.3.6
- Owner changed from abeham to svonolfe
- Status changed from reviewing to assigned
- Version changed from 3.3.5 to 3.3.6
Removed IBX for now in r6522, it will be reintegrated in 3.3.6
comment:12 Changed 13 years ago by svonolfe
- Owner changed from svonolfe to abeham
- Status changed from assigned to reviewing
comment:13 Changed 12 years ago by abeham
- Status changed from reviewing to readytorelease
Okay, thanks for making the changes!
comment:14 Changed 12 years ago by abeham
- Version changed from 3.3.6 to 3.3.5
corrected version, still 3.3.5
comment:15 Changed 12 years ago by swagner
- Resolution set to done
- Status changed from readytorelease to closed
- Version changed from 3.3.5 to 3.3.6
Replaced tour data table with a text box as a tour visualization to prevent out of memory exceptions for large instances in r6447