# A Hybrid Ant Colony Optimization for Dynamic Multidepot Vehicle Routing Problem

Authors: Haitao Xu; Pan Pu; Feng Duan
Journal: Discrete Dynamics in Nature and Society
 (2018)

---

## Abstract

In the real world, the vehicle routing problem (VRP) is dynamic and variable, so dynamic vehicle routing problem (DVRP) has obtained more and more attentions among researchers. Meanwhile, due to actual constraints of service hours and service distances, logistics companies usually build multiple depots to serve a great number of dispersed customers. Thus, the research of dynamic multidepot vehicle routing problem (DMDVRP) is significant and essential. However, it has not attracted much attention. In this paper, firstly, a clustering approach based on the nearest distance is proposed to allocate all customers to the depots. Then a hybrid ant colony optimization (HACO) with mutation operation and local interchange is introduced to optimize vehicle routes. In addition, in order to deal with dynamic problem of DMDVRP quickly, a real-time addition and optimization approach is designed to handle the new customer requests. Finally, thet-test is applied to evaluate the proposed algorithm; meanwhile the relations between degrees of dynamism (dod) and HACO are discussed minutely. Experimental results show that the HACO algorithm is feasible and efficient to solve DMDVRP.


---

## Body

## 1. Introduction

In the history of VRP, the most original and famous routing problem is Traveling Salesman Problem (TSP) [1]. By transforming the TSP, a great number of different kinds of VRP are designed. Generally, VRP has been classified to the following several variants: Capacitated VRP (CVRP), VRP with time windows (VRPTW), VRP with Pickup and Delivery (VRPPD), multidepot VRP (MDVRP), and so on [2–6]. Most particularly, considering that many logistics companies are desirous to improve service quality and save time, the MDVRP receives more and more attentions.In VRP models, most of the researchers usually define some basic information concerning customers’ locations and demands, available vehicles, etc., which are entirely known before carrying out service. However, VRP is dynamic in most of the actual situations; in other words, the arrangements of customers are changing gradually over time, although a part of customer requests may be known in advance. In recent years, due to the development of new technologies, such as Global Position System, Communication Technology, Information Technology, some researchers have studied DVRP. However, few researchers focus on DVRP with multiple depots, so this paper will study dynamic multidepot vehicle routing problem (DMDVRP) [7].Comparatively, the number of research projects on the DMDVRP is fewer. T. C. Su introduced a dynamic vehicle control and scheduling of a multidepot physical distribution system in 1999 [8]. For solving dynamic multidepot pickup and delivery problem, T. Huth and D. C. Mattfeld proposed a framework to anticipate dynamic events by model adaptation in 2006 [9]. In 2008, A. Hadjar and F. Soumis introduced multidepot vehicle scheduling problem with time windows, which is a dynamic window reduction. Y. Kuo and C. C. Wang proposed an insertion heuristic to solve dynamic multidepot vehicle routing problem where the pick-up and delivery requests are both considered in 2014 [10]. Liu Y et al. proposed a method with three steps to solve the multiperiod and multidepot dynamic vehicle routing problem with time windows in 2016 [7].In general, DMDVRP is a NP-hard problem [11], so some exact algorithms (branch and bound algorithm, linear programming, cutting plane algorithm, etc.) are almost impossible to solve it in finite time. However, modern heuristic algorithms, such as ant colony optimization (ACO) [12, 13], genetic algorithm (GA) [14–16], and particle swarm optimization (PSO) [17], have the ability to generate high quality solutions, although they may not search the best solution. In these approaches, ACO is widely applied to solve different types of VRP.The original ACO was put forward by Dorigo in his Ph.D. Thesis [18], which is called ant system. However, it is nonconvergent and easy to fall into local optimization. To improve its weaknesses, many researchers have formed several variants of the ant system, such as the ant colony system, the elite ant system, and the largest ant system [19]. In addition, some new mechanisms are proposed to optimize the algorithm, such as enlarging the degree of random search [13], N-Opt local random search, and designing distributed control [20]. For DMDVRP, the objective of the algorithm is not only to search the optimal solution, but also to track the optimal solution through the information of the previous search space over time. Based on this consideration, a hybrid ACO is proposed to solve DMDVRP.There are two main contributions in this paper. The first contribution of this paper is to use hybrid ACO algorithm to solve DMDVRP, and the method strives to improve the randomization and avoids falling into local search prematurely. In order to improve ACO, the following modifications of ACO are implemented:(1)
Dividing region by the nearest distance cluster(2)
Optimizing vehicle routes with mutation operation(3)
Improving the solutions with local interchange operationHybrid ACO has shown its advantages through a large number of comparative experiments based on data sets of different scales.The second contribution is that a real-time addition and optimization approach is designed to add new real-time customers to known routes and immediately optimize vehicle routes. The process of dynamic optimization can be accelerated.The remainder of this paper is organized as follows. In Section2, we describe DMDVRP model and define the problem. In Section 3, the details of hybrid ACO are shown. A real-time addition and optimization approach is introduced in Section 4. Experimental results are discussed in Section 5. Some conclusions are provided in Section 6.


## 2. Dynamic Multidepot Vehicle Routing Problem

### 2.1. The Description of DMDVRP

In the real world, MDVRP is affected by the dynamic environment. With the wide application of information technology and Global Positioning System (GPS) technology, the process of logistics service can be tracked and adjusted in real time. Due to the development of these new technologies, the service mode of plan-execute is replaced by the dynamic execution task [21].Generally speaking, the dynamic nature of DMVRP mainly reflects the uncertainty of customer requests in the service process. Specifically, the type of request includes the uncertain quantity of goods [21–23] and the uncertain service time [24, 25]. This paper focuses on the change of service time and processing orders dynamically according to customer request time. A DMDVRP example is shown in Figure 1. In Figure 1(a), three different depots (red square) are responsible to serve the customers (black dots) which are allocated to them, and black and red lines represent initial routes. In Figure 1(b), some new customers (blue triangle) are added to system, and some new routes will be generated in time.Figure 1
An example of DMDVRP with three depots.
(a)
Initial routes (b)
Dynamic routes


### 2.2. The Formulation of DMDVRP

