\documentclass[10pt]{article}

\usepackage{fullpage}
\usepackage{setspace}
\usepackage{parskip}
\usepackage{titlesec}
\usepackage[section]{placeins}
\usepackage{xcolor}
\usepackage{breakcites}
\usepackage{lineno}
\usepackage{hyphenat}





\PassOptionsToPackage{hyphens}{url}
\usepackage[colorlinks = true,
            linkcolor = blue,
            urlcolor  = blue,
            citecolor = blue,
            anchorcolor = blue]{hyperref}
\usepackage{etoolbox}
\makeatletter
\patchcmd\@combinedblfloats{\box\@outputbox}{\unvbox\@outputbox}{}{%
  \errmessage{\noexpand\@combinedblfloats could not be patched}%
}%
\makeatother


\usepackage[round]{natbib}
\let\cite\citep




\renewenvironment{abstract}
  {{\bfseries\noindent{\abstractname}\par\nobreak}\footnotesize}
  {\bigskip}

\titlespacing{\section}{0pt}{*3}{*1}
\titlespacing{\subsection}{0pt}{*2}{*0.5}
\titlespacing{\subsubsection}{0pt}{*1.5}{0pt}


\usepackage{authblk}


\usepackage{graphicx}
\usepackage[space]{grffile}
\usepackage{latexsym}
\usepackage{textcomp}
\usepackage{longtable}
\usepackage{tabulary}
\usepackage{booktabs,array,multirow}
\usepackage{amsfonts,amsmath,amssymb}
\providecommand\citet{\cite}
\providecommand\citep{\cite}
\providecommand\citealt{\cite}
% You can conditionalize code for latexml or normal latex using this.
\newif\iflatexml\latexmlfalse
\providecommand{\tightlist}{\setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}%

\AtBeginDocument{\DeclareGraphicsExtensions{.pdf,.PDF,.eps,.EPS,.png,.PNG,.tif,.TIF,.jpg,.JPG,.jpeg,.JPEG}}

\usepackage[utf8]{inputenc}
\usepackage[greek,english]{babel}










\begin{document}

\title{Title}



\author[1]{Ishwarya Anand}%
\affil[1]{Affiliation not available}%


\vspace{-1em}



  
  \date{May 08, 2024}


\begingroup
\let\center\flushleft
\let\endcenter\endflushleft
\maketitle
\endgroup








\sloppy




\section*{Travelling Salesman Problem}
Travelling Salesman Problem (TSP): Given a set of cities and distance between every pair of cities, the problem is to find the shortest possible route that visits every city exactly once and returns to the starting point.
Note the difference between Hamiltonian Cycle and TSP. The Hamiltoninan cycle problem is to find if there exist a tour that visits every city exactly once. Here we know that Hamiltonian Tour exists (because the graph is complete) and in fact many such tours exist, the problem is to find a minimum weight Hamiltonian Cycle.\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.70\columnwidth]{figures/Euler12/Euler12}
\caption{{Example of TSP\protect\cite{geeksforgeeks}
{\label{773614}}%
}}
\end{center}
\end{figure}

For example, consider the graph shown in figure. A TSP tour in the graph is 1-2-4-3-1. The cost of the tour is 10+25+30+15 which is 80.

The problem is a famous NP hard problem. There is no polynomial time know solution for this problem.

Following are different solutions for the traveling salesman problem.



\subsection*{Recursive Brute Force Algorithm}
\begin{itemize}
\item Consider city 1 as the starting and ending point.
\item Generate all (n-1)! Permutations of cities.
\item Calculate cost of every permutation and keep track of minimum cost permutation.
\item Return the permutation with minimum cost
\end{itemize}
\selectlanguage{greek}\textbf{Time Complexity: Θ(n!)}\selectlanguage{english}



\subsection*{Genetic Algorithm}\cite{operator}
\begin{itemize}
\item Step 1. Create an initial population of P chromosomes.

\item Step 2. Evaluate the fitness of each chromosome.

\item Step 3. Choose P/2 parents from the current population via proportional selection.

\item Step 4. Randomly select two parents to create offspring using crossover operator.

\item Step 5. Apply mutation operators for minor changes in the results.

\item Step 6. Repeat Steps 4 and 5 until all parents are selected and mated.

\item Step 7. Replace old population of chromosomes with new one.

\item Step 8. Evaluate the fitness of each chromosome in the new population.

\item Step 9. Terminate if the number of generations meets some upper bound; otherwise go to Step 3.
\end{itemize}
\subsection*{Crossover Operator for TSP}
Two routes are randomly generated from the tournament population and then participate in crossover to produce a new route.
An example crossover of route1 and route2
\begin{itemize}
\item Route1 : [NY, SF, Houston, Chicago, Boston, Austin, Seattle, Denver, Dallas, LA]
\item Route2 : [LA, Seattle, Austin, Boston, Denver, NY, Houston, Dallas, SF, Chicago]
\item Intermediate crossover route : [NY, SF, Houston, Chicago, Boston, null, null, null, null]
\item Final crossover route : [NY, SF, Houston, Chicago, Boston, LA, Seattle, Austin, Denver]
\end{itemize}
\subsection*{Mutation Operator for TSP}
This operator generates a random permutation of the elements present in one chromosome.
An example route mutation
\begin{itemize}
\item Original route : [Boston, Denver, Los Angeles, Austin, New York, Seattle, Chicago, San Fransisco, Dallas, Houston]
\item Mutated route : [Boston, Denver, New York, Austin, Los Angeles, Seattle, San Fransisco, Chicago, Dallas, Houston]
\end{itemize}



\subsection*{Ant Colony Optimization}
Ants can achieve impressive results as a group while searching for food. FInding food is an optimization problem(gathering food while minimizing the energy to do that). Stigmergy is where individual organisms interact with each other through modifications of their environment. It is a form of self organization that can produce complex structures and behaviour without the need for planning or direct communication. Ants find shortest path from colony to food source using Stigmergy. They use phermones(a chemical they produce) to mark a path for other ants to follow. When other ants come across a phermone trail, they follow it with a certain probability. This probability increases relative to the strength of the phermone trail. Phermone strength increases relative to the number of ants that have followed that trail and how recent this has happened. Ants don't always follow the same phermone trail because some of them should always be searching for new food sources. Phermone trail decreases over time so that ones that no longer lead anywhere stop being attractive and are replaced by other trails. 
We exploit some elements of Stigmergy to solve Travelling Salesman Problem.



\section*{Source Code}
\subsection*{Recursive Brute Force ALgorithm to solve Travelling Salesman Problem}
\subsection*{Route.java}\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.84\columnwidth]{figures/2/2}

\end{center}
\end{figure}

\subsection*{City.java}

\selectlanguage{english}
\FloatBarrier
\bibliographystyle{plainnat}
\bibliography{bibliography/converted_to_latex.bib%
}

\end{document}

