A hybrid iterated local search algorithm for the multi-compartment vehicle routing problem

Abstract

Multi-compartment vehicle routing problem (MCVRP) is an extension of the classical capacitated vehicle routing problem where products with different characteristics are transported together in one vehicle with multiple compartments. This paper deals with this problem, whose objective is to minimize the total travel distance while satisfying the capacity and maximum route length constraints. We proposed a hybrid iterated local search metaheuristic (HILS) algorithm to solve it. In the framework of iterated local search, the current solution was improved iteratively by five neighborhood operators. For every obtained neighborhood solution after the local search procedure, a large neighborhood search-based perturbation method was executed to explore larger solution space and get a better neighborhood solution to take part in the next iteration. In addition, the worse solutions found by the algorithm were accepted by the nondeterministic simulated annealing-based acceptance rule to keep the diversification of solutions. Computation experiments were conducted on 28 benchmark instances and the experimental results demonstrate that our presented algorithm finds 17 new best solutions, which significantly outperforms the existing state-of-the-art MCVRP methods.

Keywords

Multi-compartment vehicle routing problem hybrid metaheuristic iterated local search large neighborhood search simulated annealing

1 Introduction

In the practice of product distribution, there is more than one type of product to be delivered. The increasing diversity of products and their different characteristics bring new requirements for distribution vehicles. It is necessary to use vehicles with multiple compartments to meet the needs of multi-products in one delivery, especially in cold chain logistics, petrol oil transportation, waste collection, etc. In this situation, different types of products can be delivered by the same vehicle, which has several compartments to serve different types of products simultaneously. This gives rise to a new problem, that is, the multi-compartment vehicle routing problem (MCVRP).

Vehicle routing problem (VRP) is a classical combinatorial optimization problem, which has been studied widely in many application fields. A lot of research achievements have been obtained [1–5]. As a new extension of the classical vehicle routing problem, MCVRP is different from it, because multiple types of products are transported on the vehicle with multiple compartments resulting the higher complexity. Owing to its higher application significance, MCVRP has been applied in fuel distribution [6–8], cold chain transportation [9], waste collection [10] and grocery distribution [11]. Therefore, it is really important and valuable to study this problem.

The general MCVRP comes from the capacitated vehicle routing problem (CVRP), in which each vehicle has only one compartment. For MCVRP, the vehicles are split into several compartments with certain capacities, and each type of product must be stored in a certain compartment of the same vehicle. Its optimization objective is to find the best routing plan with the minimum total travel distance when meeting the capacity and maximum route length constraints. Like VRP, the solution approaches of MCVRP usually include exact algorithms, heuristics, and metaheuristics, which have been used in various kinds of optimization problems [12–16]. There are various heuristics or metaheuristics have been developed for MCVRP, such as ant colony optimization [17–19], genetic algorithm [8], adaptive variable neighborhood search [7, 8], tabu algorithm [20] and artificial bee colony [7] and so on. Although these algorithms can solve the MCVRP, their quality still needs to be improved. MCVRP is a kind of combinatorial optimization problem with high intractability, thus developing an efficient algorithm for MCVRP remains a big challenge.

The main contributions of this study are described in the following. First, we model the general MCVRP on the basis of the classical vehicle routing problem. Then, an iterated local search metaheuristic, named HILS, is developed for MCVRP, which is mixed with five improvement neighborhood operators. Second, we use a perturbation method based on large neighborhood search (LNS) to disturb the neighborhood solution avoiding the local optima. When a neighborhood solution is obtained, it will be first destroyed and then repaired, which can seek a better solution from a relatively larger solution space. Third, the inferior solutions found by the algorithm are accepted by a certain probability, which is an acceptance rule based on the simulated annealing (SA) algorithm. Finally, we test the effectiveness of the hybridization of different perturbation methods and acceptance rules. Furthermore, we also test the influence of different perturbation strengths.

The remainder of this paper is organized as follows. Section 2 gives the related works about MCVRP. The mathematical formulation of MCVRP is defined in Section 3. Section 4 describes the design of the proposed algorithm. Experimental results and analysis are given in Section 5. Finally, we conclude and give a future research direction.

2 Related works

This paper studies the basic general MCVRP that comes from the CVRP including only the core attributes without adding other extension attributes. Thus, we just summarize the works of literature about the general MCVRP. The recent reviews of MCVRP can be found in [21, 22].

The solution approaches for MCVRP include exact algorithms, heuristics, and metaheuristics. Exact algorithms can find the optimal solution when the problem scale is small. Archettic et al. [23] compared single-commodity with multi-commodity delivery routing problems and then developed a branch-price-and-cut algorithm to solve small instances with 3 compartments and 15 customers. In addition, the authors also used a heuristic algorithm to solve some bigger instances. Mirzaei and Wohlk [24] addressed the MCVRP problem where a certain kind of product must be served by one vehicle, and then proposed a branch-and-price algorithm to solve it.

As the problem scale of MCVRP increases, heuristics or metaheuristics have been gradually applied to solve the MCVRP problems. Fallahi et al. [25] proposed two algorithms including a memetic algorithm combined with a path relinking procedure as a kind of post-optimization technique, and a tabu algorithm to solve MCVRP. These algorithms were tested on a set of instances modified on the basis of standard CVRP instances. The results showed that the tabu algorithm can find better solutions but require more computation time. Reed et al. [17] developed an ant colony system algorithm for classical CVRP and MCVRP, which combined with a 2-opt local search. They also gave the generation strategy of the MCVRP benchmark instances. Abdulkader et al. [18] generated 28 benchmark MCVRP instances inspired by [17], and then proposed a hybrid algorithm ant colony combing with several local search procedures for the MCVRP. Kaabachi et al. [7] presented a hybrid self-adaptive variable neighborhood search and an artificial bee colony algorithm for the same problem defined in [18]. These two algorithms were first used to solve 36 small randomly-generated problem instances and compared the results with optimal solutions found by CPLEX. Then, the 28 larger instances proposed by [18] were solved and the results revealed the effectiveness of two algorithms. Finally, the algorithms were applied to a real case study.

Recently, Yahyaoui et al. [8] developed an adaptive variable neighborhood search mixed with self-learning local search procedures, and a genetic algorithm based on the partially matched crossover to solve the MCVRP problem, which was the same as that proposed by [7]. After that, Guo et al. [19] designed a hybrid ant colony optimization algorithm for the same MCVRP, which combined the ant colony optimization with two types of variable neighborhood descent techniques. The hybrid algorithm was used to solve 14 MCVRP instances proposed by [18].

