.. _ls:


*************************************************************************************************
Local Search
*************************************************************************************************

Theory
=======================================


* `Slides <../_static/slides/06-local-search.pdf>`_



Project : TSP with Local Search
=======================================
Your goal is to implement methods used in a local search to solve the Traveler Salesman Problem. In the base code given, a solution is represented by a list of integers representing cities. For instance the list ``[2,0,1]`` represents the tour going like this : ``2 -> 0 -> 1 -> 2``. 

It is important to differentiate the operations applied index-wise and city-wise. For instance, the ``twoOpt`` method in ``Candidate`` class is applied index-wise, while the distance method in ``TSPInstance`` class is applied city-wise.

Implementation
---------------

All the files related to this project are in the package ``localsearch``. You have to modify six classes:


#. ``Candidate.java`` 
#. ``BestSelection.java`` 
#. ``BestWithTabuSelection.java`` 
#. ``BeamSearchInitialization.java`` 
#. ``BeamSearchAppend.java`` 
#. ``BeamSearchInsert.java`` 
#. ``LKH.java`` 


Two Opt
~~~~~~~~~~~~~~

The first method to implement is the ``twoOpt`` method in ``Candidate.java``. This method takes two indices (``index1`` and ``index2``) and reverse the cities in the tour from ``index1 + 1`` and ``index2``. For instance, if the tour is ``[2,0,1,3,4]`` and ``index1 = 1`` and ``index2 = 3``, the new tour will be ``[2,0,3,1,4]``. This way, a twoOpt between index1 and index2 places the city at ``index2`` as the successor of the city at ``index1``. Note : this methods also updates the total distance (cost) of the tour.

Best Selection
~~~~~~~~~~~~~~

The most important part of a local search is the neighbor selection. The class ``FirstSelection.java`` contains the method ``getNeighbor`` that returns the first improving neighbor found among all ``twoOpt`` movements possible. You are asked to implement the same method in the class ``BestSelection.java``. This method should return the best improving neighbor found among all ``twoOpt`` movements possible. The best neighbor is the one that minimizes the total distance of the tour. If no improving neighbor is found, the method should return the ``Candidate`` given in argument.

Tabu
~~~~~~~~

Tabu is a common metaheuristic used in local search. The idea is to avoid returning to a previous state by forbidding a given move for a given number of iterations. In the ``BestWithTabuSelection.java`` class, you are asked to implement the ``getNeighbor`` method that returns the best improving neighbor found among all ``twoOpt`` movements possible that is not obtained through a tabu move. Once a movement is applied it should be added to the tabu list. Note : the movement tabu is a movement that would reset the solution to it's previous state. In our case, if we set the city2 to be the successor of city1, the tabu movement is to set the former successor of city1 to be it's new successor.

BeamSearch Initialization
~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Another important component of the local search is the initialization of the solution. In the ``BeamSearchInitialization.java`` class, you are asked to implement the ``getInitialSolution`` method that returns an initial candidate. To obtain the initial candidate, you need to construct a tour by starting at city 0 and selecting the best city to add to the partial solution. At each iteration you need to only keep p (beamWidth) best partial solution. Next, in ``BeamSearchAppend.java`` and ``BeamSearchInsert.java`` implement the expand function so that the beamsearch constructs solution only by appending to the end or inserting anywhere is the current partial solution. Following the course naming convention, k = lookAhead = 1.

LKH
~~~~~~~~~~~~~~
LKH is a strong heuristic to improve an existing solution. This heuristic uses a reference structure as a temporary solution to apply improving move and convert it back to a candidate solution. With the help of the pseudo code, implement the methods in ``LKH.java``. Note the methods ``findBestC`` and  ``reversePath`` are given to help you implement ``applyLKH``


Gradescope
---------------

On `Gradescope <https://www.gradescope.com/>`_, find the written assignment for the project.
Part of your assignment requires to report experimental results under the form of a graph.


..
    Traveling Salesman Problem: 2-Opt
    """""""""""""""""""""""""""""""""""""""

    You are given a suboptimal solution: [1,2,3,4,5] (list of the visited nodes).
    If the optimal solution is [4,1,3,2,5], what is the minimal sequence of 2-Opt moves to reach the solution?

    Vehicle Routing Problem: Clark-Wright Savings Algorithm
    """""""""""""""""""""""""""""""""""""""

    Given the following demands and distances between the depot and the customers, find an initial solution to the Vehicle Routing Problem with a **maximum capacity of 50** using the `Clark-Wright Savings Algorithm <http://web.mit.edu/urban_or_book/www/book/chapter6/6.4.12.html>`_.

    ======== == == == == ==
    Customer 1  2  3  4  5
    Demand   15 10 15 20 30
    ======== == == == == ==

    ========= ===== == == == == ==
    Distances depot 1  2  3  4  5
    depot           15 10 20 10 25
    1                  5  15 15 5
    2                     25 10 10
    3                        5  5
    4                           20
    5
    ========= ===== == == == == ==