\documentclass[11pt,twoside]{article}\makeatletter

\IfFileExists{xcolor.sty}%
  {\RequirePackage{xcolor}}%
  {\RequirePackage{color}}
\usepackage{colortbl}
\usepackage{wrapfig}
\usepackage{ifxetex}
\ifxetex
  \usepackage{fontspec}
  \usepackage{xunicode}
  \catcode`⃥=\active \def⃥{\textbackslash}
  \catcode`❴=\active \def❴{\{}
  \catcode`❵=\active \def❵{\}}
  \def\textJapanese{\fontspec{Noto Sans CJK JP}}
  \def\textChinese{\fontspec{Noto Sans CJK SC}}
  \def\textKorean{\fontspec{Noto Sans CJK KR}}
  \setmonofont{DejaVu Sans Mono}
  
\else
  \IfFileExists{utf8x.def}%
   {\usepackage[utf8x]{inputenc}
      \PrerenderUnicode{–}
    }%
   {\usepackage[utf8]{inputenc}}
  \usepackage[english]{babel}
  \usepackage[T1]{fontenc}
  \usepackage{float}
  \usepackage[]{ucs}
  \uc@dclc{8421}{default}{\textbackslash }
  \uc@dclc{10100}{default}{\{}
  \uc@dclc{10101}{default}{\}}
  \uc@dclc{8491}{default}{\AA{}}
  \uc@dclc{8239}{default}{\,}
  \uc@dclc{20154}{default}{ }
  \uc@dclc{10148}{default}{>}
  \def\textschwa{\rotatebox{-90}{e}}
  \def\textJapanese{}
  \def\textChinese{}
  \IfFileExists{tipa.sty}{\usepackage{tipa}}{}
\fi
\def\exampleFont{\ttfamily\small}
\DeclareTextSymbol{\textpi}{OML}{25}
\usepackage{relsize}
\RequirePackage{array}
\def\@testpach{\@chclass
 \ifnum \@lastchclass=6 \@ne \@chnum \@ne \else
  \ifnum \@lastchclass=7 5 \else
   \ifnum \@lastchclass=8 \tw@ \else
    \ifnum \@lastchclass=9 \thr@@
   \else \z@
   \ifnum \@lastchclass = 10 \else
   \edef\@nextchar{\expandafter\string\@nextchar}%
   \@chnum
   \if \@nextchar c\z@ \else
    \if \@nextchar l\@ne \else
     \if \@nextchar r\tw@ \else
   \z@ \@chclass
   \if\@nextchar |\@ne \else
    \if \@nextchar !6 \else
     \if \@nextchar @7 \else
      \if \@nextchar (8 \else
       \if \@nextchar )9 \else
  10
  \@chnum
  \if \@nextchar m\thr@@\else
   \if \@nextchar p4 \else
    \if \@nextchar b5 \else
   \z@ \@chclass \z@ \@preamerr \z@ \fi \fi \fi \fi
   \fi \fi  \fi  \fi  \fi  \fi  \fi \fi \fi \fi \fi \fi}
\gdef\arraybackslash{\let\\=\@arraycr}
\def\@textsubscript#1{{\m@th\ensuremath{_{\mbox{\fontsize\sf@size\z@#1}}}}}
\def\Panel#1#2#3#4{\multicolumn{#3}{){\columncolor{#2}}#4}{#1}}
\def\abbr{}
\def\corr{}
\def\expan{}
\def\gap{}
\def\orig{}
\def\reg{}
\def\ref{}
\def\sic{}
\def\persName{}\def\name{}
\def\placeName{}
\def\orgName{}
\def\textcal#1{{\fontspec{Lucida Calligraphy}#1}}
\def\textgothic#1{{\fontspec{Lucida Blackletter}#1}}
\def\textlarge#1{{\large #1}}
\def\textoverbar#1{\ensuremath{\overline{#1}}}
\def\textquoted#1{‘#1’}
\def\textsmall#1{{\small #1}}
\def\textsubscript#1{\@textsubscript{\selectfont#1}}
\def\textxi{\ensuremath{\xi}}
\def\titlem{\itshape}
\newenvironment{biblfree}{}{\ifvmode\par\fi }
\newenvironment{bibl}{}{}
\newenvironment{byline}{\vskip6pt\itshape\fontsize{16pt}{18pt}\selectfont}{\par }
\newenvironment{citbibl}{}{\ifvmode\par\fi }
\newenvironment{docAuthor}{\ifvmode\vskip4pt\fontsize{16pt}{18pt}\selectfont\fi\itshape}{\ifvmode\par\fi }
\newenvironment{docDate}{}{\ifvmode\par\fi }
\newenvironment{docImprint}{\vskip 6pt}{\ifvmode\par\fi }
\newenvironment{docTitle}{\vskip6pt\bfseries\fontsize{22pt}{25pt}\selectfont}{\par }
\newenvironment{msHead}{\vskip 6pt}{\par}
\newenvironment{msItem}{\vskip 6pt}{\par}
\newenvironment{rubric}{}{}
\newenvironment{titlePart}{}{\par }

\newcolumntype{L}[1]{){\raggedright\arraybackslash}p{#1}}
\newcolumntype{C}[1]{){\centering\arraybackslash}p{#1}}
\newcolumntype{R}[1]{){\raggedleft\arraybackslash}p{#1}}
\newcolumntype{P}[1]{){\arraybackslash}p{#1}}
\newcolumntype{B}[1]{){\arraybackslash}b{#1}}
\newcolumntype{M}[1]{){\arraybackslash}m{#1}}
\definecolor{label}{gray}{0.75}
\def\unusedattribute#1{\sout{\textcolor{label}{#1}}}
\DeclareRobustCommand*{\xref}{\hyper@normalise\xref@}
\def\xref@#1#2{\hyper@linkurl{#2}{#1}}
\begingroup
\catcode`\_=\active
\gdef_#1{\ensuremath{\sb{\mathrm{#1}}}}
\endgroup
\mathcode`\_=\string"8000
\catcode`\_=12\relax

\usepackage[a4paper,twoside,lmargin=1in,rmargin=1in,tmargin=1in,bmargin=1in,marginparwidth=0.75in]{geometry}
\usepackage{framed}

\definecolor{shadecolor}{gray}{0.95}
\usepackage{longtable}
\usepackage[normalem]{ulem}
\usepackage{fancyvrb}
\usepackage{fancyhdr}
\usepackage{graphicx}
\usepackage{marginnote}

\renewcommand{\@cite}[1]{#1}


\renewcommand*{\marginfont}{\itshape\footnotesize}

\def\Gin@extensions{.pdf,.png,.jpg,.mps,.tif}

  \pagestyle{fancy}

\usepackage[pdftitle={Towards The Solution of Variants of Vehicle Routing Problem},
 pdfauthor={}]{hyperref}
\hyperbaseurl{}

	 \paperwidth210mm
	 \paperheight297mm
              
\def\@pnumwidth{1.55em}
\def\@tocrmarg {2.55em}
\def\@dotsep{4.5}
\setcounter{tocdepth}{3}
\clubpenalty=8000
\emergencystretch 3em
\hbadness=4000
\hyphenpenalty=400
\pretolerance=750
\tolerance=2000
\vbadness=4000
\widowpenalty=10000

\renewcommand\section{\@startsection {section}{1}{\z@}%
     {-1.75ex \@plus -0.5ex \@minus -.2ex}%
     {0.5ex \@plus .2ex}%
     {\reset@font\Large\bfseries}}
\renewcommand\subsection{\@startsection{subsection}{2}{\z@}%
     {-1.75ex\@plus -0.5ex \@minus- .2ex}%
     {0.5ex \@plus .2ex}%
     {\reset@font\Large}}
\renewcommand\subsubsection{\@startsection{subsubsection}{3}{\z@}%
     {-1.5ex\@plus -0.35ex \@minus -.2ex}%
     {0.5ex \@plus .2ex}%
     {\reset@font\large}}
\renewcommand\paragraph{\@startsection{paragraph}{4}{\z@}%
     {-1ex \@plus-0.35ex \@minus -0.2ex}%
     {0.5ex \@plus .2ex}%
     {\reset@font\normalsize}}
\renewcommand\subparagraph{\@startsection{subparagraph}{5}{\parindent}%
     {1.5ex \@plus1ex \@minus .2ex}%
     {-1em}%
     {\reset@font\normalsize\bfseries}}


\def\l@section#1#2{\addpenalty{\@secpenalty} \addvspace{1.0em plus 1pt}
 \@tempdima 1.5em \begingroup
 \parindent \z@ \rightskip \@pnumwidth 
 \parfillskip -\@pnumwidth 
 \bfseries \leavevmode #1\hfil \hbox to\@pnumwidth{\hss #2}\par
 \endgroup}
\def\l@subsection{\@dottedtocline{2}{1.5em}{2.3em}}
\def\l@subsubsection{\@dottedtocline{3}{3.8em}{3.2em}}
\def\l@paragraph{\@dottedtocline{4}{7.0em}{4.1em}}
\def\l@subparagraph{\@dottedtocline{5}{10em}{5em}}
\@ifundefined{c@section}{\newcounter{section}}{}
\@ifundefined{c@chapter}{\newcounter{chapter}}{}
\newif\if@mainmatter 
\@mainmattertrue
\def\chaptername{Chapter}
\def\frontmatter{%
  \pagenumbering{roman}
  \def\thechapter{\@roman\c@chapter}
  \def\theHchapter{\roman{chapter}}
  \def\thesection{\@roman\c@section}
  \def\theHsection{\roman{section}}
  \def\@chapapp{}%
}
\def\mainmatter{%
  \cleardoublepage
  \def\thechapter{\@arabic\c@chapter}
  \setcounter{chapter}{0}
  \setcounter{section}{0}
  \pagenumbering{arabic}
  \setcounter{secnumdepth}{6}
  \def\@chapapp{\chaptername}%
  \def\theHchapter{\arabic{chapter}}
  \def\thesection{\@arabic\c@section}
  \def\theHsection{\arabic{section}}
}
\def\backmatter{%
  \cleardoublepage
  \setcounter{chapter}{0}
  \setcounter{section}{0}
  \setcounter{secnumdepth}{2}
  \def\@chapapp{\appendixname}%
  \def\thechapter{\@Alph\c@chapter}
  \def\theHchapter{\Alph{chapter}}
  \appendix
}
\newenvironment{bibitemlist}[1]{%
   \list{\@biblabel{\@arabic\c@enumiv}}%
       {\settowidth\labelwidth{\@biblabel{#1}}%
        \leftmargin\labelwidth
        \advance\leftmargin\labelsep
        \@openbib@code
        \usecounter{enumiv}%
        \let\p@enumiv\@empty
        \renewcommand\theenumiv{\@arabic\c@enumiv}%
	}%
  \sloppy
  \clubpenalty4000
  \@clubpenalty \clubpenalty
  \widowpenalty4000%
  \sfcode`\.\@m}%
  {\def\@noitemerr
    {\@latex@warning{Empty `bibitemlist' environment}}%
    \endlist}

\def\tableofcontents{\section*{\contentsname}\@starttoc{toc}}
\parskip0pt
\parindent1em
\def\Panel#1#2#3#4{\multicolumn{#3}{){\columncolor{#2}}#4}{#1}}
\newenvironment{reflist}{%
  \begin{raggedright}\begin{list}{}
  {%
   \setlength{\topsep}{0pt}%
   \setlength{\rightmargin}{0.25in}%
   \setlength{\itemsep}{0pt}%
   \setlength{\itemindent}{0pt}%
   \setlength{\parskip}{0pt}%
   \setlength{\parsep}{2pt}%
   \def\makelabel##1{\itshape ##1}}%
  }
  {\end{list}\end{raggedright}}
\newenvironment{sansreflist}{%
  \begin{raggedright}\begin{list}{}
  {%
   \setlength{\topsep}{0pt}%
   \setlength{\rightmargin}{0.25in}%
   \setlength{\itemindent}{0pt}%
   \setlength{\parskip}{0pt}%
   \setlength{\itemsep}{0pt}%
   \setlength{\parsep}{2pt}%
   \def\makelabel##1{\upshape ##1}}%
  }
  {\end{list}\end{raggedright}}
\newenvironment{specHead}[2]%
 {\vspace{20pt}\hrule\vspace{10pt}%
  \phantomsection\label{#1}\markright{#2}%

  \pdfbookmark[2]{#2}{#1}%
  \hspace{-0.75in}{\bfseries\fontsize{16pt}{18pt}\selectfont#2}%
  }{}
      \def\TheFullDate{2011-09 2011-09-01 (revised: 2011 September 01 September 2011)}
\def\TheID{\makeatother }
\def\TheDate{2011-09 2011-09-01}
\title{Towards The Solution of Variants of Vehicle Routing Problem}
\author{}\makeatletter 
\makeatletter
\newcommand*{\cleartoleftpage}{%
  \clearpage
    \if@twoside
    \ifodd\c@page
      \hbox{}\newpage
      \if@twocolumn
        \hbox{}\newpage
      \fi
    \fi
  \fi
}
\makeatother
\makeatletter
\thispagestyle{empty}
\markright{\@title}\markboth{\@title}{\@author}
\renewcommand\small{\@setfontsize\small{9pt}{11pt}\abovedisplayskip 8.5\p@ plus3\p@ minus4\p@
\belowdisplayskip \abovedisplayskip
\abovedisplayshortskip \z@ plus2\p@
\belowdisplayshortskip 4\p@ plus2\p@ minus2\p@
\def\@listi{\leftmargin\leftmargini
               \topsep 2\p@ plus1\p@ minus1\p@
               \parsep 2\p@ plus\p@ minus\p@
               \itemsep 1pt}
}
\makeatother
\fvset{frame=single,numberblanklines=false,xleftmargin=5mm,xrightmargin=5mm}
\fancyhf{} 
\setlength{\headheight}{14pt}
\fancyhead[LE]{\bfseries\leftmark} 
\fancyhead[RO]{\bfseries\rightmark} 
\fancyfoot[RO]{}
\fancyfoot[CO]{\thepage}
\fancyfoot[LO]{\TheID}
\fancyfoot[LE]{}
\fancyfoot[CE]{\thepage}
\fancyfoot[RE]{\TheID}
\hypersetup{citebordercolor=0.75 0.75 0.75,linkbordercolor=0.75 0.75 0.75,urlbordercolor=0.75 0.75 0.75,bookmarksnumbered=true}
\fancypagestyle{plain}{\fancyhead{}\renewcommand{\headrulewidth}{0pt}}

\date{}
\usepackage{authblk}

\providecommand{\keywords}[1]
{
\footnotesize
  \textbf{\textit{Index terms---}} #1
}

\usepackage{graphicx,xcolor}
\definecolor{GJBlue}{HTML}{273B81}
\definecolor{GJLightBlue}{HTML}{0A9DD9}
\definecolor{GJMediumGrey}{HTML}{6D6E70}
\definecolor{GJLightGrey}{HTML}{929497} 

\renewenvironment{abstract}{%
   \setlength{\parindent}{0pt}\raggedright
   \textcolor{GJMediumGrey}{\rule{\textwidth}{2pt}}
   \vskip16pt
   \textcolor{GJBlue}{\large\bfseries\abstractname\space}
}{%   
   \vskip8pt
   \textcolor{GJMediumGrey}{\rule{\textwidth}{2pt}}
   \vskip16pt
}

\usepackage[absolute,overlay]{textpos}

\makeatother 
      \usepackage{lineno}
      \linenumbers
      
\begin{document}

             \author[1]{Dr. Pawan  Jindal}

             \affil[1]{  }

\renewcommand\Authands{ and }

\date{\small \em Received: 22 July 2011 Accepted: 17 August 2011 Published: 1 September 2011}

\maketitle


\begin{abstract}
        


Some of the problems that are used extensively in -real life are NP complete problems. There is no any algorithm which can give the optimal solution to NP complete problems in the polynomial time in the worst case. So researchers are applying their best efforts to design the approximation algorithms for these NP complete problems. Approximation algorithm gives the solution of a particular problem, which is close to the optimal solution of that problem. In this paper, a study on variants of vehicle routing problem is being done along with the difference in the approximation ratios of different approximation algorithms as being given by researchers and it is found that Researchers are continuously applying their best efforts to design new approximation algorithms which have better approximation ratio as compared to the previously existing algorithms.

\end{abstract}


\keywords{Approximation algorithms, Vehicle Routing problem with time widows, NP  completeness.}

\begin{textblock*}{18cm}(1cm,1cm) % {block width} (coords) 
\textcolor{GJBlue}{\LARGE Global Journals \LaTeX\ JournalKaleidoscope\texttrademark}
\end{textblock*}

\begin{textblock*}{18cm}(1.4cm,1.5cm) % {block width} (coords) 
\textcolor{GJBlue}{\footnotesize \\ Artificial Intelligence formulated this projection for compatibility purposes from the original article published at Global Journals. However, this technology is currently in beta. \emph{Therefore, kindly ignore odd layouts, missed formulae, text, tables, or figures.}}
\end{textblock*}


\let\tabcellsep& 	 	 		 
\section[{INTRODUCTION}]{INTRODUCTION}\par
ransportation supports most of the social and economic activities. The annual cost of excess travel in U.S.A. has been estimated approximately 45 billion USD \hyperref[b68]{[68]} and the turnover of transportation of goods in Europe is approximately 168 billion USD per year. In United Kingdom, France and Denmark transportation represents approximately 15\%, 9\% and 15\% of national expenditures respectively \hyperref[b70]{[70]}. It is well known fact that the vehicle routing problem is a combinatorial optimization and integer programming problem in which service to finite number of customers with a fleet of vehicles is being done. Vehicle routing problem was proposed by Dantzig and Ramser in 1959. Vehicle routing problem is an important optimization problem in the fields of distribution, transportation, and logistics. In Vehicle Routing problem, goods have to be delivered to the customers who have placed orders for such goods in such a way so that the total cost of the delivering of goods to the customers can be minimized. In VRP each and every customer has a given demand and no any vehicles can service more customers than its predefined capacity. Many algorithms have been designed by researchers for searching for good solutions to the problem, but no any polynomial time algorithms have been designed which can give the exact solution of Vehicle Routing problem with time windows in the polynomial time in the worst case. There are several variations of the vehicle routing problems. In Vehicle Routing Problem with Pickup and Delivery, a large number of goods have to be moved from certain pickup locations to other delivery locations and the goal is to find optimal routes for vehicles to visit the pickup and drop-off locations so that the cost of delivering the goods to the different locations can be minimmized. In Vehicle Routing Problem with LIFO pinciple, a large number of goods have to be moved from certain pickup locations to other delivery locations and the goal is to find optimal routes for vehicles to visit the pickup and drop-off locations so that the cost of delivering the goods to the different locations can be minimmized with the restriction of the item being delivered must be that item most recently picked up. The benefit of this scheme over the previous scheme is the reduction of the loading and unloading times at delivery locations because there is no need to temporarily unload items. In Vehicle Routing Problem with Time Windows, there are n numbers of cities. Each and every city has a particular time windows [R (v), D (v)]. Where R (v) represents the releasing time for a particular vertex and D(v) represents the deadline for a particular vertex and the goal is to visit the maximum number of cities with in their time windows. Time windows are when they can be considered non biding for penalty cost. Time windows are called hard when they cannot be violated, i.e. if any vehicle reaches to a particular city too early so it must wait unless and until the time windows opens and the vehicle is not allowed to arrive late. In Capacitated Vehicle Routing Problem, the vehicles have limited capacity of the goods that must be delivered. In Capacitated Vehicle Routing Problem with time windows [R(v),D(v)], the vehicles have limited capacity of the goods that must be delivered. The most important application of VPRTW includes deliveries to supermarkets, industrial refuse collection, routing of school bus, security patrol services, urban newspaper distribution etc. The Vehicle Routing Problem with Time Windows has already been studied in the literature of Operations Research ( \hyperref[b0]{[1,}\hyperref[b9]{10]}). Different heuristics \hyperref[b8]{[9,}\hyperref[b16]{17,}\hyperref[b17]{18,}\hyperref[b18]{19]} like Simulated Annealing, local search, Genetic algorithms, cutting plane and branch and bound methods \hyperref[b19]{[20,}\hyperref[b13]{14,}\hyperref[b15]{16]} have been proposed to get the optimal solution of this problem. For general graphs, when there are a constant number of different time windows Chekuri and Kumar \hyperref[b7]{[8]} gave a constant-factor T (MDVRP) customers get their deliveries from several depots. In VRP with Time Windows [71] each and every customer has time window (R[v], D[v]) where D  {\ref [v]} represents the deadline for a particular customer while R[v] represents the releasing time for a particular customer and the goal is to visit the maximum number of customers in their time windows (R[v], D  {\ref [v]}). In Stochastic VRP (SVRP) any customer may have a random behavior. In Periodic VRP (PVRP) delivery to the customer is being done in some days. In Split Delivery VRP (SDVRP) several vehicles serve a customer. In the split delivery vehicle routing problem (SDVRP) there is no any restriction of visiting each and every customer exactly visited once.\par
Additionally, the demand of each and every customer may be greater than the capacity of the vehicles. It is well known fact that the SDVRP is NP-hard problem, even under restricted conditions on the costs, when each and every vehicle have a capacity greater than two, But it can be solved in the time complexity of polynomial time when the vehicles have a maximum capacity of two. The cost saving that which can be obtained by allowing split deliveries can be up to 50\% of the cost of the optimal solution of the VRP.\par
The variant of the VRP  {\ref [71]} in which the demand of a customer may be greater than the vehicle capacity, but vehicle has to serve every customer minimum number of the possible time. The cost saving which can be obtained by allowing more than the minimum number of required visits to each and every customer to be served by vehicle can be again up to 50\%. Simple heuristics that serve the customers with demands greater than the vehicle capacity by full load out-andback trips until the demands become less than the vehicle capacity may be quite far from the optimal solution.\par
Three heuristic methods [71] have been already proposed for the solution of the SDVRP: The local search, a simple and effective tabu search algorithm and a sophisticated heuristic which uses the information collected during the tabu search, builds promising routes and solves MILP models to decide which routes to use and how to serve the customers through those routes to obtain the solution which is close to the optimal solution. The heuristics will be compared on a set of benchmark instances.\par
In VRP with Backhauls (VRPB) vehicle must pick something up from the customer after all deliveries are done to the customers. VRP with Backhauls (VRPB) is also known as the linehaul-backhaul problem which is an extension of the Capacitated VRP (CVRP) where the customer set is partitioned into two subsets. The first subset contains the linehaul customers; each requires a given quantity of product which has to be delivered. The second subset contains the backhaul customers, where a given quantity of inbound product must be picked up. This customer partition is extremely frequent in practical situations. Grocery industry is a common example, where supermarkets and shops are the linehaul customers and grocery suppliers are the backhaul customers. It has been widely recognized that in this mixed distribution-collection context a significant saving in transportation costs can be achieved by visiting backhaul customers in distribution routes. More precisely, the VRPB [71] can be stated as the problem of determining a set of vehicle routes visiting all customers, and (a) each vehicle performs exactly one route; (b) each route starts as well as finishes at the depot; (c) for each route the total load associated with linehaul and backhaul customers should never exceed, separately, the vehicle capacity; (d) on each route the backhaul customers, are visited after all linehaul customers; and (e) the total distance traveled by the vehicles to serve the customers is minimized. The constraint (d) is practically motivated by the fact that vehicles are rear loaded which proves that the onboard load rearrangement required by a mixed service is difficult to carry out at customer locations. The most important reason is that, in many applications, line haul customers have a higher service priority as compared to backhaul customers. In VRP with Pick-Ups and Deliveries (VRPPD) the vehicle picks something up and delivers it to the customer. There are two sets of decision variables x and s. For ?j, i?n+1, j?0 and each vehicle each edge (I,j) where i k we define x ijk as If V[72] represents set of vehicles and all vehicles are considered to be identical. C represents set of customers. G=(N, A) represents directed graph where N represents the set of vertices of graph while E represents the set of edges of graph. This particular directed graph consists of |C|+2 number of vertices, where customers are denoted 1,2,3,????,n and the depot is represented by the vertex "0"(the starting depot) and the vertex "n+1"(the returning depot). N is the set of vertices. There is no edge ending at the vertex "0" or originating from the vertex "n+1". c ij ( where i?j) represents the cost of traveling from the vertex I to the vertex j. t ij ( where i?j) represents the service time at the customer i. Each vehicle has a capacity q and each customer i has a demand d i . Each and every customer has a time window [a i , b i ] and a vehicle must arrive at the customer before b i . If any vehicle arrives to the customer before the time windows opens, that vehicle has to be wait until ai to service the customer. The time windows for both depots are assumed to be identical to [a 0 ,b 0 ] which represents the scheduling horizon. The vehicle cannot leave the depot before a 0 and must The decision variable s ik is defined for each and vertex i and each vehicle k and denoted the time when the vehicle k starts to service the customer i. When the vehicle k does not service to the customer i, sik has no meaning and consequently its value is considered irrelevant. As we have assumed a 0 =0 and therefore s 0k =0 for all k. The goal in the case of VRPTW is to design a set of routes that minimizes the total cost, such that 1, if vehicle k drives directly from vertex i to the vertex The above informal definition of VRPTW can be stated mathematically as a multicommodity network flow problem with time windows and the capacity constraints:\par
The main goal of the objective function (  {\ref 1}) is to minimize the total travel cost. The constraint (2) ensures that each customer is visited exactly once while constraint (3) ensures that a vehicle can only be loaded up to its capacity. Equations 4 indicated that each and every vehicle must leave the depot 0. Equation \hyperref[formula_0]{5}indicates that when a vehicle arrives at a customer it must leave for another destination. Equation \hyperref[formula_1]{6}indicates that all vehicles must arrive at the depot n+1. Inequality \hyperref[b6]{(7)} indicates the relationship between the departure time of vehicle from the customer and its immediate successor. Constraint \hyperref[b7]{(8)} indicates the observation of time windows. Integrality constraints are shown by \hyperref[b8]{(9)}. The model for the representation of VRPTW can also incorporate a constraint giving an upper bound on the number of vehicles, as is the case in Desrosiers, Dumas, Solomon and Soumis \hyperref[b59]{[59]}. 
\section[{III. VEHICLE ROUTING PROBLEM WITH TIME WINDOWS IS NP COMPLETE PROBLEM}]{III. VEHICLE ROUTING PROBLEM WITH TIME WINDOWS IS NP COMPLETE PROBLEM}\par
Sorting algorithms like selection sort, bubble sort, insertion sort are known as quadratic sorting because these algorithms have time complexity of O(n 2 ) in the worst case where n is the size of input. Sorting algorithms like counting sort, radix sort and bucket sort have linear time complexity in the worst case So these algorithms are known as sorting in linear time. It is well known fact that all problems cannot be solved in polynomial time in the worst case. For example, Turing's famous "Halting Problem," which cannot be solved by any computer, no matter how much time is provided. Those problems that can be solved, but in time O(n k ) for any constant k are known as tractable problems or easy problems. For example sorting algorithms like selection sort, bubble sort, insertion sort, counting sort, radix sort and bucket sort can give sorted output in the time complexity of polynomial time so sorting problems are tractable problems or easy problems. Those problems that can not be solved, in polynomial time O(n k ) for any constant k but they require super-polynomial time for their executions are known as intractable problems or hard problems. No polynomial-time algorithm has yet been discovered for an NP-complete problem which can solve the problem in the polynomial time in the worst case nor anyone has been able to prove that no polynomial-time algorithm can exist for any one of NPcomplete problems. So P ? NP question has been one of the deepest, most perplexing open research problems in theoretical computer science since it was first proposed in 1971.\par
The class P consists of those problems which can be solved in polynomial time in the worst case. More specifically, they are problems that can be solved in time O(n k ) for some constant k, where n is the size of the input to the problem. Problems like sorting problem, searching problems are in class P. The class NP consists of those problems that are "verifiable" in polynomial time. If a "certificate" of a solution is being given, then we could verify that the certificate is correct in time polynomial in the size of the input to the problem. x ijk = \{ 1, if vehicle k drives directly from vertex i to the vertex 0, otherwise. min? ? ?c ij x ijk such that (1) As it well known fact that approximation algorithms give the approximation result which is close to the optimal value to a particular problem. Most of the problems of practical significance are NP-complete but we cannot avoid them. There are three approaches to getting around NP-completeness of the problems. First, if the size of inputs is small, an algorithm which has exponential running time may be a satisfactory algorithm to solve a problem. Second, we may isolate those special cases that are solvable in polynomial time. Third, we can find out the solution which is close to the optimal solution of the problem and that solution can be easily found out with the help of the polynomial time approximation algorithm. Suppose there is an optimization problem in which each potential solution has a positive cost. It is well known fact that the optimization problem can be divided in the two parts.k?V i?N j?N ? ?x ijk =1 ? i? C (2) k?V j?N ? d i ?x ijk ?q ? k? V (3) i?C j?N ?x 0jk =1 ? k? V (4) j?N ? x ihk -?x hjk =0 ? h? C, ? k? V, (\textbf{5}) i?N j?N ?x i,n+1,k =1 ? k? V\textbf{(6}\par
The maximization problem and the minimization problem. In maximization problem, we want to maximize the value of output to a problem and in minimization problem we want to minimize the value of output. If the size of the input of a problem is n. Let C* be the cost as being obtained by optimal solution of a problem and C is the cost as being obtained by approximation algorithm \hyperref[b49]{[49]}. Then the approximation ratio ? (n) is defined as Maximum The definitions of approximation ratio and of ? (n)-approximation algorithm apply for both minimization and maximization problems. It is well known fact that for a maximization problem, 0 < C ? C*and the ratio C*/C gives the ratio by which the cost of optimization algorithm is larger than that of the cost of the approximate solution. Also, for a minimization problem, 0 < C* ? C, and the ratio C/C* gives the ratio by which the cost of the approximate solution is greater than the cost of an optimal solution. Since all solutions are assumed to have positive cost, these ratios are always well defined. Also the approximation ratio of an approximation algorithm \hyperref[b49]{[49]} is never less than 1. For some problems, there are polynomial-time approximation algorithms which have small constant approximation ratios, but for other problems, the best known polynomial-time approximation algorithms have approximation ratios that grow as functions of the size of input of the problem.\par
An approximation scheme for an optimization problem \hyperref[b49]{[49]} is defined as an approximation algorithm which takes as input an instance of the problem, along 
\section[{IV. COMPARISON OF APPROXIMATION ALGORITHMS FOR VEHICLE ROUTING PROBLEM}]{IV. COMPARISON OF APPROXIMATION ALGORITHMS FOR VEHICLE ROUTING PROBLEM}\par
Arkin, Mitchell and Narasimhan \hyperref[b26]{[26]} gave first non-trivial (2+?) approximation algorithm for orienteering points in the Euclidean plane. A. Blum, S. Chawla, D. Karger, T. Lane, A. Meyerson, and M. Minkoff \hyperref[b5]{[6]} gave the first approximation algorithm with a ratio of 4 for points in arbitrary metric spaces. After then N. Bansal, A. Blum., S. Chawla, and A. Meyerson \hyperref[b23]{[24]} designed a new approximation algorithm for orienteering problem which improved this ratio to 3. A related problem to the orienteering problem is the minimum excess problem as being defined in \hyperref[b5]{[6]}. In \hyperref[b5]{[6]} the pseudo code for the orienteering problem depends upon the pseudo code of the min-excess problem. Also the min-excess problem can be approximated using algorithms for the k-stroll problem. In the k-stroll problem, the goal is to find a minimum length walk from source vertex s to target vertex t that visits at least k vertices. It is well known fact that k-stroll problem and the orienteering problem are equivalent to each other in terms of exact solvability because in both of these problems, the mission is to find the minimum length path from the source vertex s to the destination vertex t which covers maximum number of distinct vertices. The results in \hyperref[b5]{[6,}\hyperref[b23]{24]} are based on existing approximation algorithms for k-stroll in undirected graphs. N. Bansal, A. Blum, S. Chawla and A. Meyerson. \hyperref[b23]{[24]} gave approximation algorithm for Deadline-TSP which has the time complexity of O(logn) and they gave approximation algorithm for Vehicle Routing problem with time windows which has time complexity of O (log n) . Further they gave a bicriteria approximation algorithm for Deadline-TSP as well as for Vehicle Routing problem with time windows. If ? > 0, their bicriteria approximation algorithm produces a log (1/?) approximation, while deadlines exceeds by a factor of (1+?). C. Chekuri, N. Korula, and M. Pal \hyperref[b42]{[42]} designed (2+?) approximation for orienteering in undirected graphs, which improves upon the 3-approximation of \hyperref[b23]{[24]}. C. Chekuri, N. Korula, and M. Pal \hyperref[b42]{[42]} designed an improved O (log OPT) approximation for orienteering in directed graphs, where OPT<= n is the number of vertices visited by an optimal solution which improves over the previously result. Further it was being proved that for the time-window problem, an O (log OPT) approximation can be easily achieved even for directed graphs if the algorithm is allowed quasi-polynomial time.\par
If D(v) represents the deadline for a particular vertex v and R(v) represents the releasing time for a particular vertex v. Let L(v) = D(v) ? R(v) denotes the length of the directed graphs. C. Chekuri and N. Korula. Designed an O(alog Lmax) approximation when R(v) and D(v) both are integer valued for each v and they designed an O(a max\{log OPT, log Lmax/Lmin \}) approximation. They also designed an O(log Lmax/Lmin) approximation when there is no starting vertex and terminating vertex is being defined. Early surveys of solution techniques for the VRPTW \hyperref[b67]{[67]} can be found in Golden and Assad \hyperref[b57]{[57]}, Desrochers et al. \hyperref[b58]{[58]}, and Chiang \& Russell \hyperref[b66]{[66]}. Desrosiers et al. \hyperref[b59]{[59]} and Cordeau et al. \hyperref[b60]{[60]} gave exact solution techniques for VRPTW. The complete explanation of these exact techniques can be found in Larsen \hyperref[b61]{[61]} and Cook and Rich \hyperref[b62]{[62]}. Researchers designed different approximation algorithms for VRPTW based on different designing techniques like Dynamic programming, Simulated Annealing etc. Fleischmann \hyperref[b63]{[63]} and Taillard et al. \hyperref[b64]{[64]} have used heuristic for VRP without time windows. In Taillard et al. \hyperref[b64]{[64]}, have designed solutions to the classical vehicle routing problem by using a TS heuristic. The routes which are obtained combine to produce workdays for the vehicles by solving a bin packing problem, an idea which is previously introduced in Fleischmann \hyperref[b63]{[63]}. Compbell and Savelsbergh \hyperref[b65]{[65]} has reported about insertion heuristics which can efficiently handle different types of constraints including time windows and multiple uses of vehicles. Compbell and Savelsbergh \hyperref[b65]{[65]} introduced the home delivery problem which is the variant of Vehicle Routing problem and it is more closely related to realworld applications. Current VRPTW heuristics can be categorized as follows: (i) construction heuristics, (ii) improvement heuristics and (iii) meta-heuristics. Construction heuristics are sequential or parallel algorithms which aims at designing initial solutions to routing problems that can be easily improved upon by meta-heuristics or improvement heuristics. Sequential algorithms are being used to build a route for each vehicle, one after another with the help of decision functions for the selection of the customer which has to be inserted in the route and the insertion position within the route. Parallel algorithms build the routes for all vehicles in parallel by using a pre-computed estimate of the number of routes. As it has been already discussed that the best known polynomial time approximation ratios for Vehicle Routing problem with time windows are O (log OPT) for undirected graphs and O (log OPT) in directed graphs.\par
In this paper, a study on variants of vehicle routing problem is being done along with the difference in the approximation ratios of approximation algorithm as being given by researchers and it is found that Researchers are continuously applying their best efforts to design new approximation algorithms which have better approximation ratio as compared to the previously existing approximation algorithms. Researchers are proposing new heuristics for variants of Vehicle Routing problems. \begin{figure}[htbp]
\noindent\textbf{}\includegraphics[]{image-2.png}
\caption{\label{fig_0}}\end{figure}
    \begin{figure}[htbp]
\noindent\textbf{} \par 
\begin{longtable}{P{0.85\textwidth}}
Any problem will be lie in the class NPC-and we refer to\\
it as being NP-complete-if the problem is in NP and is\\
as "hard" as any problem in NP. The first NP complete\\
problem is the circuit-satisfiability problem, in which we\\
are given a Boolean combinational circuit which is being\\
consists of AND, OR, and NOT gates and the question\\
is to know whether there is any set of Boolean inputs to\\
this circuit that causes its output to be 1.It is well known\\
fact that the concept of NP-complete was firstly\\
introduced by Stephen Cook in 1971 in a paper entitled\\
"The complexity of theorem-proving procedures" on\\
pages 151-158 of the Proceedings of the 3rd Annual\\
ACM Symposium on Theory of Computing, Although the\\
term NP-complete did not appear anywhere in his\\
paper. At that conference, there was a debate among\\
the computer researchers about whether NP-complete\\
problems could be solved in polynomial time on a\\
deterministic Turing machine or not. At that time, John\\
Hopcroft brought everyone at the conference to a\\
consensus that the question of whether NP-complete\\
problems are solvable in polynomial time or not must be\\
put off to be solved at some later time ,since nobody\\
had any formal proofs for their claims. No any scientist\\
has yet been able to prove conclusively whether NP-\\
complete problems are solvable in polynomial time or\\
not. Also The Clay Mathematics Institute is offering a\\
US\$1 million reward to any researcher who has a formal\\
proof that P=NP or that P?NP. Researchers are\\
continuously doing hard work in this field to give the\\
formal prove of either P=NP or P?NP but did not\\
achieve success in this field till date. Also In the\\
celebrated Cook-Levin theorem, Cook proved that the\\
Boolean satisfiability problem is NP-complete problem.\\
In 1972, Richard Karp proved that several other\\
problems are also NP-complete; So it shows that there\\
is a class of NP-complete problems. Satisfiability,0-1\\
Integer Programming, Clique, Set ,Vertex Cover, Set\\
Covering, Feedback Node Set ,Feedback Arc Set,\\
Directed Hamilton Circuit Undirected Hamilton Circuit j?N ,Satisfiability With At Most 3 Literals Per Clause, xijk (sik+ tij-sjk)?0 ? i,j?N, ? k?V (7) Chromatic Number ,Cover, Exact, Hitting, Steiner Tree,\\
(8) 3-Dimensional Matching Knapsack (Karp's definition of Knapsack is closer to Subset sum), Job Sequencing, ai?sik?bi ? i,?N, ? k?V Partition Max Cut. After then, thousands of other\end{longtable} \par
  {\small\itshape [Note: xijk ?\{0,1\} ? i,j?N, ? k?V\hyperref[b8]{(9)} Hamiltonian-cycle problem is in class NP because In Hamiltonian-cycle problem, directed graph G = (V, E) is being given, and then certificate of this problem would be a sequence problems have been shown to be NP-complete problems by reductions from other problems previously shown to be NP-complete. There is no any algorithm which can solve Vehicle Routing Problem with time windows in the polynomial time in the worst case. It is well known fact that Vehicle Routing Problem with time windows is NP complete problem.]} 
\caption{\label{tab_1}}\end{figure}
 			\footnote{© 2011 Global Journals Inc. (US) Towards The Solution of Variants of Vehicle Routing Problem} 		 		\backmatter  			  				\begin{bibitemlist}{1}
\bibitem[Aho et al. ()]{b51}\label{b51} 	 		\textit{},  		 			A V Aho 		,  		 			J E Hopcroft 		,  		 			J D Ullman 		.  	 	 		\textit{Data Structures and Algorithms}  		1984. Addison-Wesley.  	 
\bibitem[Golden et al. ()]{b57}\label{b57} 	 		\textit{},  		 			Bruce L Golden 		,  		 			Arjang A Assad 		,  		 			Edward A Wasil 		.  	 	 		\textit{Introduction. Computers \& OR}  		1986. 13  (2-3)  p. .  	 
\bibitem[Hall ()]{b25}\label{b25} 	 		\textit{},  		 			Prentice Hall 		.  		1993. Upper Saddle River, New Jersey.  	 
\bibitem[Desrosiers ()]{b59}\label{b59} 	 		\textit{},  		 			Dumas Desrosiers 		.  		1995.  	 
\bibitem[Arora and Karakostas ()]{b27}\label{b27} 	 		‘A 2 + ? approximation algorithm for the k-MST problem’.  		 			S Arora 		,  		 			G Karakostas 		.  	 	 		\textit{Preliminary version in Proc. of ACM-SIAM SODA},  				2006. 2000. 107 p. .  	 
\bibitem[Karuno and Nagamochi ()]{b14}\label{b14} 	 		‘A 2-approximation algorithm for the multi-vehicle scheduling problem on a path with release and handling times’.  		 			Y Karuno 		,  		 			H Nagamochi 		.  	 	 		\textit{Proceedings of the European Symposium on Algorithms},  				 (the European Symposium on Algorithms)  		2001. p. .  	 
\bibitem[Garg ()]{b32}\label{b32} 	 		‘A 3-approximation for the minimum tree spanning k vertices’.  		 			N Garg 		.  	 	 		\textit{Proceedings of the 37th Annual Symposium on Foundations of Computer Science},  				 (the 37th Annual Symposium on Foundations of Computer Science)  		1996. IEEE Computer Society. p. .  	 
\bibitem[Blum et al. ()]{b33}\label{b33} 	 		‘A Constant-Factor Approximation Algorithm for the k-MST Problem’.  		 			R Blum 		,  		 			S Ravi 		,  		 			Vempala 		.  	 	 		\textit{Preliminary version in Proc. Of ACMSTOC},  				1999. 1996. 58 p. .  	 
\bibitem[Goemans and Williamson ()]{b39}\label{b39} 	 		‘A general approximation technique for constrained forest problems’.  		 			M X Goemans 		,  		 			D P Williamson 		.  	 	 		\textit{SIAM Journal on Computing}  		1995. 24 p. .  	 
\bibitem[Desrochers et al. ()]{b8}\label{b8} 	 		‘A new optimization algorithm for the vehicle routing problem with time windows’.  		 			M Desrochers 		,  		 			J Desrosiers 		,  		 			M Solomon 		.  	 	 		\textit{Operations Research}  		1992. 40 p. .  	 
\bibitem[Cook and Rich ()]{b62}\label{b62} 	 		\textit{A Parallel Cutting-Plane Algorithm for the Vehicle Routing Problems with Time Windows},  		 			W Cook 		,  		 			J L Rich 		.  		1999. Houston, U.S.A.  		 			Department of Computational and Applied Mathematics, Rice University 		 	 	 (Working Paper) 
\bibitem[Chekuri ()]{b36}\label{b36} 	 		‘A recursive greedy algorithm for walks in directed graphs’.  		 			C Chekuri 		,  		 			M 		.  	 	 		\textit{Proceedings of the 46th Annual Symposium on Foundations of Computer Science},  				 (the 46th Annual Symposium on Foundations of Computer Science)  		2005. IEEE Computer Society. p. .  	 
\bibitem[Allahverdi et al. ()]{b1}\label{b1} 	 		‘A review of scheduling research involving setupconsiderations’.  		 			J Allahverdi 		,  		 			T Gupta 		,  		 			Aldowaisan 		.  	 	 		\textit{Omega, Int. Journal of Management Science}  		1999. 27 p. .  	 
\bibitem[Wisner and Siferd ()]{b21}\label{b21} 	 		‘A survey of u.s. manufacturing practices in make-to-order machine shops’.  		 			J Wisner 		,  		 			S Siferd 		.  	 	 		\textit{Production and Inventory Management Journal}  		1995. 1 p. .  	 
\bibitem[Jordan ()]{b12}\label{b12} 	 		‘A two-phase genetic algorithm to solve variants of the batch sequencing problem’.  		 			C Jordan 		.  	 	 		\textit{International Journal of Production Research (UK)}  		1998. 36  (3)  p. .  	 
\bibitem[Cordeau et al. ()]{b60}\label{b60} 	 		‘A unified tabu search heuristic forvehicle routing problems with time windows’.  		 			G Cordeau 		,  		 			A Laporte 		,  		 			Mercier 		.  	 	 		\textit{Journal of the Operational Research Society}  		2001. 52 p. .  	 
\bibitem[Ahuja et al.]{b24}\label{b24} 	 		 			R K Ahuja 		,  		 			T L Magnanti 		,  		 			J B Orlin 		.  		\textit{Network Flows: Theory, Algorithms, and Applications},  				 	 
\bibitem[G-Brassard and Bratley ()]{b56}\label{b56} 	 		\textit{Algorithmics: Theory and Practice},  		 			P G-Brassard 		,  		 			Bratley 		.  		1988. Prentice-Hall.  	 
\bibitem[Thangiah et al. ()]{b19}\label{b19} 	 		‘Algorithms for the vehicle routing problems with time deadlines’.  		 			S R Thangiah 		,  		 			I H Osman 		,  		 			R Vinayagamoorthy 		,  		 			T Sun 		.  	 	 		\textit{American Journal of Mathematical and Management Sciences}  		1993. 13  (3\&4)  p. .  	 
\bibitem[Chekuri ()]{b37}\label{b37} 	 		‘An O(log n) Approximation for the Asymmetric Traveling Salesman Path Problem Theory of Computing’.  		 			C Chekuri 		,  		 			M 		.  	 	 		\textit{Preliminary version in Proc. of APPROX},  				2007. 2005. 3 p. .  	 
\bibitem[Banachowski et al. ()]{b53}\label{b53} 	 		\textit{Analysis of Algorithms and Data Structures},  		 			L Banachowski 		,  		 			A Kreczmar 		,  		 			W Rytter 		.  		1991. Addison-Wesley.  	 
\bibitem[Bansal et al. ()]{b23}\label{b23} 	 		‘Approximation algorithms for deadline-TSP and vehicle routing with time-windows’.  		 			N Bansal 		,  		 			A Blum 		,  		 			S Chawla 		,  		 			A Meyerson 		.  	 	 		\textit{Proceedings of the 36th Annual ACM Symposium on Theory of Computing},  				 (the 36th Annual ACM Symposium on Theory of ComputingNew York, NY, USA)  		2004. ACM. p. .  	 
\bibitem[Blum et al. ()]{b5}\label{b5} 	 		‘Approximation algorithms for orienteering and discounted-reward tsp’.  		 			S Blum 		,  		 			D Chawla 		,  		 			T Karger 		,  		 			A Lane 		,  		 			M Meyerson 		,  		 			Minkoff 		.  	 	 		\textit{Proceedings of the 44th Foundations of Computer Science},  				 (the 44th Foundations of Computer Science)  		2003.  	 
\bibitem[Frederickson and Wittman ()]{b7}\label{b7} 	 		‘Approximation algorithms for the traveling repairman and speeding deliveryman problems with unit-time windows’.  		 			G N Frederickson 		,  		 			B Wittman 		.  	 	 		\textit{Proceedings of APPROX-RANDOM},  				 (APPROX-RANDOM)  		2007. 4627 p. .  	 
\bibitem[Bruno and Downey ()]{b6}\label{b6} 	 		‘Complexity of task sequencing with deadlines, set-up times and changeover costs’.  		 			J Bruno 		,  		 			P Downey 		.  	 	 		\textit{SIAM Journal on Computing}  		1978. 7  (4)  p. .  	 
\bibitem[Baase ()]{b52}\label{b52} 	 		\textit{Computer Algorithms: Introduction to Design and Analysis},  		 			S Baase 		.  		1988. Addison-Wesley.  	 
\bibitem[Campbell and Savelsbergh ()]{b65}\label{b65} 	 		‘Efficient insertion heuristics for vehicle routing and scheduling problems’.  		 			A M Campbell 		,  		 			M Savelsbergh 		.  	 	 		\textit{Transportation Science}  		2004. 38  (3)  p. .  	 
\bibitem[King and Mast ()]{b68}\label{b68} 	 		‘Excess Travel: Causes, Extent and Consequences’.  		 			G F King 		,  		 			C F Mast 		.  	 	 		\textit{Transportation Research}  		1997. Record1111. p. .  	 
\bibitem[Horowitz and Sahni ()]{b48}\label{b48} 	 		\textit{Fundamental of Computer Algorithms},  		 			E Horowitz 		,  		 			S Sahni 		.  		1982. Computer Science Press.  	 
\bibitem[Tan et al. ()]{b17}\label{b17} 	 		‘Heuristic methods for vehicle routing problem with time windows’.  		 			K Tan 		,  		 			L Lee 		,  		 			K Zhu 		.  	 	 		\textit{Proceedings of the 6th AI and Math},  				 (the 6th AI and Math)  		2000.  	 
\bibitem[Chekuri et al.]{b42}\label{b42} 	 		\textit{Improved Algorithms for Orienteering and Related Problems},  		 			C Chekuri 		,  		 			N Korula 		,  		 			M P´al 		.  		 	 
\bibitem[Awerbuch et al. ()]{b28}\label{b28} 	 		‘Improved approximation guarantees for minimumweight k-trees and prizecollecting salesmen’.  		 			B Awerbuch 		,  		 			Y Azar 		,  		 			A Blum 		,  		 			S Vempala 		.  	 	 		\textit{Proc. of ACM STOC},  				 (of ACM STOC)  		1998. 1995. 28 p. .  	 
\bibitem[Awerbuch et al. ()]{b3}\label{b3} 	 		‘Improved approximation guarantees for minimumweight k-trees and prizecollecting salesmen’.  		 			B Awerbuch 		,  		 			Y Azar 		,  		 			A Blum 		,  		 			S Vempala 		.  	 	 		\textit{Siam J. Computing}  		1999. 28  (1)  p. .  	 
\bibitem[Cormen et al. ()]{b49}\label{b49} 	 		\textit{Introduction to Algorithms},  		 			T Cormen 		,  		 			C Leiserson 		,  		 			R Rivest 		.  		1991. MIT Press.  	 
\bibitem[Tel]{b55}\label{b55} 	 		\textit{Introduction to Distributed Algorithms},  		 			G Tel 		.  		 		 			Cambridge Univ. Press1995 		 	 
\bibitem[Savelsbergh ()]{b18}\label{b18} 	 		‘Local search for routing problems with time windows’.  		 			M Savelsbergh 		.  	 	 		\textit{Annals of Operations Research}  		1985. 4 p. .  	 
\bibitem[Chekuri and Kumar ()]{b35}\label{b35} 	 		‘Maximum coverage problem with group budget constraints and applications’.  		 			C Chekuri 		,  		 			A Kumar 		.  	 	 		\textit{Proceedings of APPROXRANDOM},  				 (APPROXRANDOM)  		2004. p. .  	 
\bibitem[Lawler et al. ()]{b44}\label{b44} 	 		‘Nagarajan and R. Ravi. Poly-logarithmic approximation algorithms for directed vehicle routing problems’.  		 			E L Lawler 		,  		 			A H G Kan 		,  		 			J K Lenstra 		,  		 			D B Shmoys 		.  	 	 		\textit{Proceedings of APPROXRANDOM},  				 (APPROXRANDOM)  		1985. 2007. John Wiley \& Sons Inc. 44 p. .  	 	 (The Traveling salesman problem: a guided tour of combinatorial optimization) 
\bibitem[Bar-Yehuda et al. ()]{b4}\label{b4} 	 		‘On approximating a geometric prize-collecting traveling salesman’.  		 			R Bar-Yehuda 		,  		 			G Even 		,  		 			S Shahar 		.  	 	 		\textit{Proceedings of the European Symposium on Algorithms},  				 (the European Symposium on Algorithms)  		2003.  	 
\bibitem[Bar-Yehuda et al. ()]{b31}\label{b31} 	 		‘On approximating a geometric prize-collecting traveling salesman problem with time windows’.  		 			R Bar-Yehuda 		,  		 			G Even 		,  		 			S Shahar 		.  	 	 		\textit{Preliminary version in Proc. Of ESA},  				2005. 2003. 55 p. .  	 
\bibitem[Frieze et al. ()]{b30}\label{b30} 	 		‘On the worst-case performance of some algorithms for the asymmetric traveling salesman problem’.  		 			A M Frieze 		,  		 			G Galbiati 		,  		 			F Maffioli 		.  	 	 		\textit{Networks}  		1982. 12  (1)  p. .  	 
\bibitem[Larsen ()]{b61}\label{b61} 	 		\textit{Parallelization of the Vehicle Routing Problem with TimeWindows},  		 			J Larsen 		.  		1999. Lyngby, Denmark.  		 			Institute of Mathematical Modelling, Technical University of Denmark 		 	 	 (Ph.D. thesis) 
\bibitem[Chaudhuri et al. ()]{b34}\label{b34} 	 		‘Paths, trees, and minimum latency tours’.  		 			K Chaudhuri 		,  		 			B Godfrey 		,  		 			S Rao 		,  		 			K Talwar 		.  	 	 		\textit{44th Annual Symposium on Foundations of Computer Science},  				2003. IEEE Computer Society. p. .  	 
\bibitem[Crainic and Laporte ()]{b69}\label{b69} 	 		‘Planning Models for Freight Transportation’.  		 			T G Crainic 		,  		 			G Laporte 		.  	 	 		\textit{European Journal of Operational Research}  		1997. 97 p. .  	 
\bibitem[Proc. of ACM-SIAM SODA (2008)]{b43}\label{b43} 	 		\textit{Proc. of ACM-SIAM SODA},  				 (of ACM-SIAM SODA)  		January 2008.  	 
\bibitem[Reingold et al. ()]{b0}\label{b0} 	 		 			E M Reingold 		,  		 			J Nievergelt 		,  		 			N Deo 		.  		\textit{Combinatorial Algorithms: Theory and Practice},  				1977. Prentice-Hall.  	 
\bibitem[Arkin et al. ()]{b2}\label{b2} 	 		‘Resource-constrained geometric network optimization’.  		 			E M Arkin 		,  		 			J S B Mitchell 		,  		 			G Narasimhan 		.  	 	 		\textit{Symposium on Computational Geometry},  				1998. p. .  	 
\bibitem[Arkin et al. ()]{b26}\label{b26} 	 		‘Resource-constrained geometric network optimization’.  		 			E M Arkin 		,  		 			J S B Mitchell 		,  		 			G Narasimhan 		.  	 	 		\textit{Symposium on Computational Geometry},  				1998. p. .  	 
\bibitem[Garg ()]{b38}\label{b38} 	 		‘Saving an epsilon: a 2-approximation for the k-MST problem in graphs’.  		 			N Garg 		.  	 	 		\textit{Proceedings of the 37th Annual ACM Symposium on Theory of computing},  				 (the 37th Annual ACM Symposium on Theory of computing)  		2005. ACM. p. .  	 
\bibitem[Gravel et al. ()]{b11}\label{b11} 	 		‘Scheduling jobs in a alcan aluminium factory using a genetic algorithm’.  		 			M Gravel 		,  		 			W Price 		,  		 			C Gagn 		.  	 	 		\textit{International Journal of Production Research}  		2000. 38  (13)  p. .  	 
\bibitem[Chiang and Russell ()]{b66}\label{b66} 	 		‘Simulated annealing metaheuristics for the vehicle routing problem with time windows’.  		 			W Chiang 		,  		 			R A Russell 		.  	 	 		\textit{Annals of Operations Research}  		1996. 63.  	 
\bibitem[Tsitsiklis ()]{b20}\label{b20} 	 		‘Special cases of traveling salesman and repairman problems with time windows’.  		 			J Tsitsiklis 		.  	 	 		\textit{Networks}  		1992. 22 p. .  	 
\bibitem[Tsitsiklis ()]{b46}\label{b46} 	 		‘Special cases of traveling salesman and repairman problems with time windows’.  		 			J N Tsitsiklis 		.  	 	 		\textit{Networks}  		1992. 22  (3)  p. .  	 
\bibitem[Yang and Liao ()]{b22}\label{b22} 	 		‘Survey of scheduling research involving setup times’.  		 			W Yang 		,  		 			C Liao 		.  	 	 		\textit{International Journal of Systems Science}  		1999. 30  (2)  p. .  	 
\bibitem[Baeza-Yates (1995)]{b54}\label{b54} 	 		‘Teaching Algorithms’.  		 			R Baeza-Yates 		.  	 	 		\textit{IV Iberoamerican Congress on Computer Science Education}  		July 1995.  	 
\bibitem[Aho et al. ()]{b50}\label{b50} 	 		\textit{The Design and Analysis of Computer Algorithms},  		 			A V Aho 		,  		 			J E Hopcroft 		,  		 			J D Ullman 		.  		1974. Addison-Wesley.  	 
\bibitem[Golden et al. ()]{b10}\label{b10} 	 		‘The orienteering problem’.  		 			B Golden 		,  		 			L Levy 		,  		 			R Vohra 		.  	 	 		\textit{Naval Research Logistics}  		1987. 34 p. .  	 
\bibitem[Golden et al. ()]{b40}\label{b40} 	 		‘The orienteering problem’.  		 			B L Golden 		,  		 			L Levy 		,  		 			R Vohra 		.  	 	 		\textit{Naval Research Logistics}  		1987. 34  (3)  p. .  	 
\bibitem[Chen and Har-Peled ()]{b47}\label{b47} 	 		‘The orienteering problem in the plane revisited’.  		 			K Chen 		,  		 			S Har-Peled 		.  	 	 		\textit{Preliminary version in Proc. of ACM SoCG},  				2008. 2006. 38 p. .  	 
\bibitem[Kantor and Rosenwein ()]{b13}\label{b13} 	 		‘The orienteering problem with time windows’.  		 			M Kantor 		,  		 			M Rosenwein 		.  	 	 		\textit{Journal of the Operational Research Society}  		1992. 43 p. .  	 
\bibitem[Balas ()]{b29}\label{b29} 	 		‘The prize collecting traveling salesman problem’.  		 			E Balas 		.  	 	 		\textit{Networks}  		1989. 19  (6)  p. .  	 
\bibitem[Gutin and Punnen ()]{b41}\label{b41} 	 		\textit{The traveling salesman problem and its variations},  		 			G Gutin 		,  		 			A P Punnen 		.  		2002. Berlin: Springer.  	 
\bibitem[Fleischmann ()]{b63}\label{b63} 	 		\textit{The vehicle routing problem with multiple use of vehicles},  		 			B Fleischmann 		.  		1990. Universitat Hamburg, Germany.  	 	 (Working Paper. Fachbereich Wirtschaftswissenschaften) 
\bibitem[Toth and Vigo ()]{b45}\label{b45} 	 		 			P Toth 		,  		 			D Vigo 		.  		\textit{The vehicle routing problem. SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial Mathematics},  				 (Philadelphia PA)  		2001.  	 
\bibitem[Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms]{b70}\label{b70} 	 		\textit{Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms},  		 	 
\bibitem[Liong Choong Yeun ()]{b67}\label{b67} 	 		\textit{Vehicle Routing Problem: Models and Solutions Journal of Quality Measurement and Analysis},  		 			Liong Choong Yeun 		.  		2008. 4 p. .  	 	 (Wan Rosmanira Ismail, Khairuddin Omar2 \& Mourad Zirour) 
\bibitem[Taillard et al. ()]{b64}\label{b64} 	 		‘Vehicle routing with multiple use of vehicles’.  		 			E D Taillard 		,  		 			G Laporte 		,  		 			M Gendreau 		.  	 	 		\textit{Journal of the Operational Research Society}  		1996. 47 p. .  	 
\bibitem[Kolen et al. ()]{b15}\label{b15} 	 		‘Vehicle routing with time windows’.  		 			A R Kolen 		,  		 			H Kan 		,  		 			Trienekens 		.  	 	 		\textit{Operations Research}  		1987. 35 p. .  	 
\bibitem[Thangiah (ed.) ()]{b16}\label{b16} 	 		\textit{Vehicle Routing with Time Windows using Genetic Algorithms, Application Handbook of Genetic Algorithms: New Frontiers},  		 			S Thangiah 		.  		II. Lance Chambers (ed.)  		1995. CRC Press.  	 
\bibitem[Desrochers et al. ()]{b9}\label{b9} 	 		‘Vehicle routing with time windows: optimization and approximation’.  		 			M Desrochers 		,  		 			J Lenstra 		,  		 			M Savelsbergh 		,  		 			F Soumis 		.  	 	 		\textit{Vehicle Routing: Methods and Studies},  				 			B L Golden,  			A A Assad 		 (ed.)  		 (North-Holland, Amsterdam)  		1988. p. .  	 
\bibitem[Vehicle Routing with Time Windows: Optimization and Approximation -Desrochers, Lenstra]{b58}\label{b58} 	 		\textit{Vehicle Routing with Time Windows: Optimization and Approximation -Desrochers, Lenstra},  		 	 	 (et al. -1988) 
\end{bibitemlist}
 			 		 	 
\end{document}