The successful applications of these metaheuristics have prompted the research of the solution approaches for MCVRP. However, the existing solution methods still need to be improved due to the intractability of MCVRP. Not like VRP, MCVRP has not been paid more attention, and the solution approaches for MCVRP and its variants have a large room for improvement. As the literature [22] suggests, more effective and innovative solution approaches need to be developed.

In this paper, we developed a hybrid iterated local search to solve MCVRP. Iterated local search (ILS) is a kind of simple and effective single-solution metaheuristic, which has been successfully applied in solving VRP and its variants [4]. ILS is easy to implement, and it can be integrated with other algorithms effectively. Its good performance and high integration ability promote us to solve MCVRP by a hybrid ILS approach with large neighborhood search and simulated annealing.

3 Problem description

In this section, we will describe the multi-compartment vehicle routing problem. Assume there is a distribution center and some distribution customers in an area. We describe it as a graph problem G = (V, A). V = {0, 1, 2, . . . , n} is the vectors of the graph, where 0 represents the distribution center that is the depot. C = {1, 2, 3, . . . , n} is the set of distribution customer nodes. For every vector on the graph, the arcs of it can be described as A = {(i, j) |i, j ∈ V}. There are K homogeneous multi-compartment vehicles located at the depot, K = {1, 2, 3, . . . , k}. Each vehicle has multiple compartments with fixed capacity, and the capacity of each compartment may be different. Each customer node has M = {1, 2, 3, . . . , m} types of goods to be served. Every customer i has a known demand d_im that is the demand of product m, and the node is visited only once by only one vehicle. At the same time, the product m must be put into the corresponding compartment with the capacity of Q_m, which just delivers product m. At any time, the total demand of product m must not exceed Q_m. $Q_{m}^{k}$ represents the total quantity of product m by vehicle k after visiting node i. The binary decision variable x_ijk = 1 denotes that the vehicle k directly visits node j after visiting node i. The distance cost between any nodes on the graph is d_ij. The vehicle starts from the depot, visits some customers and then returns to the depot. The total travel distance of one vehicle cannot exceed the maximum route length L. The objective of this problem aims to find the best routes planning to have the minimum total travel distance.

The mathematical formulation of the MCVRP can be defined as follows.

Minimize: $\sum_{k \in K} \sum_{i \in V} \sum_{j \in V} d_{ij} x_{ijk}$ (1)

Subject to: $\sum_{k \in K} \sum_{i \in C} x_{ijk} = 1, \forall j \in C$ (2) $\sum_{k \in K} \sum_{j \in C} x_{ijk} = 1, \forall i \in C$ (3) $\sum_{i \in C} x_{0 ik} = \sum_{j \in C} x_{j 0 k} = 1, \forall k \in K$ (4) $d_{im} \leq Q_{im}^{k} \leq Q_{m}, \forall i \in V, k \in K, m \in M$ (5) $(Q_{im}^{k} + q_{jm}) x_{ijk} \leq Q_{jm}^{k}, \forall i \in V, k \in K, m \in M$ (6) $\sum_{i \in V} \sum_{j \in V} d_{ij} x_{ijk} \leq L, \forall k \in K$ (7) $x_{ijk} \in {0, 1}, \forall i \in V, j \in V, i \neq j, k \in K$ (8)

Equation (1) defines the optimization objective, which is to minimize the total travel distance. Constraints (2) and (3) ensure that every customer must be served only once by one vehicle. Constraint (4) indicates that every vehicle must start from the depot and end the depot. Inequality (5) ensures that the total quantity of each product must not exceed the capacity of the compartment at any time. Inequality (6) represents the accumulation of each product in a vehicle. If the vehicle visits node j after visiting node i, $Q_{im}^{k} + q_{jm} = Q_{jm}^{k}$ , otherwise $(Q_{im}^{k} + q_{jm}) x_{ijk} = 0$ . Inequality (7) states the total travel distance of each vehicle cannot exceed the maximum route length L. The value of the decision variable x_ijk is defined in Equation (8).

4 Proposed algorithm

4.1 Overall description of HILS

The general ILS is a flexible local search-based metaheuristic algorithm framework, which has been successfully applied to many combinatorial optimization problems. ILS is an approximation metaheuristic algorithm and it can find a relatively better solution in a reasonable time. The general components of ILS include the construction of an initial solution, local search, perturbation, and acceptance. Among of the components, perturbation and acceptance are important to keep the diversity of the algorithm. In this paper, we combine the ILS algorithm with a large neighborhood search and simulated annealing to improve the effectiveness of ILS. The framework of the hybrid algorithm (called HILS) is given in Algorithm 1.

Algorithm 1 HILS
Input: number of iteration maxiter, neighborhood list size nb, trail number iter, the minimum destruction factor p_min, the maximum destruction factor p_max, temperature T, cooling scale a, strategy rules rules.
Output: the best solution S^*
1: Initialize all the parameters and set S^* = Null, t = 0;
2: S_c = GetInitialSolution();
3: whilet < maxiterdo
4: S_n = LocalSearch(S_c, nb, rules);
5: ifS_n < S^*then
6: S^* = S_n;
7: S_c = Acceptance(S_n,S_c,T,a);
8: S_p = LNSPerturb(S_c,iter,p_min,p_max);
9: S_c = S_p;
10: T = T*a;
11: t ++;

In Algorithm1, HILS starts with an initial solution S_c and then executes iteratively three procedures including local search, perturbation, and acceptance. The main body of the HILS algorithm is between step (3) and step (11). First, the initial solution is gotten by the savings algorithm proposed by [26], which is extended to tackle multiple compartments. It’s just a matter of putting different kinds of goods into the corresponding compartment while considering the capacity constraint of compartments. For the local search of the algorithm, which is in step (4), we modify five neighborhood structures to find the local best solutions. The description of these neighborhood structures will be shown in section 4.2. For each neighborhood solution, the acceptance rules will be used to determine whether to be accepted or refused. And then the new solution will be perturbed to generate the different start points of the search. The LNS-based perturbation method is described in detail in section 4.3. As shown in Algorithm 1, the outline of the HILS algorithm is very clear, and every component collaborates with each other. When HILS terminates, the global best solution will return.

4.2 Neighborhood structures