The DMDVRP can be formalized as follows. An undirected graphG=(V,E) is established to describe mathematical model. In this model, V={VC,VD} represents the vertex set and E=vi,vj∣vi,vj∈V,i<j is the edge set. VC={v1,v2,…,vn} is the set of customers and VD={vn+1,vn+2,…,vn+m} is the set of depots. InE, we get distance matrix C=(cij) by calculating the Euclidean distance of customers vi and vj. Every customer vi has a demand qi and needs to be visited once by only one vehicle. There is also a fleet ofK identical vehicles, each with capacityQ.In the mathematical formulation that follows, binary variablexijk is equal to 1 when vehiclek visits nodej immediately after nodei.(1)Minimize∑i=1n+m∑j=1n+m∑k=1Kcijxijk,subject to(2)∑i=1n+m∑k=1Kxijk=1j=1,2,…,n;(3)∑j=1n+m∑k=1Kxijk=1i=1,2,…,n;(4)∑i=1n+m∑j=1n+mqixijk≤Qk=1,2,…,K;(5)∑i=n+1n+m∑j=1nxijk≤1k=1,2,…,K;(6)∑j=n+1n+m∑i=1nxijk≤1k=1,2,…,K.The objective (1) minimizes the total cost. Constraints (2) and (3) guarantee that each customer is served by exactly one vehicle. Vehicle capacity constraint is found in (4). Finally, constraints (5) and (6) check vehicle availability.


### 2.3. Measuring Dynamism

In most papers, three popular metrics ofdegree of dynamism [16],effective degree of dynamism, andeffective degree of dynamism with TW [22] are introduced to describe dynamism concretely. In this paper, the metric ofdegree of dynamism (dod) is selected to characterize the dynamical degree of DMDVRP, and the following is the calculation formula ofdod. The range ofdod is from 0 to 1 [16].(7)dod=count  of  customers  (known  in  advance)all  customers


## 2.1. The Description of DMDVRP

In the real world, MDVRP is affected by the dynamic environment. With the wide application of information technology and Global Positioning System (GPS) technology, the process of logistics service can be tracked and adjusted in real time. Due to the development of these new technologies, the service mode of plan-execute is replaced by the dynamic execution task [21].Generally speaking, the dynamic nature of DMVRP mainly reflects the uncertainty of customer requests in the service process. Specifically, the type of request includes the uncertain quantity of goods [21–23] and the uncertain service time [24, 25]. This paper focuses on the change of service time and processing orders dynamically according to customer request time. A DMDVRP example is shown in Figure 1. In Figure 1(a), three different depots (red square) are responsible to serve the customers (black dots) which are allocated to them, and black and red lines represent initial routes. In Figure 1(b), some new customers (blue triangle) are added to system, and some new routes will be generated in time.Figure 1
An example of DMDVRP with three depots.
(a)
Initial routes (b)
Dynamic routes


## 2.2. The Formulation of DMDVRP

The DMDVRP can be formalized as follows. An undirected graphG=(V,E) is established to describe mathematical model. In this model, V={VC,VD} represents the vertex set and E=vi,vj∣vi,vj∈V,i<j is the edge set. VC={v1,v2,…,vn} is the set of customers and VD={vn+1,vn+2,…,vn+m} is the set of depots. InE, we get distance matrix C=(cij) by calculating the Euclidean distance of customers vi and vj. Every customer vi has a demand qi and needs to be visited once by only one vehicle. There is also a fleet ofK identical vehicles, each with capacityQ.In the mathematical formulation that follows, binary variablexijk is equal to 1 when vehiclek visits nodej immediately after nodei.(1)Minimize∑i=1n+m∑j=1n+m∑k=1Kcijxijk,subject to(2)∑i=1n+m∑k=1Kxijk=1j=1,2,…,n;(3)∑j=1n+m∑k=1Kxijk=1i=1,2,…,n;(4)∑i=1n+m∑j=1n+mqixijk≤Qk=1,2,…,K;(5)∑i=n+1n+m∑j=1nxijk≤1k=1,2,…,K;(6)∑j=n+1n+m∑i=1nxijk≤1k=1,2,…,K.The objective (1) minimizes the total cost. Constraints (2) and (3) guarantee that each customer is served by exactly one vehicle. Vehicle capacity constraint is found in (4). Finally, constraints (5) and (6) check vehicle availability.


## 2.3. Measuring Dynamism

In most papers, three popular metrics ofdegree of dynamism [16],effective degree of dynamism, andeffective degree of dynamism with TW [22] are introduced to describe dynamism concretely. In this paper, the metric ofdegree of dynamism (dod) is selected to characterize the dynamical degree of DMDVRP, and the following is the calculation formula ofdod. The range ofdod is from 0 to 1 [16].(7)dod=count  of  customers  (known  in  advance)all  customers


## 3. A Hybrid Ant Colony Algorithm for DMDVRP

### 3.1. Hybrid Ant Colony Optimization

By reviewing previous algorithms about solving VRP, we find that ant colony algorithm (ACO) is a common and effective algorithm. In this paper, the ant colony algorithm is improved by the nearest distance clustering, mutation operation, and 2-Opt algorithm to obtain better solutions. The flowchart of hybrid ant colony optimization (HACO) for the DMDVRP is shown in Figure2. The details of HACO will be introduced in the following sections.Figure 2
The flowchart of HACO.


### 3.2. The Nearest Distance Cluster Algorithm

Generally, in order to serve customers preferably, the depots are usually placed at the locations which are as close to customers as possible. Therefore, the nearest distance cluster algorithm is proposed to exactly allocate each customer to its nearest depot. By the nearest distance cluster algorithm, a whole DMDVRP is divided into several little DVRPs; meanwhile the whole service area is divided into a set of little regions. An example of the nearest distance cluster algorithm is in Figure3; as shown, the black triangles are depots, and the different color points represent that customers are allocated to the nearest depot.Figure 3
An example of the nearest distance cluster algorithm.


### 3.3. Generate Initial Solutions

In ACO, each ant represents a vehicle and visits all customers once. The complete routes that ants have passed are initial solutions. The ants will decide to select the next customer by formula (8).(8)pijk=τi,jα×ηi,jβ∑I∉tabuτi,Iα×ηi,Iβj∉tabuk0otherwiseIn formula (8), pij(k) is the probability of selectingj as the next customer ofi. τ(i,j) and α are the pheromone density of edge (i, j) and the relative influence of the pheromone trails, respectively. η(i,j) and β are the visibility of edge (i, j) and the relative influence of the visibility values, respectively. tabuk is a list, which stores the unvisited nodes for the kth ant [12].


### 3.4. Optimization Operation

#### 3.4.1. Mutation Operation

