A TSP-based nested clustering approach to solve multi-depot heterogeneous fleet routing problem

<!-- metadata commented in wiki content


<div class="center" style="width: auto; margin-left: auto; margin-right: auto;">
<big>'''A TSP-based Nested Clustering Approach to Solve Multi-depot Heterogeneous Fleet Routing Problem'''</big></div>

<div class="center" style="width: auto; margin-left: auto; margin-right: auto;">
Mohammad Hassan Shojaeefard<sup>1,*</sup>, Morteza Mollajafari<sup>2</sup>, Seyed Hamid Reza Mousavitabar<sup>3</sup>, Mohammad Worya Khordehbinan<sup>4</sup>, Hossein Hosseinalibeiki<sup>5</sup></div>

<big><sup>1,*</sup></big>Professor, School of Mechanical Engineering, Iran University of Science and Technology, Tehran, Iran<big>.</big>

<div class="center" style="width: auto; margin-left: auto; margin-right: auto;">
[mailto:mhshsf@iust.ac.ir mhshsf@iust.ac.ir]</div>

<div class="center" style="width: auto; margin-left: auto; margin-right: auto;">
<big><sup>2</sup></big> Assistant professor, School of Automotive Engineering, Iran University of Science and Engineering, Tehran, Iran.</div>

<div class="center" style="width: auto; margin-left: auto; margin-right: auto;">
[mailto:mollajafari@iust.ac.ir mollajafari@iust.ac.ir]</div>

<big><sup>3</sup> </big>M.SC student, School of Automotive Engineering, Iran University of Science and Engineering, Tehran, Iran.

<div class="center" style="width: auto; margin-left: auto; margin-right: auto;">
[mailto:h_mousavitabar@auto.iust.ac.ir h_mousavitabar@auto.iust.ac.ir]</div>

<big><sup>4</sup> </big>Department of Computer Engineering, Islamic Azad University, Safadasht Branch, Tehran, Iran.

<div class="center" style="width: auto; margin-left: auto; margin-right: auto;">
[mailto:hossein.hosseinalibeiki@gmail.com hossein.hosseinalibeiki@gmail.com]</div>

<big><sup>5</sup> </big>Department of Civil Engineering, KN Toosi University of Technology, Tehran, Iran.
-->
==Abstract ==

The distribution of goods and urban services has made the issue of vehicle routing of particular importance to researchers. Advanced Routing Vehicle (RVRP) Rich Vehicle Routing Problem As a hybrid optimization problem, it is widely used in many transportation and logistics planning. The approach of this paper is to present a heuristic method for solving the problem called Nested Clustering for Traveling Salesman Problem (NC-TSP), in this method to optimize the search space, we break the problem in consecutive space. In the first step, using the nearest neighbor (Knn) algorithm with the center of each depot, and then using the fuzzy C-means clustering method within each cluster obtained from the Knn method, to find the optimal set of nodes. Then we solve the problem using the extension of MILP linear functions to the heterogeneous nature of the transport fleet and the warehouses that supply the goods, using the optimization algorithm (GA). The proposed approach, despite its great complexity, solves the problem to a large extent and shows promising cost-effective results in the existing criteria.

'''Keywords''': Genetic algorithm, routing, clustering, transport fleet

==1. Introduction==

The rapid development of the logistics industry has led to the sharing of resources, reduced energy consumption, increased productivity, and ultimately customer satisfaction, and has now become the main goal of this industry [1]. The problem of vehicle routing has been studied by researchers for a long time, and considering that VRP is an NP-Hard problem, so all the problems which depend on VRP are also NP-Hard problems, that have not had an exact solution. That for solving it, optimization methods shall be used. With the rise of urbanization, another type of multi-depot VRP (MDVRP) has been targeted, some researchers believe that MDVRP is a generalized issue for the traveling salesman, Where all nodes (customers) have been met with the lowest distance (cost) with the condition of passing only once from each node and returning to the source node, so with increasing the number of depots, the number of traveling sellers will increase and from each Origin, Several sellers may meet all nodes on a full tour and return to the depot [2]. The MDVRP problem was first proposed by Renaud et al. [2]. The solution method proposed for this problem was Tabu search, later this problem was presented again by Cordeau et al. using the Tabu Search Algorithm [3-5]. Time constraints in the distribution of goods are other limitations that have been the subject of many publications so far. For VRPTW, the proposed method has been to solve column production problem and using the Branch and Bound algorithm [6] to solve the problem of time window routing from genetic algorithms, Tabu search, simulated annealing, and used local search with λ-Interchange 2006 Introduced a new formula from VRPTW that includes binary variables related to arcs in the graph below. The new formula is based on TSP Algorithm formulation asymmetric with time windows and has the advantage of avoiding additional variables and linking constraints [7].

In the new VRPTW time formula, windows are modeled using path inequalities. Eliminates path inequalities, time, and capacity of inaccessible paths. In recent years, many publications have been presented in this field and all of them have solved the problem of time window routing based on meta-heuristic methods and using computational intelligence algorithms [8-10] are among these researchers who have addressed it in their publications in recent years. Other issues of interest to researchers are the combination of the time window and multi-depot of VRP, which was first proposed by Lie et al. using a hybrid genetic algorithm with adaptive local search. Finally, the problem of multi-depot vehicle routing and MHDHVRPTW heterogeneous transport fleet was considered by researchers. It has been presented many times in various publications. In the following section, we will address the issue of MHDHVRPTW.

In the following, in Section 2, the related literature is briefly reviewed. Section 3 describes the problem and develops a mathematical model. In Section 4, a hybrid genetic algorithm with variable neighborhood search is developed. Section 5 tests the algorithm and summarizes the experimental results. Section 6 provides the conclusion.

==2. Literature review==