In the framework of ILS, the current solution is improved literately by several neighborhood structures. The neighborhood operators are usually used in VRP variants including shift, swap, and other classical neighborhood operators. For this problem, we employ five neighborhood structures to explore the neighborhood solution space. When every neighborhood operator is executed, it must obtain a feasible solution satisfying all the constraints of MCVRP.

The neighborhood operators are described in the following.

(1) One point move. A customer node is selected randomly and then shifted to the same route or another route. When the operator occurs at the same route, as shown in Fig. 1(a), it need not check the capacity constraints and just check the constraints of the route length. When it occurs between the two different routes, it must check the shift whether will violate the capacity and route length constraints of both routes. If this move is feasible, the node will be removed from the original route and then inserted into the target route. In Fig. 1(b), node 2 located in route R1 will be inserted into the target route R2. After the operation, two new routes are obtained.

Fig. 1

Example of one point move operation.

(2) Two points swap. Two customer nodes swap their positions. The operator changes the position of the customers, and it will bring a change in capacity and the length of the routes. It also includes inter-route and intra-route operators. Figure 2 gives the operation illustration of this operation. Node 2 and node 4 are swapped on the same route R (In Fig. 2(a)). In this case, only the length of the route constraint is detected. For two different routes R1 and R2, node 2 and node 7 are exchanged in Fig. 2(b). The capacity and route length of routes R1 and R2 need to be checked. This operation changes the permutation of nodes to provide potentially a variety of possibilities for the search for solutions.

Fig. 2

Example of two points swap operation.

(3) 2-opt. 2-opt is a very simple and effective improvement neighborhood operator. It is used in one route to reduce its total distance. 2-opt first selects two non-adjacent edges and then removes them from the route. Then, two new edges are added while keeping the nodes between the two original edges reversed. As shown in Fig. 3, two non-adjacent edges e1 and e2 are first broken. The nodes between edges e1 and e2 are reversed, and then two new edges e3 and e4 are added to create a new route.

Fig. 3

Example of 2-opt operation.

(4) Cross. This operator is an inter-route neighborhood operator. For two different routes, it selects one edge from each route and breaks them, and then crosses the tails to create two new routes. This operator can change the nodes sequence of the routes. In Fig. 4, two edges e1 and e2 are broken, and then an edge e3 connecting node 2 and node 7 is added to generate a new route R1. At the same time, an edge e4 is added to connect node 6 and node 3 to obtain a new route R2.

Fig. 4

Example of cross operation.

(5) Or-opt. A sequence of consecutive nodes is chosen to be shifted to another position of the same route or another route. The number of customer nodes is usually an integer in [2, 4]. In this paper, the operator is executed orderly three times with the number of customer nodes of 2, 3, and 4. Figure 5 gives an example of or-opt operation. There are three continuous nodes including customer node 2, node 3 and node 4, and then they are inserted into the same route or the different route.

Fig. 5

Example of Or-opt operation.

4.3 LNS-based perturbation method

As a kind of local search-based metaheuristic, the search of ILS may trap in the local optima. The perturbation mechanism of the ILS algorithm can search from the different start points and lead the algorithm to a different local optimum. The commonly used perturbation methods consist of multi-point shift, multi-point swap, or the cross between the routes. But these methods still explore a relatively small solution space. To explore a larger neighborhood solution space, we adopt a large neighborhood search algorithm to perturb the local best solution found at every iteration. The large neighborhood search algorithm is referred to as a ruin-and-recreate strategy [27], which includes the destruction and repair of the solution two procedures. On the hand, the LNS-based perturbation method can change the structures of the local best solution. On the other hand, it can explore a relatively larger solution space and may find better neighborhood solutions.

The pseudocode description of LNS-based perturbation method (denoted as LNSPerturb) is shown in Algorithm 2.

Algorithm 2 LNSPerturb
Input: current solution S_b, the number of iteration iter, the minimum destruction factor p_min, the maximum destruction factor p_max;
Output: the best solution S_p
1: Set iteration number t = 1, removed nodes list nodes = Null;
2: S_p = S_b;
3: whilet ≤ iterdo
4: nodes = GetRemovedNodes(S_b,p_min,p_max);
5: R^* = DestroySolution(S_b,nodes);
6: S_n = RepairSolution(R^,nodes*);
7: ifS_n < S_pthen
8: S_p = S_n;
9: S_b = S_n;
10: t ++;

In Algorithm 2, steps (1) and (2) initialize the values of variables and the best solution. The main loop of the proposed algorithm is between step (3) and step (10), which consists of two phases. In the destruction phase, the customers that will be removed from the solution is first determined randomly in step (4). Then, they are deleted from the current solution in step (5). The repair procedure is step (6), which uses the cheapest insertion method to recreate the whole solution. The best solution is updated in step (7) and step (8). Next, the whole solution replaces the current solution to take part in the next iteration until the algorithm meets the termination condition. Finally, the best solution S_p will return as the perturbation solution.

In the destruction procedure, the number of removed nodes is controlled by the perturbation strength, which is a real number between 0 and 1. For example, if the perturbation strength is 0.1, it means 10% nodes of the solution will be removed. If the perturbation strength is too large, the destruction procedure will become very time-consuming and also cause difficulty in repair. But if the perturbation strength is too small, the perturbation method will have inconspicuous effectiveness. Thus, we use a random number between the minimum strength and maximum strength. It will keep the quality and efficiency from the view on the whole.

Once the number of removed nodes is gotten, the nodes are first selected and then removed from the current solution. We used a node selection strategy considering both randomness and correlation to decide the nodes to be removed. The destruction procedure is described in the following. Assume that n nodes will be destroyed. Firstly, a node is randomly selected as a seed, and then the neighborhood element lists size of 2 * n is created by the distance between the seed and other nodes. Secondly, n - 1 nodes are randomly selected from the neighborhood element lists. Finally, the seed node and n - 1 nodes are all removed from the solution, which will produce a partial infeasible solution.

In the repair procedure, we use a greedy cheapest insertion method to repair the partial solution. For every removed node, it will be inserted into the position with the lowest insertion cost. If there does not exist a position that can be inserted, a new route containing the customer will be created and then added to the solution. When the repair procedure finishes, the solution must be feasible.

4.4 Acceptance criterion

For ILS, keeping the diversity of neighborhood solutions is important to avoid trapping local optima. When a new neighborhood solution is gotten after the local search process, if this new solution is better than the current solution, the new solution will be accepted. This acceptance rule is called improved acceptance. If the algorithm always accepts the better neighborhood solution, it is easy to trap into the local optima due to the lack of multifarious solutions. To overcome this shortcoming, we use a nondeterministic acceptance rule to decide whether to accept or refuse the worse solutions. The simulated annealing-based acceptance rule is applied and defined in Equation (9).

