Improve VRP implementation

[svonolfe]

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.

[svonolfe]

Replaced tour data table with a text box as a tour visualization to prevent out of memory exceptions for large instances in r6447

[svonolfe]

Included additional operators in r6448

[svonolfe]

Improved performance of many VRP operators by optimizing the parameter lookup in r6449

[svonolfe]

Further improved performance in r6450

[svonolfe]

Worked on insertion based crossover in r6455

[svonolfe]

Added possibility to allow infeasible solutions in r6459

[svonolfe]

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.

[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

      bool success = true;
      if (!RouteUnrouted(child, distMatrix, dueTime, readyTime, serviceTime, demand, capacity, allowInfeasible)) {
        success = false;
      }
  

  like so

      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;
  

[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.

[svonolfe]

Removed IBX for now in r6522, it will be reintegrated in 3.3.6

[svonolfe]

Re-Integrated the IBX, implemented review comments in r6600, adapted VRP unit test in r6605

[abeham]

Okay, thanks for making the changes!

[abeham]

corrected version, still 3.3.5