The expansion of urbanization, logistics, and concentration, of goods in the central depot is uneconomical and companies have decided to allocate more depots in different parts of the city to compete and gain more market share according to costs and customer focus. Multiple services can create more customer satisfaction by sharing orders between depots and reducing costs and delays. Therefore, vehicle routing problem, which the first proposed by Dantzig and Ramser [11] as a general form of the traveling salesman (TPS) problem, no longer responds to the new conditions and led researchers to complete the VRP with multiple depots. MDVRP, study the VRPTW time window and the heterogeneity of the transport fleet. [[#tab-1|Table 1]] shows the different publications in this field. The problem of routing multi-depot vehicles with a heterogeneous fleet and time window MDHCVRPTW was introduced as a new approach and a complete and real problem with current conditions that have the complexities of previous problems such as time window, multiple depot, and heterogeneous transport fleet. Dondo. R [12] used the MILP algorithm for small number of nodes with minimum deviation from the optimal solution. This problem by Dondo. R [13] with using a clustering algorithm (which resulted in limiting the number of nodes) with a compact MILP mathematical model was solved. Bettinelli A. [6] presented the MDHCVRPTW branch, cut and price algorithm to solve exact changes in this method. Tummel C. [14] Introduced a Proper Linear Programming (ILP) Method for Solving MDHVRPTW this ILP obtained several large-scale scenarios using CPLEX and Gurobi Solvers was compared Guezouli L. [15], a new Clustering Approach Introduced GA-based multi-depot heterogeneous fleet for the VRPTW problem. The goal of this approach was to integrate an innovative clustering algorithm into an optimization framework. For doing this, first developed the mathematical formula for MDVRPTW, assigned nodes of each depot in the routing tour allocated the routing tour to both Clark and Wrights storage methods on several routes and optimize the planned paths using the GA algorithm. Rabbouch B. [16] Using the nearest problem clustering method, assigned the nearest depots to the nodes, and then using MILP and the innovative method (to form chromosomes), more suitable conditions were implemented to use a genetic algorithm. According to the recent literature on MDHVRPTW and MDVRPTW, one of the key parts to achieve the desired result is to use clustering to classify nodes and use optimizers. We will do the right thing to solve the problem.

<div class="center" style="font-size: 75%;">'''Table 1'''. The previous research</div>

<div id='tab-1'></div>
{| class="wikitable" style="margin: 1em auto 0.1em auto;border-collapse: collapse;font-size:85%;width:auto;" 
|-style="text-align:center"
! style="text-align: left;"| Subject  !! style="text-align: left;"| Method  !! Journal !!   Authors year
|-
|  style="text-align: left;"|A memetic algorithm based on two_arch2 for multi-depot heterogeneous-vehicle capacitated arc routing problem
|  style="text-align: left;"|A memetic algorithm
|  style="text-align: center;"|Elsevier
|  style="text-align: center;"|Cao B. (2021)  [17]
|-
|  style="text-align: left;"|The multi-depot open location routing problem with a heterogeneous fixed fleet
|  style="text-align: left;"|MILP
|  style="text-align: center;"|Elsevier
|  style="text-align: center;"|[https://www.sciencedirect.com/science/article/abs/pii/S0957417420306540  Nucamendi] S.  (2021)  [18] 
|-
|  style="text-align: left;vertical-align: top;"|Simplified swarm optimization for the heterogeneous fleet vehicle routing problem with time-varying continuous speed function
|  style="text-align: left;"|Swarm optimization
|  style="text-align: center;"|MDPI
|  style="text-align: center;"|Yeh, W.C. (2021)  [19]
|-
|  style="text-align: left;vertical-align: top;"|A simulated annealing-based approach for a real case study of vehicle routing problem with a heterogeneous fleet and time windows
|  style="text-align: left;"|Hybrid TSP and simulated annealing
|  style="text-align: center;"|Inderscience
|  style="text-align: center;"|Bernal J. (2021)  [20]
|-
|  style="text-align: left;"|Heterogeneous fleet vehicle scheduling problems for dynamic pickup and delivery problem with time windows in shared logistics platform: formulation, instances and algorithms
|  style="text-align: left;"|A hybrid scatters search parallel algorithm combined with the genetic algorithm, VNS algorithm, and tabu search algorithm 
|  style="text-align: center;"|Taylor & Francis
|  style="text-align: center;"|Su Z. (2021)  [21]
|-
|  style="text-align: left;"|Ant colony optimization for multiple pickup and multiple delivery vehicle routing problem with time window and heterogeneous fleets
|  style="text-align: left;"|Ant colony optimization algorithm
|  style="text-align: center;"|MDPI
|  style="text-align: center;"|Phuc K. (2021)  [22]
|-
|  style="text-align: left;"|The multi-depot heterogeneous vrp with backhauls: formulation and a hybrid VNS with GRAMPS meta-heuristic approach
|  style="text-align: left;"|A hybridization of (VNS) with the greedy randomized adaptive memory programming search 
|  style="text-align: center;"|Springer
|  style="text-align: center;"|Kocaturk F. (2021)  [23]
|-
|  style="text-align: left;"|A branch-and-price algorithm for the heterogeneous fleet green vehicle routing problem with time windows
|  style="text-align: left;"|The integer constraint by the Cplex solver using the columns produced by column generation
|  style="text-align: center;"|Elsevier
|  style="text-align: center;"|Yu Y. (2019)  [24]
|-
|  style="text-align: left;"|Efficient implementation of the genetic algorithm to solve rich vehicle routing problems
|  style="text-align: left;"|Genetic algorithm
|  style="text-align: center;"|Spinger
|  style="text-align: center;"|Rabbouch B. (2019)  [16]
|-
|  style="text-align: left;"|Multi-objective optimizations using genetic algorithm based clustering for multi-depot heterogeneous fleet vehicle routing problem with time windows
|  style="text-align: left;"|Hybrid clustering and genetic
|  style="text-align: center;"|Inder Sience
|  style="text-align: center;"|Guezouli L.(2018)  [15]
|-
|  style="text-align: left;"|A constructive heuristic for time-dependent multi-depot vehicle routing problem with time-windows and heterogeneous fleet
|  style="text-align: left;"|A mixed integer programming model
|  style="text-align: center;"|Elsevier
|  style="text-align: center;"|Afshar Nadjafi B. (2017)  [25]
|-
|  style="text-align: left;"|A recent brief survey for the multi depot heterogenous vehicle routing problem with time windows
|  style="text-align: left;"|Survey MDVRPTW
|  style="text-align: center;"|Springer
|  style="text-align: center;"|Rabbouch B. (2017)  [26]
|-
|  style="text-align: left;"|A branch-and-price algorithm for the multi-depot heterogeneous-fleet pickup and delivery problem with soft time windows
|  style="text-align: left;"|A branch-and-price algorithm
|  style="text-align: center;"|Elsevier
|  style="text-align: center;"| Bettinelli A. (2014)  [27]
|-
|  style="text-align: left;"|A mathematical model and a solving procedure for multi-depot vehicle routing problem with fuzzy time window and heterogeneous vehicle
|  style="text-align: left;"|Hybrid clustering and simulated annealing 
|  style="text-align: center;"|Springer
|  style="text-align: center;"|Adelzadeh M. (2014)  [28]
|-
|  style="text-align: left;"|The multi-depot heterogeneous fleet vehicle routing problem with time windows and assignment restrictions (M-Vrptwar)
|  style="text-align: left;"|Integer linear program
|  style="text-align: center;"|Springer
|  style="text-align: center;"|Tummel C. (2013)  [14]
|-
|  style="text-align: left;"|A new variable neighborhood search algorithm for the multi depot heterogeneous vehicle routing problem with time windows
|  style="text-align: left;"|A modified variable neighborhood search algorithm
|  style="text-align: center;"|Elsevier
|  style="text-align: center;"|Xu Y. (2012)  [29]
|-
|  style="text-align: left;"|A branch-and-cut-and-price algorithm for the multi-depot heterogeneous vehicle routing problem with time windows
|  style="text-align: left;"|Branch-and-cut-and-price algorithm
|  style="text-align: center;"|Elsevier
|  style="text-align: center;"|Bettinelli A. (2011)  [6]
|-
|  style="text-align: left;"|A cluster-based optimization approach for the multi-depot heterogeneous fleet vehicle routing problem with time windows
|  style="text-align: left;"|A mixed integer programming model
|  style="text-align: center;"|Elsevier
|  style="text-align: center;"|Dondo R. (2007)  [13]
|-
|  style="text-align: left;"|A reactive milp approach to the multidepot heterogeneous fleet vehicle routing problem with time windows
|  style="text-align: left;"|A  mixed integer programming model
|  style="text-align: center;"|Wiley
|  style="text-align: center;"|Dondo R. (2006)  [30]
|}


MILP The subject of this article is the problem of distribution with multiple and heterogeneous depots, in which the number and location of warehouses are predetermined. Each depots contains goods ordered by customers. Then, according to the type of customer request, it will receive services from the nearest warehouse. A heterogeneous fleet of vehicles to serve customers once due to the hard time window, the number of these vehicles is limited and for delivery or collection due to limited resources, the requested information and capacity of each node must be available to the cost function can be minimized by linear programming and the use of optimizers.

In this study, we developed the Genetic algorithm MILP base for MHDHVRPTW with a fixed traffic speed. The main contributions are as follows.

In this study, in continuous of previous work [16] we considered heterogeneous depots in such a way that some depots provide only one product and another depot is multi-product and can supply all goods.
Using the labeling algorithm for goods and depots, the basic conditions for assigning nodes or customers to depots, with the same label are provided. In the next section, we will review that the extent of the results will depend on labeling when the nearest neighbor algorithm is using for assigning customers to the nearest depot. Due to the fact that such issues are NP-hard problems, so optimization of such issues for a large number of nodes or customers is very challenging and has become one of the main objectives of this study for optimization. In this study, we used a nested clustering method to solve the problem, which we will discuss in more detail.

==3. Methodology==

The MHDHVRPTW focuses on a heterogeneous fleet and Depots with to serve a set of customers within their hard time windows for minimizing the cost function. for this aim let to considering function <math>G= {V, S}</math> that <math>V</math> is vertices  <math>V= \lbrace {v}_{1}\ldots  {v}_{n} ,{\, v}_{n+1}\ldots  {v}_{n+m}\rbrace</math> that n is total nods and m is the number of depots, also <math>S</math> denoted graph which is determined as  <math display="inline">S=\lbrace ({v}_{i}, {v}_{j}): {v}_{i} , {v}_{j}\in  V,i\not =j\rbrace,</math> the customer denoted as  <math display="inline">Vc=\lbrace {v}_{1} ,\ldots  , {v}_{n}\rbrace</math>  and depots are set as  <math display="inline">Vm=\lbrace {v}_{n+1} ,\ldots  , {v}_{n+m}\rbrace</math> this index corresponds to <math>m</math> depot, each node that is determined by <math>v_i</math> has a demand <math>d_i</math> which is not negative and zero so  <math display="inline">D=\lbrace {d}_{1} ,\ldots , {d}_{n}\rbrace</math>  and  <math display="inline">{d}_{i}=0 \forall  i=n+1 , \ldots , n+m</math> each nodes has earlier and last time in relevant time window that show as  <math display="inline">[{T}_{i}^{i}, {T}_{i}^{o}]</math> and <math>t_i</math> is duration time for each costumer. The important point is that depots have neither a time window nor a service time so  <math display="inline">{t}_{i}=0 \forall  i=n+1 , \ldots , n+m</math>, the distance between two nodes <math display="inline"> {D}_{ij }\forall  i\not =j</math>. Number of vehicle is <math>K</math> and maximum capacity of each vehicle <math>k</math> is <math>Q_k</math>. Feasible solution to the problem must satisfy the following constraints:

:* The tours have to start and finished at the same depot.

:* Each customer is served only once by one vehicle.

:* Maximum tour demand have to equal with <math>Q_k</math>.

:* Any tour demand have not be less than half <math>Q_k</math>.

:* Arrival time to any customers shall not exit that time windows which have been defined for them.

:* The number of vehicles is known and cannot increase.

:* The maximum trip duration (the summation of the traveling distance plus service time in a route) cannot exceed the route duration <math>S</math>.

It is noticeable that an arc  <math display="inline">({v}_{i},\, {v}_{j})</math> can be eliminated in the case of violation of temporal or capacity constraints.

:*  <math display="inline">{x}_{ijkp}=1</math>. If vehicle <math>k</math> pass through <math>i</math> and <math>j</math> nodes via arc <math display="inline">{v}_{i}</math> and  <math display="inline">{v}_{j}</math> <math display="inline">\forall \, i\not =j</math> and  <math display="inline">({v}_{i}\, ,{v}_{j})\in V</math> otherwise  <math display="inline">{x}_{ijkp}=</math><math>0</math>.

:*  <math display="inline">{Y}_{ij}>0</math>.  Is total demand which is remain in vehicle when is pass through node <math>i</math> to <math>j</math>.

:* <math display="inline">{W}_{ijk}>0\,</math>. Time variable is starting time in node <math>i</math>   <math display="inline">{v}_{i}\, ,\in V</math> to node <math>j</math>   <math display="inline">{v}_{j}\, ,\in V</math> by vehicle <math>k</math>  which is started from depot <math display="inline">p\in P</math>.

===3.1 Mathematical model===

In this part of the study, the main goal, which is to optimize or minimize the value of the cost function, is expressed as function (1)

{| class="formulaSCP" style="width: 100%; text-align: left;" 
|-
| 
{| style="text-align: center; margin:auto;width: 100%;" 
|-
| style="text-align: center;" | <math>minimize\sum _{i=1}^{n+m}\sum _{j=1}^{n+m}\sum _{k=1}^{K}\sum _{p=n+1}^{n+m}{D}_{ij}{X}_{ijkp}</math>
|}
| style="width: 5px;text-align: right;white-space: nowrap;" |(1)
|}

The constraints to minimize the cost function are as follows:

1) Ensuring each customer will be visited or serviced only once

{| class="formulaSCP" style="width: 100%; text-align: left;" 
|-
| 
{| style="text-align: center; margin:auto;width: 100%;" 
|-
| style="text-align: center;" | <math>\sum _{i=1}^{n+m}\sum _{k=1}^{K}\sum _{p=n+1}^{n+m}{X}_{ijkp}=1,\quad j=1,\ldots ,n</math>
|}
| style="width: 5px;text-align: right;white-space: nowrap;" |(2)
|}

2) Fixation a vehicle, after servicing a customer node vi, must leave to another nodes that next node can be depot or other customer

{| class="formulaSCP" style="width: 100%; text-align: left;" 
|-
| 
{| style="text-align: center; margin:auto;width: 100%;" 
|-
| style="text-align: center;" | <math>\sum _{i=1}^{n+m}\sum _{k=1}^{K}\sum _{p=n+1}^{n+m}\begin{matrix}{X}_{ijkp}=1,\\ \quad i=1,\ldots ,n\, \end{matrix}</math>
|}
| style="width: 5px;text-align: right;white-space: nowrap;" |(3)
|}

3) This restriction implies that the vehicle tour is symmetrical, in other words graph <math display="inline">({v}_{j}\, ,{v}_{i})</math> is equal to  <math display="inline">({v}_{i}\, ,{v}_{i})</math>