$S = {\begin{matrix} S_{n}, f (S_{n}) < f (S_{c}) \\ S_{n}, e^{[- (f (S_{n}) - f (S_{c})) / Δ t]} > p, p \in (0, 1) \end{matrix}}_$ (9)

where S_c and S_n are the current solution and new neighborhood solution respectively, Δt is the current temperature, p is a random number between 0 and 1, and f (S_n) is the objective value of S_n. When S_n is better than S_c, S_n is always accepted. If S_n is inferior than S_c, S_n is accepted by a certain probability.

5 Computational experiments

In this section, we will describe the setting of parameters and conduct some experiments to evaluate the performance of our proposed algorithm. The proposed algorithm was coded by C# in Visual Studio 2019. All the experiments were executed on a personal computer with Intel i7-6700 CPU @3.40GHz and 8G RAM running windows 10 64-bit operating system. The proposed algorithm was executed 10 times.

5.1 Parameters settings

For the HILS algorithm, there are three types of parameters to be decided including the parameters of ILS, perturbation method, and acceptance rule respectively. The number of maximum iteration is set to 100, and the size of the neighborhood list is 30. For the perturbation method, the maximum trail number is set to 30. The perturbation strength is randomly selected from a range of [0.05, 0.4], which means the minimum and maximum perturbation strength is 0.05 and 0.4. For the SA-based acceptance rule, the initial value of temperature is set to 2 and the cooling rate is set to 0.9. In addition, we appoint that if the current solution does not be improved continuously 20 times, the algorithm will terminate.

5.2 Benchmark instances

To evaluate the performance of the proposed algorithm, we use 28 benchmark instances designed by [18]. These instances come from CVRP instances using the strategy of [17]. The capacity of the vehicle is split into two compartments by 1:3 ratio. Meanwhile, the two different strategies are used to produce 28 benchmark instances. The detail of generation benchmark instances is provided by [18]. For these instances, the number of customers is between 50 and 199, and there are also some instances with maximum route length constraints except capacity constraints.

5.3 Computational results and comparison

To investigate the effectiveness of the proposed algorithm, we conducted some experiments to compare it with the existing state-of-the-art algorithms for MCVRP.

Firstly, we used HILS to solve 28 benchmark instances, and then compared it with six MCVRP algorithms developed in recent years. The comparison algorithms include a classical ant colony algorithm (ACS) [17], a hybridized ant colony (HAC) [18], a hybrid self-adaptive general variable neighborhood algorithm (HAVNS) [7], a hybrid artificial bee colony (HABC) [7], an adaptive variable neighborhood search (AVNS) [8], and a partially matched crossover-based genetic algorithm (GAPMX) [8]. These algorithms were developed for the same MCVRP problem defined in this paper.

Table 1 gives the results of HILS and the other six algorithms. For HILS, we calculate the best solution, worst solution, average solution, standard deviation, and average computation time, which are shown in column Best, column Worst, column Avg, column Std, and column T respectively. For other algorithms, the best solutions obtained by them come from the corresponding literature. The results shown in bold denote that they are the best solutions. The underlined and bold results indicate the instances where HILS outperforms or equals the start-of-the-art results.

Table 1
comparison results of HILS and six algorithms on 28 instances

Instance ACS HAC HAVNS HABC AVNS GAPMX HILS

Best Worst Avg Std T(s)

vrpnc1a 569.564 550.70 550.70 550.42 550.70 551 550.70 552.19 551.97 0.49 2.61

vrpnc1b 569.118 551.94 506.18 502.83 506.18 551 548.77 567.64 552.3 6.52 1.14

vrpnc2a 957.525 890.68 881.84 890.68 890.68 901 875.13 890.15 882.75 4.48 2.67

vrpnc2b 954.856 918.96 918.96 914.00 918.96 914 880.31 925.27 901.72 14.17 2.59

vrpnc3a 964.132 874.07 878.83 875.24 880.84 894 865.23 882.61 873.53 5.85 2.71

vrpnc3b 959.327 895.26 898.64 895.39 900.63 914 865.82 882.79 874.62 4.96 2.46

vrpnc4a 1253.860 1126.12 1126.12 1126.12 1126.12 1243 1089.91 1120.61 1110.99 7.78 6.42

vrpnc4b 1254.510 1159.48 1159.48 1159.48 1159.48 1204 1113.15 1160.6 1139.18 14.14 6.06

vrpnc5a 1587.020 1444.29 1408.86 1385.71 1408.86 1470 1380.69 1452.62 1425.23 21.43 8.14

vrpnc5b 1640.590 1525.87 1515.25 1492.02 1515.25 1570 1426.27 1514.79 1471.55 15.99 9.77

vrpnc6a 573.274 557.49 557.49 557.49 557.49 560 557.49 569.06 560.48 4.47 0.68

vrpnc6b 573.378 559.37 503.82 503.94 505.56 563 555.43 564.28 559.09 2.66 1.02

vrpnc7a 997.007 928.24 928.24 928.24 928.24 980 927.62 953.88 941.85 7.85 3.55

vrpnv7b 969.337 932.67 932.67 932.67 932.67 960 930.66 960.08 946.39 8.59 2.57

vrpnc8a 963.381 882.96 888.50 885.50 890.20 880 876.67 912.87 891.85 12.13 3.61

vrpnc8b 976.212 884.85 887.35 885.14 889.30 884 874.82 920.97 891.68 16.26 2.44

vrpnc9a 1343.08 1228.88 1211.21 1221.00 1211.32 1221 1212.66 1279.51 1246.29 17.55 5.58

vrpnc9b 1346.63 1226.58 1221.26 1226.00 1220.58 1226 1213.66 1251.71 1232.36 15.13 5.87

vrpnc10a 1645.58 1511.65 1505.23 1504.68 1505.23 1680 1493.77 1554.12 1521.09 17.02 10.51

vrpnc10b 1659.94 1526.02 1517.65 1516.86 1517.65 1683 1499.63 1582.94 1532.97 24.01 12.16

vrpnc11a 1133.880 1110.45 1110.45 1110.45 1110.45 1130 1115.97 1132.47 1126.53 4.33 2.61

vrpnc11b 1247.490 1221.73 1221.73 1220.43 1221.73 1250 1217.47 1254.56 1231.27 11.68 1.14

