\documentclass{beamer}
\usetheme[style=plain]{uu}

%% unicode support
\usepackage[utf8]{inputenc}
\usepackage{ucs}
\usepackage{autofe}

\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{hyperref}

\usepackage{algpseudocode}
\usepackage{algorithm}



%% Metainformation
%% PDF stuff
\usepackage{datetime}
\usepackage{ifpdf}
\ifpdf
\pdfinfo{
    /Author (J.P.PizaniFlor, L.T. van Binsbergen, S.Fafianie)
    /Title (Genetic algorithm with iterated local search for solving a location-routing problem)
    /Keywords (Evolutionary Computing, Genetic Algorithm, Genetic Programming, location routing, local search)
    /CreationDate (D:\pdfdate)
}
\fi

\title[GA and ILS]{Genetic algorithm with iterated local search for solving a location-routing problem (2012)}
\subtitle[]{by Houda Derbel, Bassem Jarboui, Saïd Hanafi, Habib Chabchoub}

\date{\today}

\author[Binsbergen, Fafianie, Pizani Flor]
{
    L.T. van~Binsbergen
    \and S.~Fafianie
    \and J.P.~Pizani Flor
}

\institute[Utrecht University]
{
    Department of Information and Computing Sciences \\
    Utrecht University
}

\subject{Evolutionary Computing}



% The document itself
\begin{document}
    \begin{frame}
        \titlepage
    \end{frame}

    \begin{frame}
        \frametitle{Table of Contents}
        \tableofcontents
    \end{frame}