Mutation operation is derived from genetic algorithms (GA) primitively [23, 24], but it can be applied to fusing other optimization algorithms. For example, the optimization operation can help ACO get further solutions in the period of searching. The most important step of mutation operation is to randomly select a solution and exchange customers by mutation probability Pm. Therefore, the operational process may produce new solutions and increase the likelihood of searching a better solution.Generally,Pm has influence on the performance in the mutation. If Pm is so small it is not easy to produce the new individual. If Pm is so large the algorithm becomes a purely random search algorithm. Therefore, the adaptive method is applied to change the mutation probability with the fitness. At the same time, considering the mutation coefficientk, it can also affect the performance of mutation. Pm andk can be determined according to the following formulas.(9)Pm=Pm1-Pm2fm-favgfmax-favg,fm≥favgPm1,fm≺favg(10)k=k1+k2fm-favgfmax-favg,fm≥favgk1+k2,fm≺favgwhere fmax is the largest fitness value, favg is average in groups, and fm is the fit value for mutation. Pm1, Pm2, k1, and k2 are initial variables [25].In most GA, considering that biological gene mutation is a small probability event, the mutation rate is less than 0.1. However, in view of the aim of exploring greater search space, a mutation operation with a larger mutation rate is introduced to optimize route. Figure4 is a demo of mutation operation process. The red line route and the black line route are serviced by two different vehicles. By exchanging 4 and 6, two new routes (1-3-2-6-1 and 1-4-5-1) are generated and have more appropriate arrangements.Figure 4
The example of mutation operation.


#### 3.4.2. Local Interchange Operation

In all local optimization algorithms, 2-Opt is a common and classical heuristic proposed by Croes [26] in 1958. The main idea is to try to choose a route and exchange two adjacent locations and calculate the results of new route. This operation may avoid local optimization and obtain a better route.In this paper, the 2-Opt optimization is applied to improve the route. First, swapping the locations of all possible adjacent customers generates some new potential routes. Then we test each new route to see if this pair of exchanges can improve the quality of the route [27]. Finally, the best route will be selected to replace previous old route. Figure 5 is a demo of 2-Opt operation: (a) is the original route and (b) is the new route of implementing the operation of exchanging 2 and 7.Figure 5
The demo of 2-Opt operation.
(a)
Route before 2-Opt (b)
Route after 2-Opt


### 3.5. Update of Pheromone Information

In ACO, the most important step is the update of ant pheromones, which is key to obtain high quality solution. In order to ensure that each link has the same advantages, the following formula will be implemented to update pheromones:(11)τijnew=ρ×τijold+∑kKΔτijkρ∈0,1In formula (11), τijnew and τijold are the new and initial pheromone concentration of link (i,j), respectively, ρ is a constant and regulates the rate of evaporation, k is the number of all routes, K is the number of the routes in specific solution, and Δτijk is the increased pheromone of link (i,j) in route k.


## 3.1. Hybrid Ant Colony Optimization

By reviewing previous algorithms about solving VRP, we find that ant colony algorithm (ACO) is a common and effective algorithm. In this paper, the ant colony algorithm is improved by the nearest distance clustering, mutation operation, and 2-Opt algorithm to obtain better solutions. The flowchart of hybrid ant colony optimization (HACO) for the DMDVRP is shown in Figure2. The details of HACO will be introduced in the following sections.Figure 2
The flowchart of HACO.


## 3.2. The Nearest Distance Cluster Algorithm

Generally, in order to serve customers preferably, the depots are usually placed at the locations which are as close to customers as possible. Therefore, the nearest distance cluster algorithm is proposed to exactly allocate each customer to its nearest depot. By the nearest distance cluster algorithm, a whole DMDVRP is divided into several little DVRPs; meanwhile the whole service area is divided into a set of little regions. An example of the nearest distance cluster algorithm is in Figure3; as shown, the black triangles are depots, and the different color points represent that customers are allocated to the nearest depot.Figure 3
An example of the nearest distance cluster algorithm.


## 3.3. Generate Initial Solutions

In ACO, each ant represents a vehicle and visits all customers once. The complete routes that ants have passed are initial solutions. The ants will decide to select the next customer by formula (8).(8)pijk=τi,jα×ηi,jβ∑I∉tabuτi,Iα×ηi,Iβj∉tabuk0otherwiseIn formula (8), pij(k) is the probability of selectingj as the next customer ofi. τ(i,j) and α are the pheromone density of edge (i, j) and the relative influence of the pheromone trails, respectively. η(i,j) and β are the visibility of edge (i, j) and the relative influence of the visibility values, respectively. tabuk is a list, which stores the unvisited nodes for the kth ant [12].


## 3.4. Optimization Operation

### 3.4.1. Mutation Operation

Mutation operation is derived from genetic algorithms (GA) primitively [23, 24], but it can be applied to fusing other optimization algorithms. For example, the optimization operation can help ACO get further solutions in the period of searching. The most important step of mutation operation is to randomly select a solution and exchange customers by mutation probability Pm. Therefore, the operational process may produce new solutions and increase the likelihood of searching a better solution.Generally,Pm has influence on the performance in the mutation. If Pm is so small it is not easy to produce the new individual. If Pm is so large the algorithm becomes a purely random search algorithm. Therefore, the adaptive method is applied to change the mutation probability with the fitness. At the same time, considering the mutation coefficientk, it can also affect the performance of mutation. Pm andk can be determined according to the following formulas.(9)Pm=Pm1-Pm2fm-favgfmax-favg,fm≥favgPm1,fm≺favg(10)k=k1+k2fm-favgfmax-favg,fm≥favgk1+k2,fm≺favgwhere fmax is the largest fitness value, favg is average in groups, and fm is the fit value for mutation. Pm1, Pm2, k1, and k2 are initial variables [25].In most GA, considering that biological gene mutation is a small probability event, the mutation rate is less than 0.1. However, in view of the aim of exploring greater search space, a mutation operation with a larger mutation rate is introduced to optimize route. Figure4 is a demo of mutation operation process. The red line route and the black line route are serviced by two different vehicles. By exchanging 4 and 6, two new routes (1-3-2-6-1 and 1-4-5-1) are generated and have more appropriate arrangements.Figure 4
The example of mutation operation.


### 3.4.2. Local Interchange Operation