vrpnc12a 911.861 912.64 901.22 901.15 901.36 913 902.59 921.1 912.82 5.33 2.67

vrpnc12b 970.833 950.79 935.62 923.25 936.25 960 950.79 975.11 964.13 8.63 2.59

vrpnc13a 1577.45 1556.46 1549.93 1549.82 1550.56 1570 1563.66 1593.69 1583.7 10.45 3.26

vrpnc13b 1572.11 1550.12 1538.67 1536.38 1540.37 1572 1562.46 1594.58 1579.97 11.42 5.35

vrpnc14a 914.857 911.35 911.35 911.35 911.35 913 911.98 936.26 919.4 9.24 2.98

vrpnc14b 970.933 965.84 965.84 965.84 965.84 973 966.30 994.58 978.41 10.76 4.01

Average 1109.205 1048.41 1040.47 1038.29 1041.21 1076.07 1033.20 1067.89 1050.15 10.48 4.18

Instance	ACS	HAC	HAVNS	HABC	AVNS	GAPMX	HILS
vrpnc1a	569.564	550.70	550.70	550.42	550.70	551	550.70	552.19	551.97	0.49	2.61
vrpnc1b	569.118	551.94	506.18	502.83	506.18	551	548.77	567.64	552.3	6.52	1.14
vrpnc2a	957.525	890.68	881.84	890.68	890.68	901	875.13	890.15	882.75	4.48	2.67
vrpnc2b	954.856	918.96	918.96	914.00	918.96	914	880.31	925.27	901.72	14.17	2.59
vrpnc3a	964.132	874.07	878.83	875.24	880.84	894	865.23	882.61	873.53	5.85	2.71
vrpnc3b	959.327	895.26	898.64	895.39	900.63	914	865.82	882.79	874.62	4.96	2.46
vrpnc4a	1253.860	1126.12	1126.12	1126.12	1126.12	1243	1089.91	1120.61	1110.99	7.78	6.42
vrpnc4b	1254.510	1159.48	1159.48	1159.48	1159.48	1204	1113.15	1160.6	1139.18	14.14	6.06
vrpnc5a	1587.020	1444.29	1408.86	1385.71	1408.86	1470	1380.69	1452.62	1425.23	21.43	8.14
vrpnc5b	1640.590	1525.87	1515.25	1492.02	1515.25	1570	1426.27	1514.79	1471.55	15.99	9.77
vrpnc6a	573.274	557.49	557.49	557.49	557.49	560	557.49	569.06	560.48	4.47	0.68
vrpnc6b	573.378	559.37	503.82	503.94	505.56	563	555.43	564.28	559.09	2.66	1.02
vrpnc7a	997.007	928.24	928.24	928.24	928.24	980	927.62	953.88	941.85	7.85	3.55
vrpnv7b	969.337	932.67	932.67	932.67	932.67	960	930.66	960.08	946.39	8.59	2.57
vrpnc8a	963.381	882.96	888.50	885.50	890.20	880	876.67	912.87	891.85	12.13	3.61
vrpnc8b	976.212	884.85	887.35	885.14	889.30	884	874.82	920.97	891.68	16.26	2.44
vrpnc9a	1343.08	1228.88	1211.21	1221.00	1211.32	1221	1212.66	1279.51	1246.29	17.55	5.58
vrpnc9b	1346.63	1226.58	1221.26	1226.00	1220.58	1226	1213.66	1251.71	1232.36	15.13	5.87
vrpnc10a	1645.58	1511.65	1505.23	1504.68	1505.23	1680	1493.77	1554.12	1521.09	17.02	10.51
vrpnc10b	1659.94	1526.02	1517.65	1516.86	1517.65	1683	1499.63	1582.94	1532.97	24.01	12.16
vrpnc11a	1133.880	1110.45	1110.45	1110.45	1110.45	1130	1115.97	1132.47	1126.53	4.33	2.61
vrpnc11b	1247.490	1221.73	1221.73	1220.43	1221.73	1250	1217.47	1254.56	1231.27	11.68	1.14
vrpnc12a	911.861	912.64	901.22	901.15	901.36	913	902.59	921.1	912.82	5.33	2.67
vrpnc12b	970.833	950.79	935.62	923.25	936.25	960	950.79	975.11	964.13	8.63	2.59
vrpnc13a	1577.45	1556.46	1549.93	1549.82	1550.56	1570	1563.66	1593.69	1583.7	10.45	3.26
vrpnc13b	1572.11	1550.12	1538.67	1536.38	1540.37	1572	1562.46	1594.58	1579.97	11.42	5.35
vrpnc14a	914.857	911.35	911.35	911.35	911.35	913	911.98	936.26	919.4	9.24	2.98
vrpnc14b	970.933	965.84	965.84	965.84	965.84	973	966.30	994.58	978.41	10.76	4.01
Average	1109.205	1048.41	1040.47	1038.29	1041.21	1076.07	1033.20	1067.89	1050.15	10.48	4.18

As reported in Table 1, the HILS algorithm has the best average solution and outperforms the other six existing MCVRP algorithms. HILS decreases the total travel distance by 6.85%, 1.45%, 0.70%, 0.49%, 0.77%, and 3.98% on average respectively, compared with ACS, HAC, HAVNS, HABC, AVNS, and GAPMX algorithms. From the viewpoint of finding the best solutions, the HILS algorithm finds 17 best solutions in 28 instances and its success rate is 60.7%. For these comparison algorithms, the HABC algorithm presented by [7] finds the 10 best solutions and its success rate is 35.71%, which outperforms the other five algorithms. From this, we can conclude that the HILS algorithm has a better ability to find the best solutions than other comparison algorithms. In addition, we also find that our proposed algorithm can solve effectively relatively large instances, which have 150 or 199 customers.

Secondly, we take the ACS algorithm developed by [17] as the baseline algorithm and calculated the improvement percentage of the other algorithms on 28 instances. The computation formulation is defined in Equation (10). $Improvement % = \frac{{BF}_{ACS} - A}{{BF}_{ACS}} \times 100 %$ (10) where BF_ACS is the best solution obtain by the ACS algorithm, A denotes the best solution found by comparison algorithm, i.e., HAC or HILS. When the value of the improvement percentage is below zero, it means that the algorithm cannot find a better solution than the ACS algorithm. The improvement percentage of HILS and comparison algorithms compared with the ACS baseline algorithm are shown in Table 2. The maximum, minimum, and average improvement percentages are indicated in columns Max, Min, and Avg respectively.

