Opened 6 years ago

Closed 6 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 6 years ago by svonolfe

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

comment:2 Changed 6 years ago by svonolfe

Included additional operators in r6448

comment:3 Changed 6 years ago by svonolfe

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

comment:4 Changed 6 years ago by svonolfe

  • Status changed from new to accepted

comment:5 Changed 6 years ago by svonolfe

Further improved performance in r6450

comment:6 Changed 6 years ago by svonolfe

Worked on insertion based crossover in r6455

comment:7 Changed 6 years ago by svonolfe

Added possibility to allow infeasible solutions in r6459

comment:8 Changed 6 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 6 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
        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;
    

comment:10 Changed 6 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 6 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 6 years ago by svonolfe

  • Owner changed from svonolfe to abeham
  • Status changed from assigned to reviewing

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

Last edited 6 years ago by svonolfe (previous) (diff)

comment:13 Changed 6 years ago by abeham

  • Status changed from reviewing to readytorelease

Okay, thanks for making the changes!

comment:14 Changed 6 years ago by abeham

  • Version changed from 3.3.6 to 3.3.5

corrected version, still 3.3.5

comment:15 Changed 6 years ago by swagner

  • Resolution set to done
  • Status changed from readytorelease to closed
  • Version changed from 3.3.5 to 3.3.6
Note: See TracTickets for help on using tickets.