In all local optimization algorithms, 2-Opt is a common and classical heuristic proposed by Croes [26] in 1958. The main idea is to try to choose a route and exchange two adjacent locations and calculate the results of new route. This operation may avoid local optimization and obtain a better route.In this paper, the 2-Opt optimization is applied to improve the route. First, swapping the locations of all possible adjacent customers generates some new potential routes. Then we test each new route to see if this pair of exchanges can improve the quality of the route [27]. Finally, the best route will be selected to replace previous old route. Figure 5 is a demo of 2-Opt operation: (a) is the original route and (b) is the new route of implementing the operation of exchanging 2 and 7.Figure 5
The demo of 2-Opt operation.
(a)
Route before 2-Opt (b)
Route after 2-Opt


## 3.4.1. Mutation Operation

Mutation operation is derived from genetic algorithms (GA) primitively [23, 24], but it can be applied to fusing other optimization algorithms. For example, the optimization operation can help ACO get further solutions in the period of searching. The most important step of mutation operation is to randomly select a solution and exchange customers by mutation probability Pm. Therefore, the operational process may produce new solutions and increase the likelihood of searching a better solution.Generally,Pm has influence on the performance in the mutation. If Pm is so small it is not easy to produce the new individual. If Pm is so large the algorithm becomes a purely random search algorithm. Therefore, the adaptive method is applied to change the mutation probability with the fitness. At the same time, considering the mutation coefficientk, it can also affect the performance of mutation. Pm andk can be determined according to the following formulas.(9)Pm=Pm1-Pm2fm-favgfmax-favg,fm≥favgPm1,fm≺favg(10)k=k1+k2fm-favgfmax-favg,fm≥favgk1+k2,fm≺favgwhere fmax is the largest fitness value, favg is average in groups, and fm is the fit value for mutation. Pm1, Pm2, k1, and k2 are initial variables [25].In most GA, considering that biological gene mutation is a small probability event, the mutation rate is less than 0.1. However, in view of the aim of exploring greater search space, a mutation operation with a larger mutation rate is introduced to optimize route. Figure4 is a demo of mutation operation process. The red line route and the black line route are serviced by two different vehicles. By exchanging 4 and 6, two new routes (1-3-2-6-1 and 1-4-5-1) are generated and have more appropriate arrangements.Figure 4
The example of mutation operation.


## 3.4.2. Local Interchange Operation

In all local optimization algorithms, 2-Opt is a common and classical heuristic proposed by Croes [26] in 1958. The main idea is to try to choose a route and exchange two adjacent locations and calculate the results of new route. This operation may avoid local optimization and obtain a better route.In this paper, the 2-Opt optimization is applied to improve the route. First, swapping the locations of all possible adjacent customers generates some new potential routes. Then we test each new route to see if this pair of exchanges can improve the quality of the route [27]. Finally, the best route will be selected to replace previous old route. Figure 5 is a demo of 2-Opt operation: (a) is the original route and (b) is the new route of implementing the operation of exchanging 2 and 7.Figure 5
The demo of 2-Opt operation.
(a)
Route before 2-Opt (b)
Route after 2-Opt


## 3.5. Update of Pheromone Information

In ACO, the most important step is the update of ant pheromones, which is key to obtain high quality solution. In order to ensure that each link has the same advantages, the following formula will be implemented to update pheromones:(11)τijnew=ρ×τijold+∑kKΔτijkρ∈0,1In formula (11), τijnew and τijold are the new and initial pheromone concentration of link (i,j), respectively, ρ is a constant and regulates the rate of evaporation, k is the number of all routes, K is the number of the routes in specific solution, and Δτijk is the increased pheromone of link (i,j) in route k.


## 4. A Real-Time Addition and Optimization Approach

In this section, a new real-time addition and optimization approach is applied to dynamically add new customer to known routes; meanwhile it can optimize the new generated route. The procedure of this approach is shown in Figure6.Figure 6
The flowchart of real-time addition and optimization approach.


### 4.1. The Strategy of Adding New Customers to Known Routes

In the strategy of adding new customers to known routes, a working day is split into 24 same length time slices, and the customer requests are occurring in each time slice. The distances between each new customer and the serving customers or just finished serving customers are computed and compared, and the new customer will be added to the route which is the nearest to the new customer. If the new customer demands exceed the vehicle capacity, they will be handled by arranging another vehicle, and an extra route will be formed.An example of this strategy is shown in Figure7; as shown, some customers (black dots) have been known in advance. Red lines and black lines represent initial designed routes to serve known customers. As time goes on, new customers (blue triangle N1, N2, N3) are added to system, and the distances between N1 and the serving or just finished serving customers (black dots 3, 5, 8) will be computed, respectively; then new customer (N1) is added to the nearest route (0-7-8-N1-9-0). Similarly, the new customers (N2, N3) are added to routes (0-1-2-3-N2-0, 0-4-5-N3-6-0), respectively. Although the new generated routes are not the best, the optimized operations will be conducted in the next section.Figure 7
An example of the strategy of adding new customers to known routes.


### 4.2. Reoptimize Routes Dynamically

Due to adding some new customers to initial routes, the routes need to be reoptimized dynamically. Each new route is divided into two subroutes, and the first subroute which has been served remains unchanged; meanwhile, the remaining part is optimized by mutation and 2-Opt in Section3.4.


## 4.1. The Strategy of Adding New Customers to Known Routes

In the strategy of adding new customers to known routes, a working day is split into 24 same length time slices, and the customer requests are occurring in each time slice. The distances between each new customer and the serving customers or just finished serving customers are computed and compared, and the new customer will be added to the route which is the nearest to the new customer. If the new customer demands exceed the vehicle capacity, they will be handled by arranging another vehicle, and an extra route will be formed.An example of this strategy is shown in Figure7; as shown, some customers (black dots) have been known in advance. Red lines and black lines represent initial designed routes to serve known customers. As time goes on, new customers (blue triangle N1, N2, N3) are added to system, and the distances between N1 and the serving or just finished serving customers (black dots 3, 5, 8) will be computed, respectively; then new customer (N1) is added to the nearest route (0-7-8-N1-9-0). Similarly, the new customers (N2, N3) are added to routes (0-1-2-3-N2-0, 0-4-5-N3-6-0), respectively. Although the new generated routes are not the best, the optimized operations will be conducted in the next section.Figure 7
An example of the strategy of adding new customers to known routes.


## 4.2. Reoptimize Routes Dynamically

Due to adding some new customers to initial routes, the routes need to be reoptimized dynamically. Each new route is divided into two subroutes, and the first subroute which has been served remains unchanged; meanwhile, the remaining part is optimized by mutation and 2-Opt in Section3.4.


