\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={Vehicle Routing Problem with Time Window Constrain using KMeans Clustering to Obtain the Closest Customer},
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{2022-01-14 (revised: 14 January 2022)}
\def\TheID{\makeatother }
\def\TheDate{2022-01-14}
\title{Vehicle Routing Problem with Time Window Constrain using KMeans Clustering to Obtain the Closest Customer}
\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]{Jai Keerthy Chowlur Revanna}
\author[2]{Nushwan Yousif B.Al-Nakash}
\renewcommand\Authands{ and }
\date{\small \em Received: 3 December 2021 Accepted: 31 December 2021 Published: 14 January 2022}
\maketitle
\begin{abstract}
In this paper, the problem statement is solving the Vehicle Routing Problem with Time Window constraint using the Ant Colony Algorithm with K-Means Clustering. In this problem, the vehicles must start at a common depot, pickup from various warehouses, deliver to the respective nodes within the time window defined by the customer and return back to the depot.The objectives defined are to reduce number of vehicles employed, the total logistics cost and to reduce carbon emissions. The mathematical model described in this paper has considered multiple pickup and multiple delivery points. The proposed solution of this paper aims to provide better and more efficient solution while minimizing areas of conflict so as to provide the best output on a large scale.
\end{abstract}
\keywords{ant colony optimization(ACO), k-means clustering, vehicle routing problem(VRP), time dependent vehicle routing problem(TDVRP).}
\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[{I. Introduction}]{I. Introduction}\par
ransportation is one of the primary requisites of civilization and this fact continues to be true even today. In today's world of quick and safe deliveries, there has been a need for better service, reduction of vehicles used, maximizing profit, reduction in travel time variation and reduction of overall travel cost. To define these problems together, the term Vehicle Routing Problems was coined. This problem deals with the supply chain of an organization. Transportation is the backbone of the logistics of any organization and it takes up about 40 to 50 \% of the total logistics cost, as stated in https://www.cogoport.com/blogs/transportcost (accessed on 11 October, 2021). This includes international and domestic transport, customs, all modes of transport such as air, water, land and so on. It can be inferred that transportation cost is a major and important factor in the supply chain of an organization, so its cost optimization becomes a necessity. The logistics branch of the organization must work on the management of transportation, deliver within customer provided time frames, competing with other organizations for better service and service rates effectively, handling unpredictable events and so on.\par
The world is witnessing the digital growth spurt and along with its influence on almost every sphere of life and nature. Integration of logistics and e-business will be a fruitful endeavor. This incorporation will lead to improvement in customer service, tracking, deliverance, time effectiveness as well as reduction in the overall cost.\par
Looking at the technical aspects of the Vehicle Routing Problem (VRP), there are initially p vehicles located at a depot that must deliver different amounts of supplies to q customers. Now, the VRP will aim to find the optimal route that a group of vehicles serve a group of users. This way a standard solution is obtained which contains all the routes that start and end at the depot, with the constraint that the goods are delivered within or before the time range set by the customer, capacity limit and the working time of the drivers are also considered. This paper will discuss how the Ant Colony Optimization with KMeans Clustering (ACO-KMeans) has been employed to minimize costs when delivering goods from depot to the customer within or before the time frame constraint set. The mathematical model defined in this paper will tackle and solve the problems related to distribution, e-logistics, retail networks and so on.\par
Dantzig and Ramser \hyperref[b0]{[1]} were the first ones to introduce the Vehicle Routing Problem in 1959. Their solution was based on Linear programming. It was a truck dispatching problem that dealt with the delivery of gasoline at gas stations. Later, \hyperref[b1]{[2]} Clarke and Wright came up with the savings method and it was termed as the Clarke-Wright algorithm. Their practical methodology gave better results than the Ramser-Dantzig algorithm. This was because the latter algorithm simply linked the customer pairs that were close to each other, which means that only distance constraint was considered, while the former not only considered the distance constraint, but they also reduced the distance rather than linking the two customers to different routes. Fast forward to 1992, Daskin and Malandraki came up with the time dependent vehicle routing problem (TDVRP) \hyperref[b2]{[3]}. Then another solution was introduced by Ichoua et al. \hyperref[b3]{[4]} which had a step function along with a piecewise linear function of time distribution which was fulfilling the FIFO (first in first out) principle, which was defined by T Jai Keerthy Chowlur Revanna * , Nushwan Yousif B.Al-Nakash ? , PhD Ahn et al. with this, several researches and studies popped up. Some were utilizing route construction savings method and an insertion method to solve incapacitated TDVRP(with/without time windows), some had heuristic solutions \hyperref[b7]{[8]}\hyperref[b8]{[9]}\hyperref[b9]{[10]}, some metaheuristic algorithms \hyperref[b4]{[5]}\hyperref[b5]{[6]}\hyperref[b6]{[7]} and others hyper heuristics \hyperref[b10]{[11]}.\par
Figure {\ref 1}. given below is a generalized view of how a VRP is solved.
\section[{Figure 1: General VRP solving method}]{Figure 1: General VRP solving method}\par
Many works of solving the VRP with the Time Window Constraint were inherited from the travelling salesman problem. The method used by the salesman to find the best and optimal route to deliver the goods to the respective customers from one or more depot and also take the goods from the customer back to the respective depots within the constraints set, has been extensively used in VRP, with the inclusion of extra constraints. Similar VRP variants have been mentioned below:\par
? Vehicle Routing Problem with the Time Window Constraint \hyperref[b11]{[12]} that has been set by customers, ? Another modified VRP with the added constraint of using limited number of vehicles of varying holding capacity has been published as Mixed Fleet Vehicle Routing (MFVRP) \hyperref[b12]{[13]},\par
? Another paper which has VRP with an added constraint where customers can request for delivery or pickup with the requirement that in every single delivery route, all pickups and deliveries to the customers are completed. This is known as Vehicle Routing Problem with Backhauls (VRPB) \hyperref[b12]{[13]}.\par
This paper has five sections in total. Section 1 deals with the introduction while section 2 deals with the literature survey. Section 3 handles the mathematical model of the proposed system [ACO using KMeans Clustering Algorithm], section 4 will explain the approach to the solution, section 5 will have the results and case studies, with section 6 concluding the paper.
\section[{II. Literature Survey}]{II. Literature Survey}\par
One of the heuristic solutions mentioned was provided by Hideki Hashimoto, Mutsunori Yagiura and Toshihide Ibaraki \hyperref[b7]{[8]}. In their paper they generalized VRPTW by making travelling costs and duration to be time-dependent functions. They used local search algorithm to find the routes of vehicles and using that, evaluated a neighborhood solution. they proposed an algorithm that could efficiently pick optimal routes using data from previous dynamic programming recursion that were used to evaluate the present solution. they even included a filtering method that determines which spaces in the neighborhood are not to be searched so as to avoid dead ends in improving the solution. they finally conclude with a local search algorithm that combines all their modifications.\par
A metaheuristic solution was proposed by YiyoKuo \hyperref[b5]{[6]}. In the research paper, the author has considered fuel consumption and carbon emission as the constraints to the Time-Dependent Vehicle Routing Problem (TDVRP). The paper has proposed an algorithm that determines a route that consumes less fuel and has the least carbon emissions. With this algorithm the author was able to provide an overall improvement of 22.69\% in minimizing transportation distances and 24.61\% improvement in fuel consumption.\par
[11] has used a two-phase method that includes Genetic Algorithms along with Random Search incorporating simulated annealing concepts to solve the time dependent vehicle routing problem (TDVRP). This is a hyper heuristic solution.\par
Paper \hyperref[b13]{[14]} has taken into consideration the problems of carbon pollution and environmental issues. Electric vehicles were considered to reduce the various problems mentioned but it brought along with it the issue of charging locations and battery capacity. To tackle these problems, a new variant in the classical VRPTW was brought about which integrated the ideas of multiple charging points that also have the facility of swapping batteries. The authors proposed a mixed integer programming model to tackle the issue using the improved ant colony optimization (ACO) algorithm with hybridised insertion heuristics and enhanced local search.\par
Another reference has been taken from \hyperref[b14]{[15]} which is quite close in similarity with this paper's solution. The problem that the paper addressed was that deliverance of perishable goods within a given time frame was a daunting task and if unexpected events took place, the extremely important goods would not reach their destination, leading to a molehill of problems and difficulties. The authors Yao Wu, Bin Zheng and Xueliang Zhou have proposed a working model where the idea of disruption management has been employed to create a disruption recovery model with a different type split delivery that is used for inter-route recourse based on a previous TDVRPTW. It takes into account the nature of perishable goods and dynamic travel route choice in urban road networks. The, a tabu search algorithm is brought up to create a solution for the initial routing problem. This will be further extended to create the disruption recovery plan. \hyperref[b15]{[16]} Researchers have also used a novel ant colony optimization algorithm based on improved brainstorm optimization (IBSO-ACO) to solve VRP with soft time windows. According to this paper, the classical ant colony algorithm has been modified to efficiently solve the local optimum problem. Their research has given proof that it can achieve a lower routing cost at a high convergence rate than the classical ant colony (ACO) and the stimulated annealing ant colony algorithms.\par
Looking into other heuristic strategies involved, \hyperref[b16]{[17]} has the space-filling curve with optimal partitioning as a solution while another has three-phase heuristics which has been developed by grouping a heuristicbased clustering algorithm solving VRP \hyperref[b17]{[18]}. Summary of other important state-of-art modern heuristics is available in \hyperref[b18]{[19,}\hyperref[b19]{20]}.\par
In this paper, we will be solving the Vehicle Routing Problem with Time Windows constraint using the modified Ant Colony Optimization with KMeans Clustering. Ants use pheromones to leave behind a trail for its comrades so as to use the optimal path fixed to reach the food source. There has been several researches based on this behaviour of ants, such as \hyperref[b21]{[21]}, which was the first paper to be published on this topic. Papers \hyperref[b23]{[22]}\hyperref[b24]{[23]}\hyperref[b25]{[24]}\hyperref[b26]{[25]}\hyperref[b27]{[26]}\hyperref[b28]{[27]} have various hybrid versions of ACO in varied fields.\par
Using this behaviour of ants and with the help of previous research work based on a somewhat similar problem, this paper aims to solve VRPTW using the KMeans Clustering algorithm to find the most optimal path to the customer.
\section[{III. Mathematical Model of Proposed System}]{III. Mathematical Model of Proposed System}\par
This part will use certain terms and elements from \hyperref[b29]{[28]}. It is a case study based on VRPTW regarding fresh food distribution centres. There will be two subsets of service nodes: pickup set ??\textunderscore ?? and delivery set ??\textunderscore ??. The values of these terms are |??\textunderscore ??| = ?? and |??\textunderscore ??| = ?? respectively. Now, starting depot node is set to 0 and end depot is set to (?? + ?? + 1). A node will be replicated if it needs both delivery and pickup. Each vehicle has its set capacity and operation cost. If there is an order between pickup node ?? and delivery node ?? then there will be a set ?? which contains pairs of (??, ??).\par
Looking at the objective function that minimizes total travelling cost, the equation is as follows?????? ? ?? ??? ? ?? ,????? ?? ?? ???? ?? ???? ?? ??\textbf{(1)}\par
Here, ?? refers to the number of clusters and ?? refers to the centroid of clusters.\par
The next equation makes sure that each node is served by at least one vehicle? ?? ??? ? ????? 1 ?? ?? ???? ? 1 ??? ? ??\textbackslash \{0, ?? + ?? + 1\}\textbf{(2)}\par
Equation ( \hyperref[formula_2]{3}) showcases the constraint where the same vehicle ?? must pick and order from node ?? and deliver it to node ??.? ????? 2 ?? ?? ???? ? ? ????? 2 ?? ???? ?? = 0 ??? ? ??, ?(??, ??) ? ??\textbf{(3)}\par
A vehicle must pass starting and ending depots at least once and this is shown by equations ( {\ref 4}) and ( \hyperref[formula_3]{5})? ????? 1 ?? 0?? ?? ? 1, ??? ? ?? (4) ? ????? 2 ?? ??,??+??+1 ?? ? 1, ??? ? ??\textbf{(5)}\par
If a vehicle reaches a node, it must leave it as well. This is shown in equation \hyperref[b5]{[6]},? ?? ??? 2 ?? ???? ?? = ? ????? 2 ?? ???? ?? ??? ? ??\textbackslash \{0, ?? + ?? + 1\}, ?? ? ??, ?? ? ??, ?? ? ??\textbf{(6)}\par
Equations ( \hyperref[formula_5]{7}) and ( \hyperref[formula_6]{8}) have integrated time constraints, subtour elimination and load constraints.???? ?? ?? + (?? ???? + ?? ?? ) ? ????????(1 ? ?? ???? ?? ) ? ???? ?? ?? , ??? ? ??, ?? ? ?? 1 , ?? ? ?? 2\textbf{(7)}???? ?? ?? + ?? ?? ? ????????(1 ? ?? ???? ?? ) ? ???? ?? ?? , ??? ? ??, ?? ? ?? 1 , ?? ? ?? 2 , ?? ? ??\textbf{(8)}\par
Now, if there is an order placed between two nodes and the pickup node must be visited before the delivery node, then equation \hyperref[b8]{(9)} shows it.???? ?? ?? ? ?? ???? (?? ?? + ?? ???? ) + ???? ?? ?? , ??? ? ??, ?? ? ??\textunderscore ??, ?? ? ??\textunderscore ??\textbf{(9)}\par
Equation \hyperref[b9]{(10)} shows time constraint while \hyperref[b10]{(11)} shows capacity bound constraint.?? ?? ? ???? ?? ?? ? ð??"ð??" ?? , ??? ? ??\textbackslash \{0, ?? + ?? + 1\}, ?? ? ??\textbf{(10)}(?? ?? + ?? ?? , ?? ?? ) ? ???? ?? ?? ? (0, ?? ?? ), ??? ? ??, ?? ? ??\textbf{(11)}\par
Now showcasing the constraint of limiting number of vehicles used and maximum working duration in equations ( \hyperref[formula_10]{12}) and \hyperref[b12]{(13)}.? ????? ? ????? ?? 0?? ?? ? ??\textbf{(12)}?? ?????? ? ???? ??+??+1 ?? ? ???? 0 ?? , ??? ? ??\textbf{(13)}\par
This mathematical model is a small-scale solution.
\section[{Approach to the Solution}]{Approach to the Solution}\par
In this paper, the Vehicle Routing Problem with Time Window constraint has been resolved using a modified version of the Ant Colony Optimization using KMeans Clustering. Marco Dorigo was the first person to introduce Ant Colony Optimization, in the 90s, in his Ph.D. thesis. The solution algorithm is based on the behaviour of ants, the way they live in colonies and search for food. While an ant goes around, searching for food, it leaves behind pheromones that act as a beacon. It acts as a communication mechanism and each time the ant leaves a pheromone trail, it tells the other ants about the quality and quantity of food the former ant had been carrying. This way, there are several set paths that the ants use based on the number of pheromones released in a path. The shortest and fastest route is chosen for maximum traffic.\par
Ant Colony Optimization (ACO) algorithm is a probabilistic technique based on the above phenomenon to find the optimal path. With the inclusion of KMeans Clustering, this modified approach has solved the constraints of the MPMDVRPTWHF, which has resulted in shorter time consumption, delivery within the time window and lower transportation costsalong with the inclusion of multiple pickup and delivery nodes wherein a pickup point might or might not have multiple delivery locations. The flowchart below showcases the solution setup. In the graph ?? = (??, ??), each arc (??, ??) has been assigned a variable called pheromone trail ?? ???? . The probabilities of better solution is directly proportional to the pheromone intensity. This means that when an ant wants to go to another node from its current node, it will choose the one with the maximum pheromone intensity. to make this work, a fixed quantity of pheromone is allocated to every arc. To decide which node to proceed to (node ??), the ????? ant will use the pheromone trail ?? ???? which is showcased below:?? ???? ?? = [?? ???? ] ?? [?? ???? ] ?? ?? ???? ?? ?? ?? [?? ???? ] ?? [?? ???? ] ?? , ??ð??"ð??" ?????? ?? ?? (14)\par
Initially, all probabilities are set to 1. ?? = 1 ?? ???? is a heuristic value, pheromone concentration on the edge when the ant travels from node ?? to nodev??is denoted by ?? ???? and relative influence of the pheromone concentration and the heuristic value is shown by ??and ??.\par
If we go into the specifics, then ?? ???? denotes how much favourable is the next node ?? while ?? ???? implies how much better is the next node relatively.
\section[{b) Solution Construction}]{b) Solution Construction}\par
In this scenario, the solution is generated when an artificial ant takes vehicles from the vehicle set and constructs a path, starting from the warehouse or depot, by choosing those nodes that satisfy the set of constraints. The ant continues to build the route until the limit of route length has been reached or when the time window constraint has been disobeyed. so, in forming the route, the ant will check each node whether it fulfils all the constraints and if it finds such a node, it will append it to the route, update the variables and go for the next node, using the updated variables. These changes in each iteration are all recorded in a solution set, which will then be used for finding the best solution from the set. When determining the optimal route for the best solution, pheromone update is used which includes pheromone deposition and pheromone evaporation. + ??? ? 0 and ?? is a constant. In each iteration, ?? number of ants find?? ?????? = ? ?? ??=1 ?? ??
\section[{??}]{??}\par
of average total distance. Then pheromone is updated by the elitist and best ants.\par
After the evaporation process, only the best and the elitist ants can update the pheromone deposits on the optimal path chosen, which is given by the equation?? ???? = ?? ???? + ? ?? ???? * + ? ?? ?1 ??=1 ?? ???? ?? (16)\par
Where,??? ???? ?? = \{ ?? ? ?? ?? ?? ??ð??"ð??" ????? ???????? ?????? ?????????????? ???? ???????? (??, ??)0 0 ????????????????? (\textbf{17})??? ???? * = \{ ?? ???? ??ð??"ð??" ???????? ???????? ??ð??"ð??" ???????????????? ???? (??, ??)0 ?????????????????\textbf{(18)}\par
Looking at equations 17 and 18, it can be concluded that there are two types of pheromone depositions that are deposited on the trails during the pheromone update process. First, if ?? elitist ants have travelled a path, that path will be updated as the best solution so far (????), in accordance with the ACO+KMeans Clustering algorithm. ??? ???? * denotes the pheromone update by the elitist ants. Second, out of the ?? ants available, only (?? ? 1) best ants, in the current iteration, can deposit pheromone on the path they have traversed. The term ???? ???? ?? is used to denote the pheromone quantity laid down on the trails that have been traversed by them and the amount of pheromone that have been deposited by the ants are determined by their solution quality ?? ?? and rank ?? and the value is equal to ???? ???? ?? . To summarize, the elitist ants need to increase the probability of the best-solution so far after each iteration as the values that are updated will act as reference values for the next iteration. The ranking methodology has been employed in \hyperref[b16]{[17]} so as to reduce pheromone deposition on those routes that have relatively lesser favourability.
\section[{Case Study a) Dataset Used}]{Case Study a) Dataset Used}\par
The dataset has been obtained from consulting firms Horizon Consulting Inc. and EATEAM Inc. and their clients from students CPT work and it has been preprocessed to Solomon-100 standard test set which have 20 problem cases. The pre-processed real world dataset from above firms includes x-y location coordinates, service time, demand by customers, due dates and ready time. This section will be in comparison with \hyperref[b32]{[30]} as it has used the same data set. This comparison will help in proving that the proposed solution from this paper is the better method of solving the (MPMDVRPTWHF) as it gives better cost reduction with lesser percentage of carbon emissions, along with optimized fuel consumptions and lesser vehicles used.
\section[{b) Parameters Defined}]{b) Parameters Defined}\par
The parameters defined in this paper are derived from \hyperref[b32]{[30]} as this paper is in comparison with the latter. Similar to \hyperref[b32]{[30]} the delivery vehicle used is a refrigerator car and the set of pre-defined parameters are given below.
\section[{Parameters}]{Parameters}
\section[{c) Result Analysis}]{c) Result Analysis}\par
The entire result section has used the Pareto optimal principle for obtaining the solution. The Pareto Principle states that 80 percent of a project's benefit comes from 20 percent of the work. The optimal version of it makes the sub objectives suppressed so as to efficiently solve the main objective. Due to this there is very little scope of conflict of objectives from the sub objectives and a noiseless solution id obtained.\par
Referring to \hyperref[b32]{[30]}, this paper the objectives chosen will be carbon emission reduction, total cost, time frame and customer satisfaction.\par
Using several test cases of 25,50,75 and 100 customers in three different scenarios, the proposed ACO algorithm with KMeans clustering provides a better solution in comparison. The results are arranged in the Pareto optimal solution format. {\ref 25}) test table is used here for obtaining the most optimal path with better results of the constraints set. This solution has used the Pareto optimal approach and figure 3 has shown the comparison between \hyperref[b2]{[3]} and this paper. It is clearly visible from the graph that the proposed algorithm of ACO+KMeans [PS\textunderscore KPSO] clustering has better output in terms of carbon emission, customer satisfaction and total transportation cost. This part has used the c101(50) test table. 5 trucks have been employed with respective paths (0, 43, 42, 41, 40, 44, 46, 45, 48, 50, 49, 47,0), (0, 5, 3, 7, 8, 10, 11, 9, 6, 4, 2, 1,0), (0, 20, 24, 25, 27, 29, 30, 28, 26, 23, 22, 21,0), (0, 32, 33, 31, 35, 37, 38, 39, 36, 34,0) and (0, \hyperref[b12]{13,}\hyperref[b16]{17,}\hyperref[b17]{18,}\hyperref[b18]{19,}\hyperref[b14]{15,}\hyperref[b15]{16,}\hyperref[b13]{14,}\hyperref[b11]{12,} {\ref 0)}. The end are 33.43 for carbon emissions, 5942.72 cost and 100 percent customer satisfaction. Figure \hyperref[fig_5]{5} shows the comparison between \hyperref[b32]{[30]} and this paper results while figure \hyperref[fig_6]{6} displays the routes taken by the 5 trucks. The c101(75) dataset has been used in this part. The number of vehicles used is 8 with the most optimal paths chosen respectively: (0, 43, 42, 41, 40, 44, 46, 45, 48, 51, 50, 52, 49, 47, 0), (0, 5, 3, 7, 8, 10, 11, 9, 6, 4, 2, 1, 75, 0), (0, 32, 33, 31, 35, 37, 38, 39, 36, 34, 0), (0, 67, 65, 63, 62, 74, 72, 61, 64, 68, 66, 69, 0), (0, \hyperref[b19]{20,}\hyperref[b25]{24,}\hyperref[b26]{25,}\hyperref[b28]{27,}\hyperref[b31]{29,}\hyperref[b32]{30,}\hyperref[b29]{28,}\hyperref[b27]{26,}\hyperref[b24]{23,}\hyperref[b23]{22,}\hyperref[b21]{21,} {\ref 0)}, (0, 57, 55, 54, 53, 56, 58, 60, 59, 0), (0, \hyperref[b12]{13,}\hyperref[b16]{17,}\hyperref[b17]{18,}\hyperref[b18]{19,}\hyperref[b14]{15,}\hyperref[b15]{16,}\hyperref[b13]{14,}\hyperref[b11]{12,} {\ref 0)} and (0, 71, 70, 73, 0)\par
The final results of carbon emissions, total cost and customer satisfaction are 54.96, 10639.71 and 100 percent respectively. Figures \hyperref[fig_9]{7 and 8} showcase the comparison between \hyperref[b32]{[30]} and this paper and the route distribution of the vehicles.
\section[{Global Journal of Computer Science and Technology}]{Global Journal of Computer Science and Technology}\par
Volume XXII Issue I Version I This section has used the c101 (100) dataset. Now looking \hyperref[b32]{[30]}, there are better results in terms of carbon emission, cost and customer satisfaction (69.03, 13561.41 and 100 percent). Instead of 23 vehicles, 10 vehicles have been employed and the most optimal paths are chosen: (0, 5, 3, 7, 8, 10, 11, 9, 6, 4, 2, 1, 75, 0), (0, 43, 42, 41, 40, 44, 46, 45, 48, 51, 50, 52, 49, 47, 0), (0, \hyperref[b19]{20,}\hyperref[b25]{24,}\hyperref[b26]{25,}\hyperref[b28]{27,}\hyperref[b31]{29,}\hyperref[b32]{30,}\hyperref[b29]{28,}\hyperref[b27]{26,}\hyperref[b24]{23,}\hyperref[b23]{22,}\hyperref[b21]{21,} {\ref 0)}, (0, 67, 65, 63, 62, 74, 72, 61, 64, 68, 66, 69, 0), (0, 90, 87, 86, 83, 82, 84, 85, 88, 89, 91, 0), (0, 57, 55, 54, 53, 56, 58, 60, 59, 0), (0, 98, 96, 95, 94, 92, 93, 97, 100, 99, 0), (0, 32, 33, 31, 35, 37, 38, 39, 36, 34, 0), (0, \hyperref[b12]{13,}\hyperref[b16]{17,}\hyperref[b17]{18,}\hyperref[b18]{19,}\hyperref[b14]{15,}\hyperref[b15]{16,}\hyperref[b13]{14,}\hyperref[b11]{12} Looking at all the results above, it is easily discernible that the ACO+KMeans clustering algorithm has performed way better than the improved Ant Colony algorithm and the normal Ant Colony Algorithm. With lesser number of vehicles employed, lesser carbon emission levels noted and better cost management, the proposed system has shown its effectiveness and viability for usage in the real-world logistics problems. The proposed algorithm PS\textunderscore KPSO has provided about 10.37\%, 46.9\%, 61.98\% and 78.81\% reduction in total costs for 25, 50, 75 and 100 customers while there are about 46.61\% , 53.27\% and 61.16\% reduction in total carbon emissions for 50, 75 and 100 customers, when compared with \hyperref[b32]{[30]}. Along with the aforementioned improvements, there is 100\% customer satisfaction in all the cases. The proposed algorithm (ACO+KMeans Clustering) has outperformed the Modified Ant Colony Algorithm and the original Ant Colony algorithm. Table \hyperref[tab_3]{2} compares the results of the proposed algorithm and modified ant colony algorithm.
\section[{Global Journal of Computer Science and Technology}]{Global Journal of Computer Science and Technology}\par
Volume XXII Issue I Version I In the Solomon-100 dataset, there are three formats of destination grouping. One is a cluster format (C), one is a random format (R) and one is a randomclustered format (RC). These three formats have been used for 25, 50, 75 and 100 customers. So other than C101, there are C201, R211, R201 and RC201. The comparison between the proposed algorithm (ACO+KMeans algorithm) and modified Ant Colony algorithm \hyperref[b32]{[30]} have been given in Table \hyperref[tab_4]{4}. The data from Table \hyperref[tab_4]{4} helps in evaluating the effectiveness of the proposed algorithm. Even with increase in the number of customers, be it clustered, random or both, there is barely any increase in the number of vehicles employed. With an average of 2.625 vehicles per case, this greatly affects the total travel, storage, damage and fuel costs while reducing the carbon footprint by a great extent, ultimately helping not only the economy of the organisation but also trying to improve the environmental condition of the Earth. It can be assumed from the results data that there is a high probability of increase in number of customers. As the number of vehicles employed is less, there is scope of increasing customer reach and maybe there is a chance of increasing the speed of delivery. With the new electronic vehicle usage, there will be even more cuts in the carbon footprint value and better customer coverage.
\section[{Conclusion}]{Conclusion}\par
This paper discusses the vehicle routing problem with time window constraint (VRPTW) along with added constraints of number of vehicles, logistics cost, overall carbon emission rate along with multiple pickup and delivery points faced by firms EATEAM and Horizon Consulting Inc. in their logistical operations. A meta heuristic Ant Colony Algorithm with KMeans Clustering was employed to solve the problem statement. Looking at the literature survey in this paper, it is observable that Vehicle Routing Problem has had several approaches with varying results, which in turn leads to the fact that VRP with added constraints is a difficult problem to solve.\par
The solution provided in this paper has been compared with \hyperref[b32]{[30]}, which has a similar problem statement, and the results of the proposed Ant colony Algorithm with KMeans Clustering has performed far better and has provided very less scope of improvement in the discussed problem areas.\par
In future researches on similar topics, it's a hope that this paper will be a good leverage for the researchers and this solution can be further modified for more improvements.\begin{figure}[htbp]
\noindent\textbf{2}\includegraphics[]{image-2.png}
\caption{\label{fig_0}Figure 2 :}\end{figure}
\begin{figure}[htbp]
\noindent\textbf{}\includegraphics[]{image-3.png}
\caption{\label{fig_1}(}\end{figure}
\begin{figure}[htbp]
\noindent\textbf{3}\includegraphics[]{image-4.png}
\caption{\label{fig_2}Figure 3 :}\end{figure}
\begin{figure}[htbp]
\noindent\textbf{4}\includegraphics[]{image-5.png}
\caption{\label{fig_3}Figure 4 :}\end{figure}
\begin{figure}[htbp]
\noindent\textbf{5}\includegraphics[]{image-6.png}
\caption{\label{fig_5}Figure 5 :}\end{figure}
\begin{figure}[htbp]
\noindent\textbf{6}\includegraphics[]{image-7.png}
\caption{\label{fig_6}Figure 6 :}\end{figure}
\begin{figure}[htbp]
\noindent\textbf{7}\includegraphics[]{image-8.png}
\caption{\label{fig_8}Figure 7 :}\end{figure}
\begin{figure}[htbp]
\noindent\textbf{8}\includegraphics[]{image-9.png}
\caption{\label{fig_9}Figure 8 :}\end{figure}
\begin{figure}[htbp]
\noindent\textbf{}\includegraphics[]{image-10.png}
\caption{\label{fig_10}}\end{figure}
\begin{figure}[htbp]
\noindent\textbf{9}\includegraphics[]{image-11.png}
\caption{\label{fig_11}Figure 9 :}\end{figure}
\begin{figure}[htbp]
\noindent\textbf{10}\includegraphics[]{image-12.png}
\caption{\label{fig_12}Figure 10 :}\end{figure}
\begin{figure}[htbp]
\noindent\textbf{13}\includegraphics[]{image-13.png}
\caption{\label{fig_14}Figure 13 :}\end{figure}
\begin{figure}[htbp]
\noindent\textbf{14}\includegraphics[]{image-14.png}
\caption{\label{fig_15}Figure 14 :}\end{figure}
\begin{figure}[htbp]
\noindent\textbf{11}\includegraphics[]{image-15.png}
\caption{\label{fig_16}Figure 11 :}\end{figure}
\begin{figure}[htbp]
\noindent\textbf{1517}\includegraphics[]{image-16.png}
\caption{\label{fig_17}Figure 15 :Figure 17 :}\end{figure}
\begin{figure}[htbp]
\noindent\textbf{19}\includegraphics[]{image-17.png}
\caption{\label{fig_18}Figure 19 :}\end{figure}
\begin{figure}[htbp]
\noindent\textbf{21}\includegraphics[]{image-18.png}
\caption{\label{fig_19}Figure 21 :}\end{figure}
\begin{figure}[htbp]
\noindent\textbf{23}\includegraphics[]{image-19.png}
\caption{\label{fig_20}Figure 23 :}\end{figure}
\begin{figure}[htbp]
\noindent\textbf{25}\includegraphics[]{image-20.png}
\caption{\label{fig_21}Figure 25 :}\end{figure}
\begin{figure}[htbp]
\noindent\textbf{}\includegraphics[]{image-21.png}
\caption{\label{figure21}}\end{figure}
\begin{figure}[htbp]
\noindent\textbf{} \par
\begin{longtable}{P{0.4665957446808511\textwidth}P{0.07957446808510638\textwidth}P{0.13382978723404254\textwidth}P{0.10308510638297871\textwidth}P{0.06691489361702127\textwidth}}
\multicolumn{2}{l}{Pheromone update is used to elevate the pheromone}\tabcellsep \multicolumn{3}{l}{values either increase or decrease at a constant rate}\\
\multicolumn{2}{l}{values that are found on good solution paths and}\tabcellsep {}[29].\tabcellsep \\
\multicolumn{2}{l}{decrease those that are on bad solution paths. In}\tabcellsep \tabcellsep \multicolumn{2}{l}{The pheromone evaporation equation is given}\\
\multicolumn{2}{l}{pheromone deposition and evaporation, pheromone}\tabcellsep \multicolumn{2}{l}{as such,}\\
\tabcellsep ?? ???? = ?? ???? ? ?? ?????? ??\tabcellsep + ???,\tabcellsep ?(??, ??) ? ??\tabcellsep (15)\\
\multicolumn{2}{l}{Where trail persistence 1 ? ?? ? 0 of the}\tabcellsep \tabcellsep \\
evaporation factor 1 ? ?\tabcellsep ?? ?? ??????\tabcellsep \tabcellsep \\
\tabcellsep \tabcellsep \tabcellsep \tabcellsep Year 2022\\
\tabcellsep \tabcellsep \tabcellsep \tabcellsep )\\
\tabcellsep \tabcellsep \tabcellsep \tabcellsep D\\
\tabcellsep \tabcellsep ??\tabcellsep \\
\tabcellsep \tabcellsep \tabcellsep \tabcellsep © 2022 Global Journals\end{longtable} \par
\caption{\label{tab_0}}\end{figure}
\begin{figure}[htbp]
\noindent\textbf{2} \par
\begin{longtable}{P{0.26887755102040817\textwidth}P{0.06938775510204082\textwidth}P{0.0889030612244898\textwidth}P{0.04987244897959184\textwidth}P{0.04119897959183673\textwidth}P{0.01951530612244898\textwidth}P{0.1582908163265306\textwidth}P{0.13443877551020408\textwidth}P{0.004336734693877551\textwidth}P{0.015178571428571427\textwidth}}
\tabcellsep \tabcellsep ACOMO\tabcellsep \tabcellsep \tabcellsep \tabcellsep PS\textunderscore KPSO\tabcellsep \tabcellsep \tabcellsep \\
PID\tabcellsep NUM\textunderscore CUST\tabcellsep C (CNY)\tabcellsep CE\tabcellsep CS\tabcellsep NV\tabcellsep C (CNY)\tabcellsep CE\tabcellsep CS\tabcellsep NV\\
C101\textunderscore 25\tabcellsep 25\tabcellsep 3481.31\tabcellsep 19.73\tabcellsep 98.4\tabcellsep 5\tabcellsep 3138.070823\tabcellsep \multicolumn{2}{l}{19.50420315 100}\tabcellsep 3\\
C101\textunderscore 50\tabcellsep 50\tabcellsep 9583.7\tabcellsep 53.75\tabcellsep 99.2\tabcellsep 11\tabcellsep 5942.717648\tabcellsep \multicolumn{2}{l}{33.43172956 100}\tabcellsep 5\\
C101\textunderscore 75\tabcellsep 75\tabcellsep 20195.27\tabcellsep 94.87\tabcellsep 99.47\tabcellsep 17\tabcellsep 10639.70989\tabcellsep \multicolumn{2}{l}{54.95890959 100}\tabcellsep 8\\
C101\textunderscore 100\tabcellsep 100\tabcellsep 31202.27\tabcellsep 129.87\tabcellsep 99.6\tabcellsep 23\tabcellsep 13561.40714\tabcellsep \multicolumn{2}{l}{69.03832969 100}\tabcellsep 10\\
\multicolumn{3}{l}{b. Results with other test cases}\tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep \end{longtable} \par
\caption{\label{tab_3}Table 2 :}\end{figure}
\begin{figure}[htbp]
\noindent\textbf{4} \par
\begin{longtable}{P{0.39920333839150224\textwidth}P{0.05288315629742033\textwidth}P{0.02063732928679818\textwidth}P{0.025796661608497723\textwidth}P{0.07158573596358118\textwidth}P{0.11157056145675265\textwidth}P{0.0032245827010622154\textwidth}P{0.014188163884673746\textwidth}P{0.06707132018209408\textwidth}P{0.051593323216995446\textwidth}P{0.032245827010622154\textwidth}}
\tabcellsep \tabcellsep \tabcellsep PS\textunderscore KACO\tabcellsep \tabcellsep \tabcellsep \tabcellsep \tabcellsep ACOMO\tabcellsep \tabcellsep \\
PID\tabcellsep \multicolumn{2}{l}{NUM\textunderscore CUST TOT\textunderscore VEH}\tabcellsep NV\tabcellsep C\tabcellsep CE\tabcellsep CS\tabcellsep NV\tabcellsep C\tabcellsep CE\tabcellsep CS\\
C\textunderscore 201\textunderscore 25\tabcellsep 25\tabcellsep 25\tabcellsep 2\tabcellsep 215.543\tabcellsep 14.864\tabcellsep 100\tabcellsep 3\tabcellsep 613.81\tabcellsep 22.28\tabcellsep 100\\
C\textunderscore 201\textunderscore 50\tabcellsep 50\tabcellsep 25\tabcellsep 2\tabcellsep 444.961\tabcellsep \multicolumn{2}{l}{19.7345 100}\tabcellsep 6\tabcellsep 1232.8\tabcellsep 42.46\tabcellsep 100\\
C\textunderscore 201\textunderscore 75\tabcellsep 75\tabcellsep 25\tabcellsep 3\tabcellsep 511.09\tabcellsep \multicolumn{2}{l}{26.2824 100}\tabcellsep 9\tabcellsep 2177.34\tabcellsep 58.81\tabcellsep 100\\
C\textunderscore 201\textunderscore 100\tabcellsep 100\tabcellsep 25\tabcellsep 3\tabcellsep 591.557\tabcellsep \multicolumn{2}{l}{27.9907 100}\tabcellsep 13\tabcellsep 2221.71\tabcellsep 99.08\tabcellsep 100\\
r\textunderscore 201\textunderscore 25\tabcellsep 25\tabcellsep 25\tabcellsep 2\tabcellsep 543.693\tabcellsep \multicolumn{2}{l}{21.8306 100}\tabcellsep 5\tabcellsep 946.39\tabcellsep 45.17\tabcellsep 100\\
r\textunderscore 201\textunderscore 50\tabcellsep 50\tabcellsep 25\tabcellsep 2\tabcellsep 1039.39\tabcellsep \multicolumn{2}{l}{32.3543 100}\tabcellsep 6\tabcellsep 1404.82\tabcellsep 69.75\tabcellsep 100\\
r\textunderscore 201\textunderscore 75\tabcellsep 75\tabcellsep 25\tabcellsep 3\tabcellsep 1368.58\tabcellsep \multicolumn{2}{l}{44.4869 100}\tabcellsep 7\tabcellsep 2482.75\tabcellsep 98.4\tabcellsep 100\\
r\textunderscore 201\textunderscore 100\tabcellsep 100\tabcellsep 25\tabcellsep 4\tabcellsep 1995.19\tabcellsep \multicolumn{2}{l}{62.9339 100}\tabcellsep 13\tabcellsep 2931.63\tabcellsep 111.02\tabcellsep 100\\
r\textunderscore 211\textunderscore 25\tabcellsep 25\tabcellsep 25\tabcellsep 1\tabcellsep 375.432\tabcellsep \multicolumn{2}{l}{13.1144 100}\tabcellsep 2\tabcellsep 400\tabcellsep 24.11\tabcellsep 100\\
r\textunderscore 211\textunderscore 50\tabcellsep 50\tabcellsep 25\tabcellsep 2\tabcellsep 1391.42\tabcellsep \multicolumn{2}{l}{39.8279 100}\tabcellsep 7\tabcellsep 600\tabcellsep 44.87\tabcellsep 100\\
r\textunderscore 211\textunderscore 75\tabcellsep 75\tabcellsep 25\tabcellsep 2\tabcellsep 1199.99\tabcellsep \multicolumn{2}{l}{35.7638 100}\tabcellsep 7\tabcellsep 873.41\tabcellsep 72.94\tabcellsep 100\\
r\textunderscore 211\textunderscore 100\tabcellsep 100\tabcellsep 25\tabcellsep 3\tabcellsep 1867.28\tabcellsep \multicolumn{2}{l}{55.0745 100}\tabcellsep 9\tabcellsep 1080.64\tabcellsep 84.49\tabcellsep 100\\
r\textunderscore c201\textunderscore 25\tabcellsep 25\tabcellsep 25\tabcellsep 2\tabcellsep 454.046\tabcellsep \multicolumn{2}{l}{19.9274 100}\tabcellsep 4\tabcellsep 847.18\tabcellsep 31.43\tabcellsep 100\\
r\textunderscore c201\textunderscore 50\tabcellsep 50\tabcellsep 25\tabcellsep 3\tabcellsep 974.703\tabcellsep \multicolumn{2}{l}{36.1249 100}\tabcellsep 8\tabcellsep 1554.47\tabcellsep 80\tabcellsep 100\\
r\textunderscore c201\textunderscore 75\tabcellsep 75\tabcellsep 25\tabcellsep 4\tabcellsep 1623.5\tabcellsep \multicolumn{2}{l}{55.0429 100}\tabcellsep 10\tabcellsep 2186.5\tabcellsep 121.39\tabcellsep 100\\
r\textunderscore c201\textunderscore 100\tabcellsep 100\tabcellsep 25\tabcellsep 4\tabcellsep 1927.47\tabcellsep \multicolumn{2}{l}{61.4963 100}\tabcellsep 11\tabcellsep 2959.41\tabcellsep 139.2\tabcellsep 100\end{longtable} \par
\caption{\label{tab_4}Table 4 :}\end{figure}
\backmatter \begin{bibitemlist}{1}
\bibitem[ Oper. Res ()]{b20}\label{b20} \textit{}, \textit{Oper. Res} 2011. 215 p. .
\bibitem[Voss et al. ()]{b22}\label{b22} \textit{}, S Voss , S Martello , I H Osman , C Roucairol . 2012. Boston, MA, USA: Kluver Academic Publishers. p. .
\bibitem[Xu et al. ()]{b30}\label{b30} \textit{}, , Xu , A Hajiyev , S Nickel , M Gen . 2018. Singapore: Springer. p. .
\bibitem[Dondo and Cerda ()]{b17}\label{b17} ‘A cluster-based optimization approach for the multi depot heterogeneous fleet vehicle routing problem with time windows’. R Dondo , Cerda . \textit{Eur. J. Oper. Res} 2007. 176 p. .
\bibitem[Wu et al. ()]{b14}\label{b14} ‘A Disruption Recovery Model for Time-Dependent Vehicle Routing Problem With Time Windows in Delivering Perishable Goods’. Y Wu , B Zheng , X Zhou . \xref{http://dx.doi.org/10.1109/ACCESS.2020.3032018}{10.1109/ACCESS.2020.3032018}. \textit{IEEE Access} 2020. 8 p. .
\bibitem[Cordeau et al. ()]{b18}\label{b18} ‘A guide to vehicle routing heuristics’. . F Cordeau , M Gendreau , G Laporte , . Y Potvinand , F Semet . \textit{J. Oper. Res. Soc} 2002. 53 p. .
\bibitem[Zhang and Tang ()]{b26}\label{b26} ‘A new hybrid ant colony optimization algorithm for the vehicle routing problem’. X Zhang , L Tang . \textit{Pattern Recognit. Lett} 2009. 30 p. .
\bibitem[Kumar and Panneerselvam ()]{b12}\label{b12} ‘A Survey on the Vehicle Routing Problem and Its Variants’. S N Kumar , R Panneerselvam . \textit{Intelligent Information Management} 2012. 4 p. .
\bibitem[Osvald A and Stirn L Z ()]{b4}\label{b4} ‘A vehicle routing algorithm for the distribution of fresh vegetables and similar perishable food’. Osvald A , Stirn L Z . \textit{Journal of Food Engineering} 2008. 85 (2) p. .
\bibitem[Mazzeo and Loiseau ()]{b27}\label{b27} \textit{An ant colony algorithm for the capacitated vehicle routing. Electron. Notes Discret. ath}, S Mazzeo , I Loiseau . 2004. 18 p. .
\bibitem[Balseiro S R and Loiseau I ()]{b6}\label{b6} ‘An ant colony algorithm hybridized with insertion heuristics for the time de pendent vehicle routing problem with time windows’. Balseiro S R , Ramonet Loiseau I . \textit{Computers \& Operations Research} 2011. 38 (6) p. .
\bibitem[Szeto et al.]{b19}\label{b19} ‘An artificial ee colony algorithm for the capacitated vehicle routing problem’. W Y Szeto , Y Wu , S C Ho . \textit{Eur}
\bibitem[Ma et al.]{b29}\label{b29} ‘An Improved ACO for the multi-depot vehicle routing problem with time windows’. Y Ma , . ; Han , K Kang , F Yan . \textit{Proceedings of the Tenth International Conference on Management Science and Engineering Management}, (the Tenth International Conference on Management Science and Engineering Management)
\bibitem[Ma et al. ()]{b25}\label{b25} ‘An Improved ACO for the multi-depot vehicle routing problem with time windows’. Y Ma , Han , K Kang , F Yan . \textit{Proceedings of the Tenth International Conference on Management Science and Engineering Management}, Xu, A Hajiyev, S Nickel, M Gen (ed.) (the Tenth International Conference on Management Science and Engineering ManagementSingapore) 2018. Springer. p. .
\bibitem[Yu et al. ()]{b28}\label{b28} ‘An improved ant colony optimization for vehicle routing problem’. B Yu , Z Z Yang , B Z Yao . \textit{Eur. . Oper. Res} 2009. 196 p. .
\bibitem[Bullnheimer et al. ()]{b31}\label{b31} ‘An improved ant system for the vehicle routing problem’. B Bullnheimer , R F Hartl , C Strauss . \textit{Ann. Oper. Res} 1999. 89 p. .
\bibitem[Hashimoto H et al. ()]{b7}\label{b7} ‘An iterated local search algorithm for the timedependent vehicle routing problem with time windows’. Hashimoto H , Yagiura M , Ibaraki T . \textit{Discrete Optimization} 2008. 5 (2) p. .
\bibitem[Tan et al. ()]{b23}\label{b23} ‘Ant colony optimization for capacitated vehicle routing problem’. W F Tan , L S Lee , Z A Majid , H V Seow . \textit{J. Comput. Sci} 2012. 8 p. .
\bibitem[Bullnheimer et al.]{b21}\label{b21} ‘Applying the ant system to the vehicle routing problem’. B Bullnheimer , R F Hartl , C Strauss . \textit{Meta-Heuristics: advances and Trends in Local Search or Optimization},
\bibitem[Müller ()]{b11}\label{b11} ‘Approximative Solutions to the Bicriterion Vehicle Routing Problem with Time Windows’. J Müller . \textit{European Journal of Operational Research} 2010. 202 p. .
\bibitem[Wu et al. ()]{b15}\label{b15} ‘Brainstorming-Based Ant Colony Optimization for Vehicle Routing With Soft Time Windows’. L Wu , Z He , Y Chen , D Wu , J Cui . \xref{http://dx.doi.org/10.1109/ACCESS.2019.2894681}{10.1109/ACCESS.2019.2894681}. \textit{IEEE Access} 19643-19652, 2019. 7.
\bibitem[Zhao et al. ()]{b32}\label{b32} ‘Cold Chain Logistics Path Optimization via Improved Multi-Objective Ant Colony Algorithm’. B Zhao , H Gui , H Li , J Xue . doi: 10.1109/ ACCESS.2020.3013951. \textit{IEEE Access} 2020. 8 p. .
\bibitem[Doerner et al. ()]{b24}\label{b24} ‘Savings Ants for the vehicle routing problem’. K Doerner , M Gronalt , R F Hartl , M Reimann , C Strauss , M Stummer . \textit{Lect. Notes Comput. Sci} 2002, 2279. p. .
\bibitem[Clarke and Wright ()]{b1}\label{b1} ‘Scheduling of vehicles from a central depot to a number of delivery points’. G Clarke , J W Wright . \textit{Operations Research} 1964. 12 (4) p. .
\bibitem[Mao et al. ()]{b13}\label{b13} ‘The Electric Vehicle Routing Problem With Time Windows and Multiple Recharging Options’. H Mao , J Shi , Y Zhou , G Zhang . \xref{http://dx.doi.org/10.1109/ACCESS.2020.3003000}{10.1109/ACCESS.2020.3003000}. \textit{IEEE Access} 2020. 8 p. .
\bibitem[Bowerman and Calamai ()]{b16}\label{b16} ‘The space filling curve with optimal partitioning heuristic for the vehicle routing problem’. R L Bowerman , P H Calamai . \textit{Eur. J .Oper. Res} 1994. 76 p. .
\bibitem[Figliozzi M A]{b8}\label{b8} ‘The time dependent vehicle routing problem with time windows: benchmark problems, an efficient solution algorithm, and solution characteristics’. Figliozzi M A . \textit{Transportation}
\bibitem[Dantzig and Ramser ()]{b0}\label{b0} ‘The truck dispatching problem’. G B Dantzig , J H Ramser . \textit{Management Science} 1959. 6 (1) p. .
\bibitem[Malandraki C and Daskin M S ()]{b2}\label{b2} ‘Time dependent vehicle routing problems: formulations, properties and heuristic algorithms’. Malandraki C , Daskin M S . \textit{Transportation Science} 1992. 26 (3) p. .
\bibitem[Minocha B and Tripathi S ()]{b10}\label{b10} ‘Two phase algorithm for solving VRPTW problem’. Minocha B , Tripathi S . \textit{International Journal of Artificial Intelligence and Expert Systems} 2013. 4 (1) p. .
\bibitem[Kuo ()]{b5}\label{b5} ‘Using simulated annealing to minimize fuel consumption for the time-dependent vehicle routing problem’. Y Kuo . \textit{Computers \& Industrial Engineering} 2010. 59 (1) p. .
\bibitem[Ichoua S et al. ()]{b3}\label{b3} ‘Vehicle dispatching with time-dependent travel times’. Ichoua S , M Gendreau , Potvin J Y . \textit{European Journal of Operational Research} 2003. 144 (2) p. .
\bibitem[Kok A L and Schutten J ()]{b9}\label{b9} ‘Vehicle routing under time-dependent travel times: the impact of congestion avoidance’. Hans E Kok A L , Schutten J . \textit{Computers \& Operations Research} 2012. 39 (5) p. .
\end{bibitemlist}
\end{document}