\AtBeginSection[]
{
    \begin{frame}[plain]
        \begin{center}
            \usebeamerfont{section title}\insertsection
        \end{center}
    \end{frame}
}

    \section{Problem Description}
    \label{sec:problem}

        \subsection{Problem Definition}
        \label{subsec:definition}
            \begin{frame}
                \frametitle{Problem Definition}
                \begin{itemize}
                    \item Location Routing Problem (LRP)
                    \item set of costumers $I = \{1,\ldots,n\}$
                    \item set of potential depots $J = \{1,\ldots,m\}$
                    \item limited capacity $b_{j}$ and fixed cost $f_{j}$
                    \item non-negative demand $d_{i}$
                    \item travelling cost $c_{ij}$
                \end{itemize}
            \end{frame}

            \begin{frame}
                \frametitle{Problem Definition}
                \begin{itemize}
                    \item each depot has a single incapacitated vehicle
                    \item vehicle begins and ends its route at its depot
                    \item find a subset of depots to be opened
                    \item elaborate vehicle tours to meet customer demands
                    \item minimize total cost of location and delivery
                \end{itemize}
            \end{frame}

        \subsection{Related Work}
        \label{subsec:related}
            \begin{frame}
                \frametitle{Related Work}
                \begin{itemize}
                    \item combination of Vehicle Routing Problem(VRP) and Facility Location Problem(FLP)
                    \item branch and bound method - Laporore and Norbert(1981)
                    \begin{itemize}
                        \item single-facility LRP
                        \item no tour length restrictions
                    \end{itemize}

                    \item branch and cut method - Laport, Norbert and Arpin(1986)
                    \begin{itemize}
                        \item capacitated vehicles and depots (CLRP)
                        \item fixed number of vehicles
                    \end{itemize}

                    \item heuristic approaches
                    \begin{itemize}
                        \item simulated annealing - Wu, Low and Bai (2002)
                        \item greedy randomized adaptive procedure (GRASP)
                        \item tabu search - Albreda-Sambola et al. (2005)
                    \end{itemize}
                \end{itemize}
            \end{frame}

        \subsection{Hybrid Approach}
        \label{subsec:hybrid}
            \begin{frame}
                \frametitle{Hybrid Approach}
                \begin{itemize}
                    \item Genetic Algorithm
                    \begin{itemize}
                        \item population of solutions may lead to global optimum
                        \item sub-optimal solutions are not improved fast enough
                    \end{itemize}

                    \item Iterated Local Search
                    \begin{itemize}
                        \item find local optimum quickly
                        \item may not find global optimum
                    \end{itemize}

                    \item hybrid approach maximizes the chance of convergence to an optimal solution by using
                        various search spaces
                \end{itemize}
            \end{frame}

            \begin{frame}
                \frametitle{Hybrid Approach}
                \begin{itemize}
                    \item generate and evaluate random population of solutions

                    \item in each cycle:
                    \begin{itemize}
                        \item select parents $x_{1}$ and $x_{2}$
                        \item apply crossover to $x_{1}$ and $x_{2}$ to generate child $x_{new}$
                        \item apply mutation to $x_{new}$
                        \item apply ILS to $x_{new}$ if fitness($x_{new}) < (1+\delta)\cdot fitness_{best}$
                        \item select fittest
                    \end{itemize}
                \end{itemize}
            \end{frame}


    \section{Genetic Algorithm}
    \label{sec:ga}

        \subsection{Solution Representation}
        \label{subsec:representation}
            \begin{frame}
                \frametitle{Solution Representation}
                \begin{itemize}
                    \item solution $x$ is represented by:
                    \begin{itemize}
                        \item $A(x) = \{a_{1},\ldots,a_{n}\}$ assignment configuration
                        \item $a_{i} = j$ means costumer $i$ is assigned to depot $j$
                        \item $P(x) = \{p_{1},\ldots,p_{n}\}$ rank of a costumer on a given route
                        \item customer $p_{i}$ is served before $p_{i'}$ if $i < i'$
                    \end{itemize}
                \end{itemize}
            \end{frame}

            \begin{frame}
                \frametitle{Solution Representation}
                \includegraphics[scale=0.25]{imgs/solution.png}
            \end{frame}

        \subsection{Parent selection}
        \label{subsec:selection}
            \begin{frame}   
                \frametitle{Parent Selection}
                \begin{itemize}
                    \item $\mathbb{P}([k]) = \frac{2k}{M(M + 1)}$
                    \item $[k]$ is the $k$th chromosome in descending order
                    \item $M$ is the population size
                \end{itemize}
            \end{frame}

        \subsection{Genetic Operators}
        \label{subsec:crossover}
            \begin{frame}
                \frametitle{Crossover operator}
                \begin{itemize}
                    \item 1-point crossover for the assignment configuration $A$
                    \item 1-point order crossover for the permutation configuration $P$:
                \end{itemize}
                \includegraphics[scale=0.45]{imgs/crossover.png}
            \end{frame}

            \begin{frame}
                \frametitle{Mutation}
                \begin{block}{Assignment configuration}
                    \begin{itemize}
                        \item Mutating $A$ by randomly changing an assignment to any other depot
                        \item Possibly introducing a new depot, or removing one
                        \item Performed according to a probability distribution $\mathbb{P}_{a}$
                    \end{itemize}
                \end{block}

                \begin{block}{Permutation configuration}
                    \begin{itemize}
                        \item Mutation on $P$ is performed by taking a random customer and inserting
                            it at a random position
                        \item Shifting other customers towards the old location of the customer
                        \item Performed according to probability distribution $\mathbb{P}_{p}$
                    \end{itemize}
                \end{block}
            \end{frame}

            \begin{frame}
                \frametitle{Fitness function}
                \begin{itemize}
                    \item $fitness(x) = cost(x) + penalty(x)$
                    \item $cost(x)$ is the sum of all the driving and depot costs
                    \item $penalty(x) = \sum_{j\in J}\;\alpha\; max\{0,D_j(x) - b_j\}$
                \end{itemize}
            \end{frame}

            \begin{frame}
                \frametitle{Replacement}
                \begin{itemize}
                    \item The newly created child is compared to the worst in the current population
                \end{itemize}
            \end{frame}


    \section{Iterated Local Search}
    \label{sec:ils}

        \subsection{High-level description}
        \label{subsec:algorithm}
            \begin{frame}
                \frametitle{ILS structure}
                \begin{algorithm}[H]
                    \begin{algorithmic}
                        \Require $x_{0}$ is an initial solution
                        \State $\hat{x} \gets localsearch(x_{0})$
                        \Repeat
                            \State $x \gets perturbation(\hat{x})$
                            \State $\tilde{x} \gets localsearch(x)$
                            \If{$fitness(\hat{x}) < fitness(\tilde{x})$} $\hat{x} \gets \tilde{x}$ \EndIf
                        \Until{Termination condition is met}
                    \end{algorithmic}
                    \label{alg:ils}
                    \caption{General structure of the used ILS}
                \end{algorithm}
            \end{frame}

            \begin{frame}
                \frametitle{Local search method used}
                \begin{algorithm}[H]
                    \begin{algorithmic}
                        \Require an initial solution $x$
                        \State $ x_{1} \gets $ first improvement on $x$ using neighbourhood $\mathcal{N}1$
                        \State $ x_{2} \gets $ first improvement on $x_{1}$ using neighbourhood $\mathcal{N}2$
                        \State $ x_{3} \gets $ first improvement on $x_{2}$ using neighbourhood $\mathcal{N}3$
                        \State $ x_{4} \gets $ first improvement on $x_{3}$ using neighbourhood $\mathcal{N}4$
                        \If{$fitness(x_{4}) < fitness(x_{1})$}
                            \State $ x \gets x_{4} $
                            \State Go to line 1
                        \EndIf
                    \end{algorithmic}
                    \label{alg:localsearch}
                    \caption{General structure of the local search method used}
                \end{algorithm}
            \end{frame}

        \subsection{Neighborhood structures}
        \label{subsec:neighbourhood}
            \begin{frame}
                \frametitle{Neighbourhood structures}
                Four structures were used:

                \begin{itemize}
                    \item N1 and N2: involving 2 routes
                    \begin{itemize}
                        \item N1: swap two customers
                            \begin{figure}[h]
                                \includegraphics[scale=0.20]{imgs/neighbourhood_n1.png}
                            \end{figure}
                        \item N2: move customer from one route to another
                            \begin{figure}[h]
                                \includegraphics[scale=0.20]{imgs/neighbourhood_n2.png}
                            \end{figure}
                    \end{itemize}

                \end{itemize}
            \end{frame}

            \begin{frame}
                \frametitle{Neighbourhood structures}
                Four structures were used:
                \begin{itemize}
                    \item N3 and N4: intra-route
                    \begin{itemize}
                        \item N3: swap two customers
                            \begin{figure}[h]
                                \includegraphics[scale=0.20]{imgs/neighbourhood_n3.png}
                            \end{figure}
                        \item N4: move customer to another position in the route
                            \begin{figure}[h]
                                \includegraphics[scale=0.20]{imgs/neighbourhood_n4.png}
                            \end{figure}
                    \end{itemize}
                \end{itemize}
            \end{frame}

        \subsection{Perturbation}
        \label{subsec:perturbation}
            \begin{frame}
                \frametitle{Perturbation criterion}
                \begin{itemize}
                    \item Local moves concern only open depots
                    \item Perturbation opens new depots, preserving variability
                    \item Perturbation criterion:
                    \begin{itemize}
                        \item Select a random \emph{open} depot
                        \item Move the customer assigned from the original depot to another (open or closed)
                            one.
                        \item Affects only configuration A of each chromossome (assignment)
                    \end{itemize}
                \end{itemize}
            \end{frame}


    \section{Conclusions and Comparison}
    \label{sec:conclusions}

        \subsection{Test instances}
        \label{subsec:testinstances}
            \begin{frame}
                \frametitle{Test instances}
                \begin{itemize}
                    \item Benchmarks proposed by Albreda-Sambola et al. (2005)
                    \item Five sets of instances: S1, S2, S3, M2, M3
                    \begin{itemize}
                        \item S1, S2 and S3: 5 facilities, 10, 20 and 30 customers
                        \item M2 and M3: 10 facilities, 20 and 30 customers
                    \end{itemize}

                    \item Instances further parameterized by 2 other variables:
                    \begin{itemize}
                        \item $R_{1}$: Ratio between total customer demand and total depot capacity
                        \item $R_{2}$: Value proportional to the fixed cost of opening a depot
                    \end{itemize}
                \end{itemize}
            \end{frame}

            \begin{frame}
                \frametitle{Parameter setting}
                \begin{itemize}
                    \item Generic parameters:
                    \begin{itemize}
                        \item Population size (M): 40
                        \item Mutation probability on configuration A ($\mathbb{P}_{p}$): 0.7
                        \item Mutation probability on configuration P ($\mathbb{P}_{p}$): 0.9
                        \item \emph{Penalty} constant used in fitness evaluation ($\alpha$): 1000
                    \end{itemize}

                \item ILS parameters:
                    \begin{itemize}
                        \item $\delta$ coefficient: 0.1 (ILS used rarely)
                        \item Termination condition: 100 sucessive iterations with no improvement
                    \end{itemize}
                \end{itemize}
            \end{frame}

        \subsection{Comparison}
        \label{subsec:comparison}
            \begin{frame}
                \frametitle{Comparative study}
                \begin{itemize}
                    \item Execution results compared with best-known solutions
                    \item Best-known solutions: Albreda-Sambola et al. (2005), using \emph{tabu search}
                    \item Two dimensions were measured in the experiment:
                    \begin{itemize}
                        \item \emph{\%gap}: average deviaton of found solution to the a-priori lower
                            bound (global optimum)
                        \item \emph{Time}: running time over ten instances
                    \end{itemize}

                    \item \emph{t-test} done over \%gap to verify the divergence between the two scenarios
                \end{itemize}
            \end{frame}

        \subsection{Conclusions}
        \label{subsec:conclusions}
            \begin{frame}
                \frametitle{Experimental results}
                Some notable results from the comparative study:
                \newline

                \begin{itemize}
                    \item \textbf{S1:} GA\&ILS finds all optima and beats TS in running time, but pure
                        ILS comes close (\emph{\%gap}) in less time.
                    \pause
                    \item \textbf{S2:} GA\&ILS has slightly smaller \emph{\%gap} than pure ILS, both much
                        better than TS
                    \pause
                    \item \textbf{M3 (largest):} ILS beats TS completely and GA\&ILS slightly in terms of
                        \emph{\%gap}, TS has around 10x larger running time than both others.
                    \pause
                    \item \textbf{t-test (\emph{\%gap}):} ILS and GA\&ILS beat TS with error risk close to
                        0. GA\&ILS beats pure ILS with error risk of 15\%.
                \end{itemize}
            \end{frame}

            \begin{frame}
                \frametitle{Conclusions}
                \begin{itemize}
                    \item Hybridization between GA and ILS to solve the LRP efficiently
                    \begin{itemize}
                        \item ILS improves each generation outputted by the GA
                        \item Genetic operators AND neighbourhood structures take into account
                            location and routing \emph{simultaneously}
                    \end{itemize}
                    \pause

                    \item Proposed algorithm was compared to five problem sets from the literature
                    \begin{itemize}
                        \item Improves over best-known approach (TS) both in quality of solutions
                            \emph{and} in computational requirements
                    \end{itemize}
                    \pause

                    \item Authors suggest applying VNS (Variable Neighbourhood Search) combined with GA as
                        future study
                \end{itemize}
            \end{frame}

\end{document}