## 5. Experimental Results and Discussions

In this section, the performance of HACO algorithm solving for DMVVRP is evaluated strictly and completely. Through a series of experiments based on different data sets, the HACO will be analyzed by solution quality, running time, degrees of dynamism, and so on. The data sets are completely open and can be available athttp://neo.lcc.uma.es/vrp/vrp-instances/multiple-depot-vrp-instances/. The detailed information of data sets is shown in Table 1. In this table, the numbers of depots, the numbers of customers, and the capacity are explained.Table 1
The detailed information of data sets.
Problem Depots Customers Capacity 01 4 50 80 02 4 50 160 03 5 75 140 04 2 100 100 05 2 100 200 06 3 100 100 07 4 100 100 08 2 249 500 09 3 249 500 10 4 249 500 11 5 249 500 12 2 80 60 13 4 160 60 14 4 48 200 15 4 96 195 16 4 144 190 17 4 192 185 18 4 240 180 19 4 288 175Table2 shows that the parameters are used in HACO. The number of ants is 30; weight of pheromone is 2; weight of visibility is 1; evaporation rate of pheromone is 0.8; initial mutation rate is 0.8; number of iterations is 100. The algorithm implementation is based on the MATLAB (2010b) language, and the computer configuration is an Intel(R) Core (TM) i5-6500 3.19 GHz, 8 GB RAM running Windows 10(x64). All the results are averaged over 10 runs.Table 2
HACO parameters settings.
Parameter Description Value M The number of Ants 30 α Weight of pheromone 2 β Weight of visibility 1 ρ Evaporation rate of pheromone 0.8 t Initial Mutation rate 0.1 N Number of iterations 100


### 5.1. Comparisons Based on Four Different ACO

The comparisons of the solution quality in terms of the route length and running time among four proposed ACO algorithms are implemented in this section, and the four algorithms are ACO, MACO, LACO, and HACO, respectively. The ACO is from Montemanni et al. [28]; MACO and LACO are basic ACO fusing mutation operation and 2-Opt, respectively; modifying ACO with mutation operation and 2-Opt forms the final HACO. In addition, the scale of experimental data sets is between 80 and 288, and the degree of dynamism is 0.3. Table 3 gives the route length and running time of four algorithms. In this paper, the best solutions are in bold entries. From the comparisons, MACO, LACO, and HACO are 3.25%, 0.73%, and 10.9% less than the ACO, respectively. The results indicate that the mutation operation and 2-Opt can improve ACO effectively, and HACO is effective algorithm for solving DMDVRP.Table 3
Comparisons based on four different ACO.
Problem ACO MACO LACO HACO Length Time Length Time Length Time Length Time 01 833.06 35.27 839.46 52.27 932.75 46.47 811.72 60.45 02 716.17 26.55 718.64 42.57 729.37 26.83 599.60 46.62 03 1061.86 40.24 1105.81 77.84 1062.03 43.17 1033.07 89.86 04 1490.26 81.59 1570.71 154.06 1541.79 78.66 1482.00 158.92 05 1267.82 52.54 1323.36 115.64 1240.11 54.99 1255.38 130.16 06 1313.02 79.38 1279.35 124.45 1318.54 63.79 1274.60 137.51 07 1377.80 60.93 1328.30 109.80 1322.94 60.17 1292.97 123.60 08 8737.04 147.12 8264.29 525.99 8014.18 165.17 7873.47 599.77 09 6723.11 162.60 6616.01 416.62 6820.88 168.08 6279.87 453.87 10 6357.03 138.60 6344.92 343.92 6103.97 137.69 6076.75 384.96 11 6410.59 146.39 6262.12 343.00 6202.83 142.02 6101.29 366.24 12 1539.51 68.24 1533.00 120.76 1541.37 69.29 1524.62 106.05 13 3118.52 137.43 2979.31 242.30 3124.21 142.99 3100.88 214.50 14 1561.51 23.01 1399.14 35.12 1445.15 23.61 1443.02 39.38 15 2383.12 45.73 2109.31 85.79 2436.77 44.54 2003.30 98.77 16 3173.39 77.47 3295.31 148.20 3469.17 75.40 3236.13 165.18 17 3603.98 105.81 3724.63 237.49 3604.21 115.32 3368.47 242.12 18 4035.92 154.08 6493.59 246.79 6398.13 121.50 3803.42 357.06 19 8541.46 156.46 4972.95 446.51 6468.04 176.03 4652.53 449.91 Average 3381.32 91.55 3271.59 203.64 3356.65 92.40 3011.21 222.36 Increased by 0  3.25%  0.73%  10.9%%This result may be attributed to the fact that the introduction of 2-Opt algorithm and mutation operation can improve the randomization and avoid falling into local search prematurely, and make HACO obtain better solutions.In addition, a pairedt-test is performed to investigate whether there are statistically significant differences between HACO and other improved ACO algorithms. Since it is expected that the solution quality of HACO is better than other ACO, a one-sided alternative hypothesisH1is given below:(12)H1:μH-ACO-μCA<0where μH-ACO and μCA are population mean for HACO and CA, respectively. CA refers to algorithm, which is compared with HACO. For example, if HACO is compared with MACO, the CA will refer to MACO.Table4 shows pairs, mean differences for instances, andp value at statistical level of α=0.1. The mean differences of HACOvsACO, MACO, and LACO are -370.11, -260.37, and -345.44 withp value of 0.083, 0.077, and 0.041, respectively. This indicates that HACO is statistically significantly different from other ACO; meanwhile HACO fusing mutation and 2-Opt can explore more possibilities and search better solutions.Table 4
Results of pairedt-test based on route length.
Problem HACOvs ACO HACOvs MACO HACOvs LACO Mean Difference -370.11 -260.37 -345.44 p value 0.083 0.077 0.041


### 5.2. Comparisons Based on Different Degrees of Dynamism

