Skip to content

Use insertion ranks bounds for LS operator pruning#696

Merged
jcoupey merged 35 commits intomasterfrom
enhancement/prune-LS
May 10, 2022
Merged

Use insertion ranks bounds for LS operator pruning#696
jcoupey merged 35 commits intomasterfrom
enhancement/prune-LS

Conversation

@jcoupey
Copy link
Collaborator

@jcoupey jcoupey commented Apr 15, 2022 •
edited
Loading

Issue

Fixes #583

Tasks

  • Store insertion rank bounds based on earliest/latest time for all jobs/routes
  • Store weak insertion rank bounds based on TW for all jobs/routes
  • Update relevant insertion ranks upon route changes
  • Prune MixedExchange moves
  • Prune CrossExchange moves
  • Prune TwoOpt moves
  • Prune ReverseTwoOpt moves
  • Prune IntraRelocate moves
  • Prune IntraOrOpt moves
  • Prune IntraExchange moves
  • Prune IntraCrossExchange moves
  • Prune IntraMixedExchange moves
  • Benchmark reduction in number of operator lookups
  • Benchmark computing time reduction
  • Update CHANGELOG.md
  • review

jcoupey added 30 commits February 1, 2022 14:36
@jcoupey
Put all route_costs occurences behind NDEBUG.
6d6dd41
@jcoupey
Template Solution::setup.
12526ce
@jcoupey
First take at storing insertion range based on TW.
0b091a0
@jcoupey
Update insertion ranks after local search move.
4d37573
@jcoupey
Prune Relocate moves using insertion ranges.
d4178d5
@jcoupey
Prune OrOpt moves using insertion ranges.
f8a0002
@jcoupey
Store weaker insertion range constraints based solely on TW.
4772278
@jcoupey
Set LOG_LS_OPERATORS for now.
d496ca0
@jcoupey
Prune IntraRelocate moves with weak insertion range.
c8a3ac2
@jcoupey
Prune TwoOpt moves based on weak insertion ranges.
628fa2d
@jcoupey
Prune ReverseTwoOpt moves.
412ea0e
@jcoupey
Prune IntraOrOpt moves.
6aa1d44
@jcoupey
Prune IntraExchange moves.
5b369ae
@jcoupey
Prune IntraCrossExchange moves.
34a2441
@jcoupey
Prune IntraMixedExchange moves.
8f08721
@jcoupey
Prune MixedExchange moves.
57a6dff
@jcoupey
Prune CrossExchange moves.
2fef434
@jcoupey
Switch to stronger insertion ranges for CrossExchange.
ef1fdca
@jcoupey
Switch to stronger insertion ranges for MixedExchange.
eb713a1
@jcoupey
Additionnal pruning for MixedExchange.
99209bb
@jcoupey
Variables adjustments.
42751ab
@jcoupey
Rephrase range insertion comments.
102fccf
@jcoupey
Prune UnassignedExchange moves.
e8c9498
@jcoupey
Pass SolutionState to compute_best_insertion_pd.
fa2dd98
@jcoupey
Use insertion ranks in compute_best_insertion_pd.
6e5e91f
@jcoupey
Prune compute_best_insertion.
c22aa87
@jcoupey
Store SwapChoice options in a vector, fixes #682
3430995
@jcoupey
First take at pruning inside SWAP*.
8e8aaaf
@jcoupey
Further pruning inside SWAP*.
79cf51b
@jcoupey
Pruning based on weak insertion ranks for SWAP*.
28f7832
@jcoupey jcoupey added this to the v1.12.0 milestone Apr 15, 2022
@jcoupey jcoupey self-assigned this Apr 15, 2022
@jcoupey
Copy link
Collaborator Author

jcoupey commented Apr 29, 2022

Here are some comparisons on the usual VRPTW benchmark classes using -x 5 where results are nearly always the same in quality (a very small number of solutions have changed due to different search paths after fixing #682 along the way).

Average computing times

Computed for all instances in each benchmark class.

Bench aa3a1ee fe87ad8 delta (%)
Solomon 751 385 -48.7
Homberger 200 4094 1865 -54.4
Homberger 400 20873 9526 -54.4
Homberger 600 52193 23961 -54.1

So it's a steady 2x speedup! 🎉 Of course we're talking about instances where the TW are rather tight and constraining so the pruning approach does make a bigger difference.

LS operators lookups

Here is the total number of LS operators lookups across all benchmark instances.

Bench aa3a1ee fe87ad8 delta (%)
Solomon 2362150254 938754682 -60.3
Homberger 200 14479752836 5258489935 -63.7
Homberger 400 76064030714 25687922018 -66.2
Homberger 600 155454871416 60966284162 -60.8

The total reduction shadows differences related to TW tightness in the instances. For example the reduction in number of applied operator ranges from -22.9% to -86.0% across all Solomon instances.

@jcoupey jcoupey mentioned this pull request May 4, 2022
Merged
8 tasks
@jcoupey jcoupey merged commit ca37586 into master May 10, 2022
@jcoupey jcoupey deleted the enhancement/prune-LS branch May 10, 2022 13:55
@jcoupey jcoupey mentioned this pull request May 18, 2022
Merged
13 tasks
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

No reviews

Assignees

@jcoupey jcoupey

Labels

core enhancement Local search

Projects

None yet

Milestone

v1.12.0

Development

Successfully merging this pull request may close these issues.

Prune local search moves based on TW constraints

1 participant

@jcoupey