Table 2

Improvement percentage of HILS and comparison algorithms

Algorithms	Improvement percentage (%)
	Max	Min	Avg
HAC	10.19	-0.09	5.14
HAVNS	12.13	0.38	6.08
HABC	12.68	0.38	6.25
AVNS	11.83	-0.21	5.97
GAPMX	9.45	-2.09	3.11
HILS	13.08	0.31	6.35

As shown in Table 2, the HILS has the biggest improvement percentage on average among all the algorithms, which reaches 6.35%. For the other five algorithms, their improvement percentage on average are 5.14%, 6.08%, 6.25%, 5.97%, and 3.11% respectively. In addition, HILS also has the maximum improvement percentage and it is 13.08%. The maximum improvement percentages of HAC, HAVNS, HABC and AVNS approaches are larger than 10%, while that of GAPMAX is 9.45%. For some instances in Table 1, such as vrpnc10a, vrpnc10b, vrpnc11b, vrpnc12a, and vrpnc14b, the comparison algorithms except HABC and AVNS cannot get a better solution than HAC on one or multiple instances. Although HABC, AVNS and HILS can both find better solutions than ACS, the HILS algorithm has a higher average improvement percentage value on 28 instances.

Furthermore, we calculate the number of instances whose improvement percentage values are in different ranges, and the results are shown in Fig. 6.

Fig. 6

the number of improvement instances of the six algorithms.

As shown in Fig. 6, for the HILS algorithm, improvement percentage values of 6 instances are more than 10%. For other algorithms, the maximum number of improvement percentages more than 10% is 4. In addition, the HILS algorithm has improved all the instances. These results demonstrate that the HILS algorithm is effective and outperforms the existing state-of-the-art algorithms for MCVRP.

Then, we compare the proposed algorithm with an improved hybrid ant colony optimization algorithm (IHACO) developed by [19] on 14 instances. The results of them are shown in Table 3. Column Best and column T represent the best solution and average run-time obtained by the corresponding method respectively. Column Gap indicates the improvement degree of the HILS algorithm relative to IHACO. The better solutions that were found by HILS and IHACO are shown in bold.

Table 3

Improvement percentage of HILS and comparison algorithms

Instance	IHACO		HILS		Gap(%)
	Best	T(s)	Best	T(s)
vrpnc1a	550.70	6	550.70	2.61	0.00
vrpnc1b	548.77	7	548.77	1.14	0.00
vrpnc2a	873.57	13	875.13	2.67	-0.18
vrpnc2b	888.38	15	880.31	2.59	0.91
vrpnc3a	870.11	35	865.23	2.71	0.56
vrpnc3b	871.22	16	865.82	2.46	0.62
vrpnc4a	1110.06	33	1089.91	6.42	1.82
vrpnc4b	1134.9	116	1113.15	6.06	1.92
vrpnc5a	1423.11	414	1380.69	8.14	2.98
vrpnc5b	1456.16	125	1426.27	9.77	2.05
vrpnc11a	1110.45	75	1115.97	2.61	-0.50
vrpnc11b	1218.66	71	1217.47	1.14	0.10
vrpnc12a	907.73	42	902.59	2.67	0.57
vrpnc12b	961.74	51	950.79	2.59	1.14
Average	994.68	72.79	984.49	3.83	0.86

As shown in Table 3, the HILS algorithm has a smaller average solution and the average improvement is 0.86% compared with IHACO. The HILS algorithm can gain 10 better solutions than IHACO. For instance vrpnc01a and vrpnc01b, HILS and IHACO have an identical effect for getting a solution. In general, HILS can gain better solutions than IHACO.

Finally, we compare the computation time of the proposed algorithm and comparison algorithms used in this section. The ACS [17] and HAC [18] algorithms were run on a server that has four 2.1 GHz processors with 16 core and 256GB RAM. The HAVNS [7], HABC [7], AVNS [8] and GAPMX [8] algorithms were executed on a personal computer with Intel Core i5 2.20 GHz,600 GO RAM. Their average computation times on 28 instances in Table 1 are 204.5 seconds, 128.5 seconds, 123.43 seconds, 183 seconds, 125.4 seconds and 180 seconds respectively, which are obtained from the corresponding literature [7, 8, 17, 18]. For the IHACO algorithm [19] that was run on a computer with Intel 1.80GHz and 12GB RAM, its average computation time is 72.79 seconds. The average computation time of HILS is 4.18 seconds and 3.83 seconds on two types of instances. From the view of computation time, our proposed algorithm spends less time getting better solutions. Although the computation environments of comparison algorithms are different, the HILS algorithm is not a time-consuming algorithm, which can obtain quickly the solutions.

5.4 Performance analysis of hybridization

In this section, we analyze the effect of hybridizing the ILS algorithm with LNS-based perturbation and SA-based acceptance rule. In order to test the performance of hybridization, we constructed three algorithms based on HILS to solve the MCVRP. First, we constructed a basic algorithm (denoted as ILS) by changing the perturbation method to common cross perturbation and using only the improvement acceptance rule. Then, the second algorithm (called ILS+SA) was modified to use the cross-perturbation method. Finally, the third algorithm (denoted as ILS+LNS) was updated by employing only improvement acceptance. These three algorithms had the same parameters setting of HILS and they were executed on the same personal computer. Taking the ACS algorithm as the baseline algorithm, we calculated the average total distance, total execution time, and average improvement percentage respectively. The results are shown in Table 4.

Table 4
The effectiveness of different hybridization styles

Hybridization style Average total distance Total execution time(s) Average improvement(%)

ILS 1080.80 14.85 2.08%

ILS+SA 1077.87 17.75 2.34%

ILS+LNS 1038.84 83.68 5.92%

HILS(ILS+LNS+SA) 1033.20 117.17 6.35%

Hybridization style	Average total distance	Total execution time(s)	Average improvement(%)
ILS	1080.80	14.85	2.08%
ILS+SA	1077.87	17.75	2.34%
ILS+LNS	1038.84	83.68	5.92%
HILS(ILS+LNS+SA)	1033.20	117.17	6.35%