In order to investigate the relation of degrees of dynamism (dod) and HACO, the experiment based on different dod (0.3, 0.5, 0.7) is performed in this section. Table 5 gives the detailed routes length and running time of comparisons. In addition, we count the average value, number, and proportion of different dod in terms of the routes length and running time. When dod are 0.3, 0.5, and 0.7, the proportions of the best length are 78.95%, 5.26%, and 15.79%, respectively, and the proportions of the best time are 15.79%, 52.63%, and 31.58%, respectively. By the statistical data, the results reveal that dod is directly proportional to routes length. However, the running time of dod (0.5 and 0.7) is less than that of dod (0.3). This illustrates that the proposed real-time addition and optimization approach can reduce algorithm running time, along with the increase of dod.Table 5
Comparisons based on different degrees of dynamism.
Problem dod = 0.3 dod = 0.5 dod = 0.7 Length Time Length Time Length Time 01 811.72 60.45 802.57 49.81 783.52 62.96 02 599.60 46.62 846.88 36.83 834.74 27.80 03 1033.07 89.86 1038.82 67.68 1018.35 78.12 04 1482.00 158.92 1523.84 149.00 1541.10 95.22 05 1255.38 130.16 1338.78 100.67 1718.58 183.34 06 1274.60 137.51 1378.00 106.24 1419.99 137.65 07 1292.97 123.60 1377.39 245.13 1467.39 105.61 08 7873.47 599.77 7251.37 300.56 7090.63 145.94 09 6279.87 453.87 6738.20 326.09 7358.75 298.08 10 6076.75 384.96 6713.71 311.21 7158.48 331.20 11 6101.29 366.24 6525.99 329.49 7711.66 417.96 12 1524.62 106.05 1511.59 128.06 1709.70 131.95 13 3100.88 214.50 3115.21 250.86 3407.92 270.14 14 1443.02 39.38 1487.92 27.40 2013.60 25.92 15 2003.30 98.77 2774.69 73.84 2640.64 86.81 16 3236.13 165.18 3576.19 140.96 3927.35 159.61 17 3368.47 242.12 4118.43 260.63 4419.52 290.03 18 3803.42 357.06 4457.53 312.86 5063.65 426.19 19 4652.53 449.91 5117.38 425.45 6069.40 619.00 Average 3011.24 220.78 3247.08 191.72 3545.00 204.92 Count 15 3 1 10 3 6 Proportion 78.95 % 15.79% 5.26% 52.63 % 15.79% 31.58%


### 5.3. The Analyses of Real-Time Addition and Optimization Approach

In Table6, the analyses of real-time addition and optimization approach are conducted, and the results are based on dod (0.3) in this section. In this table, the second, fourth, and fifth columns are the results of static routes length, additional extra routes length, and dynamic routes length, respectively; the third and sixth columns are static and dynamic running time; the seventh and eighth columns are the whole length and running time.Table 6
Results of real-time addition and optimization approach.
Problem Len-S Time-S Len-E Len-D Time-D All-Length All-Time 01 530.36 50.96 152.18 659.54 9.49 811.72 60.45 02 402.51 40.93 67.48 532.11 5.69 599.60 46.62 03 1787.62 77.01 160.15 872.92 12.85 1033.07 89.86 04 1018.21 128.09 340.43 1141.57 30.82 1482.00 158.92 05 788.61 102.83 288.92 966.46 27.33 1255.38 130.16 06 880.39 117.87 249.77 1024.83 19.64 1274.60 137.51 07 846.64 108.18 230.12 1062.85 15.41 1292.97 123.60 08 5471.76 578.84 731.18 7142.29 20.93 7873.47 599.77 09 4161.98 425.35 964.16 5315.71 28.51 6279.87 453.87 10 3971.37 367.37 535.12 5541.63 17.59 6076.75 384.96 11 3914.98 335.17 883.43 5217.86 31.07 6101.29 366.24 12 1101.56 71.93 336.47 1188.15 34.12 1524.62 106.05 13 2193.00 145.49 654.49 2446.39 69.01 3100.88 214.50 14 627.68 34.95 204.10 1238.92 4.43 1443.02 39.38 15 1288.89 93.90 118.85 1884.45 4.87 2003.30 98.77 16 1726.21 150.22 251.35 2984.78 14.97 3236.13 165.18 17 2043.77 218.86 266.67 3101.80 23.26 3368.47 242.12 18 2470.63 299.59 818.56 2984.85 57.47 3803.42 357.06 19 2765.14 404.28 204.28 4448.24 45.64 4652.53 449.91 Average 1999.54 197.46 392.51 2618.70 24.90 3011.21 222.36From the analyses of results based on average value, the average dynamic routes length is 2618.7, and it is 23.64% more than the average static routes length. Meanwhile, the average dynamic running time is 24.9 seconds, and it just accounts for 11.20% of the whole running time. These results reveal that the real-time addition and optimization approach can solve the DMDVRP efficiently. The strategy of adding new customers to the nearest known routes is feasible and efficient to solve dynamic problem.


### 5.4. Comparisons Based on Other Two Algorithms

In order to better evaluate the performance of the proposed HACO in terms of solution quality in minimizing travel distance, HACO is compared with previously published algorithms. These algorithms are Wang et al.’s [29] genetic algorithm (GA) and Yao et al.’s [30] particle swarm optimization (PSO), respectively.Table7 gives the best solution length and running time of this comparison and counts the number and proportion of the best length of each algorithm. From Table 6, the proposed HACO based on DMDVRP finds 12 new best solutions in the 19 problems, accounting for 63.16% of the best, while GA and PSO reach 4 and 3 best possible solutions, accounting for 21.05% and 15.79%, respectively. The results indicate that the HACO is effective algorithm for solving DMDVRP.Table 7
Comparisons based on other two algorithms.
Problem GA PSO HACO Length Time Length Time Length Time 01 736.39 61.11 788.56 68.51 811.72 60.45 02 569.69 56.96 598.73 60.50 599.60 46.62 03 931.87 97.18 911.40 101.09 1033.07 89.86 04 1374.53 126.36 1411.22 132.62 1482.00 158.92 05 1396.97 139.64 1226.40 144.05 1255.38 130.16 06 1544.30 126.95 1444.62 147.58 1274.60 137.51 07 1497.30 126.87 1475.88 146.60 1292.97 123.60 08 9253.53 447.36 7987.20 511.32 7873.47 599.77 09 8633.74 349.46 6940.90 387.90 6279.87 453.87 10 7088.22 348.61 6541.11 389.81 6076.75 384.96 11 6684.20 353.06 6686.50 382.13 6101.29 366.24 12 1616.50 134.80 1493.42 129.90 1524.62 106.05 13 4549.78 144.42 3720.01 146.55 3100.88 214.50 14 1124.46 35.76 1244.96 41.97 1443.02 39.38 15 2305.61 104.37 2107.53 111.19 2003.30 98.77 16 3549.58 151.35 3398.40 175.16 3236.13 165.18 17 3876.65 255.01 3651.31 274.10 3368.47 242.12 18 4270.49 371.66 4058.70 402.31 3803.42 357.06 19 5268.36 364.75 5486.40 396.60 4652.53 449.91 Average 3488.01 199.77 3219.64 218.42 3011.21 222.36 Count 4  3  12 Proportion 21.05%  15.79%  63.16 %


