Skip to content

Implement SWAP*#580

Merged
jcoupey merged 29 commits intomasterfrom
feature/swap-star
Oct 4, 2021
Merged

Implement SWAP*#580
jcoupey merged 29 commits intomasterfrom
feature/swap-star

Conversation

@jcoupey
Copy link
Collaborator

@jcoupey jcoupey commented Sep 21, 2021

Issue

Fixes #507

Tasks

  • Implement spotting best SWAP* option
  • First working implementation for cvrp::SwapStar operator
  • First working implementation for vrptw::SwapStar operator
  • Adjust paper approach to account for capacity constraints
  • Adjust paper approach to account for TW constraints
  • Expand search to less interesting available moves if best SWAP* option is not valid
  • Benchmark
  • Deprecate Exchange code
  • Update CHANGELOG.md
  • review

@jcoupey jcoupey added this to the v1.11.0 milestone Sep 21, 2021
@jcoupey
Copy link
Collaborator Author

jcoupey commented Sep 21, 2021

Looks like clang is unhappy due to https://stackoverflow.com/a/46115028.

@jcoupey
Copy link
Collaborator Author

jcoupey commented Sep 29, 2021

Note on benchmarks

TL;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

  • More instances solved to full number of jobs
  • Steady reduction of average optimal gap around -0.5 / -0.6 point

This may not sound like a big deal but it is significant since gaps are already quite low. For example with -x 5, average gap drops from 1.79% to 1.32% while median gap drops from 1.05% down to 0.68%.

MDVRP and HVRP

Not 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).

VRPTW

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

Comment on lines +246 to +249
const auto s_insert = get_insert_range(source.route,
s_rank,
target.route[t_rank],
sc.insertion_in_source);
Copy link
Collaborator Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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?

@jcoupey jcoupey merged commit dfcb2ab into master Oct 4, 2021
@jcoupey jcoupey deleted the feature/swap-star branch October 5, 2021 14:56
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Projects

None yet

Development

Successfully merging this pull request may close these issues.

Add SWAP* operator

1 participant