We have some findings from Table 4. First, the ILS algorithm using the SA-based acceptance rule can find better solutions, due to the diversification of the solutions. The average total distance decreases from 1080.80 to 1077.87, and the quality of the algorithm increases from 2.08% to 2.34%. Next, when the perturbation method based on a large neighborhood search is used in the ILS, the quality of the solution has improved greatly from 2.34% to 5.92%. Large neighborhood search has the property of exploring larger solution space, and its ruin-and-recreate principle makes the algorithm find better solutions. In addition, it can search the solution on the whole not in a relatively smaller solution space. Because it searches in a larger solution space, the execution time will be added to some extent. Finally, when we use both the LNS-based perturbation method and the SA-based acceptance rule in the ILS algorithm, the best improvement percentage reaches 6.35% and the best average total distance is obtained.

The results shown in Table 4 indicate that our proposed algorithm is very effective in improving the solution quality. It can be explained that the LNS-based perturbation method can search in a larger solution space on the whole, which can make it possible for the algorithm to find the best solution from a global perspective. The inferior solutions are accepted by some probability defined in the simulated annealing algorithm, which can keep the diversification of the algorithm.

5.5 Influence analysis of different perturbation strengths

For HILS, the perturbation method based on large neighborhood search not only can make it to search from a different starting point but also help it jump out of local optima. The perturbation strength can affect the quality and computation time of the algorithm due to the ruin-and-recreate principle of large neighborhood search. It is generally agreed that a suitable perturbation strength is crucial to the performance of the algorithm [28].

We did an experiment to analyze the influence of different perturbation strengths. As mentioned above, the perturbation length of the HILS algorithm is randomly selected from a range [0.05, 0.4]. We first created a list of perturbation strength PL = {0.05, 0.1, 0.15, 0.2, 0.25, 0.3, 0.35, 0.4}. Then, we constructed two other iterated local search algorithms based on the proposed algorithm. One is named HILS_A, which uses a fixed perturbation strength from PL. After preliminary testing, the perturbation strength is set to 0.2, the HILS_A algorithm can find the best results. The other is called HILS_B, and the value of perturbation strength is randomly selected from the list PL. Finally, we adopted these two algorithms to solve 28 standard instances. Meanwhile, we also take ACS as a baseline and calculate their improvement percentages.

Table 5 reports the results of HILS and its two variants. The description of improvement percentages is the same as Table 2. The first finding in Table 5 is that HILS still has the best average total distance and decreases it by 6.35% on average. The variant HILS_B has the worst performance of the three algorithms. There exist some instances that are not improved by HILS_B compared with ACS. Form the view of the total computation time, HILS_A and HILS_B spend the most and least computation time respectively. Generally speaking, the HILS algorithm can achieve a balance between quality and efficiency.

Table 5
Influence of different perturbation strengths