## 5.1. Comparisons Based on Four Different ACO

The comparisons of the solution quality in terms of the route length and running time among four proposed ACO algorithms are implemented in this section, and the four algorithms are ACO, MACO, LACO, and HACO, respectively. The ACO is from Montemanni et al. [28]; MACO and LACO are basic ACO fusing mutation operation and 2-Opt, respectively; modifying ACO with mutation operation and 2-Opt forms the final HACO. In addition, the scale of experimental data sets is between 80 and 288, and the degree of dynamism is 0.3. Table 3 gives the route length and running time of four algorithms. In this paper, the best solutions are in bold entries. From the comparisons, MACO, LACO, and HACO are 3.25%, 0.73%, and 10.9% less than the ACO, respectively. The results indicate that the mutation operation and 2-Opt can improve ACO effectively, and HACO is effective algorithm for solving DMDVRP.Table 3
Comparisons based on four different ACO.
Problem ACO MACO LACO HACO Length Time Length Time Length Time Length Time 01 833.06 35.27 839.46 52.27 932.75 46.47 811.72 60.45 02 716.17 26.55 718.64 42.57 729.37 26.83 599.60 46.62 03 1061.86 40.24 1105.81 77.84 1062.03 43.17 1033.07 89.86 04 1490.26 81.59 1570.71 154.06 1541.79 78.66 1482.00 158.92 05 1267.82 52.54 1323.36 115.64 1240.11 54.99 1255.38 130.16 06 1313.02 79.38 1279.35 124.45 1318.54 63.79 1274.60 137.51 07 1377.80 60.93 1328.30 109.80 1322.94 60.17 1292.97 123.60 08 8737.04 147.12 8264.29 525.99 8014.18 165.17 7873.47 599.77 09 6723.11 162.60 6616.01 416.62 6820.88 168.08 6279.87 453.87 10 6357.03 138.60 6344.92 343.92 6103.97 137.69 6076.75 384.96 11 6410.59 146.39 6262.12 343.00 6202.83 142.02 6101.29 366.24 12 1539.51 68.24 1533.00 120.76 1541.37 69.29 1524.62 106.05 13 3118.52 137.43 2979.31 242.30 3124.21 142.99 3100.88 214.50 14 1561.51 23.01 1399.14 35.12 1445.15 23.61 1443.02 39.38 15 2383.12 45.73 2109.31 85.79 2436.77 44.54 2003.30 98.77 16 3173.39 77.47 3295.31 148.20 3469.17 75.40 3236.13 165.18 17 3603.98 105.81 3724.63 237.49 3604.21 115.32 3368.47 242.12 18 4035.92 154.08 6493.59 246.79 6398.13 121.50 3803.42 357.06 19 8541.46 156.46 4972.95 446.51 6468.04 176.03 4652.53 449.91 Average 3381.32 91.55 3271.59 203.64 3356.65 92.40 3011.21 222.36 Increased by 0  3.25%  0.73%  10.9%%This result may be attributed to the fact that the introduction of 2-Opt algorithm and mutation operation can improve the randomization and avoid falling into local search prematurely, and make HACO obtain better solutions.In addition, a pairedt-test is performed to investigate whether there are statistically significant differences between HACO and other improved ACO algorithms. Since it is expected that the solution quality of HACO is better than other ACO, a one-sided alternative hypothesisH1is given below:(12)H1:μH-ACO-μCA<0where μH-ACO and μCA are population mean for HACO and CA, respectively. CA refers to algorithm, which is compared with HACO. For example, if HACO is compared with MACO, the CA will refer to MACO.Table4 shows pairs, mean differences for instances, andp value at statistical level of α=0.1. The mean differences of HACOvsACO, MACO, and LACO are -370.11, -260.37, and -345.44 withp value of 0.083, 0.077, and 0.041, respectively. This indicates that HACO is statistically significantly different from other ACO; meanwhile HACO fusing mutation and 2-Opt can explore more possibilities and search better solutions.Table 4
Results of pairedt-test based on route length.
Problem HACOvs ACO HACOvs MACO HACOvs LACO Mean Difference -370.11 -260.37 -345.44 p value 0.083 0.077 0.041


## 5.2. Comparisons Based on Different Degrees of Dynamism

In order to investigate the relation of degrees of dynamism (dod) and HACO, the experiment based on different dod (0.3, 0.5, 0.7) is performed in this section. Table 5 gives the detailed routes length and running time of comparisons. In addition, we count the average value, number, and proportion of different dod in terms of the routes length and running time. When dod are 0.3, 0.5, and 0.7, the proportions of the best length are 78.95%, 5.26%, and 15.79%, respectively, and the proportions of the best time are 15.79%, 52.63%, and 31.58%, respectively. By the statistical data, the results reveal that dod is directly proportional to routes length. However, the running time of dod (0.5 and 0.7) is less than that of dod (0.3). This illustrates that the proposed real-time addition and optimization approach can reduce algorithm running time, along with the increase of dod.Table 5
Comparisons based on different degrees of dynamism.
Problem dod = 0.3 dod = 0.5 dod = 0.7 Length Time Length Time Length Time 01 811.72 60.45 802.57 49.81 783.52 62.96 02 599.60 46.62 846.88 36.83 834.74 27.80 03 1033.07 89.86 1038.82 67.68 1018.35 78.12 04 1482.00 158.92 1523.84 149.00 1541.10 95.22 05 1255.38 130.16 1338.78 100.67 1718.58 183.34 06 1274.60 137.51 1378.00 106.24 1419.99 137.65 07 1292.97 123.60 1377.39 245.13 1467.39 105.61 08 7873.47 599.77 7251.37 300.56 7090.63 145.94 09 6279.87 453.87 6738.20 326.09 7358.75 298.08 10 6076.75 384.96 6713.71 311.21 7158.48 331.20 11 6101.29 366.24 6525.99 329.49 7711.66 417.96 12 1524.62 106.05 1511.59 128.06 1709.70 131.95 13 3100.88 214.50 3115.21 250.86 3407.92 270.14 14 1443.02 39.38 1487.92 27.40 2013.60 25.92 15 2003.30 98.77 2774.69 73.84 2640.64 86.81 16 3236.13 165.18 3576.19 140.96 3927.35 159.61 17 3368.47 242.12 4118.43 260.63 4419.52 290.03 18 3803.42 357.06 4457.53 312.86 5063.65 426.19 19 4652.53 449.91 5117.38 425.45 6069.40 619.00 Average 3011.24 220.78 3247.08 191.72 3545.00 204.92 Count 15 3 1 10 3 6 Proportion 78.95 % 15.79% 5.26% 52.63 % 15.79% 31.58%