{| class="formulaSCP" style="width: 100%; text-align: left;" 
|-
| 
{| style="text-align: center; margin:auto;width: 100%;" 
|-
| style="text-align: center;" | <math>\sum _{i=1}^{n+m}{X}_{ijkp}=\sum _{i=1}^{n+m}{{X}_{jikp}}_{\begin{matrix}\quad k=1,\ldots ,K\\\quad \, j=1,\ldots ,n+m,\\\, \, p=n+1,\ldots ,n+m\end{matrix}}</math>
|}
| style="width: 5px;text-align: right;white-space: nowrap;" |(4)
|}

4) determines that only one vehicle starts moving from the warehouse and passes through the  <math display="inline">({v}_{j}\, ,{v}_{i})</math> only once on the tour route

{| class="formulaSCP" style="width: 100%; text-align: left;" 
|-
| 
{| style="text-align: center; margin:auto;width: 100%;" 
|-
| style="text-align: center;" | <math>\sum _{i=1}^{n}\sum _{j=1}^{n}{{X}_{ijkp}\leq 1,}_{\begin{matrix}\quad k=1,\ldots ,K\\\quad p=n+1,\ldots ,n+m\quad \end{matrix}}</math>
|}
| style="width: 5px;text-align: right;white-space: nowrap;" |(5)
|}

