Latex Templete for Proposal

Latex Templete for Proposal

\documentclass[12pt]{article}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\usepackage{amscd}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}


\usepackage{epsfig}
\usepackage{verbatim}
\usepackage{graphicx}
\usepackage{amsthm}
\pagestyle{empty}
\usepackage{color}
%\usepackage[all,dvips]{xy}


\begin{comment}  

This LaTeX document is a template to be used by GWU CS department graduate students to create a course project proposal. 

As a guide, the document is already filled out to represent a fictitious proposal, and all you need to do is modify the entries below to represent your own proposal.


\end{comment}






\setlength{\textheight}{8.5in} \setlength{\topmargin}{0.0in}
\setlength{\headheight}{0.0in} \setlength{\headsep}{0.0in}
\setlength{\leftmargin}{0.5in}
\setlength{\oddsidemargin}{0.0in}
%\setlength{\parindent}{1pc}
\setlength{\textwidth}{6.5in}
%\linespread{1.6}

\newtheorem{definition}{Definition}
\newtheorem{problem}{Problem}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{note}[theorem]{Note}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{prop}[theorem]{Proposition}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}
\thispagestyle{empty}

\bigskip
\bigskip

\centerline{\textbf{\Large{Machine Learning Final Project Proposal}}}

\bigskip
\bigskip


\noindent \textbf{Name:} %Your name goes here.
Wenhui Zhang

\bigskip


\noindent \textbf{Proposed Topic:} %Write a brief description of the topic you wish to work on. 

Christmas is coming and it is time for Santa Claus to distribute gifts to children who are behaving themselves. This year, SantaClaus will go to 312 north american cities to get gifts delivered, which is a huge project calling for tremendous work and enormous and attentive palnning, thus figuring out the shortest route for the delivery is a hot topic at the moment. 

\bigskip

\noindent\textbf{My thesis proposal is} %Remove the comment (percentage) symbol in front of the appropriate category:

taking this as a traveling salesman problem, that is given a collection of cities and euclidean distance between these cities, what is the shortest route that visits every city and returns to the starting place.
%double with another major.


\bigskip

\noindent \textbf{Course Advisor:} %Write the name of any professor(s) you think you might want to work with on this topic. You may leave this section blank if you don't know. 
Claire Monteleoni


\bigskip

\noindent \textbf{Courses I have had which support my project proposal:} 
%List the courses which are relevant; you don't need to list every mathematics course you have ever taken. 

\begin{enumerate}
\item Mathematical Modeling
\item Probability and Stochastic Process 
\item Abstract Algebra 
\item Linear Algebra
\item Probability and Stochastic Process in EE
\end{enumerate} 


\section*{Proposal}

\bigskip



Santa Claus is supposed go to 312 north american cities to get gifts delivered, and in this project, seven different algorithms will be applied and compared, and the goal is looking for the best algorithm to figure out the shortest path. 

The nearest neighbor algorithm \cite{nearest neighbor algorithm}  follows a very simple greedy procedure. The algorithm starts with a tour containing a randomly chosen city and then always adds the nearest not yet visited city to the last city in the tour. The algorithm stops when all cities are on the tour.The nearest neighbour algorithm is easy to implement and executes quickly, but it can sometimes miss shorter routes which are easily noticed with human insight, due to its "greedy" nature. As a general guide, if the last few stages of the tour are comparable in length to the first stages, then the tour is reasonable; if they are much greater, then it is likely that there are much better tours. Another check is to use an algorithm such as the lower bound algorithm to estimate if this tour is good enough.



An extension to nearest neighbor algorithm is to repeat it with each city as the starting point and then return the best tour found. This heuristic is called repetitive nearest neighbor. This algorithm tends to use much more time than nearest neighbor algorithm but it will return the shortest path of all results trained and predicted by nearest neighbor algorithm. A brief description of repetitive nearest neighbor algorithm is like let start city be any vertex, apply the nearest-neighbor algorithm using city A as the starting vertex and calculate the total cost associated with the circuit, repeat the process using each of the other vertices  of the graph as the staring vertex, keep the best one from all the Hamilton circuits. If there is a designated starting vertex, rewrite this circuit with that vertex as the reference point.



Another category of algorithm for solving TSP problem are called insertion algorithms. An insertion procedure takes a sub-tour on k nodes at iteration k and determines which of the remaining n-k nodes shall be inserted to the sub-tour next (the selection step) and where (between which two nodes) it should be inserted (the insertion step). All insertion algorithms start with a tour consisting of an arbitrary city and then choose in each step a city k not yet on the tour. This city is inserted into the existing tour between two consecutive cities i and j, such that the insertion cost d(i,k)+d(k,j)-d(i,j)  is minimized, algorithms stop when all cities are on the tour. Following variations of insertion algorithms are implemented in this project: 
nearest insertion, in which the city k is chosen in each step as the city which is nearest to a city on the tour; 
farthest insertion, in which the city k is chosen in each step as the city which is farthest from any of the cities on the tour; cheapest insertion, in which the city k is chosen in each step such that the cost of inserting the new city is minimal; arbitrary insertion, in which the city k is chosen randomly from all cities not yet on the tour.\cite{A Generalized Insertion Heuristic for the Traveling Salesman Problem with Time Windows}



Besides, another algorithm is discussed in this project, which is called as 2-optimal algorithm. This algorithm is based on two edge exchange improvement procedure \cite{A method for solving traveling salesman problems}  . This procedure systematically exchanges two edges in the graph represented by the distance matrix till no improvements are possible. Exchanging two edges is equal to reversing part of the tour. The resulting tour is called 2-optimal.

In this project, seven algorithms are implemented and applied to Santa Claus's gift distribution problem, and the results are supposed to be compared. 




\begin{thebibliography}{99}
% NOTE: change the "9" above to "99" if you have MORE THAN 10 references.

\bibitem{nearest neighbor algorithm} Rosenkrantz, Stearns, and Philip M. ~Lewis. \textit{An Analysis and Several Heuristics for the Traveling Salesman Problem.} SIAM Jornal of Computing 6(3)  563-581.  

 
\bibitem{A Generalized Insertion Heuristic for the Traveling Salesman Problem with Time Windows} Michel Gendreau, Alain Hertz	, Gilbert Laporte, Mihnea Sta  \textit{A Generalized Insertion Heuristic for the Traveling Salesman Problem with Time Windows.}  Operations Research, Volume 46 Issue 3, March 1998 Pages 330 - 335 

 

\bibitem{A method for solving traveling salesman problems} G. A. CROES. \textit{A method for solving traveling salesman problems}, Operations Res. 6 (1958) , pp., 791-812.


\end{thebibliography}






%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%






\end{document}