Local search using movement ratings from previous iterations

[unbreaking-V]

Description: This algorithm leverages movement ratings from previous iterations with an ordered list of movements. The list should include both inter- and intra-route movements. In the case of intra-route movements, such as exchanging two edges, it is essential to thoroughly understand the description from lectures concerning the Traveling Salesman Problem.

Steps:

1. Initialize LM - a list of movements that lead to improvement, ordered from best to worst.

2. Generate initial solution ( x ).

3. Repeat:

   • Scan all new movements and add movements that lead to improvement to LM.
   • Examine movements ( m ) from LM, starting from the best until an applicable movement is found.
   • Check if ( m ) is applicable, and if not, remove it from LM.
   • If an applicable movement ( m ) is found:
     • Update ( x ) with ( m(x) ) (accept ( m(x) )).

4. Continue until an applicable movement ( m ) is found after scanning the entire LM list.

[kamil271e]

TODO:

• [x] Implement adjacency matrix to check edge directions
• [x] Update adjacency matrix after each movement application
• [x] Store cached movements with positive delta function in sorted vector
• [ ] Iterate over cached movements, apply appropriate transformation to indices of movement - based on movement applied in previous iteration
• [x] Apply logic of removing and ignoring particular movements in cached vector