template<typename S>
class operations_research::SavingsFilteredHeuristic::SavingsContainer< S >
Class storing and allowing access to the savings according to the number of vehicle types. The savings are stored and sorted in sorted_savings_per_vehicle_type_. Furthermore, when there is more than one vehicle type, the savings for a same before-->after arc are sorted in costs_and_savings_per_arc_[arc] by increasing cost(s-->before-->after-->e), where s and e are the start and end of the route, in order to make sure the arc is served by the route with the closest depot (start/end) possible. When there is only one vehicle "type" (i.e. all vehicles have the same start/end and cost class), each arc has a single saving value associated to it, so we ignore this last step to avoid unnecessary computations, and only work with sorted_savings_per_vehicle_type_[0]. In case of multiple vehicle types, the best savings for each arc, i.e. the savings corresponding to the closest vehicle type, are inserted and sorted in sorted_savings_.
This class also handles skipped Savings: The vectors skipped_savings_starting/ending_at_ contain all the Savings that weren't added to the model, which we want to consider for later: 1) When a Saving before-->after with both nodes uncontained cannot be used to start a new route (no more available vehicles or could not commit on any of those available). 2) When only one of the nodes of the Saving is contained but on a different vehicle type. In these cases, the Update() method is called with update_best_saving = true, which in turn calls SkipSavingForArc() (within UpdateNextAndSkippedSavingsForArcWithType()) to mark the Saving for this arc (with the correct type in the second case) as "skipped", by storing it in skipped_savings_starting_at_[before] and skipped_savings_ending_at_[after].
UpdateNextAndSkippedSavingsForArcWithType() also updates the next_savings_ vector, which stores the savings to go through once we've iterated through all sorted_savings_. In the first case above, where neither nodes are contained, we skip the current Saving (current_saving_), and add the next best Saving for this arc to next_savings_ (in case this skipped Saving is never considered). In the second case with a specific type, we search for the Saving with the correct type for this arc, and add it to both next_savings_ and the skipped Savings.
The skipped Savings are then re-considered when one of their ends gets inserted: When another Saving other_node-->before (or after-->other_node) gets inserted, all skipped Savings in skipped_savings_starting_at_[before] (or skipped_savings_ending_at_[after]) are once again considered by calling ReinjectSkippedSavingsStartingAt() (or ReinjectSkippedSavingsEndingAt()). Then, when calling GetSaving(), we iterate through the reinjected Savings in order of insertion in the vectors while there are reinjected savings.
Definition at line 1283 of file routing_search.h.
1.12.0