Algorithms Average Total Distance Total Execution) Time(s Improvement Percentage (%)

Max Min Avg

HILS_A 1036.50 128.33 13.20 0.22 6.11

HILS_B 1038.41 92.10 12.81 -0.14 5.93

HILS 1033.20 117.17 13.08 0.31 6.35

Algorithms	Average Total Distance	Total Execution) Time(s	Improvement Percentage (%)
HILS_A	1036.50	128.33	13.20	0.22	6.11
HILS_B	1038.41	92.10	12.81	-0.14	5.93
HILS	1033.20	117.17	13.08	0.31	6.35

6 Conclusion

The demand of different products delivered in the same vehicle with multiple compartments derives a new vehicle routing problem variant, that is, multiple-compartment vehicle routing problem (MCVRP). In this paper, we developed a hybrid iterated local search metaheuristic, named HILS, to solve it effectively. In the framework of iterated local search, we adopted iteratively some neighborhood operators to find the local best solution in the local search process. To avoid the algorithm trapping into local optimal prematurely, an effective perturbation method based on a large neighborhood search algorithm was used to perturb the neighborhood solution. Additionally, we also adopted an acceptance rule based on simulated annealing to decide the acceptance of neighborhood solutions to keep the diversification of the algorithm.

We carried out some experiments to evaluate our proposed algorithm. First, we executed our proposed algorithm on MCVRP benchmark instances and compared it with the existing state-of-the-art metaheuristics. The results reveal that our proposed algorithm can more significantly reduce the average total travel distance as well as be more competitive than the existing algorithms. Secondly, we tested and analyzed the effectiveness of hybridization. The large neighborhood search perturbation method used in the proposed algorithm can obtain better solutions than the general disturbance method like a cross of routes. We found that the use of the perturbation method based on large neighborhood search can greatly improve the quality of the proposed algorithm owing to its operation in a relatively large solution space. Meanwhile, allowing accepting worse solutions in the local search will bring the diversification of the solutions. The hybridization of these approaches brings the balance between intensification and diversification for the proposed algorithm. Finally, we analyzed the influence of different perturbation strengths. For the same large neighborhood search perturbation methods, the perturbation strength will affect the quality and inefficiency of the proposed algorithm. For different perturbation strength strategies, the perturbation strength that takes values from a continuous range can work better than that of a fixed value and discrete value.

In the future, we will do some work to improve the effectiveness and general applicability of the proposed algorithm. The main work is to improve further the robustness and stability of HILS by hybrid exact heuristics or other outstanding metaheuristics because the metaheuristics have stochastic and random characteristics. Furthermore, with the increasing use of multi-compartment vehicles in many fields, some new problem attributes such as time windows, stochastic demand, and flexible variable compartments become the new constraints of the MCVRP. Extending our proposed algorithm to solve these new MCVRP variants will be a promising research topic.

Footnotes

Acknowledgment

This work was supported partially by the Key Project of Colleges and Universities of Henan Province, China (23A520014).

References

Bodin

, Golden

, Assad

and Ball

, Routing and scheduling ofvehicles and crews: the state of the art, Computers & Operational Research 10 (1983), 63–211.

Laporte

, fifty years of vehicle routing, Transportation Science 43 (2009), 408–416.

Lahyani

, Khemakhem

and Semet

, Rich vehicle routing problems: from a taxonomy to a definition, European Journal of Operation Research 241 (2015), 1–14.

Elshaer

and Awad

, A taxonomic review of metaheuristic algorithms for solving the vehicle routing problem and its variants, Computers & Industrial Engineering 140 (2020), 106242.

Ewbank

, Wanke

, Correa

H.L.

and Figueiredo

, The capacitated vehicle routing problem revisited: using fuzzy c-means clustering, International Journal of Logistics Systems and Management 34(4) (2019), 411–430.

Hsu

Y.C.

, Walteros

J.L.

and Batta

, Solving the petroleum replenishment and routing problem with variable demands and time windows, Annals of Operations Research 294 (2018), 9–46.

Kaabachi

, Yahyaoui

, Krichen

and Dekdouk

, Measuring and evaluating hybrid metaheuristics for solving the multi-compartment vehicle routing problem, Measurement 141 (2019), 407–419.

Yahyaoui

, Kaabachi

, Krichen

and Dekdouk

, Two metaheuristic approaches for solving the multi-compartment vehicle routing problem, Operation Research 20 (2020), 2085–2108.

Chen

, Liu

and Langevin

, A multi-compartment vehicle routing problem in cold-chain distribution, Computers and Operations Research 11 (2019), 58–66.

10.

Muyldermans

and Pang

, On the benefits of co-collection:experiments with a multi-compartment vehicle routing problem algorithm, European Journal of Operational Research 206(2010), 93–103.

11.

Chen

J.M.

and Shi

, A multi-compartment vehicle routing problem with time windows for urban distribution-A comparison study on particle swarm optimization, Computers & Industrial Engineering 133 (2019), 95–106.

12.

Agushaka

J.O.

, Ezugwu

A.E.

and Abualigah

, Gazelle optimization algorithm: a novel nature-inspired metaheuristic optimizer, Neural Computing & Applications (2022). https://doi.org/10.1007/s00521-022-07854-6

13.

Abualigah

L.M.

and Khader

A.T.

, Unsupervised text feature selection technique based on hybrid particle swarm optimization algorithm with genetic operators for the text clustering, Journal of Supercomputing 73(11) (2017), 4773–4795.

14.

Parizi

M.K.

, Keynia

and Bardsiri

A.K.

, Woodpecker Mating Algorithm (WMA): a nature-inspired algorithm for solving optimization problems, International Journal of Nonlinear Analysis and Applications 11(1) (2020), 137–157.

15.

Parizi

M.K.

, Keynia

and Bardsiri

A.K.

, OWMA: An improved self-regulatory woodpecker mating algorithm using opposition-based learning and allocation of local memory for solving optimization problems, Journal of Intelligent & Fuzzy Systems 40(1) (2021), 919–946.

16.

Parizi

M.K.

, Keynia

and Bardsiri

A.K.

, HSCWMA: A New Hybrid SCA-WMA Algorithm for Solving Optimization Problems, International Journal of Information Technology and Decision Making 20(2) (2021), 775–808.

17.

Reed

, Yiannakou

and Evering

, An ant colony algorithm for the multi-compartment vehicle routing problem, Applied Soft Computing 15 (2014), 169–176.

18.

Abdulkader

M.M.S.

, Gajpal

and ElMekkawy

T.Y.

, Hybridized ant colony algorithm for the Multi-Compartment Vehicle Routing Problem, Applied Soft Computing 37 (2015), 196–203.

19.

Guo

, Qian

, Hu

, Jin

H.P.

and Feng

H.X.

, A Hybrid Ant colony Optimization Algorithm for Multi-Compartment Vehicle Routing Problem, Complexity (2020), 8839526.

20.

Silvestrin

P.V.

and Ritt

, An iterated tabu search for the multi-compartment vehicle routing problem, Computers and Operations Research 81 (2017), 192–202.

21.

Sun

L.J.

, Zhou

Y.X.

, Teng

and Hu

X.P.

, Multi-compartment vehicle routing problem: Status and Perspectives, Systems Engineering-Theory & Practicle 41(6) (2021), 1535–1546.

22.

Ostermeier

, Henke

, Hübner

and Wäscher

, Multi-compartment vehicle routing problems: State-of-the-art, modeling framework and future directions, European Journal of Operational Research 292 (2021), 799–817.

23.

Archetti

, Campbell

A.M.

and Speranza

M.G.

, Multicommodity vs. single-commodity routing, Transportation Science 50(2) (2016), 461–472.

24.

Mirzaei

and Wohlk

, Erratum to: A branch-and-price algorithm for two multi-compartment vehicle routing problem, EURO Journal on Transportation and Logistics 6(2) (2017), 185–218.

25.

Fallahi

A.E.

, Prins

and Calvo

R.W.

, A memetic algorithm and a tabu search for the multi-compartment vehicle routing problem, Computers & Operations Research 35(5) (2008), 1725–1741.

26.

Clarke

G.U.

and Wright

J.W.

, Scheduling of vehicles from a central depot to a number of delivery points, Operation Research 12(4) (1964), 568–581.

27.

Schrimpf

, Schneider

, Stamm-Wilbrandt

and Dueck

, Record breaking optimization results using the ruin and recreate principle, Journal of Computational Physics 159(2) (2000), 139–171.

28.

Pisinger

and Ropke

, A general heuristic for vehicle routing problems, Computers & Operations Research 34(8) (2007), 2403–2435.

A hybrid iterated local search algorithm for the multi-compartment vehicle routing problem

Abstract

Keywords

1 Introduction

2 Related works

3 Problem description

4.1 Overall description of HILS

4.2 Neighborhood structures

4.4 Acceptance criterion

5.1 Parameters settings

5.2 Benchmark instances

5.3 Computational results and comparison

Table 4 The effectiveness of different hybridization styles Hybridization style Average total distance Total execution time(s) Average improvement(%) ILS 1080.80 14.85 2.08% ILS+SA 1077.87 17.75 2.34% ILS+LNS 1038.84 83.68 5.92% HILS(ILS+LNS+SA) 1033.20 117.17 6.35%

Table 5 Influence of different perturbation strengths Algorithms Average Total Distance Total Execution) Time(s Improvement Percentage (%) Max Min Avg HILS_A 1036.50 128.33 13.20 0.22 6.11 HILS_B 1038.41 92.10 12.81 -0.14 5.93 HILS 1033.20 117.17 13.08 0.31 6.35

Footnotes

Acknowledgment

References

Table 4
The effectiveness of different hybridization styles

Hybridization style Average total distance Total execution time(s) Average improvement(%)

ILS 1080.80 14.85 2.08%

ILS+SA 1077.87 17.75 2.34%

ILS+LNS 1038.84 83.68 5.92%

HILS(ILS+LNS+SA) 1033.20 117.17 6.35%

Table 5
Influence of different perturbation strengths

Algorithms Average Total Distance Total Execution) Time(s Improvement Percentage (%)

Max Min Avg

HILS_A 1036.50 128.33 13.20 0.22 6.11

HILS_B 1038.41 92.10 12.81 -0.14 5.93

HILS 1033.20 117.17 13.08 0.31 6.35