## 5.3. The Analyses of Real-Time Addition and Optimization Approach

In Table6, the analyses of real-time addition and optimization approach are conducted, and the results are based on dod (0.3) in this section. In this table, the second, fourth, and fifth columns are the results of static routes length, additional extra routes length, and dynamic routes length, respectively; the third and sixth columns are static and dynamic running time; the seventh and eighth columns are the whole length and running time.Table 6
Results of real-time addition and optimization approach.
Problem Len-S Time-S Len-E Len-D Time-D All-Length All-Time 01 530.36 50.96 152.18 659.54 9.49 811.72 60.45 02 402.51 40.93 67.48 532.11 5.69 599.60 46.62 03 1787.62 77.01 160.15 872.92 12.85 1033.07 89.86 04 1018.21 128.09 340.43 1141.57 30.82 1482.00 158.92 05 788.61 102.83 288.92 966.46 27.33 1255.38 130.16 06 880.39 117.87 249.77 1024.83 19.64 1274.60 137.51 07 846.64 108.18 230.12 1062.85 15.41 1292.97 123.60 08 5471.76 578.84 731.18 7142.29 20.93 7873.47 599.77 09 4161.98 425.35 964.16 5315.71 28.51 6279.87 453.87 10 3971.37 367.37 535.12 5541.63 17.59 6076.75 384.96 11 3914.98 335.17 883.43 5217.86 31.07 6101.29 366.24 12 1101.56 71.93 336.47 1188.15 34.12 1524.62 106.05 13 2193.00 145.49 654.49 2446.39 69.01 3100.88 214.50 14 627.68 34.95 204.10 1238.92 4.43 1443.02 39.38 15 1288.89 93.90 118.85 1884.45 4.87 2003.30 98.77 16 1726.21 150.22 251.35 2984.78 14.97 3236.13 165.18 17 2043.77 218.86 266.67 3101.80 23.26 3368.47 242.12 18 2470.63 299.59 818.56 2984.85 57.47 3803.42 357.06 19 2765.14 404.28 204.28 4448.24 45.64 4652.53 449.91 Average 1999.54 197.46 392.51 2618.70 24.90 3011.21 222.36From the analyses of results based on average value, the average dynamic routes length is 2618.7, and it is 23.64% more than the average static routes length. Meanwhile, the average dynamic running time is 24.9 seconds, and it just accounts for 11.20% of the whole running time. These results reveal that the real-time addition and optimization approach can solve the DMDVRP efficiently. The strategy of adding new customers to the nearest known routes is feasible and efficient to solve dynamic problem.


## 5.4. Comparisons Based on Other Two Algorithms

In order to better evaluate the performance of the proposed HACO in terms of solution quality in minimizing travel distance, HACO is compared with previously published algorithms. These algorithms are Wang et al.’s [29] genetic algorithm (GA) and Yao et al.’s [30] particle swarm optimization (PSO), respectively.Table7 gives the best solution length and running time of this comparison and counts the number and proportion of the best length of each algorithm. From Table 6, the proposed HACO based on DMDVRP finds 12 new best solutions in the 19 problems, accounting for 63.16% of the best, while GA and PSO reach 4 and 3 best possible solutions, accounting for 21.05% and 15.79%, respectively. The results indicate that the HACO is effective algorithm for solving DMDVRP.Table 7
Comparisons based on other two algorithms.
Problem GA PSO HACO Length Time Length Time Length Time 01 736.39 61.11 788.56 68.51 811.72 60.45 02 569.69 56.96 598.73 60.50 599.60 46.62 03 931.87 97.18 911.40 101.09 1033.07 89.86 04 1374.53 126.36 1411.22 132.62 1482.00 158.92 05 1396.97 139.64 1226.40 144.05 1255.38 130.16 06 1544.30 126.95 1444.62 147.58 1274.60 137.51 07 1497.30 126.87 1475.88 146.60 1292.97 123.60 08 9253.53 447.36 7987.20 511.32 7873.47 599.77 09 8633.74 349.46 6940.90 387.90 6279.87 453.87 10 7088.22 348.61 6541.11 389.81 6076.75 384.96 11 6684.20 353.06 6686.50 382.13 6101.29 366.24 12 1616.50 134.80 1493.42 129.90 1524.62 106.05 13 4549.78 144.42 3720.01 146.55 3100.88 214.50 14 1124.46 35.76 1244.96 41.97 1443.02 39.38 15 2305.61 104.37 2107.53 111.19 2003.30 98.77 16 3549.58 151.35 3398.40 175.16 3236.13 165.18 17 3876.65 255.01 3651.31 274.10 3368.47 242.12 18 4270.49 371.66 4058.70 402.31 3803.42 357.06 19 5268.36 364.75 5486.40 396.60 4652.53 449.91 Average 3488.01 199.77 3219.64 218.42 3011.21 222.36 Count 4  3  12 Proportion 21.05%  15.79%  63.16 %


## 6. Conclusions

In the past few decades, few researchers focused on dynamic multidepot vehicle routing problem (DMDVRP). However, DMDVRP has wide application scenarios, so we have a research on DMDVRP. In order to improve the efficiency of ACO, we proposed a hybrid ant colony optimization algorithm (HACO) to solve DMDVRP. The HACO is based on fusion of ACO and the nearest distance cluster, meanwhile using mutation and 2-Opt to optimize routes further. In addition, a real-time addition and optimization approach is proposed to add customers and optimize routes dynamically.In the experiments, the ACO, MACO, LACO, and HACO are compared directly. In order to demonstrate the efficiency of proposed algorithm, thet-test is applied to perform statistical analysis. But beyond that, the relations of HACO and degree of dynamism (dod) are analyzed by a number of tests based on different dod. With the aim of testing the performance of real-time addition and optimization approach, the comparisons of static routes quality and dynamic routes quality are conducted. Experimental results show that the HACO algorithm is feasible and efficient to solve DMDVRP.



---

*Source: 3624728-2018-09-25.xml*