5) This constraint indicates that the total output of the depot is equal to the amount of customer demand that is covered by this depot

{| class="formulaSCP" style="width: 100%; text-align: left;" 
|-
| 
{| style="text-align: center; margin:auto;width: 100%;" 
|-
| style="text-align: center;" | <math>\sum _{i=n+1}^{n+m}\sum _{j=1}^{n}{Y}_{ij}\geq \sum _{j=1}^{n}{d}_{j}</math>
|}
| style="width: 5px;text-align: right;white-space: nowrap;" |(6)
|}

6) Constraint the number of vehicles 

{| class="formulaSCP" style="width: 100%; text-align: left;" 
|-
| 
{| style="text-align: center; margin:auto;width: 100%;" 
|-
| style="text-align: center;" | <math>\sum _{k=1}^{K}\sum _{j=1}^{n+m}{X}_{ijkp}\leq {{n}_{c}}_{\begin{matrix},\quad \quad \quad i=1,\ldots ,n+m,\\\quad \, p=n+1,\ldots ,n+m\end{matrix}}</math>
|}
| style="width: 5px;text-align: right;white-space: nowrap;" |(7)
|}

7)  Specifies that the demand which remains in node  <math display="inline">{j}^{th}</math> is equal to the load in the previous node <math display="inline">{i}^{th}</math> minus customer  <math display="inline">{i}^{th}</math> demand

{| class="formulaSCP" style="width: 100%; text-align: left;" 
|-
| 
{| style="text-align: center; margin:auto;width: 100%;" 
|-
| style="text-align: center;" | <math>\sum _{i=1}^{n+m}{Y}_{ij}-\sum _{i+1}^{n+m}{Y}_{ji}={d}_{j}</math>
|}
| style="width: 5px;text-align: right;white-space: nowrap;" |(8)
|}

8) Indicates that the load required to supply the customer <math display="inline">{j}^{th}</math> is less than or equal to the capacity of a given vehicle starting from the depot. This restriction ensures that the capacity of the vehicle is not violated by any type of vehicle

{| class="formulaSCP" style="width: 100%; text-align: left;" 
|-
| 
{| style="text-align: center; margin:auto;width: 100%;" 
|-
| style="text-align: center;" | <math>{Y}_{ij}\leq \sum _{p=n+1}^{n+m}\sum _{i=1}^{K}{Y}_{ji}={d}_{j}</math>
|}
| style="width: 5px;text-align: right;white-space: nowrap;" |(9)
|}

9) Checked that the node j is serviced in the relevant time window

{| class="formulaSCP" style="width: 100%; text-align: left;" 
|-
| 
{| style="text-align: center; margin:auto;width: 100%;" 
|-
| style="text-align: center;" | <math>{T}_{i}^{1}\leq {W}_{ik}\leq {T}_{i}^{2}</math>
|}
| style="width: 5px;text-align: right;white-space: nowrap;" |(10)
|}

10) Expresses the service starting time calculations based on the time windows which is defined for each node. In these calculations, the unit speed per unit time is considered, so the starting time plus service time of each customer plus the distance between two nodes must be equal or more than starting time of the service in the next node

{| class="formulaSCP" style="width: 100%; text-align: left;" 
|-
| 
{| style="text-align: center; margin:auto;width: 100%;" 
|-
| style="text-align: center;" | <math>{X}_{ijkp}\left( {W}_{ikp}+{t}_{i}+{D}_{ij}-{W}_{jkp}\right) \leq 0,</math>
|-
| style="text-align: center;" | <math>i=1,\ldots ,n,\, \quad j=1,\ldots ,n+m,\quad k=1,\ldots ,K,\quad  p=n+1,\ldots ,n+m</math>
|}
| style="width: 5px;text-align: right;white-space: nowrap;" |(11)
|}

11) For controlling the route duration by a vehicle, ensuring that the travel duration cannot exceed the maximum route duration <math>S</math>

{| class="formulaSCP" style="width: 100%; text-align: left;" 
|-
| 
{| style="text-align: center; margin:auto;width: 100%;" 
|-
| style="text-align: center;" | <math>\sum _{i=1}^{n}\sum _{j+1}^{n+m}{W}_{jkp}{X}_{ijkp}\leq S,\quad k=1,\ldots ,K,\, \quad \quad p=n+1,\ldots ,n+m</math>
|}
| style="width: 5px;text-align: right;white-space: nowrap;" |(12)
|}

12) Preventing customer re-service from another depot

{| class="formulaSCP" style="width: 100%; text-align: left;" 
|-
| 
{| style="text-align: center; margin:auto;width: 100%;" 
|-
| style="text-align: center;" | <math>{X}_{p1ikp2}=0,\quad \, \, i=1,\ldots n,\quad k=1,\ldots ,K,\quad {p}_{1}\not ={p}_{2}=n+1,\ldots ,n+m</math>
|}
| style="width: 5px;text-align: right;white-space: nowrap;" |(13)
|}


13) The starting and finishing of each tour is in the same depot

{| class="formulaSCP" style="width: 100%; text-align: left;" 
|-
| 
{| style="text-align: center; margin:auto;width: 100%;" 
|-
| style="text-align: center;" | <math>{X}_{ip1kp2}=0,i=1,\ldots ,n,\, \, k=1,\ldots ,K,{p}_{1}\not ={p}_{2}=n+1,\ldots ,n+m</math>
|}
| style="width: 5px;text-align: right;white-space: nowrap;" |(14)
|}

14)  This indicates that the value of the variable is binary 

{| class="formulaSCP" style="width: 100%; text-align: left;" 
|-
| 
{| style="text-align: center; margin:auto;width: 100%;" 
|-
| style="text-align: center;" | <math>{X}_{ijkp}\in \left\{ 0,1\right\} ,i,j=1,\ldots ,n+m,\, k=1,\ldots ,K,\, p=1,\ldots ,n+m</math>
|}
| style="width: 5px;text-align: right;white-space: nowrap;" |(15)
|}

15) The amount of demand of each customer cannot be zero or negative

{| class="formulaSCP" style="width: 100%; text-align: left;" 
|-
| 
{| style="text-align: center; margin:auto;width: 100%;" 
|-
| style="text-align: center;" | <math>{Y}_{ij}\geq 0,i,j=1,\ldots ,n+m</math>
|}
| style="width: 5px;text-align: right;white-space: nowrap;" |(16)
|}

16) The time variable cannot be negative

{| class="formulaSCP" style="width: 100%; text-align: left;" 
|-
| 
{| style="text-align: center; margin:auto;width: 100%;" 
|-
| style="text-align: center;" | <math>{W}_{ik}\geq 0,i=1,\ldots ,n+m,\, k=1,\ldots K</math>
|}
| style="width: 5px;text-align: right;white-space: nowrap;" |(17)
|}


