Conversation
|
Looks like |
Note on benchmarksTL;DR superseding the usual Exchange operator with the new SWAP*-adjusted implementation does improve results in most cases. This means generally reducing average/median/worst gap to optimal while stretching computing time by around 5 to 10% usually, which is definitely acceptable for the sake of quality improvement. Results vary across exploration levels and benchmarks classes so I'll just report general trends. CVRP
This may not sound like a big deal but it is significant since gaps are already quite low. For example with MDVRP and HVRPNot that many instances so probably not very significant, but same trend as above with more volatility in average gap reduction (from ~-0.1 to -0.8 point). VRPTWSteady reduction in costs for Homberger instances while average gap actually slightly increases for Solomon instances. The latter is a bit frustrating and a closer inspection shows that most Solomon instances are actually slightly improved but a few of them (in the R and RC classes) generate quite poorer solutions. I did not come up with a full explanation for this, other than the fact that the "random" instances are tougher to solve (especially with tight constraints) so any local search change is more prone to lead to getting trapped in a worse local minima. |
| const auto s_insert = get_insert_range(source.route, | ||
| s_rank, | ||
| target.route[t_rank], | ||
| sc.insertion_in_source); |
There was a problem hiding this comment.
I think this is the actual pain point for computing times since here get_insert_range populates a new std::vector that serve as insertion range for the validity checks down the line.
The reason this is required in the first place is that the actual range is mostly a part of the source route, but with the target node added either in front or back depending on respective insertion ranks.
I don't see a way to solve this better for now, but I hope there is. Maybe at some point using ranges to be able to iterate without actually building the range?
Issue
Fixes #507
Tasks
cvrp::SwapStaroperatorvrptw::SwapStaroperatorExchangecodeCHANGELOG.md