Despite many studies conducted based on the VRP, many researchers tried to present realistic applications modeling for Optimal Logistics System. Generally, possible models for routing are a function of the number of nodes or customers, models number can be found as n! That n represents the number of nodes. With increasing the number of customers and vehicles, one of the most practical methods to solving the multi- Depot logistics problem is to change the problem frame from multi depots to single depot. For achieving this goal, customers must be clustered based on depots with considering constraints from assigning customers to depots and solving the problem separately for each cluster. [[#img-1|Figure 1]]  shows the general method of solving multi-depot problems. To solve the MHDHVRPTW problem that is the subject of this study, we used a binary algorithm to label all nodes, then with considering the type of depots (single or multi goods) and the customer needs based on the type of goods that were requested, clustering for nodes or customer would be started based on the nearest depot. In this stage, after matching the goods with the supplier depots, the nodes are clustered based on the nearest neighbor (Knn) algorithm, and then using the fuzzy C-means algorithm, re-clustering will take inside each depots cluster. Acceptance of this nested clustering makes the problem space more suitable for using optimizers, especially genetic algorithms. The results show that using this innovative method caused to reduction distance that has been traveled compared to previous methods, on the other hand, due to the direct relationship between the distance and time, reducing time is concluded.

==4. Genetic algorithm and its application in routing==

The genetic algorithm is an optimization technique using the principles of biological evolution, natural selection, gene recombination, and survival of the correct gene in living natural systems, which has been used and studied in optimization topics. The components of this algorithm are primary population or random chromosomes, which is one of the primary and efficient methods for selecting the initial population of local search. Also, the fitting function is used to evaluate the quality of chromosomes. Each chromosome is a selection of two parents. Combined with intersection and mutation operators. These steps are repeated until the stop criterion is reached. [[#img-1|Figure 1]]  shows the different steps of the proposed method. In this study, each chromosome includes a round trip to the depot, the chromosome consisting of genes or nodes that customers rout in the system. The method for generating chromosomes for initial population forming is a random Selection of customers that have been clustered.

It starts based on the nearest neighbor to depots (depends on the closest node or customer to the depots the matches the product), so there is some cluster to depots numbers. 

<div id='img-1'></div>
{| style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: auto;max-width: auto;"
|-
|style="padding:10px;"|  [[Image:Review_991459929896-image1.png|240px]]
|- style="text-align: center; font-size: 75%;"
| colspan="2" style="padding:10px;"| '''Figure 1'''. Schematic of the MDVRP heuristic approach
|}

Chromosomes or primary routes are formed based on a number of nodes in a path according to the constraints (defined in the previous section). In this method, no initial solution for solving the problem is provided, and according to the problem state space, all points within a cluster are reckoned up for routing. Therefore, according to this algorithm, chromosomes or the initial population are initially formed randomly. The selection operator includes the selection of two parents for the crossover and the mutation. At this stage, by using tournament, the conditions of the operator are better selected and it is based on a random selection of people. The number of vehicles indicates the number of races or routes. Tournaments are performed with <math>k</math> members in this group to select the best two chromosomes (in terms of the fitness function) as parents chromosomes, all chromosomes produced are checked for constraints in each replication. The selection method prevents the optimal occurrence of localization and avoids wasting time in recovering impossible solutions. The crossover operator starts after the selection operator (based on tournaments) of the two-parent chromosomes as shown in [[#img-2|Figure 2]].

<div id='img-2'></div>
{| style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: auto;max-width: auto;"
|-
|style="padding:10px;"|  [[Image:Review_991459929896-image2.png|282px]]
|- style="text-align: center; font-size: 75%;"
| colspan="1" style="padding:10px;"| '''Figure 2'''. The swap mutation
|}


The crossover strategy involves randomly selecting a path from the first parent to replace a complete path in the second parent to create offspring. Offspring are rarely credible because some customers are grouped in this way without routing ([[#img-3|Figure 3]]). Therefore, the implementation steps of the genetic algorithm are as follows:

:*Due to the randomness of the initial population and the use of crossover and mutation strategies, if there are two identical nodes in two chromosomes, this node is considered in the first chromosome and is included in the tabu list, which means that The first optimal choice, if the constraints match, is in the forbidden list of nodes and stays in the path.

:*If the node is not placed in any tour, the smallest capacity of the vehicle is considered for the last tour and customer service, in this case, due to the small number of these nodes, the probability of meeting the existing restrictions is high. Mutation: Because this strategy has a limited range, in some cases a very small effect on chromosome gene unit exchange is suggested to produce better offspring. This practice is used to increase the diversity of both the population and the solutions produced. At the end of this process, the final solution is formed. Therefore, because in the cluster related to each depot, all nodes are closer to the depot of that cluster than other warehouses, it can be concluded that the path taken to service the nodes in this cluster has better conditions and the objective function has better evaluation. This condition for all steps (selection, recombination, and mutation) is repeated until a certain number of generations are reached in order to achieve the optimal customer service path.

<div id='img-3'></div>
{| style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: auto;max-width: auto;"
|-
|style="padding:10px;"|  [[Image:Review_991459929896-image3.png|300px]]
|- style="text-align: center; font-size: 75%;"
| colspan="1" style="padding:10px;"| '''Figure 3'''. The crossover strategy
|}

==5. Results and discussion==

According to several routing publications that have used Dr. Cordeu datasets, in this article, a similar database has been used for simulation. In [[#tab-2|Table 2]], the data information such as the number and capacity of vehicles, number of depot and nodes are specified.

The suggested GA code is written in MATLAB version (R2018b). The performance of the proposed method has been tested in 6 benchmark samples. These cases have been suggested by Dr. Cordeu and are considered for comparison in this article. Also, recognizing supply and service from the nearest depot has added to the problem with compared to other publications.

<div class="center" style="font-size: 75%;">'''Table 2'''. The courdeu dataset</div>

<div id='tab-2'></div>
{| class="wikitable" style="margin: 1em auto 0.1em auto;border-collapse: collapse;font-size:85%;width:auto;" 
|-style="text-align:center"
!Type !! Nodes !! Customers !! Depots !! Vehicles !! Capacity of Vehicles !! Max Tour Duration 
|-
|  style="text-align: center;vertical-align: top;"|'''Pr-01'''
|  style="text-align: center;vertical-align: top;"|52
|  style=";text-align: center;vertical-align: top;"|48
|  style="text-align: center;vertical-align: top;"|4
|  style="text-align: center;vertical-align: top;"|8
|  style="text-align: center;vertical-align: top;"|200
|  style="text-align: center;vertical-align: top;"|500
|-
|  style="text-align: center;vertical-align: top;"|'''Pr-02'''
|  style="text-align: center;vertical-align: top;"|100
|  style="text-align: center;vertical-align: top;"|96
|  style="text-align: center;vertical-align: top;"|4
|  style="text-align: center;vertical-align: top;"|12
|  style="text-align: center;vertical-align: top;"|195
|  style="text-align: center;vertical-align: top;"|480
|-
|  style="text-align: center;vertical-align: top;"|'''Pr-03'''
|  style="text-align: center;vertical-align: top;"|148
|  style="text-align: center;vertical-align: top;"|144
|  style="text-align: center;vertical-align: top;"|4
|  style="text-align: center;vertical-align: top;"|16
|  style="text-align: center;vertical-align: top;"|190
|  style="text-align: center;vertical-align: top;"|460
|-
|  style="text-align: center;vertical-align: top;"|'''Pr-04'''
|  style="text-align: center;vertical-align: top;"|196
|  style="text-align: center;vertical-align: top;"|192
|  style="text-align: center;vertical-align: top;"|4
|  style="text-align: center;vertical-align: top;"|20
|  style="text-align: center;vertical-align: top;"|185
|  style="text-align: center;vertical-align: top;"|440
|-
|  style="text-align: center;vertical-align: top;"|'''Pr-07'''
|  style="text-align: center;vertical-align: top;"|78
|  style="text-align: center;vertical-align: top;"|72
|  style="text-align: center;vertical-align: top;"|6
|  style="text-align: center;vertical-align: top;"|12
|  style="text-align: center;vertical-align: top;"|200
|  style="text-align: center;vertical-align: top;"|500
|-
|  style="text-align: center;vertical-align: top;"|'''Pr-11'''
|  style="text-align: center;vertical-align: top;"|52
|  style="text-align: center;vertical-align: top;"|48
|  style="text-align: center;vertical-align: top;"|4
|  style="text-align: center;vertical-align: top;"|4
|  style="text-align: center;vertical-align: top;"|200
|  style=";text-align: center;vertical-align: top;"|500
|-
|  style="text-align: center;vertical-align: top;"|'''Pr-17'''
|  style="text-align: center;vertical-align: top;"|78
|  style="text-align: center;vertical-align: top;"|72
|  style="text-align: center;vertical-align: top;"|6
|  style="text-align: center;vertical-align: top;"|6
|  style="text-align: center;vertical-align: top;"|200
|  style="text-align: center;vertical-align: top;"|500
|}


The data used in other articles, including B. Rabbouch (2019), are also used to achieve similar results and to better examine the proposed method with other publications. Generally using a heterogeneous fleet was the idea that has been repeatedly presented in different publications considered by ([[#tab-2|Table 2]]) researchers to reduce direct costs. Appropriating capacity for distribution or collection of goods reducing time, emissions, fuel consumption another achievement of this proposed.

In this article, regardless of all the announced benefits, it intends to show a greater reduction in the path traveled using the proposed method compared to other methods. In addition, by using a simple labeling method for customers, it assigns each node or customer to the nearest depot that owns the same product and can re-optimize the routing problem based on the stated method and get good results. To present in this regard. As previously announced, due to the lack of similar publications to compare methods, in this article we will review the proposed method for solving the MDVPRTW problem and the MDHVRPTW problem and review with other publications. In the proposed method, the basic parameters for the genetic algorithm are specified in [[#tab-3|Table 3]]. Shows the same product and can re-optimize the routing problem based on the stated method and get good results. To present in this regard. As previously announced, due to the lack of similar publications to compare methods, in this article we will review the proposed method for solving the MDVPRTW problem and the MDHVRPTW problem and review with other publications. In the proposed method, the basic parameters for the genetic algorithm are specified in [[#tab-3|Table 3]].

[[#tab-3|Table 3]] shows the best results obtained methods can be considered in the computing power for more customers, in some methods previous publications for 196 customers had due to the fact that no study on MHDHVRPTW has been published so far, so it is not possible to compare the proposed method with other methods. To compare the proposed method apart from the project conditions in this study, review the results for similar conditions in publications MDVRPTW We are dealing with Cordio dataset. [[#tab-4|Table 4]] shows the MDVRPTW problem-solving outputs using the proposed method, in which the calculation time is also implemented.

<div class="center" style="font-size: 75%;">'''Table 3'''. The results for proposed method</div>

<div id='tab-3'></div>
{| class="wikitable" style="margin: 1em auto 0.1em auto;border-collapse: collapse;font-size:85%;width:auto;" 
|-style="text-align:center"
!Pr17 !! Pr11 !! Pr07 !! Pr04 !! Pr03 !! Pr02 !! Pr01 !! colspan="2" style="text-align:center;" | Item
|-
|  style="text-align: center;vertical-align: top;"|6
|  style="text-align: center;vertical-align: top;"|6
|  style="text-align: center;vertical-align: top;"|11
|  colspan='2'  style="text-align: center;vertical-align: top;"|21
|  style="text-align: center;vertical-align: top;"|17
|  style="text-align: center;vertical-align: top;"|12
|  style="text-align: center;vertical-align: top;"|6
|  style="text-align: left;vertical-align: top;"|Route
|-
|  style="text-align: center;vertical-align: top;"|1155,48
|  style="text-align: center;vertical-align: top;"|933.27
|  style="text-align: center;vertical-align: top;"|1261.1
|  colspan='2'  style="text-align: center;vertical-align: top;"|2712.5
|  style="text-align: center;vertical-align: top;"|2132
|  style="text-align: center;vertical-align: top;"|1690.6
|  style="text-align: center;vertical-align: top;"|973.99
|  style="text-align: left;vertical-align: top;"|Distance
|-
|  style="text-align: center;vertical-align: top;"|118
|  style="text-align: center;vertical-align: top;"|99
|  style="text-align: center;vertical-align: top;"|92
|  colspan='2'  style="text-align: center;vertical-align: top;"|238
|  style="text-align: center;vertical-align: top;"|189
|  style="text-align: center;vertical-align: top;"|149
|  style="text-align: center;vertical-align: top;"|83
|  style="text-align: left;vertical-align: top;"|CPU
|}


Comparing the proposed method with the data of recent publications, the path as shown in [[#img-4|Figure 4]] is taken in this method is significantly reduced compared to other methods. In 2019, Robocha introduced an innovative method that is compared in [[#tab-5|Table 5]] with the outputs of the proposed method. In this table, the route traveled by vehicles has been significantly reduced, but the program time has also been increased to some extent. The reason for this is to perform dual and hierarchical clustering for each sample to determine the distance changes, we presented in [[#tab-4|Table 4]]. This table specifies the percentage of route reduction and how effective it can be in and how effective it can be in routing.

<div id='img-4'></div>
{| style="text-align: center; border: 1px solid #BBB; margin: 1em auto; width: auto;max-width: auto;"
|-
|  style="text-align: center;padding:10px;"| [[Image:Review_991459929896-image4.png|center|276px]]
|  style="text-align: center;padding:10px;"| [[Image:Review_991459929896-image5.png|center|288px]]
|-
|  style="text-align: center;padding:10px;"| [[Image:Review_991459929896-image6.png|center|282px]]
|  style="text-align: center;padding:10px;"| [[Image:Review_991459929896-image9.png|center|276px]]
|-
|- style="text-align: center; font-size: 75%;"
| colspan="2" style="padding:10px;"| '''Figure 4'''. Pr01 results for MHDHFVRPTW
|}


<div class="center" style="font-size: 75%;">'''Table 4'''. Comparing distance proposed method with Robucha (2019)</div>

<div id='tab-4'></div>
{| class="wikitable" style="margin: 1em auto 0.1em auto;border-collapse: collapse;font-size:85%;width:auto;" 
|-style="text-align:center"
! Pr17 !! Pr11 !! Pr07 !! Pr04 !! Pr03 !! colspan='2'  style="text-align: center;"| Pr02 !! Pr01
|-
|  style="text-align: center;vertical-align: top;"|1155.48
|  style="text-align: center;vertical-align: top;"|933.27
|  style="text-align: center;vertical-align: top;"|1261.1
|  style=";text-align: center;vertical-align: top;"|2712.5
|  style="text-align: center;vertical-align: top;"|2132
|  colspan='2'  style="text-align: center;vertical-align: top;"|1690.6
|  style="text-align: center;vertical-align: top;"|973.99
|  style="text-align: left;vertical-align: top;"|Proposed method distance
|-
|  style="text-align: center;vertical-align: top;"|1355.48
|  style=";text-align: center;vertical-align: top;"|1100.97
|  colspan='2'  style="text-align: center;vertical-align: top;"|1461.1
|  style="text-align: center;vertical-align: top;"|3012.76
|  style="text-align: center;vertical-align: top;"|2481.32
|  style="text-align: center;vertical-align: top;"|1824.49
|  style="text-align: center;vertical-align: top;"|1112.83
|  style="text-align: left;vertical-align: top;"|R. Robocha (2019) distance
|-
|  style="text-align: center;vertical-align: top;"|14.25%
|  style="text-align: center;vertical-align: top;"|7.09%
|  colspan='2' style="text-align: center;vertical-align: top;"|16.38%
|  style="text-align: center;vertical-align: top;"|11.06%
|  style="text-align: center;vertical-align: top;"|15.8%
|  style="text-align: center;vertical-align: top;"|10.8%
|  style="text-align: center;vertical-align: top;"|17.3%
|  style="text-align: left;vertical-align: top;"|Percentage changes 
|}


Comparing the proposed method with the data of recent publications, the path is taken in this method is significantly reduced compared to other methods. In 2019, Robocha introduced an innovative method that is compared in [[#tab-5|Table 5]] with the outputs of the proposed method. In this table, the route traveled by vehicles has been significantly reduced, but the program time has also been increased to some extent. The reason for this is to perform dual and hierarchical clustering for each sample to determine the distance changes, we presented [[#tab-6|Table 6]]. This table specifies the percentage of route reduction and how effective it can be in routing.

<div class="center" style="font-size: 75%;">'''Table 5'''. Comparing proposed method with Robucha (2019)</div>

<div id='tab-1'></div>
{| class="wikitable" style="margin: 1em auto 0.1em auto;border-collapse: collapse;font-size:85%;width:auto;" 
|-style="text-align:center"
!Pr17 !! Pr11 !! Pr07 !! Pr04 !! Pr03 !! Pr02 !! Pr01 !! 
|-
|  style="text-align: center;vertical-align: top;"|1155,48
|  style="text-align: center;vertical-align: top;"|933.27
|  style="text-align: center;vertical-align: top;"|1261.1
|  style="text-align: center;vertical-align: top;"|2712.5
|  style="text-align: center;vertical-align: top;"|2132
|  style="text-align: center;vertical-align: top;"|1690.6
|  style="text-align: center;vertical-align: top;"|973.99
|  style="text-align: left;vertical-align: top;"|Proposed method distance
|-
|  style="text-align: center;vertical-align: top;"|118
|  style="text-align: center;vertical-align: top;"|99
|  style="text-align: center;vertical-align: top;"|92
|  style="text-align: center;vertical-align: top;"|238
|  style="text-align: center;vertical-align: top;"|189
|  style="text-align: center;vertical-align: top;"|149
|  style="text-align: center;vertical-align: top;"|83
|  style="text-align: left;vertical-align: top;"|Proposed method CPU
|-
|  style="text-align: center;vertical-align: top;"|1355.48
|  style="text-align: center;vertical-align: top;"|1100.97
|  style="text-align: center;vertical-align: top;"|1461.1
|  style="text-align: center;vertical-align: top;"|3012.76
|  style="text-align: center;vertical-align: top;"|2481.32
|  style="text-align: center;vertical-align: top;"|1824.49
|  style="text-align: center;vertical-align: top;"|1112.83
|  style="text-align: left;vertical-align: top;"|R. Robocha (2019) method distance
|-
|  style="text-align: center;vertical-align: top;"|117.023
|  style="text-align: center;vertical-align: top;"|95.139
|  style="text-align: center;vertical-align: top;"|84.165
|  style="text-align: center;vertical-align: top;"|174.972
|  style="text-align: center;vertical-align: top;"|145.453
|  style="text-align: center;vertical-align: top;"|100.479
|  style="text-align: center;vertical-align: top;"|63.161
|  style="text-align: left;vertical-align: top;"|R. Robocha (2019) method CPU
|}


As it was announced, the maximum reduction of the path traveled by the proposed method is about 17.3% and the minimum is 7.09% compared to the recent method, while the amount of calculation time has also increased and this increase from the minimum of 0.83% It is up to a maximum of 48%, but considering that the difference in the maximum amount of CPU time  is only 49 seconds compared to the recent method, this time seems reasonable compared to the result obtained. [[#tab-6|Table 6]] shows the values obtained in the MDVRPTW State of Art problem with the answers obtained with the proposed method. The values obtained from this method are based on the best results obtained in each sample of Cordio. In this table, by comparing the lengths of the obtained paths, we conclude that the proposed method has given more appropriate answers to the MDVRPTW problem.

<div class="center" style="font-size: 75%;">'''Table 6'''. Compering proposed method with State of Art</div>

<div id='tab-6'></div>
{| class="wikitable" style="margin: 1em auto 0.1em auto;border-collapse: collapse;font-size:85%;width:auto;" 
|-style="text-align:center"
! Pr17 !! Pr11 !! Pr07 !! Pr04 !! Pr03 !! Pr02 !! Pr01
|-
|  style="text-align: center;vertical-align: top;"|1155,48
|  style="text-align: center;vertical-align: top;"|933.27
|  style="text-align: center;vertical-align: top;"|1261.1
|  style="text-align: center;vertical-align: top;"|2712.5
|  style="text-align: center;vertical-align: top;"|2132
|  style="text-align: center;vertical-align: top;"|1690.6
|  style="text-align: center;vertical-align: top;"|973.99
|  style="text-align: left;vertical-align: top;"|Proposed method distance
|-
|  style="text-align: center;vertical-align: top;"|2
|  style="text-align: center;vertical-align: top;"|1.65
|  style="text-align: center;vertical-align: top;"|1.52
|  style="text-align: center;vertical-align: top;"|4
|  style="text-align: center;vertical-align: top;"|3.15
|  style="text-align: center;vertical-align: top;"|3.48
|  style="text-align: center;vertical-align: top;"|2.38
|  style="text-align: left;vertical-align: top;"|Proposed method CPU
|-
|  style="text-align: center;vertical-align: top;"|1236.24
|  style="text-align: center;vertical-align: top;"|933.27
|  style="text-align: center;vertical-align: top;"|1418.22
|  style="text-align: center;vertical-align: top;"|2815.48
|  style="text-align: center;vertical-align: top;"|2373.65
|  style="text-align: center;vertical-align: top;"|1762.21
|  style="text-align: center;vertical-align: top;"|1047.12
|  style="text-align: left;vertical-align: top;"|State of art method distance
|-
|  style="text-align: center;vertical-align: top;"|5.8
|  style="text-align: center;vertical-align: top;"|1.8
|  style="text-align: center;vertical-align: top;"|5.3
|  style="text-align: center;vertical-align: top;"|15.2
|  style="text-align: center;vertical-align: top;"|11.5
|  style="text-align: center;vertical-align: top;"|7.9
|  style="text-align: center;vertical-align: top;"|0.36
|  style="text-align: left;vertical-align: top;"|State of art method CPU 
|-
|  style="text-align: center;vertical-align: top;"|Li [9]
|  style="text-align: center;vertical-align: top;"|Li [9]
|  style="text-align: center;vertical-align: top;"|Cordeu [8]
|  style="text-align: center;vertical-align: top;"|Polacek [10]
|  style="vertical-align: top;"|Cordeu [8]
|  style="vertical-align: top;"|Cordeu [8]
|  style="text-align: left;vertical-align: top;"|Bettinelli [11]
|}

==6. Conclusion==

In this study, an attempt was made to express more realistic conditions for the distribution or collection of goods. Due to the direct relationship between route length and transportation costs, air pollutants, delivery time, etc., the aim of this study was to reduce the route for vehicles. In this study, it is specified that in order to achieve the goal of the least amount of route length in routing, it is better to use vehicles with more capacity to prevent return routes to warehouses. Also, for Hard Time Windows, more vehicles should be provided for delivery of goods on time. One of the issues that can be studied in the future to optimize the routing of vehicles with multiple depots and heterogeneous vehicles is to study based on multi-objectives with the goals of minimizing the length and of vehicles, the appropriateness of vehicle capacity, and number.

==References==
<div class="auto" style="text-align: left;width: auto; margin-left: auto; margin-right: auto;font-size: 85%;">

[1] Mollajafari M., Shahhoseini H.S. An efficient ACO-based algorithm for scheduling tasks onto dynamically reconfigurable hardware using TSP-likened construction graph. Appl Intell., 45:695–712, 2016.

[2] Renaud J., Laporte G.,  Boctor F.F. A tabu search heuristic for the multi-depot vehicle routing problem. Computers & Operations Research, 23(3):229-235, 1996.

[3] Cordeau J.‐F., Gendreau M., Laporte G. A tabu search heuristic for periodic and multi‐depot vehicle routing problems. Networks: An International Journal, 30(2):105-119, 1997.

[4] Mollajafari M., Shojaeefard M.H. TC3PoP: A time-cost compromised workflow scheduling heuristic customized for cloud environments. Cluster Computing, 1-18, 2021.

[5] Shahhoseini H.S., Kandzi E.S., Mollajafari M. Nonflat surface level pyramid: a high connectivity multidimensional interconnection network. The Journal of Supercomputing, 67(1):31-46, 2014.

[6] Bettinelli A., Ceselli A., Righini G. A branch-and-cut-and-price algorithm for the multi-depot heterogeneous vehicle routing problem with time windows. Transportation Research Part C: Emerging Technologies, 19(5):723-740, 2011.

[7] Mohtavipour S.M., Mollajafari M.,  Naseri A. A novel packet exchanging strategy for preventing HoL-blocking in fat-trees. Cluster Comput, 23:461–482, 2020.

[8] Pan B., Zhang Z., Lim A. Multi-trip time-dependent vehicle routing problem with time windows. European Journal of Operational Research, 291(1):218-231, 2021.

[9] Mollajafari M., Shahhoseini H.S. A repair-less genetic algorithm for scheduling tasks onto dynamically reconfigurable hardware. International Review on Computers and Software, 6(2):206-212, 2011.

[10] Mollajafari M., Shahhoseini H.S. Cost-optimized GA-based heuristic for scheduling time-constrained workflow applications in infrastructure clouds using an innovative feasibility-assured decoding mechanism. J. Inf. Sci. Eng., 32(6):1541-1560, 2016.

[11] Dantzig G. B., Ramser J.H. The truck dispatching problem. Management Science, 6(1):80-91, 1959.

[12] Dondo R.,  Mendez C.A., Cerdá J. An optimal approach to the multiple-depot heterogeneous vehicle routing problem with time window and capacity constraints. Latin American Applied Research, 33(2):129-134, 2003.

[13] Dondo R., Cerdá J. A cluster-based optimization approach for the multi-depot heterogeneous fleet vehicle routing problem with time windows. European Journal of Operational Research, 176(3):1478-1507, 2007.

[14] Tummel C., et al. The Multi-depot heterogeneous fleet vehicle routing problem with time windows and assignment restrictions (m-vrptwar). Automation, Communication and Cybernetics in Science and Engineering 2011/2012,  Springer, Berlin, Heidelberg,  767-779, 2013. 

[15] Guezouli L., Abdelhamid S. Multi-objective optimisation using genetic algorithm based clustering for multi-depot heterogeneous fleet vehicle routing problem with time windows. International Journal of Mathematics in Operational Research, 13(3):332-349, 2018.

[16] Rabbouch B., Saâdaoui F., Mraihi R. Efficient implementation of the genetic algorithm to solve rich vehicle routing problems. Operational Research, 21:1763–1791, 2021.

[17] Cao B., Zhang W., Wang X., Zhao J., Gu Y.,  Zhang Y. A memetic algorithm based on two_Arch2 for multi-depot heterogeneous-vehicle capacitated Arc routing problem. Swarm and Evolutionary Computation, 63, 100864, 2021.

[18] Nucamendi-Guillén S., Padilla A.G., Olivares-Benitez E., Moreno-Vega J.M. (2021). The multi-depot open location routing problem with a heterogeneous fixed fleet. Expert Systems with Applications, 165, 113846, 2021.

[19] Yeh W.C.,  Tan S.Y. Simplified swarm optimization for the heterogeneous fleet vehicle routing problem with time-varying continuous speed function. Electronics, 10(15):1775, 2021.

[20] Bernal J., Escobar J.W.,  Linfati R. A simulated annealing-based approach for a real case study of vehicle routing problem with a heterogeneous fleet and time windows. International Journal of Shipping and Transport Logistics, 13(1-2):185-204, 2021.

[21] Su Z., Li W., Li J., Cheng B. Heterogeneous fleet vehicle scheduling problems for dynamic pickup and delivery problem with time windows in shared logistics platform: formulation, instances and algorithms. International Journal of Systems Science: Operations & Logistics, 1-25, 2021.

[22] Phuc K., Nguyen P., and Phuong Thao, N.L. "Ant colony optimization for multiple pickup and multiple delivery vehicle routing problem with time window and heterogeneous fleets." Logistics, 5(2):28, 2021.

[23] Kocatürk F., Tütüncü G.Y., Salhi S.  The multi-depot heterogeneous VRP with backhauls: formulation and a hybrid VNS with GRAMPS meta-heuristic approach. Annals of Operations Research, 1-26, 2021.

[24] Yu Y., Wang S., Wang J., Huang M. A branch-and-price algorithm for the heterogeneous fleet green vehicle routing problem with time windows. Transportation Research Part B: Methodological, 122:511-527, 2019.

[25] Afshar-Nadjafi B., Afshar-Nadjafi A. A constructive heuristic for time-dependent multi-depot vehicle routing problem with time-windows and heterogeneous fleet. Journal of King Saud University-Engineering Sciences, 29(1):29-34, 2017. 

[26] Rabbouch B., Mraihi R., Saâdaoui F. A recent brief survey for the multi depot heterogenous vehicle routing problem with time windows. In International Conference on Hybrid Intelligent Systems, 147-157, 2017.

[27] Bettinelli A., Ceselli A., Righini G. A branch-and-price algorithm for the multi-depot heterogeneous-fleet pickup and delivery problem with soft time windows. Mathematical Programming Computation, 6(2):171-197, 2014.

[28] Adelzadeh M., Asl V.M., Koosha M.  A mathematical model and a solving procedure for multi-depot vehicle routing problem with fuzzy time window and heterogeneous vehicle. International Journal of Advanced Manufacturing Technology, 75(5-8):793-802, 2014.

[29] Xu Y., Wang L., Yang Y. A new variable neighborhood search algorithm for the multi depot heterogeneous vehicle routing problem with time windows. Electronic Notes in Discrete Mathematics, 39:289-296, 2012.

[30] Dondo R., Cerdá J. A reactive MILP approach to the multidepot heterogeneous fleet vehicle routing problem with time windows. International Transactions in Operational Research, 13(5):441-459, 2006.

[31] Polacek M., Hartl R.F., Doerner K., Reimann M. A variable neighborhood search for the multidepot vehicle routing problem with time windows. J. Heuristics, 10(6) 613–627, 2004.

[32] Li J., Li Y.,  Pardalos P.M. Multi-depot vehicle routing problem with time windows under shared depot resources. Journal of Combinatorial Optimization, 31(2):515-532, 2016.