# Evolutionary Hyperheuristics for Location-Routing Problem with Simultaneous Pickup and Delivery

Authors: Yanwei Zhao; Longlong Leng; Jingling Zhang; Chunmiao Zhang; Wanliang Wang
Journal: Complexity
 (2020)

---

## Abstract

This paper presents an evolution-based hyperheuristic (EHH) for addressing the capacitated location-routing problem (CLRP) and one of its more practicable variants, namely, CLRP with simultaneous pickup and delivery (CLRPSPD), which are significant and NP-hard model in the complex logistics system. The proposed approaches manage a pool of low-level heuristics (LLH), implementing a set of simple, cheap, and knowledge-poor operators such as “shift” and “swap” to guide the search. Quantum (QS), ant (AS), and particle-inspired (PS) high-level learning strategies (HLH) are developed as evolutionary selection strategies (ESs) to improve the performance of the hyperheuristic framework. Meanwhile, random permutation (RP), tabu search (TS), and fitness rate rank-based multiarmed bandit (FRR-MAB) are also introduced as baselines for comparisons. We evaluated pairings of nine different selection strategies and four acceptance mechanisms and monitored the performance of the first four outstanding pairs in 36 pairs by solving three sets of benchmark instances from the literature. Experimental results show that the proposed approaches outperform most fine-tuned bespoke state-of-the-art approaches in the literature, and PS-AM and AS-AM perform better when compared to the rest of the pairs in terms of obtaining a good trade-off of solution quality and computing time.


---

## Body

## 1. Introduction

As one of the complex systems, logistics network design brings plenty of benefits in terms of economy, society, and environment. Recent years have witnessed great success in applying various tools for optimizing and managing complex logistics system to drive profit and service quality of freight transport [1]. One of such tools is location-routing problem (LRP) [2], integrating two types of decisions: facility location problem and vehicle routing problem (VRP) [3]. Among various extensions to the basic LRP, CLRP and CLRPSPD have been proposed in order to represent different features of practical problems in the complex logistics systems. Meanwhile, an effective solution method should be developed for providing competitive solutions for benchmark instances within reasonable computing time for both CLRP and CLRPSPD. Hence, this paper presents a novel approach to solve both problems.Both CLRP and CLRPSPD are NP-hard, and they are more complicated and time-consuming to solve, especially CLRPSPD. Therefore, it is unlikely to achieve the proven optimality for large instances within reasonable computing time [4]. Our previous work [2] applied a novel framework of hyperheuristic to solve CLRPSPD using tabu search, FRR-MAB, and combination of both as selection strategies and five acceptance criteria. However, the main difference between this paper and our previous work can be obtained: (1) the high-level strategies were inspired from evolutionary algorithms instead of the above strategies; (2) four basic acceptance criteria were developed in this paper which were not used by our previous work; (3) this paper aims at solving the benchmark instances of the CLRP and CLRPSPD, but our previous work only tackled the latter; (4) the pool of operators in our previous work was classified under the premise of nature of operators which was given in advance, but in this paper, the nature of operators was unknown. Moreover, the difference between this paper and Ref. [4] can be drawn that our paper focuses on a different solution method for both CLRP and CLRPSPD, namely, hyperheuristic approach. Therefore, the main contributions are as follows:(i)
Aiming at solving two basic models in complex logistics system, we explore a generality-oriented and emerging heuristic for solving both subjects in complex logistics network, namely, evolutionary hyperheuristic-based iterated local search.(ii)
Inspired from the process of metaheuristics, several ESs are developed for implementing an online learning strategy for adaptively selecting promising sequence of LLHs to attempt to realize the global search, that is, QS, AS, and PS. Other most recent and relevant nonevolutionary selection strategies (RP, TS, and FRR-MAB) [5–7] are also chosen as the baseline for comparison.(iii)
Four basic acceptance criteria are used to pair up with ES and non-ES to examine their performance, that is, All Moves (AM), Naïve Acceptance (NA), Great Deluge (GD), and Simulated Annealing (SA).The remainder of this study is organized as follows. Section2 provides a brief review about the approaches for problem domains and hyperheuristic over recent decades. In Section 3, the three-index MIP formulation for CLRPSPD is defined. The proposed evolution-based selection strategies are described in Section 4, and evaluation and discussion are presented in Section 5. Finally, conclusions are given in Section 6.


## 2. Literature Review

Two types of reviews are concerned in this section: one for problem domains (CLRP/LRPSPD) and one for approaches (i.e., hyperheuristic and HH). The former mainly focuses on effective approaches for solving CLRP and CLRPSPD, while the latter reviews recent technologies in developing HH and applications of HH in real world.


### 2.1. Location-Routing Problem

In the complex logistics, CLRPSPD is a more practical variant version of CLRP by considering reverse logistics, that is, goods need to be picked up from clients when vehicles deliver goods to clients. Firstly, we review some recent approaches for CLRP, and then recent state of CLRPSPD is investigated.As the main component in CLRP, VRP has been studied for decades. In the last years, several researchers have devoted to the development of VRP. Ant colony algorithm was applied to solve network intensive vehicle service [8]. Multiple population-based genetic algorithm was utilized to solve train-set circulation plan problem [9]. A hybrid tabu search algorithm was developed for a real-world problem [10], that is, open VRP considering fuel consumption. Meanwhile, several approaches were developed for solving a variant of VRP [11], namely, VRP with time windows. However, the above papers did not analyse the effects of depots on the logistics networks.Among the variants of LRP, the CLRP has recently emerged as one of the most addressed, initiated in Ref. [12], applied in many practical applications, such as, glass recycling [13], food distribution [14], obnoxious waste [15], disaster relief [16], and so on. Several surveys on CLRP are provided in Refs. [17–21]. The above surveys proposed classification schemes in aspects of either structural characteristics or solution approaches and also summarized variants and extensions of CLRP, but summary on the best approaches for solving CLRP was not provided.Considering the tailored solution methods of solving the CLRP, several exact methods have been devoted to solving CLRP, such as, branch-and-cut-and-price [22], branch-and-cut [23, 24], and dynamic programming [25], which are the most effective exact methods in tackling CLRP. However, no one is able to achieve proven optimality to large-scale instances within reasonable CPU time. The most effective heuristics have been suggested to tackle large instances and mentioned hereafter.A two-phase metaheuristic method with TS architecture was proposed by decomposing CLRP into two subproblems [26]. An iterative two-phase approach was applied in Ref. [27]. In their algorithm, clients were clustered into supercustomers, then the Lagrangian relaxation method was used in the location phase, and granular TS (GTS) constraints were suggested to improve the routes in the second phase. A clustering analysis was presented to generate the routes data, and then depot location is solved with the collapsed routes [28]. In the method proposed in Ref. [29], a neural network combining with a self-organizing map and TS was applied to solve single-depot LRP. An iterative heuristic was presented for LRP on the plane by iteratively processing feedback information of two decision problems [30].More recently, a hybridized GRASP was developed [31], and an evolutionary local search (ELS) procedure was used to search within two solution spaces. SA heuristic based on three random neighbourhoods was studied [32]. An adaptive large neighbourhood search heuristic by combining hierarchical structure and several operators was developed [33]. Two-phase hybrid heuristic was presented by constructing two phases: construction phase and improvement phase [34]. The method was developed using a hierarchical ant colony structure in multiple ant colony optimization algorithm [35]. GTS with a variable neighbourhood search algorithm was for solving CLRP [36]. A unique genetic algorithm was proposed for CLRP [37], using local search procedures in the mutation phase without changing the standard GA framework. Besides, the aforementioned exact and heuristic approaches have been applied successfully to CLRP by many researchers, and most require efficient constructive methods for obtaining the initial population.Little attention has been received in developing the CLRPSPD. This subject was first addressed in Ref. [38]. In their paper, an exact algorithm named branch-and-cut method combined SA (BC-SA) was studied. Next year, the same authors developed two types of formulas for CLRPSPD: node- and flow-based formulas [39]. Multistart SA was proposed to incorporate multistart hill climbing strategies into SA framework [40]. Two-echelon CLRPSPD has been addressed to tackle the instances with less than 50 clients [41]. However, no instances with more than 100 clients have been solved to prove optimality by the above four approaches. The SA employing three local neighbourhood search mechanisms was developed to solve few instances with more than 100 clients [4]. The aforementioned methods have devoted to the development of CLRPSPD and achieved significant success in obtaining high solution quality at the expense of significantly high computing times. Our previous work [2] could outperform the above papers in terms of computing times and solution quality by developing a general framework of hyperheuristics using iterated local search procedures.


### 2.2. Hyperheuristic

Conclusion derived from the aforementioned approaches for CLRP and CLRPSPD can be drawn that different search operators are involved in those methods, e.g., hill climbers, mutation heuristics, and crossovers, which may be effective in finding global optima. However, it is hard for them to obtain trade-off between exploration (exploring new solutions) and exploitation (exploiting better solutions) rooting in that no corresponding strategies are suggested to efficiently evaluate and manage those operators at right time, showing poor performance concerning computing times. Moreover, existing search-based approaches are generally domain-dependent, resulting in a hard task for tester without a deep knowledge in domain. The ideal of hyperheuristic was defined as “heuristics to choose heuristics” [5, 42]. Posteriorly, an extensive version was developed as a methodology and classified into two types: heuristic selection and heuristic generation (heuristics to generate heuristics) [43]. This paper focuses on the former based on single-point-search method, and brief description and review is provided hereafter.In the framework of selection HH, two levels are concerned: HLH and LLH. The HLH manipulates the space consisting of a fixed pool of LLHs which directly modify the space of solutions [44]. Two main categories can be considered in HLH: selection strategies and acceptance criteria [45]. The role of heuristic selection mechanism is to intelligently construct effective sequences of heuristics from the pool of LLHs, while acceptance criterion aims at deciding whether to accept or reject new solution after applying the chosen LLH [46]. By analysing the source of feedback information, three modules can be considered: online, offline, and no-learning. Choice function [5, 47], reinforcement learning [48], TS [2, 6, 49–52], and FRR-MAB [2, 53–57] are examples for online selection strategies, and simple random, random descent, RP, etc., are viewed as no-learning methods. Several metaheuristic-based strategies for designing hyperheuristics have been proposed in the literature: ant colony-, particle-, and quantum-inspired hyperheuristic. Characteristics of most evolutionary hyperheuristics in the literature are presented in Table 1, where for each EHH category, application domain, source of publication, main feature, and publishing year are provided. As far as acceptance criterion is concerned, two types are involved: determinate and nondeterminate methods. The former determinately accepts the resultant result, such as all moves, only improving, improving, and equal while NA, SA, GD, and Monte Carlo are instanced as the nondeterminate methods for accepting the new solutions.Table 1
Ant-, particle-, and quantum-based hyperheuristics.
Evolutionary type
Application domain
Publication
Main feature
Ant-based HH
Scheduling
[60]
Population/paired
Project presentation scheduling
[61]
Population/paired
2D bin packing
[62]
Population/paired
Travelling tournament
[63]
Population/paired
P-median
[64]
Population/paired
WDM networks
[65]
Population & single-point/paired
WDM networks
[66]
Population/paired
Dynamic environment
[67]
Single-point/paired
Travelling salesman
[68]
Population/paired
Flow shop scheduling
[69]
Population/single
Particle-based HH
Academic scheduling
[70]
Population/multi-heuristics
Examinations scheduling
[71]
Population/multi-heuristics
Project scheduling
[72]
Population/multi-heuristics
Grid resource scheduling
[73]
Population/single-heuristic
Quantum-based HH
Energy-aware scheduling
[74]
Population/single-heuristicWith the popularity of hyperheuristic, it has been widely applied in practice, such as 2D regular and irregular packing problems [73], nurse rostering [74], vehicle routing problem [54], construction levelling problem [52], software project scheduling problem [56], t-ways test suite generation [6, 75], deriving products for variability test of feature models [55], fast machine reassignment [76], and timetabling [77–81]. We refer interested readers to these papers [43, 82, 83] for extensive review on hyperheuristic.To the best of our knowledge, evolutionary hyperheuristics have not been used thus far to address the basic models of complex logistics network, i.e., CLRP and CLRPSPD.


## 2.1. Location-Routing Problem

In the complex logistics, CLRPSPD is a more practical variant version of CLRP by considering reverse logistics, that is, goods need to be picked up from clients when vehicles deliver goods to clients. Firstly, we review some recent approaches for CLRP, and then recent state of CLRPSPD is investigated.As the main component in CLRP, VRP has been studied for decades. In the last years, several researchers have devoted to the development of VRP. Ant colony algorithm was applied to solve network intensive vehicle service [8]. Multiple population-based genetic algorithm was utilized to solve train-set circulation plan problem [9]. A hybrid tabu search algorithm was developed for a real-world problem [10], that is, open VRP considering fuel consumption. Meanwhile, several approaches were developed for solving a variant of VRP [11], namely, VRP with time windows. However, the above papers did not analyse the effects of depots on the logistics networks.Among the variants of LRP, the CLRP has recently emerged as one of the most addressed, initiated in Ref. [12], applied in many practical applications, such as, glass recycling [13], food distribution [14], obnoxious waste [15], disaster relief [16], and so on. Several surveys on CLRP are provided in Refs. [17–21]. The above surveys proposed classification schemes in aspects of either structural characteristics or solution approaches and also summarized variants and extensions of CLRP, but summary on the best approaches for solving CLRP was not provided.Considering the tailored solution methods of solving the CLRP, several exact methods have been devoted to solving CLRP, such as, branch-and-cut-and-price [22], branch-and-cut [23, 24], and dynamic programming [25], which are the most effective exact methods in tackling CLRP. However, no one is able to achieve proven optimality to large-scale instances within reasonable CPU time. The most effective heuristics have been suggested to tackle large instances and mentioned hereafter.A two-phase metaheuristic method with TS architecture was proposed by decomposing CLRP into two subproblems [26]. An iterative two-phase approach was applied in Ref. [27]. In their algorithm, clients were clustered into supercustomers, then the Lagrangian relaxation method was used in the location phase, and granular TS (GTS) constraints were suggested to improve the routes in the second phase. A clustering analysis was presented to generate the routes data, and then depot location is solved with the collapsed routes [28]. In the method proposed in Ref. [29], a neural network combining with a self-organizing map and TS was applied to solve single-depot LRP. An iterative heuristic was presented for LRP on the plane by iteratively processing feedback information of two decision problems [30].More recently, a hybridized GRASP was developed [31], and an evolutionary local search (ELS) procedure was used to search within two solution spaces. SA heuristic based on three random neighbourhoods was studied [32]. An adaptive large neighbourhood search heuristic by combining hierarchical structure and several operators was developed [33]. Two-phase hybrid heuristic was presented by constructing two phases: construction phase and improvement phase [34]. The method was developed using a hierarchical ant colony structure in multiple ant colony optimization algorithm [35]. GTS with a variable neighbourhood search algorithm was for solving CLRP [36]. A unique genetic algorithm was proposed for CLRP [37], using local search procedures in the mutation phase without changing the standard GA framework. Besides, the aforementioned exact and heuristic approaches have been applied successfully to CLRP by many researchers, and most require efficient constructive methods for obtaining the initial population.Little attention has been received in developing the CLRPSPD. This subject was first addressed in Ref. [38]. In their paper, an exact algorithm named branch-and-cut method combined SA (BC-SA) was studied. Next year, the same authors developed two types of formulas for CLRPSPD: node- and flow-based formulas [39]. Multistart SA was proposed to incorporate multistart hill climbing strategies into SA framework [40]. Two-echelon CLRPSPD has been addressed to tackle the instances with less than 50 clients [41]. However, no instances with more than 100 clients have been solved to prove optimality by the above four approaches. The SA employing three local neighbourhood search mechanisms was developed to solve few instances with more than 100 clients [4]. The aforementioned methods have devoted to the development of CLRPSPD and achieved significant success in obtaining high solution quality at the expense of significantly high computing times. Our previous work [2] could outperform the above papers in terms of computing times and solution quality by developing a general framework of hyperheuristics using iterated local search procedures.


## 2.2. Hyperheuristic

Conclusion derived from the aforementioned approaches for CLRP and CLRPSPD can be drawn that different search operators are involved in those methods, e.g., hill climbers, mutation heuristics, and crossovers, which may be effective in finding global optima. However, it is hard for them to obtain trade-off between exploration (exploring new solutions) and exploitation (exploiting better solutions) rooting in that no corresponding strategies are suggested to efficiently evaluate and manage those operators at right time, showing poor performance concerning computing times. Moreover, existing search-based approaches are generally domain-dependent, resulting in a hard task for tester without a deep knowledge in domain. The ideal of hyperheuristic was defined as “heuristics to choose heuristics” [5, 42]. Posteriorly, an extensive version was developed as a methodology and classified into two types: heuristic selection and heuristic generation (heuristics to generate heuristics) [43]. This paper focuses on the former based on single-point-search method, and brief description and review is provided hereafter.In the framework of selection HH, two levels are concerned: HLH and LLH. The HLH manipulates the space consisting of a fixed pool of LLHs which directly modify the space of solutions [44]. Two main categories can be considered in HLH: selection strategies and acceptance criteria [45]. The role of heuristic selection mechanism is to intelligently construct effective sequences of heuristics from the pool of LLHs, while acceptance criterion aims at deciding whether to accept or reject new solution after applying the chosen LLH [46]. By analysing the source of feedback information, three modules can be considered: online, offline, and no-learning. Choice function [5, 47], reinforcement learning [48], TS [2, 6, 49–52], and FRR-MAB [2, 53–57] are examples for online selection strategies, and simple random, random descent, RP, etc., are viewed as no-learning methods. Several metaheuristic-based strategies for designing hyperheuristics have been proposed in the literature: ant colony-, particle-, and quantum-inspired hyperheuristic. Characteristics of most evolutionary hyperheuristics in the literature are presented in Table 1, where for each EHH category, application domain, source of publication, main feature, and publishing year are provided. As far as acceptance criterion is concerned, two types are involved: determinate and nondeterminate methods. The former determinately accepts the resultant result, such as all moves, only improving, improving, and equal while NA, SA, GD, and Monte Carlo are instanced as the nondeterminate methods for accepting the new solutions.Table 1
Ant-, particle-, and quantum-based hyperheuristics.
Evolutionary type
Application domain
Publication
Main feature
Ant-based HH
Scheduling
[60]
Population/paired
Project presentation scheduling
[61]
Population/paired
2D bin packing
[62]
Population/paired
Travelling tournament
[63]
Population/paired
P-median
[64]
Population/paired
WDM networks
[65]
Population & single-point/paired
WDM networks
[66]
Population/paired
Dynamic environment
[67]
Single-point/paired
Travelling salesman
[68]
Population/paired
Flow shop scheduling
[69]
Population/single
Particle-based HH
Academic scheduling
[70]
Population/multi-heuristics
Examinations scheduling
[71]
Population/multi-heuristics
Project scheduling
[72]
Population/multi-heuristics
Grid resource scheduling
[73]
Population/single-heuristic
Quantum-based HH
Energy-aware scheduling
[74]
Population/single-heuristicWith the popularity of hyperheuristic, it has been widely applied in practice, such as 2D regular and irregular packing problems [73], nurse rostering [74], vehicle routing problem [54], construction levelling problem [52], software project scheduling problem [56], t-ways test suite generation [6, 75], deriving products for variability test of feature models [55], fast machine reassignment [76], and timetabling [77–81]. We refer interested readers to these papers [43, 82, 83] for extensive review on hyperheuristic.To the best of our knowledge, evolutionary hyperheuristics have not been used thus far to address the basic models of complex logistics network, i.e., CLRP and CLRPSPD.


## 3. Mathematical Formulation

CLRPSPD is a more practical variant of CLRP considering the reverse logistics in which the pickup and delivery take place at the same time for each client [4]. The CLRPSPD and CLRP are defined on a complete directed graph G = (V, E), where V = J∪I is a set of nodes in which J and I represent the potential depot and client nodes, respectively, and E = {(i, j): i, j ∈ V, i ≠ j}\{(i, j): i, j ∈ J} is the set of arcs. Each arc (i, j) ∈ E has a nonnegative distance cij. Each client i ∈ I has a positive delivery demand qi and pickup demand pi (only for the CLRPSPD). A storage capacity wj and a fixed opening cost fj are associated with each potential depot j ∈ J. The index set of vehicle types is denoted by K consisting of homogeneous vehicles with capacity Q. The objective is to determine the optimal plan of the set of depots and routes to minimize the total costs consisting of opened depot, vehicle, and travel costs.Two types of MIP formulations for CLRPSPD are defined in Refs. [38, 39]: node- and flow-based formulations, whose distinction depends on the definition of additional variables in the graph: nodes or arcs, and similarity of the above two is built on two-index concept. In this paper, three-index flow-based MIP formulation is defined for CLRPSPD. Before describing this formulation, some assumptions should be considered:(i)
Each route is served by one vehicle, and each client is served only once.(ii)
Each vehicle must return to the departure depot at the end of the route.(iii)
Goods of each client are delivered and picked up at the same location, and the goods are delivered to each client before being picked up.(iv)
The total vehicle load at any arc must not exceed the vehicle capacity.(v)
The total delivery and pickup demands of clients served by each depot cannot exceed the depot capacity.Decision variables:xijk=1,if arci,jis operated by vehiclek0,otherwisezij=1,if clientiis served by depotj0,otherwiseyi=1,if depotiis selected to operate0,otherwiseAdditional variables:Uijk: the dynamic load of each arc (i, j) operated by vehicle k.Based on the aforementioned assumptions and notations, the proposed flow-based formulation [2] is as follows:(1)minFitness=∑j∈Jfjyj+∑i∈J∑j∈I∑k∈Kfkxijk+∑i∈V∑j∈V∑k∈Kcijxijk,subject to(2)∑i∈V∑k∈Kxijk=1,∀j∈I,(3)∑i∈J∑j∈Jxijk=0,∀k∈K,(4)∑i∈Vxijk=∑i∈Vxjik,∀j∈V,∀k∈K,(5)∑i∈J∑j∈Ixijk≤1,∀k∈K,(6)∑i∈S∑j∈Sxijk≤S−1,∀k∈K,(7)∑j∈Jzij=1,∀i∈I,(8)∑j∈Ixijk+∑j∈Ixjgk≤1,∀i,g∈J,∀k∈K,i≠g,(9)∑i∈Izij≥yj,∀j∈J,(10)zij≤yj,∀i∈I,∀j∈J,(11)∑j∈I∑k∈Kxijk≥yi,∀i∈J,(12)∑j∈Ixijk≤yi,∀i∈J,∀k∈K,(13)xijk+zig+∑m∈J,g≠mzjm≤2,∀i,j∈I,∀k∈K,∀g∈J,(14)max∑i∈Izij×qi,∑i∈Izij×pi≤wj×yj,∀j∈J,(15)∑i∈J∑j∈IUijk=∑i∈V∑j∈Ixijk×qj,∀k∈K,(16)∑i∈I∑j∈JUijk=∑i∈V∑j∈Jxijk×pj,∀k∈K,(17)∑k∈K∑i∈VUijk−qj=∑k∈K∑i∈VUjik−pj,∀j∈I,(18)0≤Uijk≤Q×xijk,∀i,j∈V,∀k∈K.In this three-index flow-based MIP formulation, objective function (1) represents the fitness value Fitness consisting of the total costs composed of fixed lease cost of depots and vehicles and travelling cost of edges; constraint (2) guarantees that each client is served only once; constraint (3) eliminates routes between depots; constraint (4) ensures that entering and leaving edge to each node is equal; constraint (5) requires that only one route is assigned to one vehicle and the vehicle only departs from one depot; subcircuits in each route are forbidden by constraint (6); constraint (7) eliminates the situation that one client is served by plural different depots; constraint (8) specifies that plural different depots must not exist in the same route; constraints (9) and (10) enforce that clients are assigned to the selected depots and each depot to open must serve at least one client; each vehicle is assigned to the chosen depots and each selected depot must have at least one vehicle, which is ensured by constraints (11) and (12); constraint (13) ensures two consecutive clients of each route are served by the same depot; constraint (14) forbids that total delivery and pickup demands of clients must not exceed the depot’s capacity; constraint (15) guarantees that the total delivery demands of all clients served by each depot should equal to depot’s total delivery load; constraint (16) requires that the total pickup demands of all clients served by each depot should equal to depot’s total pickup load; equation (17) expresses the proper movement of load delivery and/or pickup; constraint (18) makes sure that the total load of each arc of vehicles must not exceed vehicle’s capacity.


## 4. Proposed Approach

In the following sections, we introduce HH by describing the adopted solution representation, effective constructive heuristic, low-level heuristics for domains, nine selection strategies, and four acceptance criteria for high-level heuristic.


### 4.1. Solution Representation

The solution representation plays an important role in improving the performance of an algorithm for the CLRPSPD, which should include all routes and the chosen depot of each route. Therefore, a string of cells are used to represent a complete solution which determines the assigned clients to each vehicle, the depots to be selected, and the sequence of clients to be visited by a specific vehicle starting and ending at the same depot. The solution representation in this paper applies a simple and efficient encoding [2], which is a complete set of vehicle routes, that is, R = {r1, r2, …, rK} with inserting the chosen depot at two ends of each route. Meanwhile, we also store the attributes of each route in the second subcell of each route. It is worth noting that our chromosome representation can meet the constraints (2)–(18) for avoiding restoring the feasibility of solutions and allowing fast evaluation of its fitness value without the need for decoding.


### 4.2. Initial Solution

The initialization method is an improved greedy heuristic (inspired from the approach in Ref. [4]), named here as regret-k greedy heuristic (RKGH), proposed by our previous work [2]. After implementing greedy heuristic [4], configuration of depots (m ≥ 2) has been determined. Let xik  ∈ {1, 2, …, m} be a variable that indicates the depot for client i that has the kth lowest cost, that is,c(i, xik) ≤ c(i, xik′). Using this notation, we can define a regret-k value Δck(i) as Δck(i) = c(i, xik) − c(i, xi1). In other words, the regret-k value is the difference in the cost for client placed in the first best depot and its kth best depot. The RKGH chooses to assign the client i that maximizes(19)maxα×∑j∈kΔcji.The multiplierα depends the remaining capacity of each depot, α = 1 representing that client i is served by this depot without violating the capacitated constraints; otherwise, α is set to 0. In this paper, the value of k is also set to 2, namely, R2GH is applied.


### 4.3. Hyperlevel Heuristics

In this paper, we use different pairings of operators’ vector and acceptance criterion. There are 36 possible pairings of nine operators’ vectors and four acceptance criteria. Several strategies are involved: RP, TS, FRR-MAB, QS, AS, and PS, and three variants are also developed. The strategies implementing QS, PS, AS, and their variants can be categorised as ES. Four acceptance criteria are provided in this paper: AM, NA, GD, and SA. The brief descriptions are presented in the following sections.


#### 4.3.1. Operator Selection Vector Design

Operator selection strategies in the literature generally assign a probability to each operator and use a roulette wheel or tournament-like process to select the LLHs according to them [54], named as operator selection vector. The selection vector consists of an array of operators, each with a probability of selection. In this paper, selection vector is designed by assigning a probability to each LLH, and the initial selection vector of LLHs has an equal probability of selection.(1)
RP: the initial vector is not changed during the run, and all LLHs have an equal selection probability regardless of performance, also called as fixed selector [84], so the random one is chosen as a baseline for comparison with others.(2)
TS: tabu list is used to prohibit LLHs with recently poor performance from being applied too soon. The LLHs belonging to be tabu (i.e., the selection probability is 0) are released (i.e., the selection probability is initial value) whenever other LLHs make a change in objective function, which is slightly different from the aspiration criterion [51].(3)
FRR-MAB [7]: FRR-MAB was proposed to adaptively select appropriate LLH based on its recent performance storing in slide windows implementing FIFO mechanism. Two successive stages are discussed: credit assignment and selection mechanism. The former offers the method to measure the impact on the quality in search process caused by the application of recent LLHs, while the latter selects one LLH with maximizing received credit values for generating new solution. For applying selection vector, the reward value of each LLH is normalized as selection probability. The other version based on FRR-MAB is combined with TS (viewed as FMT) proposed by our previous work [2], absorbing the rapid response capability of TS to exclude LLHs with poor performance.(4)
QS: a heuristics search space withξ LLHs in QS is defined as(20)H=h1,h2,L,hξ=β1β2Lβξα1α2Lαξ,wherehi = βiαi represents hiQ-bit and |βi|2 and |αi|2 give the probability that hi selects and disuses state, respectively, and guarantee |αi|2 + |βi|2 = 1. A learning strategy based on Q-gate is utilized to update selection probability |βi|2 of hi based on real-time performance.(21)αit+1βit+1=cosθit−sinθitsinθitcosθit×αitβit,(22)Δθt=Δθ0×1−kttmax,(23)θit=fπt−fπbestt×αit×βit×xit−bxitfπt−fπbestt×αit×βit×Δθt,whereαitβit is the Q-bit of hi during tth iteration and θit is the rotation angle of each Q-bit; Δθt is rotation angle in tth iteration; k is uniformly distributed within 01; tmax is the maximum iteration; πt and πbestt are, respectively, sequence of current selected LLHs and selected LLHs in obtaining the best solution; xit and bxit are the state of hi of current and global sequence of selected LLHs; πt = 4671 represents the current sequence of LLHs; and xt can be illustrated asxt = 1001011 if ξ = 7. The other version based on QS is combined with TS (named as QS2), absorbing the rapid response capability of TS to exclude LLHs with poor performance.(5)
AS: inspired from application of ant colony optimization (ACO) in travelling salesman problem (TSP) and 0/1 knapsack problem, two versions of AS are developed into adaptively making decisions on selecting favourable sequence of LLHs. The first variant (paired-AS, AS2) highlights the joint performance of pairs of LLHs by determining next LLH (one at a time) based on probabilities proportional to the pheromone levels of each heuristic pair shown in equation (24); in this version, pheromone laying criterion [59] is modified for laying the pheromone for pairs which reach an improvement to the previous function, that is, if an ant performs heuristics hx, hy, and hz and hy leads to a nonimproving solution and hz provides a better solution, pheromone will be laid on edge x-z and neither x-y nor y-z, while the latter (single-AS, AS) emphasizes individual performance of each LLH by viewing the performance information of individual LLH as its pheromone trail [67]. Possible sequence of LLHs is selected by normalizing pheromone trail as selection probabilities.(24)pijt+1=τijt+1∑j∈ξ,j≠iτijt+1,(25)τijt+1=ρ⋅τijt+FIRjηij,if antkselectsi,j,ρ⋅τijt,otherwise,whereτijt (ξ × ξ) and pijt (ξ × ξ) define, respectively, the pheromone trail and selection probability of i-j edge in tth iteration; 0 < ρ ≤ 1 represents the evaporation rate for pheromone; FIRj is fitness improvement rate compared to previous solutions [7, 55]; and ηij (ξ × ξ) is the visibility information illustrating heuristic information. The above equation (25) is used to update pheromone trail with ηij = Ti + Tj (Ti indicates the running time of hi), while equation (25) can be modified for AS with ηj = Tj by ignoring the previous hi.(6)
PS: PS has been nominated as HLH strategies to measure effectiveness of their order placement and selection mechanism. Each particle is a vector ofξ numbers representing the selection probabilities of LLHs obtained by normalizing the position (using the original formulations) of this particle. The particles impose the order that the LLHs are applied to solution domain. Each particle is evaluated using performance indicator FIR.(26)pit=Xit∑i∈ξXit.Among the last seven selection strategies, probabilities of selecting LLHs are utilized to order LLHs, with the maximum utility score/weight being placed in the front of the list. The chosen LLHs are then applied in sequence following this order. However, the sequence of selected LLHs are randomly permutated to modify the current solution for RP and TS.


#### 4.3.2. Acceptance Criteria Design

After recent application of the LLHs, the obtained solution is considered for accepting as incumbent solution into next iteration. If the new solution is at least as good as the previous solution it will replace, and then it is automatically accepted as current solution regardless of the nature of an acceptance mechanism; otherwise, acceptance criterion is utilized to whether discard the new solution or not [65, 84]. The following four acceptance criteria are proposed to pair up with the above selection strategies, aiming at pointing out which pairs perform better than others.(1)
AM [5]: the current result is replaced by all new results with probability value at 1.(2)
NA [84]: the current result is replaced by no-improving results with probability value at 0.5.(3)
GD [50, 84]: a no-improving result is accepted if it is better than a dynamically changing threshold value which depends on the current and historical fitness information. For determining the range of accepting a child solution, a threshold value is applied, which decreases with the increase in iteration.(27)Sthresholdt=1+0.5×1−ttmax×Gbestt,wheret and tmax indicate the current steps and the maximum iteration and Gbest (t) represents the global best solution objective value found so far.(4)
SA [65]: new solutions are accepted as the current solutions if the probability criterion is met, that is, improving results are accepted with probability value at 1 while no-improving results are accepted if a uniform value within [0, 1] is less the critical value. The probability of accepting a no-improving solution in SA is calculated for making a decision on whether accepting it or not [65]:(28)pt=e−Δf/ΔFt1−t/tmax,where Δf is the difference in the quality between the new solution and current solution and ΔFt represents the expected range for maximum solution quality change, ΔFt = Gbest (t) − Gbest (0).


### 4.4. Low-Level Heuristics

The pool of LLHs can be viewed as a “black box” which are used to perturb the incumbent solution by either intensifying or diversifying the search in the search region, which is used in Ref. [2]. They normally are a set of simple, cheap, and knowledge-poor LLHs [5]. The module of this paper is composed of 13 LLHs h1, h2, …, h13 across two pools of heuristics: mutational heuristic (MH) and local search/hill climber (HC), which are identified by the role in improving or worsening the solution. The first six LLHs are implemented to explore new region: 2-opt, or-opt, shift, interchange, add, and Shaw. Others are utilized to exploit better solutions: relocation, 2-opt, 3-opt, relocate, and 1-interchange algorithm, which apply intra and inter-route moves.The detailed information ofh1∼h4 can be obtained from Ref. [54], which are simple and basic mutational heuristics. The h5 heuristic diversifies the open depots by opening a new one and randomly assigning between 1 and 2/3 of the routes to it [37]. As to the last diversified LLH h6 [85], it is a method named as destroy-and-repair operator proposed to remove related clients, i.e., clients that are geographically close to each other and reinserted into best positions. In our paper, basic greedy heuristic [86] is suggested to reinsert removal clients back into routes. The disturbed solutions are accepted as long as the above acceptance criteria and the vehicle capacity at each arc and depots capacity are obeyed.The relocationh7 is developed to reselect the appropriate depots for determined routes. Each route is collapsed into a cluster and the smallest insertion costs can be calculated as the distance of the depots in the original routes. The depots with the larger number of clusters take priority to open. And then other unassigned clusters (from large to small order) sharing same closest depot will be arranged to its closest depot, unless the assigned depots’ capacity and cost are not satisfied. The 2-opt [87] inside the routes is equivalent to the well-known 2-opt move (h8) [88], whereas the other version of 2-opt implemented between different routes is identified (h9). Due to reduced CPU time, the intral-3-opt (h10) [89] is only considered. The relocate heuristic [90] reinserts a single client in another position inside the incumbent route (h11) or in another route (h12). The 1-interchange [91] heuristic swaps each position of client from one route with each client in another route if not sharing the same depot (h13). If improvements are found and depot capacity and vehicle load at each arc are met, the above moves are implemented, allowing them to improve incumbent solutions.The MHs often perform simple random moves to perturb the incumbent solution without guaranteeing competitive results. Although insufficient for achieving competitive results, they are useful for providing randomization and helpful for navigating out of local optima. However, HCs play a key role in quickly obtaining much better solutions at each step. Moreover, it might be desirable to apply HCs after application of any MH and to apply MHs if it is hard for HCs to provide promising solutions. Considering the above features, the proposed nine selection strategies are utilized to adaptively manage the HCs, inspired from the mechanism on management of local search heuristics [5, 54] and the method for automatically classifying according to the performance proposed in Ref. [57]. The probability for selecting any one MH as guider for getting rid of local optimality is set to 1 if and only if no HC can provide an improvement to previous objective value; otherwise, the probability value is set to 0. Hence, Figure 1 is the framework of hyperheuristics applied in this paper.Figure 1
Framework of hyperheuristic approach.Moreover, a stopping mechanism is defined by evaluation limits with maximum number of fitness evaluation (αmax), aiming at providing fair comparison.


## 4.1. Solution Representation

The solution representation plays an important role in improving the performance of an algorithm for the CLRPSPD, which should include all routes and the chosen depot of each route. Therefore, a string of cells are used to represent a complete solution which determines the assigned clients to each vehicle, the depots to be selected, and the sequence of clients to be visited by a specific vehicle starting and ending at the same depot. The solution representation in this paper applies a simple and efficient encoding [2], which is a complete set of vehicle routes, that is, R = {r1, r2, …, rK} with inserting the chosen depot at two ends of each route. Meanwhile, we also store the attributes of each route in the second subcell of each route. It is worth noting that our chromosome representation can meet the constraints (2)–(18) for avoiding restoring the feasibility of solutions and allowing fast evaluation of its fitness value without the need for decoding.


## 4.2. Initial Solution

The initialization method is an improved greedy heuristic (inspired from the approach in Ref. [4]), named here as regret-k greedy heuristic (RKGH), proposed by our previous work [2]. After implementing greedy heuristic [4], configuration of depots (m ≥ 2) has been determined. Let xik  ∈ {1, 2, …, m} be a variable that indicates the depot for client i that has the kth lowest cost, that is,c(i, xik) ≤ c(i, xik′). Using this notation, we can define a regret-k value Δck(i) as Δck(i) = c(i, xik) − c(i, xi1). In other words, the regret-k value is the difference in the cost for client placed in the first best depot and its kth best depot. The RKGH chooses to assign the client i that maximizes(19)maxα×∑j∈kΔcji.The multiplierα depends the remaining capacity of each depot, α = 1 representing that client i is served by this depot without violating the capacitated constraints; otherwise, α is set to 0. In this paper, the value of k is also set to 2, namely, R2GH is applied.


## 4.3. Hyperlevel Heuristics

In this paper, we use different pairings of operators’ vector and acceptance criterion. There are 36 possible pairings of nine operators’ vectors and four acceptance criteria. Several strategies are involved: RP, TS, FRR-MAB, QS, AS, and PS, and three variants are also developed. The strategies implementing QS, PS, AS, and their variants can be categorised as ES. Four acceptance criteria are provided in this paper: AM, NA, GD, and SA. The brief descriptions are presented in the following sections.


### 4.3.1. Operator Selection Vector Design

Operator selection strategies in the literature generally assign a probability to each operator and use a roulette wheel or tournament-like process to select the LLHs according to them [54], named as operator selection vector. The selection vector consists of an array of operators, each with a probability of selection. In this paper, selection vector is designed by assigning a probability to each LLH, and the initial selection vector of LLHs has an equal probability of selection.(1)
RP: the initial vector is not changed during the run, and all LLHs have an equal selection probability regardless of performance, also called as fixed selector [84], so the random one is chosen as a baseline for comparison with others.(2)
TS: tabu list is used to prohibit LLHs with recently poor performance from being applied too soon. The LLHs belonging to be tabu (i.e., the selection probability is 0) are released (i.e., the selection probability is initial value) whenever other LLHs make a change in objective function, which is slightly different from the aspiration criterion [51].(3)
FRR-MAB [7]: FRR-MAB was proposed to adaptively select appropriate LLH based on its recent performance storing in slide windows implementing FIFO mechanism. Two successive stages are discussed: credit assignment and selection mechanism. The former offers the method to measure the impact on the quality in search process caused by the application of recent LLHs, while the latter selects one LLH with maximizing received credit values for generating new solution. For applying selection vector, the reward value of each LLH is normalized as selection probability. The other version based on FRR-MAB is combined with TS (viewed as FMT) proposed by our previous work [2], absorbing the rapid response capability of TS to exclude LLHs with poor performance.(4)
QS: a heuristics search space withξ LLHs in QS is defined as(20)H=h1,h2,L,hξ=β1β2Lβξα1α2Lαξ,wherehi = βiαi represents hiQ-bit and |βi|2 and |αi|2 give the probability that hi selects and disuses state, respectively, and guarantee |αi|2 + |βi|2 = 1. A learning strategy based on Q-gate is utilized to update selection probability |βi|2 of hi based on real-time performance.(21)αit+1βit+1=cosθit−sinθitsinθitcosθit×αitβit,(22)Δθt=Δθ0×1−kttmax,(23)θit=fπt−fπbestt×αit×βit×xit−bxitfπt−fπbestt×αit×βit×Δθt,whereαitβit is the Q-bit of hi during tth iteration and θit is the rotation angle of each Q-bit; Δθt is rotation angle in tth iteration; k is uniformly distributed within 01; tmax is the maximum iteration; πt and πbestt are, respectively, sequence of current selected LLHs and selected LLHs in obtaining the best solution; xit and bxit are the state of hi of current and global sequence of selected LLHs; πt = 4671 represents the current sequence of LLHs; and xt can be illustrated asxt = 1001011 if ξ = 7. The other version based on QS is combined with TS (named as QS2), absorbing the rapid response capability of TS to exclude LLHs with poor performance.(5)
AS: inspired from application of ant colony optimization (ACO) in travelling salesman problem (TSP) and 0/1 knapsack problem, two versions of AS are developed into adaptively making decisions on selecting favourable sequence of LLHs. The first variant (paired-AS, AS2) highlights the joint performance of pairs of LLHs by determining next LLH (one at a time) based on probabilities proportional to the pheromone levels of each heuristic pair shown in equation (24); in this version, pheromone laying criterion [59] is modified for laying the pheromone for pairs which reach an improvement to the previous function, that is, if an ant performs heuristics hx, hy, and hz and hy leads to a nonimproving solution and hz provides a better solution, pheromone will be laid on edge x-z and neither x-y nor y-z, while the latter (single-AS, AS) emphasizes individual performance of each LLH by viewing the performance information of individual LLH as its pheromone trail [67]. Possible sequence of LLHs is selected by normalizing pheromone trail as selection probabilities.(24)pijt+1=τijt+1∑j∈ξ,j≠iτijt+1,(25)τijt+1=ρ⋅τijt+FIRjηij,if antkselectsi,j,ρ⋅τijt,otherwise,whereτijt (ξ × ξ) and pijt (ξ × ξ) define, respectively, the pheromone trail and selection probability of i-j edge in tth iteration; 0 < ρ ≤ 1 represents the evaporation rate for pheromone; FIRj is fitness improvement rate compared to previous solutions [7, 55]; and ηij (ξ × ξ) is the visibility information illustrating heuristic information. The above equation (25) is used to update pheromone trail with ηij = Ti + Tj (Ti indicates the running time of hi), while equation (25) can be modified for AS with ηj = Tj by ignoring the previous hi.(6)
PS: PS has been nominated as HLH strategies to measure effectiveness of their order placement and selection mechanism. Each particle is a vector ofξ numbers representing the selection probabilities of LLHs obtained by normalizing the position (using the original formulations) of this particle. The particles impose the order that the LLHs are applied to solution domain. Each particle is evaluated using performance indicator FIR.(26)pit=Xit∑i∈ξXit.Among the last seven selection strategies, probabilities of selecting LLHs are utilized to order LLHs, with the maximum utility score/weight being placed in the front of the list. The chosen LLHs are then applied in sequence following this order. However, the sequence of selected LLHs are randomly permutated to modify the current solution for RP and TS.


### 4.3.2. Acceptance Criteria Design

After recent application of the LLHs, the obtained solution is considered for accepting as incumbent solution into next iteration. If the new solution is at least as good as the previous solution it will replace, and then it is automatically accepted as current solution regardless of the nature of an acceptance mechanism; otherwise, acceptance criterion is utilized to whether discard the new solution or not [65, 84]. The following four acceptance criteria are proposed to pair up with the above selection strategies, aiming at pointing out which pairs perform better than others.(1)
AM [5]: the current result is replaced by all new results with probability value at 1.(2)
NA [84]: the current result is replaced by no-improving results with probability value at 0.5.(3)
GD [50, 84]: a no-improving result is accepted if it is better than a dynamically changing threshold value which depends on the current and historical fitness information. For determining the range of accepting a child solution, a threshold value is applied, which decreases with the increase in iteration.(27)Sthresholdt=1+0.5×1−ttmax×Gbestt,wheret and tmax indicate the current steps and the maximum iteration and Gbest (t) represents the global best solution objective value found so far.(4)
SA [65]: new solutions are accepted as the current solutions if the probability criterion is met, that is, improving results are accepted with probability value at 1 while no-improving results are accepted if a uniform value within [0, 1] is less the critical value. The probability of accepting a no-improving solution in SA is calculated for making a decision on whether accepting it or not [65]:(28)pt=e−Δf/ΔFt1−t/tmax,where Δf is the difference in the quality between the new solution and current solution and ΔFt represents the expected range for maximum solution quality change, ΔFt = Gbest (t) − Gbest (0).


## 4.3.1. Operator Selection Vector Design

Operator selection strategies in the literature generally assign a probability to each operator and use a roulette wheel or tournament-like process to select the LLHs according to them [54], named as operator selection vector. The selection vector consists of an array of operators, each with a probability of selection. In this paper, selection vector is designed by assigning a probability to each LLH, and the initial selection vector of LLHs has an equal probability of selection.(1)
RP: the initial vector is not changed during the run, and all LLHs have an equal selection probability regardless of performance, also called as fixed selector [84], so the random one is chosen as a baseline for comparison with others.(2)
TS: tabu list is used to prohibit LLHs with recently poor performance from being applied too soon. The LLHs belonging to be tabu (i.e., the selection probability is 0) are released (i.e., the selection probability is initial value) whenever other LLHs make a change in objective function, which is slightly different from the aspiration criterion [51].(3)
FRR-MAB [7]: FRR-MAB was proposed to adaptively select appropriate LLH based on its recent performance storing in slide windows implementing FIFO mechanism. Two successive stages are discussed: credit assignment and selection mechanism. The former offers the method to measure the impact on the quality in search process caused by the application of recent LLHs, while the latter selects one LLH with maximizing received credit values for generating new solution. For applying selection vector, the reward value of each LLH is normalized as selection probability. The other version based on FRR-MAB is combined with TS (viewed as FMT) proposed by our previous work [2], absorbing the rapid response capability of TS to exclude LLHs with poor performance.(4)
QS: a heuristics search space withξ LLHs in QS is defined as(20)H=h1,h2,L,hξ=β1β2Lβξα1α2Lαξ,wherehi = βiαi represents hiQ-bit and |βi|2 and |αi|2 give the probability that hi selects and disuses state, respectively, and guarantee |αi|2 + |βi|2 = 1. A learning strategy based on Q-gate is utilized to update selection probability |βi|2 of hi based on real-time performance.(21)αit+1βit+1=cosθit−sinθitsinθitcosθit×αitβit,(22)Δθt=Δθ0×1−kttmax,(23)θit=fπt−fπbestt×αit×βit×xit−bxitfπt−fπbestt×αit×βit×Δθt,whereαitβit is the Q-bit of hi during tth iteration and θit is the rotation angle of each Q-bit; Δθt is rotation angle in tth iteration; k is uniformly distributed within 01; tmax is the maximum iteration; πt and πbestt are, respectively, sequence of current selected LLHs and selected LLHs in obtaining the best solution; xit and bxit are the state of hi of current and global sequence of selected LLHs; πt = 4671 represents the current sequence of LLHs; and xt can be illustrated asxt = 1001011 if ξ = 7. The other version based on QS is combined with TS (named as QS2), absorbing the rapid response capability of TS to exclude LLHs with poor performance.(5)
AS: inspired from application of ant colony optimization (ACO) in travelling salesman problem (TSP) and 0/1 knapsack problem, two versions of AS are developed into adaptively making decisions on selecting favourable sequence of LLHs. The first variant (paired-AS, AS2) highlights the joint performance of pairs of LLHs by determining next LLH (one at a time) based on probabilities proportional to the pheromone levels of each heuristic pair shown in equation (24); in this version, pheromone laying criterion [59] is modified for laying the pheromone for pairs which reach an improvement to the previous function, that is, if an ant performs heuristics hx, hy, and hz and hy leads to a nonimproving solution and hz provides a better solution, pheromone will be laid on edge x-z and neither x-y nor y-z, while the latter (single-AS, AS) emphasizes individual performance of each LLH by viewing the performance information of individual LLH as its pheromone trail [67]. Possible sequence of LLHs is selected by normalizing pheromone trail as selection probabilities.(24)pijt+1=τijt+1∑j∈ξ,j≠iτijt+1,(25)τijt+1=ρ⋅τijt+FIRjηij,if antkselectsi,j,ρ⋅τijt,otherwise,whereτijt (ξ × ξ) and pijt (ξ × ξ) define, respectively, the pheromone trail and selection probability of i-j edge in tth iteration; 0 < ρ ≤ 1 represents the evaporation rate for pheromone; FIRj is fitness improvement rate compared to previous solutions [7, 55]; and ηij (ξ × ξ) is the visibility information illustrating heuristic information. The above equation (25) is used to update pheromone trail with ηij = Ti + Tj (Ti indicates the running time of hi), while equation (25) can be modified for AS with ηj = Tj by ignoring the previous hi.(6)
PS: PS has been nominated as HLH strategies to measure effectiveness of their order placement and selection mechanism. Each particle is a vector ofξ numbers representing the selection probabilities of LLHs obtained by normalizing the position (using the original formulations) of this particle. The particles impose the order that the LLHs are applied to solution domain. Each particle is evaluated using performance indicator FIR.(26)pit=Xit∑i∈ξXit.Among the last seven selection strategies, probabilities of selecting LLHs are utilized to order LLHs, with the maximum utility score/weight being placed in the front of the list. The chosen LLHs are then applied in sequence following this order. However, the sequence of selected LLHs are randomly permutated to modify the current solution for RP and TS.


## 4.3.2. Acceptance Criteria Design

After recent application of the LLHs, the obtained solution is considered for accepting as incumbent solution into next iteration. If the new solution is at least as good as the previous solution it will replace, and then it is automatically accepted as current solution regardless of the nature of an acceptance mechanism; otherwise, acceptance criterion is utilized to whether discard the new solution or not [65, 84]. The following four acceptance criteria are proposed to pair up with the above selection strategies, aiming at pointing out which pairs perform better than others.(1)
AM [5]: the current result is replaced by all new results with probability value at 1.(2)
NA [84]: the current result is replaced by no-improving results with probability value at 0.5.(3)
GD [50, 84]: a no-improving result is accepted if it is better than a dynamically changing threshold value which depends on the current and historical fitness information. For determining the range of accepting a child solution, a threshold value is applied, which decreases with the increase in iteration.(27)Sthresholdt=1+0.5×1−ttmax×Gbestt,wheret and tmax indicate the current steps and the maximum iteration and Gbest (t) represents the global best solution objective value found so far.(4)
SA [65]: new solutions are accepted as the current solutions if the probability criterion is met, that is, improving results are accepted with probability value at 1 while no-improving results are accepted if a uniform value within [0, 1] is less the critical value. The probability of accepting a no-improving solution in SA is calculated for making a decision on whether accepting it or not [65]:(28)pt=e−Δf/ΔFt1−t/tmax,where Δf is the difference in the quality between the new solution and current solution and ΔFt represents the expected range for maximum solution quality change, ΔFt = Gbest (t) − Gbest (0).


## 4.4. Low-Level Heuristics

The pool of LLHs can be viewed as a “black box” which are used to perturb the incumbent solution by either intensifying or diversifying the search in the search region, which is used in Ref. [2]. They normally are a set of simple, cheap, and knowledge-poor LLHs [5]. The module of this paper is composed of 13 LLHs h1, h2, …, h13 across two pools of heuristics: mutational heuristic (MH) and local search/hill climber (HC), which are identified by the role in improving or worsening the solution. The first six LLHs are implemented to explore new region: 2-opt, or-opt, shift, interchange, add, and Shaw. Others are utilized to exploit better solutions: relocation, 2-opt, 3-opt, relocate, and 1-interchange algorithm, which apply intra and inter-route moves.The detailed information ofh1∼h4 can be obtained from Ref. [54], which are simple and basic mutational heuristics. The h5 heuristic diversifies the open depots by opening a new one and randomly assigning between 1 and 2/3 of the routes to it [37]. As to the last diversified LLH h6 [85], it is a method named as destroy-and-repair operator proposed to remove related clients, i.e., clients that are geographically close to each other and reinserted into best positions. In our paper, basic greedy heuristic [86] is suggested to reinsert removal clients back into routes. The disturbed solutions are accepted as long as the above acceptance criteria and the vehicle capacity at each arc and depots capacity are obeyed.The relocationh7 is developed to reselect the appropriate depots for determined routes. Each route is collapsed into a cluster and the smallest insertion costs can be calculated as the distance of the depots in the original routes. The depots with the larger number of clusters take priority to open. And then other unassigned clusters (from large to small order) sharing same closest depot will be arranged to its closest depot, unless the assigned depots’ capacity and cost are not satisfied. The 2-opt [87] inside the routes is equivalent to the well-known 2-opt move (h8) [88], whereas the other version of 2-opt implemented between different routes is identified (h9). Due to reduced CPU time, the intral-3-opt (h10) [89] is only considered. The relocate heuristic [90] reinserts a single client in another position inside the incumbent route (h11) or in another route (h12). The 1-interchange [91] heuristic swaps each position of client from one route with each client in another route if not sharing the same depot (h13). If improvements are found and depot capacity and vehicle load at each arc are met, the above moves are implemented, allowing them to improve incumbent solutions.The MHs often perform simple random moves to perturb the incumbent solution without guaranteeing competitive results. Although insufficient for achieving competitive results, they are useful for providing randomization and helpful for navigating out of local optima. However, HCs play a key role in quickly obtaining much better solutions at each step. Moreover, it might be desirable to apply HCs after application of any MH and to apply MHs if it is hard for HCs to provide promising solutions. Considering the above features, the proposed nine selection strategies are utilized to adaptively manage the HCs, inspired from the mechanism on management of local search heuristics [5, 54] and the method for automatically classifying according to the performance proposed in Ref. [57]. The probability for selecting any one MH as guider for getting rid of local optimality is set to 1 if and only if no HC can provide an improvement to previous objective value; otherwise, the probability value is set to 0. Hence, Figure 1 is the framework of hyperheuristics applied in this paper.Figure 1
Framework of hyperheuristic approach.Moreover, a stopping mechanism is defined by evaluation limits with maximum number of fitness evaluation (αmax), aiming at providing fair comparison.


## 5. Computational Evaluation

In this paper, we explore the performance of a set of hyperheuristics in solving CLRP and CLRPSPD. The experiments consist of four parts. In the first part, an overall picture related to the selection strategies and acceptance alternatives is provided to rank the performance of 36 pairs and determine first four outstanding pairs for the following experiments. Then, the efficiency and features are analysed for the chosen pairs by implementing on the three sets of CLRP benchmark instances. In the third part, we explore the performance of selected pairs in solving CLRPSPD benchmark sets. Finally, the performance of selected pairs is tested against recent and effective tailored approaches in the literature.


### 5.1. Experimental Design

The presented HH approach with 36 pairs is coded in Matlab 8.6 and runs on a desktop computer with Intel Core (TM) i7-6700K (4.00 GHz) and 8 GB RAM, under Windows 10; it is embedded in the CLOR tool, available by emailing to us.As far as calibration is considered, two types of parameters are concerned: specific selection strategy parameters and common hyperheuristic parameters. The former relates to the setting of selection strategies, while the latter accounts for the common parameters between LLHs and HLH, and they are summarized in Table2.Table 2
Configuration for each selection strategy.
Strategies
Parameters
Values
Common parameters
FRR-MAB
Scaling factorC
0.5 [7]
Initial probabilityp=0.5
Sliding windows sizeW
25 [56]
Population sizeSLLH = 1 (single-point search)
QS/QS2
Initial rotation angle, Δθ0
0.02π
Population sizeSHLH = 1 (only one individual)
Initial probability amplitudesα, β
0.7071 [74]
Maximum fitness evaluationαmax (Eq. 29)
AS/AS2
Initial pheromone,τij/τi
0
Maximum iterationtmax = 106
Initial visibility,ηij/ηi
0
Evaporation rate,ρ
0.2 [69]
PS
Learning factors,c1, c2
2 [72]
Inertia weight,w
1 [72]Some of the specified parameters follow defaults suggested in the literature, and others were determined by conducting an initial experiment with various settings aiming at obtaining relative better results within reasonable CPU time. As to common hyperheuristic parameters, initial selection probabilityp is set to 0.5 for each LLH in line with the initial probability amplitudes of QS; tabu list size lt is set to 7 which is the number of HCs; as single-point-based search hyperheuristic framework is investigated in this paper, the sizes of population used in the LLH and HLH are set at 1. For fairly comparing the running time of each pair, the maximum number of fitness evaluation for each instance is provided, which was different from the method in Ref. [2] (i.e., the maximum iterations without improving solution), depending directly on the number of clients, depots, and vehicles:(29)αmax=a×m+n+K2.Aiming at obtaining a good trade-off between solution quality and computing time, the multipliera is taking on the value 5 for all instances in this paper.


### 5.2. Benchmark Instances

Three sets of CLRP benchmark instances were adopted to evaluate the efficiency and features of each pair for hyperheuristic. These sets are provided in Refs. [26–28]. One separation approach is used to generate the datasets of CLRPSPD from the above CLRP benchmarks, instanced as W type in Ref. [92] with setting 0.8 for β.The first benchmark instances [28] contain 19 cases. The number of clients ranges from 12 to 318, and the number of depots m varies between 2 and 15, and the fixed vehicle cost fv is not given. In the randomly generated set [27], the number of clients ranges from 20 to 200, the number of depots m is 5 and 10, and vehicle capacity Q is {70, 150} and fv = 1000. The benchmark instances [26] are also randomly generated which contain 36 cases with n ∈ {100, 150, 200}, m ∈ {10, 20}, Q = 150, and fv = 10. And the clients’ demand of this benchmark ranges from 1 to 20. The above three benchmark sets are available at http://sweet.ua.pt/sbarreto/or_http://prodhonc.free.fr/homepage.Euclidean distances are applied in all datasets. In Prins et al. benchmark set for CLRPSPD, the obtained distances are multiplied by 100 (rounded up to the next integer in CLRP) and the total costs are rounded up to the next integer, which is different from the sets obtained in Refs. [4, 38]. The working cost of vehicle for each instance with less than 100 clients in the first set increases to 20, namely, fv = 20.


### 5.3. Results

#### 5.3.1. Experiment on 36 Pairs

The first set of experiment is performed to compare the performance of 36 pairs of hyperheuristics aiming at determining the first four outstanding pairs for the following experiments. Nine CLRP instances in Barreto set with the number of clients ranging from 50 to 318 were used to test performance of each pair, implementing fifty runs on each instance. The maximum number of fitness evaluation is set to 10000. Aiming at comparing and scoring for all pairs, formula (1) scoring system was adopted, which was used to rank the approaches by CHESC (Cross-domain Heuristic Search Challenge) before 2010 (http://www.asap.cs.nott.ac.uk/external/chesc2011/). The top eight approaches are given a score of 10, 8, 6, 5, 4, 3, 2, and 1 point for each problem from the best to the worst, successively [65]. The rest of the methods receive a score of 0. In this paper, the score of 10 points is assigned to the pairs which can exploit the best known solution (BKS), and the scores for the rest of pairs are similar to formula (1) scoring system. Therefore, 90 is the maximum overall score a pair can get.Experiment results are shown in Table3, where the overall scores of the best four pairs, nine selection strategies, and four acceptance criteria are provided. As can be seen from the results, HH performing AS-AM is the best clear winner, and PS-AM, QS2-SA, and TS-SA also outperform other pairs. The hyperheuristic using AS, FRR-MAB-TS, TS, and RP as selection components performs better than others regardless of the acceptance component, and several interesting conclusions can be drawn from the overall scores that (1) TS could promote better performance for selection strategies by excluding the LLHs with poor performance, when compared with the performance of selection strategies without TS, reaching an average improvement about score 25 point; (2) the performance of AS using 0/1 knapsack problem outperforms AS2 applying TSP, in other words, compared to the one laying ant pheromone trails at routes, the mechanism laying ant pheromone trails on vertices (i.e., LLHs) have a greater chance of success in guiding ants to select the promising sequence of LLHs; (3) PS-AM and QS2-SA ranks the second/third place in overall scores of pairings, even if the performance of PS/QS2 is barely satisfactory. From the last four scores of acceptance component regardless of the selection component, AM and SA rank, respectively, the first and second with a score 529 and 518, while the other two receive a score of 473 and 429, respectively.Table 3
The overall formula (1) scores for the top four pairs and strategies.
Pairs
Overall score
AS-AM
73
PS-AM
67
QS2-SA
66
TS-SA
65
RP
222
TS
229
FRR-MAB
204
FMT
233
QS
176
QS2
215
AS
242
AS2
212
PS
216
AM
529
NA
473
GD
429
SA
518Figure2 shows the box plot for the scores of nine selection strategies and four acceptance criteria. In the box plot, the minimum and maximum values obtained (excluding the outliers), the lower and upper quartiles, and median are shown.Figure 2
Box plots of scores for a statistical comparison of (a) selection strategies and (b) acceptance criteria.
(a)
(b)From such analysis and answering the first experiments, we identify AS-AM as the best pair considering most cases and scores, and additional PS-AM, QS2-SA, and TS-SA are also selected to conduct the following experiments.


#### 5.3.2. Experiment on CLRP

The first four outstanding pairs were tested performing fifty runs on each instance, from which best found solution, gaps to BKS, and computing time are shown, providing the insufficient page space. Results for three CLRP benchmark instances are shown in Tables4–6. The first column of each table is the name of each instances, followed by BKS, and results concerning four pairs which contain best found results (Best), gap (in percentage) to the BKS, and average computing time in seconds (CPU). Average and median values for gaps and CPU are displayed in the last two rows.Table 4
Results for the CLRP instances in Barreto set.
Set
BKS
TS-SA
QS2-SA
AS-AM
PS-AM
Best
Gap
CPU
Best
Gap
CPU
Best
Gap
CPU
Best
Gap
CPU
P12-2
204.0
204.0
0.00
0.1
204.0
0.00
0.1
204.0
0.00
0.1
204.0
0.00
0.1
G21-5
424.9
424.9
0.00
0.4
424.9
0.00
0.4
424.9
0.00
0.4
424.9
0.00
0.3
G22-5
585.1
585.1
0.00
0.3
585.1
0.00
0.4
585.1
0.00
0.3
585.1
0.00
0.3
M27-5
3062.0
3062.0
0.00
0.6
3062.0
0.00
0.6
3062.0
0.00
0.5
3062.0
0.00
0.5
G29-5
512.1
512.1
0.00
0.6
512.1
0.00
0.6
512.1
0.00
0.5
512.1
0.00
0.5
G32-5
562.2
562.2
0.00
0.7
562.2
0.00
0.7
562.2
0.00
0.6
562.2
0.00
0.6
G32-5-2
504.3
504.3
0.00
0.6
504.3
0.00
0.7
504.3
0.00
0.6
504.3
0.00
0.5
G36-5
460.4
460.4
0.00
0.9
460.4
0.00
0.9
460.4
0.00
0.8
460.4
0.00
0.7
C50-5
565.6
565.6
0.00
2.0
565.6
0.00
2.2
565.6
0.00
1.8
565.6
0.00
1.6
P55-15
1112.1
1112.1
0.00
4.2
1112.1
0.00
5.2
1112.1
0.00
4.6
1112.8
0.06
4.2
C75-10
844.4
844.4
0.00
7.9
844.4
0.00
7.9
844.4
0.00
7.0
844.4
0.00
6.3
P85-7
1622.5
1622.5
0.00
9.6
1622.5
0.00
9.7
1622.5
0.00
8.6
1622.5
0.00
7.7
D88-8
355.8
355.8
0.00
7.0
355.8
0.00
6.3
355.8
0.00
6.5
355.8
0.00
5.9
C100-10
833.4
833.4
0.00
11.4
833.4
0.00
12.3
833.4
0.00
10.6
833.4
0.00
8.3
O117-14
12290.3
12290.3
0.00
18.3
12290.3
0.00
18.4
12290.3
0.00
16.4
12290.3
0.00
14.6
M134-8
5709.0
5709.0
0.00
32.7
5709.0
0.00
33.0
5709.0
0.00
29.9
5709.0
0.00
24.1
D150-10
43919.9
43919.9
0.00
42.7
43919.9
0.00
45.0
43919.9
0.00
38.3
43919.9
0.00
33.1
P318-4
7249.3a
4484.2
−0.50
156.4
4145.9
−0.56
110.0
3966.0
−0.59
126.8
3991.1
−0.58
78.8
P318-4-2
13070.0b
10866.5
−0.33
243.4
8293.0
−0.72
213.0
10269.4
−0.42
260.6
10905.1
−0.33
125.3
AV
68099.3
67837.8
−0.04
28.4
67684.6
−0.07
24.6
67779.1
−0.05
27.1
67813.9
−0.04
16.5
MD
0.00
4.2
0.00
5.2
0.00
4.6
0.00
4.2
Bold numbers are the best known solutions. Italic numbers are the minimum value among four obtained solutions. Underscore numbers are the obtained values less than the best known solutions.aResults minus 550000. bResults minus 650000.Table 5
Results for the CLRP instances in Prins set.
Set
BKS
TS-SA
QS2-SA
AS-AM
PS-AM
Best
Gap
CPU
Best
Gap
CPU
Best
Gap
CPU
Best
Gap
CPU
20-5-1
54793
54793
0.00
0.5
54793
0.00
0.5
54793
0.00
0.5
54793
0.00
0.5
20-5-1b
39104
39104
0.00
0.3
39104
0.00
0.3
39104
0.00
0.2
39104
0.00
0.2
20-5-2
48908
48908
0.00
0.5
48908
0.00
0.6
48908
0.00
0.4
48908
0.00
0.4
20-5-2b
37542
37542
0.00
0.3
37542
0.00
0.3
37542
0.00
0.3
37542
0.00
0.2
50-5-1
90111
90111
0.00
3.9
90111
0.00
4.1
90111
0.00
2.9
90111
0.00
2.6
50-5-1b
63242
63242
0.00
1.8
63242
0.00
2.0
63242
0.00
1.9
63242
0.00
1.7
50-5-2
88298
88298
0.00
4.2
88298
0.00
4.3
88298
0.00
3.6
88298
0.00
3.4
50-5-2b
67308
67373
0.10
2.1
67308
0.00
2.1
67449
0.21
1.7
67308
0.00
1.5
50-5-2bis
84055
84055
0.00
3.5
84055
0.00
3.7
84055
0.00
3.1
84055
0.00
2.9
50-5-2bbis
51822
51822
0.00
2.4
51822
0.00
2.5
51822
0.00
2.1
51822
0.00
2.0
50-5-3
86203
86203
0.00
3.9
86203
0.00
4.3
86203
0.00
3.4
86203
0.00
3.1
50-5-3b
61830
61830
0.00
1.9
61830
0.00
1.9
61830
0.00
1.6
61830
0.00
1.6
100-5-1
274814
276096
0.47
28.9
276144
0.48
30.9
275601
0.29
25.8
275598
0.29
22.6
100-5-1b
213615
213654
0.02
14.1
213654
0.02
13.5
213671
0.03
12.2
213654
0.02
10.9
100-5-2
193671
193671
0.00
35.1
193671
0.00
34.4
193671
0.00
26.6
193671
0.00
26.0
100-5-2b
157095
157129
0.02
14.1
157144
0.03
15.2
157110
0.01
13.8
157129
0.02
12.3
100-5-3
200079
200079
0.00
34.3
200079
0.00
34.5
200079
0.00
25.7
200079
0.00
26.8
100-5-3b
152441
152441
0.00
13.8
152441
0.00
13.0
152441
0.00
12.3
152441
0.00
11.3
100-10-1
287695
287688
0.00
31.7
287688
0.00
32.8
287688
0.00
27.4
287688
0.00
25.4
100-10-1b
230989
231608
0.27
17.6
231833
0.37
16.7
231833
0.37
11.1
232222
0.53
13.8
100-10-2
243590
243590
0.00
28.6
243590
0.00
29.2
243590
0.00
24.4
243590
0.00
22.0
100-10-2b
203988
203988
0.00
15.7
203988
0.00
17.4
203988
0.00
15.5
203988
0.00
14.1
100-10-3
250882
252890
0.80
33.8
252890
0.80
33.2
252751
0.74
27.9
252890
0.80
27.2
100-10-3b
204317
204567
0.12
15.8
204567
0.12
15.4
204567
0.12
13.8
204567
0.12
12.9
200-10-1
475294
475770
0.10
268.1
476166
0.18
263.8
476002
0.15
219.6
476722
0.30
190.0
200-10-1b
377043
375820
−0.32
135.0
376313
−0.19
121.4
376662
−0.10
96.7
375836
−0.32
91.0
200-10-2
449006
449037
0.01
250.9
449142
0.03
236.7
449332
0.07
210.4
449110
0.02
132.4
200-10-2b
374280
373882
−0.11
153.0
373973
−0.08
151.1
374039
−0.06
125.8
374093
−0.05
110.6
200-10-3
469433
470780
0.29
247.8
471043
0.34
223.1
471043
0.34
208.2
471073
0.35
124.8
200-10-3b
362653
362276
−0.10
161.2
362349
−0.08
122.0
362596
−0.02
110.0
362640
0.00
113.1
AV
196470
196608
0.06
50.8
196663
0.07
47.7
196667
0.07
41.0
196674
0.07
33.6
MD
196875
0.00
14.9
0.00
15.3
0.00
13.1
0.00
12.6
Bold numbers are the best known solutions. Italic numbers are the minimum value among four obtained solutions. Underscore numbers are the obtained values less than the best known solutions.Table 6
Results for the CLRP instances in Tuzun and Burke.
Set
BKS
TS-SA
QS2-SA
AS-AM
PS-AM
Best
Gap
CPU
Best
Gap
CPU
Best
Gap
CPU
Best
Gap
CPU
P1
1467.68
1467.68
0.00
15.2
1467.68
0.00
15.4
1467.68
0.00
13.0
1467.68
0.00
11.6
P2
1449.20
1448.37
−0.06
20.4
1449.20
0.00
20.1
1449.20
0.00
17.6
1448.37
−0.06
14.7
P3
1394.80
1394.80
0.00
15.1
1394.80
0.00
16.4
1394.93
0.01
14.2
1394.80
0.00
12.3
P4
1432.29
1432.29
0.00
20.7
1432.29
0.00
20.9
1432.29
0.00
17.6
1432.29
0.00
15.4
P5
1167.16
1167.16
0.00
14.5
1167.16
0.00
15.7
1167.16
0.00
13.2
1167.16
0.00
12.0
P6
1102.24
1102.24
0.00
19.0
1102.24
0.00
18.8
1102.24
0.00
16.2
1102.24
0.00
14.5
P7
791.66
791.66
0.00
15.6
791.66
0.00
15.8
791.66
0.00
13.4
791.66
0.00
12.6
P8
728.30
728.30
0.00
17.8
728.30
0.00
17.6
728.30
0.00
15.4
728.30
0.00
12.9
P9
1238.24
1238.49
0.02
16.6
1238.49
0.02
15.9
1238.49
0.02
14.6
1238.49
0.02
13.6
P10
1245.31
1245.31
0.00
23.9
1245.42
0.01
27.6
1245.31
0.00
18.1
1245.31
0.00
15.5
P11
902.26
902.26
0.00
15.3
902.26
0.00
15.4
902.26
0.00
12.9
902.26
0.00
11.9
P12
1018.29
1018.29
0.00
17.9
1018.29
0.00
18.2
1018.29
0.00
15.6
1018.29
0.00
12.7
P13
1866.75
1895.83
1.56
61.8
1895.83
1.56
63.1
1892.17
1.36
53.6
1895.83
1.56
52.9
P14
1823.20
1820.12
−0.17
62.1
1822.69
−0.03
61.3
1822.15
−0.06
53.8
1822.69
−0.03
42.1
P15
1964.30
1965.12
0.04
57.0
1965.12
0.04
57.9
1965.12
0.04
48.9
1965.12
0.04
42.6
P16
1792.80
1792.77
−0.00
70.9
1792.77
−0.00
69.9
1792.77
−0.00
66.9
1792.77
−0.00
55.3
P17
1443.33
1443.32
−0.00
58.6
1443.32
−0.00
64.5
1443.32
−0.00
53.7
1443.32
−0.00
51.3
P18
1434.60
1434.82
0.02
63.0
1433.16
−0.10
64.1
1433.49
−0.08
53.2
1431.24
−0.23
46.6
P19
1204.42
1204.42
0.00
63.5
1204.42
0.00
64.6
1204.42
0.00
57.1
1204.42
0.00
61.7
P20
930.99
927.63
−0.36
64.3
931.28
0.03
65.6
931.28
0.03
54.3
929.26
−0.19
43.8
P21
1694.18
1694.18
0.00
71.3
1694.18
0.00
64.2
1694.18
0.00
55.3
1694.18
0.00
52.1
P22
1392.01
1392.01
0.00
61.6
1392.18
0.01
64.6
1392.01
0.00
53.1
1392.01
0.00
49.3
P23
1198.20
1197.95
−0.02
57.5
1197.95
−0.02
57.2
1197.95
−0.02
48.3
1197.95
−0.02
40.8
P24
1151.80
1151.80
0.00
72.1
1151.80
0.00
73.1
1151.80
0.00
61.2
1151.80
0.00
52.9
P25
2243.40
2237.73
−0.25
136.6
2240.37
−0.14
131.1
2244.64
0.06
91.2
2244.79
0.06
84.9
P26
2138.40
2139.67
0.06
137.9
2139.67
0.06
130.1
2144.49
0.28
102.5
2141.09
0.13
73.2
P27
2209.30
2204.93
−0.20
178.8
2208.48
−0.04
151.4
2209.36
0.00
110.0
2207.69
−0.07
96.1
P28
2222.90
2226.50
0.16
160.4
2223.61
0.03
150.3
2228.27
0.24
113.2
2221.59
−0.06
110.4
P29
2073.70
2074.86
0.06
137.7
2079.96
0.30
130.6
2076.16
0.12
100.4
2077.01
0.16
88.9
P30
1692.17
1685.65
−0.39
135.8
1685.65
−0.39
129.5
1687.38
−0.28
102.6
1685.78
−0.38
80.6
P31
1453.18
1449.96
−0.22
175.1
1449.46
−0.26
153.4
1450.90
−0.16
114.8
1453.89
0.05
100.4
P32
1082.46
1082.46
0.00
167.3
1082.46
0.00
152.6
1082.46
0.00
108.5
1082.46
0.00
111.2
P33
1954.70
1949.29
−0.28
126.3
1950.60
−0.21
127.8
1947.84
−0.35
112.6
1949.38
−0.27
78.6
P34
1918.93
1916.18
−0.14
137.4
1911.73
−0.38
129.6
1917.98
−0.05
91.7
1912.61
−0.33
82.5
P35
1762.00
1760.60
−0.08
155.6
1761.22
−0.04
161.1
1760.04
−0.11
117.3
1760.63
−0.08
113.3
P36
1390.87
1390.87
0.00
167.3
1390.87
0.00
148.2
1390.87
0.00
111.1
1390.94
0.01
117.5
AV
1499.33
1499.32
−0.01
77.6
1499.63
0.01
74.5
1499.97
0.03
59.6
1499.59
0.01
52.5
MD
1439.07
0.00
62.6
0.00
64.4
0.00
53.8
0.00
50.3
Bold numbers are the best known solutions. Italic numbers are the minimum value among four obtained solutions. Underscore numbers are the obtained values less than the best known solutions.For the first three pairs (Table4), the BKSs of instances with less than 150 clients are exploited with average gap at −0.04% for TS-SA, −0.07% for QS2-SA, and −0.05% for AS-AM. Only one BKS cannot be found by the last pair with highest gap at 0.06% and average value at −0.04%. Concerning the median values of gaps to BKS, they take on the value 0. Computing times are on average less than 29, 25, 27, and 17 s, and median values are lower than 6 s even if the largest instances exist. Two new BKS are found by four pairs, obtaining an improvement of over 0.5% for Perl83-318 × 4 by PS-AM and over 0.7% for Perl83-318 × 4-2 by QS2-SA.In the second benchmark (Table5), at least 16 BKS can be found by the four pairs, with difference in finding the Best of 50-5-2b. Four new BKSs in this set are obtained, respectively, reaching an improvement of over 0.3% for 200-10-1b by TS-SA and PS-AM and 0.1% for 200-10-2b and 200-10-3b by TS-SA. Concerning gaps of Best, average values are, respectively, 0.06% for TS-SA and 0.07% for other pairs, and the highest gaps are less than 0.8% for four pairs. Median values equal to 0 for all pairs. Average and median values for CPU are, respectively, 50.8 and 14.9 s for TS-SA, 47.7 and 15.3 s for QS2-SA, 41 and 13.1 s for AS-AM, and 33.6 and 12.6 s for PA-AM.For the Tuzun and Burke benchmark (Table6), TS-SA and PS-AM tie for first place in the number of new BKS found with 13 new BKSs, and QS2-SA tails the winner to take the second place by exploiting 12 new BKSs and AS-AM is in the last place. Concerning the number of solution less than or equal to BKS, TS-SA, PS-AM, and QS2-SA, respectively, rank the first, second, and third with 29, 28, and 27 solutions less than or equal to BKS, and AS-AM ranks the last place with 26 solutions less than or equal to BKS. What surprised us is that the number of new BKS accounts for over 30%, except for AS-AM with 27.8% of 36 instances in this benchmark. Concerning gaps of Best, average values are, respectively, −0.01% for TS-SA, 0.01% for QS2-SA and PS-AM, and 0.03% for SA-AM, and median values are 0 for all pairs. Computing times are on average 77.6, 74.5, 59.6, and 52.5 s, and median values are 62.6, 64.4, 53.8, and 50.3 s.We conduct statistical analysis for obtained results of three CLRP benchmark sets in Tables4–6 through Table 7 based on multiple pairwise comparisons with 95% confidence level (i.e., α = 0.05), namely, Friedman tests. In the Friedman test, the null hypothesis (H0) is only rejected if the Friedman statistic (χ2) is greater than the critical value, looking up in χ2 table through sample size and confidence level, and post hoc test based on Wilcoxon Rank-Sum should be carried out to detect the significant difference among samples, when needed; otherwise, the null hypothesis (H0) is accepted indicating that no significant difference is concerned among four pairs. In Table 7, Friedman statistics (χ2) take the values 3.923 for Barreto et al., 6.750 for Prins et al., and 6.201 for Tuzun and Burke, which are, respectively, lower than 10.117, 18.493, and 23.269, indicating that there is no significant difference among performance of four pairs.Table 7
Friedman’s test results for CLRP benchmark instances (α = 0.05).
Benchmark
Mean ranks for four pairs
Test statistics
Conclusion
TS-SA
QS2-SA
AS-AM
PS-AM
n
χ
2
df
p
Barreto set
2.58
2.42
2.37
2.63
19
3.923
3
0.270
χ
2 < critical value, accept H0
Prins set
2.18
2.58
2.60
2.63
30
6.750
3
0.080
Tuzun and Burke
2.19
2.61
2.65
2.54
36
6.201
3
0.102


#### 5.3.3. Experiment on CLRPSPD

The CLRPSPD benchmark instances, which were first converted in Refs. [2, 38], were also used to evaluate the features of the best four pairs. However, this paper only considered the W type of the above sets for the CLRPSPD. The main reason is that the sets of X, Y, and Z types show the same characteristics with the original sets of CLRP, and it is most difficult to obtain BKSs for the instances using W type separation approach. All BKSs were obtained from Ref. [1]. Results for the three CLRPSPD benchmark instances are shown in Tables 8–10. The first column of each table is the name of each instances, followed by the best known solution (BKS), data concerning the first four best pairs which contain best results (Best), gap (in percentage) to the BKS, and average computing time in seconds (CPU). Average (AV) and median values (MD)for gaps or gap and CPU are displayed in the last two rows.Table 8
Results for the CLRPSPD instances in Barreto set.
Instance
BKS
TS-SA
QS2-SA
AS-AM
PS-AM
Best
Gap
CPU
Best
Gap
CPU
Best
Gap
CPU
Best
Gap
CPU
P12-2
243.98
243.98
0.00
0.1
243.98
0.00
0.1
243.98
0.00
0.1
243.98
0.00
0.1
G21-5
528.42
528.42
0.00
0.4
528.42
0.00
0.5
528.42
0.00
0.3
528.42
0.00
0.3
G22-5
653.8
653.80
0.00
0.3
653.80
0.00
0.4
653.80
0.00
0.3
653.80
0.00
0.2
M27-5
3142.02
3142.02
0.00
0.6
3142.02
0.00
0.7
3142.02
0.00
0.5
3142.02
0.00
0.5
G29-5
592.1
592.10
0.00
0.6
592.10
0.00
0.6
592.10
0.00
0.4
592.10
0.00
0.4
G32-5
696.38
696.38
0.00
0.9
696.38
0.00
1.0
696.38
0.00
0.8
696.38
0.00
0.7
G32-5-2
595.27
595.27
0.00
0.7
595.27
0.00
0.8
595.27
0.00
0.6
595.27
0.00
0.6
G36-5
540.37
540.37
0.00
0.9
540.37
0.00
1.0
540.37
0.00
0.7
540.37
0.00
0.7
C50-5
708.37
708.37
0.00
1.9
708.37
0.00
2.0
708.37
0.00
1.5
708.37
0.00
1.4
P55-15
1327.06
1327.06
0.00
3.9
1327.06
0.00
4.0
1327.06
0.00
3.4
1327.06
0.00
3.1
C75-10
1132.8
1132.80
0.00
8.4
1135.61
0.25
8.6
1135.61
0.25
7.2
1137.59
0.42
6.1
P85-7
1855.55
1855.55
0.00
12.2
1855.55
0.00
12.4
1855.55
0.00
10.3
1855.55
0.00
6.3
D88-8
497.6
497.98
0.08
7.1
497.98
0.08
7.4
497.60
0.00
6.4
497.98
0.08
5.8
C100-10
1011.53
1011.53
0.00
13.7
1013.12
0.16
14.0
1011.53
0.00
11.4
1011.53
0.00
10.6
O117-14
12350.2
12350.20
0.00
17.4
12350.20
0.00
17.2
12350.20
0.00
15.3
12350.20
0.00
13.3
M134-8
5913.51
5913.51
0.00
28.5
5922.38
0.15
29.8
5913.51
0.00
24.8
5922.38
0.15
21.2
D150-10
44955.31
44955.31
0.00
46.6
44955.31
0.00
42.2
44960.92
0.01
37.2
44955.31
0.00
35.7
P318-4
4650.09a
4650.85a
0.00
199.7
4650.85a
0.00
144.9
4650.85a
0.00
151.3
4650.85a
0.00
105.0
P318-4-2
6435.73b
6435.73
b
0.00
310.7
6435.73
b
0.00
268.2
5633.50
b
−0.11
259.9
5633.50
b
−0.11
114.6
AV
72362.55
70938.49
0.00
34.5
70939.18
0.03
29.3
70896.69
0.01
28.0
70896.98
0.03
17.2
MD
0.00
3.9
0.00
4.00
0.00
3.4
0.00
3.1
Bold numbers are the best known solutions. Underscore and italic numbers are the obtained values less than the best known solutions.aResults minus 560000. bResults minus 700000.Table 9
Results for the CLRPSPD instances in Prins set.
Instance
BKS
TS-SA
QS2-SA
AS-AM
PS-AM
Best
Gap
CPU
Best
Gap
CPU
Best
Gap
CPU
Best
Gap
CPU
20-5-1
56350
56350
0.00
0.5
56350
0.00
0.5
56350
0.00
0.3
56350
0.00
0.3
20-5-1b
40678
40678
0.00
0.3
40678
0.00
0.3
40678
0.00
0.2
40678
0.00
0.2
20-5-2
49712
49712
0.00
0.5
49712
0.00
0.6
49712
0.00
0.3
49712
0.00
0.3
20-5-2b
38357
38357
0.00
0.3
38357
0.00
0.3
38357
0.00
0.2
38357
0.00
0.2
50-5-1
100240
100240
0.00
4.0
100240
0.00
4.1
100240
0.00
3.4
100240
0.00
3.1
50-5-1b
68993
68993
0.00
1.8
68993
0.00
2.3
68993
0.00
2.1
68993
0.00
1.8
50-5-2
94280
94280
0.00
5.1
94280
0.00
5.2
94280
0.00
4.4
94280
0.00
3.1
50-5-2b
69123
69123
0.00
2.7
69123
0.00
2.7
69123
0.00
2.2
69123
0.00
2.0
50-5-2bis
86349
86349
0.00
4.0
86349
0.00
4.0
86349
0.00
3.5
86349
0.00
3.3
50-5-2bbis
52356
52356
0.00
2.8
52356
0.00
2.6
52356
0.00
2.3
52356
0.00
2.1
50-5-3
90419
90419
0.00
4.9
89737
−0.75
4.7
90419
0.00
3.4
90419
0.00
3.8
50-5-3b
62178
62178
0.00
2.0
62178
0.00
2.1
62178
0.00
1.7
62178
0.00
1.6
100-5-1
290168
290280
0.04
43.5
290280
0.04
46.6
290401
0.08
38.7
290505
0.12
34.1
100-5-1b
219199
223968
2.18
18.9
223966
2.17
18.6
223968
2.18
16.9
223966
2.17
18.0
100-5-2
206049
206170
0.06
32.9
206078
0.01
36.7
206170
0.06
30.2
206308
0.13
29.8
100-5-2b
162077
162083
0.00
15.1
162077
0.00
15.7
162077
0.00
13.4
162077
0.00
12.1
100-5-3
209142
209142
0.00
43.2
209142
0.00
41.5
209142
0.00
34.5
209142
0.00
30.6
100-5-3b
156971
157027
0.04
16.2
157027
0.04
15.9
157027
0.04
14.4
157027
0.04
12.2
100-10-1
326093
326093
0.00
40.5
326093
0.00
40.8
326093
0.00
35.1
326093
0.00
30.8
100-10-1b
272889
272889
0.00
21.8
272889
0.00
21.6
272889
0.00
18.5
272889
0.00
14.1
100-10-2
253074
253609
0.21
39.4
253096
0.01
40.5
253640
0.22
34.1
253074
0.00
29.6
100-10-2b
208941
208941
0.00
20.9
208944
0.00
21.8
208941
0.00
18.9
208941
0.00
16.5
100-10-3
268137
268451
0.12
41.3
268416
0.10
39.0
268531
0.15
35.7
268349
0.08
32.6
100-10-3b
214828
214828
0.00
16.0
214828
0.00
17.9
214828
0.00
15.5
214828
0.00
13.5
200-10-1
529512
498257
−5.90
334.6
498451
−5.87
306.0
499084
−5.75
233.5
498066
−5.94
187.8
200-10-1b
393699
384277
−2.39
195.2
393924
0.06
170.2
385287
−2.14
155.7
385737
−2.02
135.7
200−10-2
463637
463968
0.07
316.4
463913
0.06
282.1
464111
0.10
249.2
464031
0.08
178.3
200-10-2b
380670
380924
0.07
206.4
380833
0.04
173.4
381031
0.09
138.5
380611
−0.02
117.0
200-10-3
485379
485882
0.10
307.9
485946
0.12
304.5
486009
0.13
240.8
486134
0.16
162.3
200-10-3b
369201
369938
0.20
183.3
370303
0.30
171.8
370213
0.27
131.5
370412
0.33
101.6
AV
206192
−0.17
64.1
206485
−0.12
59.8
206283
−0.15
49.3
206241
−0.16
39.3
MD
0.00
17.6
0.00
18.3
0.00
16.2
0.00
13.8
Bold numbers are the minimum value among four obtained solutions. Underscore and italic numbers are the obtained values less than the best known solutions.Table 10
Results for the CLRPSPD instances in Tuzun and Burke.
Case
BKS
TS-SA
QS2-SA
AS-AM
PS-AM
Best
Gap
CPU
Best
Gap
CPU
Best
Gap
CPU
Best
Gap
CPU
P1
1504.45
1504.45
0.00
18.8
1504.45
0.00
19.5
1504.45
0.00
16.5
1504.86
0.03
14.2
P2
1474.33
1474.33
0.00
19.5
1474.33
0.00
18.8
1474.33
0.00
17.2
1474.33
0.00
14.4
P3
1414.35
1414.46
0.01
17.6
1415.13
0.06
17.5
1414.35
0.00
15.4
1414.35
0.00
13.2
P4
1477.49
1481.50
0.27
20.3
1484.29
0.46
19.5
1477.49
0.00
18.2
1477.49
0.00
15.1
P5
1230
1233.69
0.30
18.9
1233.24
0.26
18.6
1227.89
−0.17
16.5
1233.54
0.29
14.7
P6
1123.72
1123.72
0.00
17.9
1123.72
0.00
19.2
1123.72
0.00
16.6
1123.72
0.00
12.2
P7
812.42
812.42
0.00
18.8
812.42
0.00
22.0
812.42
0.00
16.3
812.42
0.00
15.0
P8
752.66
751.89
−0.10
24.0
754.15
0.20
23.3
752.41
−0.03
19.0
759.21
0.87
11.6
P9
1273.3
1273.30
0.00
18.8
1273.30
0.00
19.2
1273.30
0.00
15.8
1273.30
0.00
14.5
P10
1265.1
1265.10
0.00
22.5
1265.02
−0.01
22.8
1266.20
0.09
20.0
1265.10
0.00
17.4
P11
911.52
911.52
0.00
20.3
911.52
0.00
18.4
911.52
0.00
16.8
911.52
0.00
15.4
P12
1033.38
1031.94
−0.14
23.5
1033.38
0.00
22.6
1033.27
−0.01
20.2
1033.38
0.00
18.1
P13
1943.41
1947.92
0.23
59.1
1946.58
0.16
58.5
1949.76
0.33
49.9
1947.98
0.24
41.9
P14
1848.69
1848.69
0.00
66.1
1856.10
0.40
67.4
1859.17
0.57
58.4
1862.25
0.73
46.4
P15
2011.29
2011.32
0.00
67.7
2011.39
0.00
71.3
2016.29
0.25
58.5
2012.29
0.05
49.1
P16
1856.03
1861.73
0.31
63.5
1859.97
0.21
69.8
1862.65
0.36
59.4
1859.32
0.18
47.5
P17
1479.77
1484.97
0.35
69.3
1490.83
0.75
69.3
1483.73
0.27
58.7
1491.36
0.78
48.9
P18
1452.49
1453.05
0.04
67.1
1453.58
0.08
68.4
1452.28
−0.01
58.6
1452.73
0.02
47.8
P19
1228.49
1228.11
−0.03
60.6
1228.52
0.00
61.3
1228.49
0.00
53.9
1228.69
0.02
47.5
P20
949.82
949.82
0.00
68.3
951.62
0.19
68.7
950.06
0.03
58.9
949.82
0.00
45.7
P21
1732.81
1736.52
0.21
60.9
1736.45
0.21
61.9
1737.80
0.29
53.2
1735.63
0.16
42.9
P22
1426.41
1426.45
0.00
76.6
1426.66
0.02
77.4
1427.57
0.08
64.6
1425.37
−0.07
57.6
P23
1238.78
1229.69
−0.73
70.0
1226.08
−1.03
69.6
1229.69
−0.73
59.0
1229.69
−0.73
49.4
P24
1166.8
1166.80
0.00
64.0
1166.80
0.00
66.3
1166.80
0.00
57.0
1166.80
0.00
51.4
P25
2338.89
2343.12
0.18
153.2
2339.54
0.03
146.9
2343.64
0.20
102.4
2351.63
0.54
76.7
P26
2224.86
2226.41
0.07
177.6
2240.00
0.68
173.0
2238.67
0.62
122.9
2228.80
0.18
115.1
P27
2293.85
2298.34
0.20
175.9
2298.04
0.18
178.3
2297.87
0.18
115.3
2302.65
0.38
112.1
P28
2292.91
2303.17
0.45
154.4
2303.63
0.47
147.1
2301.04
0.35
107.2
2307.62
0.64
95.8
P29
2159.62
2163.17
0.16
160.2
2158.57
−0.05
159.8
2159.83
0.01
110.2
2169.93
0.48
89.4
P30
1727.67
1731.95
0.25
175.1
1733.80
0.35
172.7
1729.77
0.12
132.2
1729.04
0.08
103.6
P31
1483.34
1486.36
0.20
172.0
1484.89
0.10
171.2
1484.87
0.10
116.8
1486.35
0.20
114.3
P32
1101.65
1102.31
0.06
149.0
1102.29
0.06
138.4
1103.93
0.21
96.7
1102.44
0.07
100.5
P33
2001.36
2002.82
0.07
154.9
2003.39
0.10
147.4
2002.79
0.07
129.5
2003.16
0.09
75.5
P34
1973.43
1975.63
0.11
164.1
1977.83
0.22
165.5
1981.09
0.39
115.5
1982.10
0.44
107.9
P35
1801.82
1810.44
0.48
177.9
1825.68
1.32
164.5
1826.61
1.38
130.4
1822.02
1.12
148.1
P36
1418.8
1425.63
0.48
151.5
1423.96
0.36
140.0
1422.24
0.24
123.9
1432.10
0.94
101.2
Av.
1541.47
0.10
83.3
1542.53
0.16
82.1
1542.44
0.14
63.9
1543.42
0.21
55.3
MD.
0.05
66.6
0.09
68.6
0.08
58.6
0.08
47.7
Bold numbers are the minimum value among four obtained solutions. Underscore and italic numbers are the obtained values less than the best known solutions. The instances are represented by “PN,” whereN represents the serial number.For the Barreto benchmark set, computing times are on average lower than 35, 30, 29, and 18 s and median values are 3.9, 4, 3.4, and 3.1 s, respectively. Concerning gaps of Best, average values are, respectively, 0, 0.03%, 0.01%, and 0.03%, and median values equal to 0. New BKSs for instance with 318 clients are found with an improvement of 0.11% to previous BKS by AS-AM and PS-AM. Gaps to BKS are very low for all instances with highest gaps lower than 0.08% for the first pair, 0.25% for the second and third pairs, and 0.42% for the last one.Looking at Table9, computing times are on average less than 65, 60, 50, and 40 s, respectively, and median values are, respectively, 17.6, 18.3, 16.2, and 13.8 s. Concerning gaps to BKSs, average and median values are, respectively, −0.17% and 0 for TS-SA, −0.12% and 0 for QS2-SA, −0.15 and 0 for third pair, and −0.16 and 0 for the last pair. From the perspective of gaps to BKSs, we verified the solutions achieved in Ref. [2]. Meanwhile, we obtained four improvements for four instances, i.e., 50-5-3 (QS2-SA), 200-10-1 (four pairs), 200-10-1b (four pairs except for QS2-SA), and 200-10-2b (PS-AM), one of them reaching an improvement of over 5.9% to previous BKSs.As shown in Table10, the computing times are on average less than 84, 83, 64, and 56 s, and median values are 66.6, 68.6, 58.6, and 47.7 s, respectively. As far as gap to BKS is concerned, average/median values are 0.1/0.05%, 0.16/0.09%, 0.14/0.08%, and 0.21/0.08%, respectively. Meanwhile, new BKSs of nine instances were obtained by our proposed algorithms, and the largest improvement was over 1% for P23 obtained by QS2-SA. The AS-AM outperformed others obtaining five new BKSs, followed by TS-SA and QS2-SA, and PS-AM performed the worst. However, the best-performing pairs was TS-SA in terms of average gap to BKSs.Statistical analysis is carried out for obtained results of three sets in Tables8–10 through Table 11 based on Friedman test. In Table 11, Friedman statistics (χ2) take the values 3.279 for Barreto et al., 4.621 for Prins et al., and 4.087 for Tuzun and Burke, which are, respectively, lower than 10.117, 18.493, and 23.269, indicating that there is no significant difference among the performance of four pairs. Therefore, we can strongly conclude that the proposed pairs could achieve high-quality solutions for the CLRPSPD benchmark instances.Table 11
Friedman’s test results for CLRPSPD benchmark instances (α = 0.05).
Benchmark
Mean ranks for four pairs
Test statistics
Conclusion
TS-SA
QS2-SA
AS-AM
PS-AM
n
χ
2
df
p
Barreto set
2.39
2.68
2.37
2.55
19
3.279
3
0.351
χ
2 < critical value, accept H0
Prins set
2.42
2.33
2.77
2.48
30
4.621
3
0.202
Tuzun and burke
2.25
2.51
2.44
2.79
36
4.087
3
0.252Overall, among the four pairs, two types of discussion and conclusions are conducted: one for problem domains and one for hyperheuristic pairs. From perspective of both subjects, the amount of CPU time depends directly on the number of clients (n), depots (m), and vehicle capacity (Q), and the relationship between running time and each of above factors is drawn in Figures 3 and 4 (excluding the outliers) and Figure 5. Several conclusions on running time are reached: (1) running time is affected by the number of clients in exponential way; (2) number of depots has slight impact on the running time, which may be resulted by few depots; (3) computing time increases with the decrease of the vehicle capacity in the form of polynomial; (4) the order of impact of the above factors effecting the running time is n, Q, and m. The first and third conclusions were also shared in Ref. [2]. Moreover, the time complexity and solution quality may depend in part on the complexity of the mathematical model. Figure 6 illustrates the impact of complexity of mathematical model on the running time. More specifically, the average computing time of tackling CLRPSPD instances increases by 4.2–21.5% for Barreto set, 30.6–46.8% for Prins set, and 5.3–10.2% for Tuzun and Burke, respectively, compared with the average running times of tackling CLRP cases. Concerning solution quality and average standard deviation, the complexity of instances is the direct acting factor consisting of the number of clients, depots and vehicles, and the distribution of clients and depots. Furthermore, the complexity of approaches or pairs of selection strategies and acceptance criteria also significantly influence the running time, standard deviation, and solution quality. PS-AM seems to be among the fastest with declining 36, 33, and 20% average running time compared to others, and AS-AM and QS2-SA rank the second and third in aspects of average running time. In terms of solutions quality, there is no significant difference among these four pairs concluded by the above Friedman tests, indicating that PS-AM and AS-AM outperform the others in obtaining a better trade-off solution quality and running time, but all pairs can obtain high solution quality within reasonable running time.Figure 3
Box plots for relationship between computing time and number of clients.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)Figure 4
Box plots for relationship between computing time and number of depots.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)Figure 5
Histogram of computing times of different vehicle capacity.
(a)
(b)
(c)
(d)Figure 6
Histogram of computing times of both subjects.
(a)
(b)
(c)
(d)


#### 5.3.4. Comparison and Evaluation

To illustrate advantages of our proposed approaches for CLRP and CLRPSPD, comparisons with the most recent and effective methods in the literature are carried out in Table12, where average gaps (AG) of best found solutions to BKS and average running time of the proposed approaches for the CLRP are provided, and they are, respectively, GRASP + ELS [31], SALRP/SALRP+ [32], ALNS/ALNS+ [33], MACO [35], HGTS [34], GRASP + ILP [25], GVTNS [36], and HGA/HGA+ [37], and for the CLRPSPD, the approaches were BC-SA [38], SA/SA∗ [4], and RP/TS/FRR-MAB/FMT [2].Table 12
Average solutions for CLRP and CLRPSPD benchmark sets.
Algorithm
Barreto set
Prins set
Tuzun and Burke
AG
CPU
AG
CPU
AG
CPU
CLRP benchmark
GRASP + ELS
0.08a
187.6a
1.11
258.2
1.30
606.6
SALRP
0.48
464.1
0.46
422.4
1.49
826.4
SALRP+
0.08
NA
0.08
NA
0.53
NA
ALNS
0.16a
177.2a
0.44
451.1
0.43
829.6
ALNS+
0.06a
1772.0a
0.27
4221.0
0.18
8103.0
HGTS
0.78a
105.2a
0.57
176.4
1.14
392.3
MACO
0.17
191.7
0.40
191.3
1.23
201.9
GRASP + ILP
0.14a
264.3a
0.12
1163.0
0.17
2589.5
GVTNS
0.67a
53.0a
0.37
91.2
0.76
201.2
HGA
0.63
42.4
0.37
73.1
0.86
86.0
HGA+
0.00
429.6
0.32
199.1
0.70
363.6
TS-SA
−0.04
28.4
0.06
50.8
−0.01
77.6
QS2-SA
−0.07
24.6
0.07
47.7
0.01
74.5
AS-AM
−0.05
27.1
0.07
41.0
0.03
58.8
PS-AM
−0.04
16.5
0.07
33.6
0.01
52.5
CLRPSPD benchmark
BC-SA
1.47a
6604.1a
NA
NA
NA
NA
SA
0.48
1460.1
NA
NA
NA
NA
SA∗
0.21
NA
NA
NA
NA
NA
RP
0.08
32.2
0.07
60.2
0.21
83.4
TS
0.02
30.54
0.06
55.2
0.10
77.6
FRR-MAB
0.01
32.46
0.02
62.7
0.08
77.3
FMT
0.00
32.73
0.01
59.8
0.02
78.6
TS-SA
0.00
34.5
−0.17
64.1
0.10
83.3
QS2-SA
0.03
29.3
−0.12
59.8
0.16
82.1
AS-AM
0.01
28.0
−0.15
49.3
0.14
63.9
PS-AM
0.03
17.2
−0.16
39.3
0.21
55.3
aConsidering only (the same) 13 out of the 19 instances.Even though the time execution comparison can be unfair, depending on many factors (computer configuration, programming languages, the number of fitness evaluation, etc.), it is a significant performance indicator for judging the advantage of approaches. As shown in Table12, our four pairs of hyperheuristic seem to be the fastest among the above methods. Furthermore, our approaches are the among best in aspects of solution quality on all CLRP and CLRPSPD benchmark sets with very small gaps. In conclusion, we can strongly conclude that our hyperheuristics are able to outperform the most recent and effective methods in terms of either solution quality or computing time.


## 5.1. Experimental Design

The presented HH approach with 36 pairs is coded in Matlab 8.6 and runs on a desktop computer with Intel Core (TM) i7-6700K (4.00 GHz) and 8 GB RAM, under Windows 10; it is embedded in the CLOR tool, available by emailing to us.As far as calibration is considered, two types of parameters are concerned: specific selection strategy parameters and common hyperheuristic parameters. The former relates to the setting of selection strategies, while the latter accounts for the common parameters between LLHs and HLH, and they are summarized in Table2.Table 2
Configuration for each selection strategy.
Strategies
Parameters
Values
Common parameters
FRR-MAB
Scaling factorC
0.5 [7]
Initial probabilityp=0.5
Sliding windows sizeW
25 [56]
Population sizeSLLH = 1 (single-point search)
QS/QS2
Initial rotation angle, Δθ0
0.02π
Population sizeSHLH = 1 (only one individual)
Initial probability amplitudesα, β
0.7071 [74]
Maximum fitness evaluationαmax (Eq. 29)
AS/AS2
Initial pheromone,τij/τi
0
Maximum iterationtmax = 106
Initial visibility,ηij/ηi
0
Evaporation rate,ρ
0.2 [69]
PS
Learning factors,c1, c2
2 [72]
Inertia weight,w
1 [72]Some of the specified parameters follow defaults suggested in the literature, and others were determined by conducting an initial experiment with various settings aiming at obtaining relative better results within reasonable CPU time. As to common hyperheuristic parameters, initial selection probabilityp is set to 0.5 for each LLH in line with the initial probability amplitudes of QS; tabu list size lt is set to 7 which is the number of HCs; as single-point-based search hyperheuristic framework is investigated in this paper, the sizes of population used in the LLH and HLH are set at 1. For fairly comparing the running time of each pair, the maximum number of fitness evaluation for each instance is provided, which was different from the method in Ref. [2] (i.e., the maximum iterations without improving solution), depending directly on the number of clients, depots, and vehicles:(29)αmax=a×m+n+K2.Aiming at obtaining a good trade-off between solution quality and computing time, the multipliera is taking on the value 5 for all instances in this paper.


## 5.2. Benchmark Instances

Three sets of CLRP benchmark instances were adopted to evaluate the efficiency and features of each pair for hyperheuristic. These sets are provided in Refs. [26–28]. One separation approach is used to generate the datasets of CLRPSPD from the above CLRP benchmarks, instanced as W type in Ref. [92] with setting 0.8 for β.The first benchmark instances [28] contain 19 cases. The number of clients ranges from 12 to 318, and the number of depots m varies between 2 and 15, and the fixed vehicle cost fv is not given. In the randomly generated set [27], the number of clients ranges from 20 to 200, the number of depots m is 5 and 10, and vehicle capacity Q is {70, 150} and fv = 1000. The benchmark instances [26] are also randomly generated which contain 36 cases with n ∈ {100, 150, 200}, m ∈ {10, 20}, Q = 150, and fv = 10. And the clients’ demand of this benchmark ranges from 1 to 20. The above three benchmark sets are available at http://sweet.ua.pt/sbarreto/or_http://prodhonc.free.fr/homepage.Euclidean distances are applied in all datasets. In Prins et al. benchmark set for CLRPSPD, the obtained distances are multiplied by 100 (rounded up to the next integer in CLRP) and the total costs are rounded up to the next integer, which is different from the sets obtained in Refs. [4, 38]. The working cost of vehicle for each instance with less than 100 clients in the first set increases to 20, namely, fv = 20.


## 5.3. Results

### 5.3.1. Experiment on 36 Pairs

The first set of experiment is performed to compare the performance of 36 pairs of hyperheuristics aiming at determining the first four outstanding pairs for the following experiments. Nine CLRP instances in Barreto set with the number of clients ranging from 50 to 318 were used to test performance of each pair, implementing fifty runs on each instance. The maximum number of fitness evaluation is set to 10000. Aiming at comparing and scoring for all pairs, formula (1) scoring system was adopted, which was used to rank the approaches by CHESC (Cross-domain Heuristic Search Challenge) before 2010 (http://www.asap.cs.nott.ac.uk/external/chesc2011/). The top eight approaches are given a score of 10, 8, 6, 5, 4, 3, 2, and 1 point for each problem from the best to the worst, successively [65]. The rest of the methods receive a score of 0. In this paper, the score of 10 points is assigned to the pairs which can exploit the best known solution (BKS), and the scores for the rest of pairs are similar to formula (1) scoring system. Therefore, 90 is the maximum overall score a pair can get.Experiment results are shown in Table3, where the overall scores of the best four pairs, nine selection strategies, and four acceptance criteria are provided. As can be seen from the results, HH performing AS-AM is the best clear winner, and PS-AM, QS2-SA, and TS-SA also outperform other pairs. The hyperheuristic using AS, FRR-MAB-TS, TS, and RP as selection components performs better than others regardless of the acceptance component, and several interesting conclusions can be drawn from the overall scores that (1) TS could promote better performance for selection strategies by excluding the LLHs with poor performance, when compared with the performance of selection strategies without TS, reaching an average improvement about score 25 point; (2) the performance of AS using 0/1 knapsack problem outperforms AS2 applying TSP, in other words, compared to the one laying ant pheromone trails at routes, the mechanism laying ant pheromone trails on vertices (i.e., LLHs) have a greater chance of success in guiding ants to select the promising sequence of LLHs; (3) PS-AM and QS2-SA ranks the second/third place in overall scores of pairings, even if the performance of PS/QS2 is barely satisfactory. From the last four scores of acceptance component regardless of the selection component, AM and SA rank, respectively, the first and second with a score 529 and 518, while the other two receive a score of 473 and 429, respectively.Table 3
The overall formula (1) scores for the top four pairs and strategies.
Pairs
Overall score
AS-AM
73
PS-AM
67
QS2-SA
66
TS-SA
65
RP
222
TS
229
FRR-MAB
204
FMT
233
QS
176
QS2
215
AS
242
AS2
212
PS
216
AM
529
NA
473
GD
429
SA
518Figure2 shows the box plot for the scores of nine selection strategies and four acceptance criteria. In the box plot, the minimum and maximum values obtained (excluding the outliers), the lower and upper quartiles, and median are shown.Figure 2
Box plots of scores for a statistical comparison of (a) selection strategies and (b) acceptance criteria.
(a)
(b)From such analysis and answering the first experiments, we identify AS-AM as the best pair considering most cases and scores, and additional PS-AM, QS2-SA, and TS-SA are also selected to conduct the following experiments.


### 5.3.2. Experiment on CLRP

The first four outstanding pairs were tested performing fifty runs on each instance, from which best found solution, gaps to BKS, and computing time are shown, providing the insufficient page space. Results for three CLRP benchmark instances are shown in Tables4–6. The first column of each table is the name of each instances, followed by BKS, and results concerning four pairs which contain best found results (Best), gap (in percentage) to the BKS, and average computing time in seconds (CPU). Average and median values for gaps and CPU are displayed in the last two rows.Table 4
Results for the CLRP instances in Barreto set.
Set
BKS
TS-SA
QS2-SA
AS-AM
PS-AM
Best
Gap
CPU
Best
Gap
CPU
Best
Gap
CPU
Best
Gap
CPU
P12-2
204.0
204.0
0.00
0.1
204.0
0.00
0.1
204.0
0.00
0.1
204.0
0.00
0.1
G21-5
424.9
424.9
0.00
0.4
424.9
0.00
0.4
424.9
0.00
0.4
424.9
0.00
0.3
G22-5
585.1
585.1
0.00
0.3
585.1
0.00
0.4
585.1
0.00
0.3
585.1
0.00
0.3
M27-5
3062.0
3062.0
0.00
0.6
3062.0
0.00
0.6
3062.0
0.00
0.5
3062.0
0.00
0.5
G29-5
512.1
512.1
0.00
0.6
512.1
0.00
0.6
512.1
0.00
0.5
512.1
0.00
0.5
G32-5
562.2
562.2
0.00
0.7
562.2
0.00
0.7
562.2
0.00
0.6
562.2
0.00
0.6
G32-5-2
504.3
504.3
0.00
0.6
504.3
0.00
0.7
504.3
0.00
0.6
504.3
0.00
0.5
G36-5
460.4
460.4
0.00
0.9
460.4
0.00
0.9
460.4
0.00
0.8
460.4
0.00
0.7
C50-5
565.6
565.6
0.00
2.0
565.6
0.00
2.2
565.6
0.00
1.8
565.6
0.00
1.6
P55-15
1112.1
1112.1
0.00
4.2
1112.1
0.00
5.2
1112.1
0.00
4.6
1112.8
0.06
4.2
C75-10
844.4
844.4
0.00
7.9
844.4
0.00
7.9
844.4
0.00
7.0
844.4
0.00
6.3
P85-7
1622.5
1622.5
0.00
9.6
1622.5
0.00
9.7
1622.5
0.00
8.6
1622.5
0.00
7.7
D88-8
355.8
355.8
0.00
7.0
355.8
0.00
6.3
355.8
0.00
6.5
355.8
0.00
5.9
C100-10
833.4
833.4
0.00
11.4
833.4
0.00
12.3
833.4
0.00
10.6
833.4
0.00
8.3
O117-14
12290.3
12290.3
0.00
18.3
12290.3
0.00
18.4
12290.3
0.00
16.4
12290.3
0.00
14.6
M134-8
5709.0
5709.0
0.00
32.7
5709.0
0.00
33.0
5709.0
0.00
29.9
5709.0
0.00
24.1
D150-10
43919.9
43919.9
0.00
42.7
43919.9
0.00
45.0
43919.9
0.00
38.3
43919.9
0.00
33.1
P318-4
7249.3a
4484.2
−0.50
156.4
4145.9
−0.56
110.0
3966.0
−0.59
126.8
3991.1
−0.58
78.8
P318-4-2
13070.0b
10866.5
−0.33
243.4
8293.0
−0.72
213.0
10269.4
−0.42
260.6
10905.1
−0.33
125.3
AV
68099.3
67837.8
−0.04
28.4
67684.6
−0.07
24.6
67779.1
−0.05
27.1
67813.9
−0.04
16.5
MD
0.00
4.2
0.00
5.2
0.00
4.6
0.00
4.2
Bold numbers are the best known solutions. Italic numbers are the minimum value among four obtained solutions. Underscore numbers are the obtained values less than the best known solutions.aResults minus 550000. bResults minus 650000.Table 5
Results for the CLRP instances in Prins set.
Set
BKS
TS-SA
QS2-SA
AS-AM
PS-AM
Best
Gap
CPU
Best
Gap
CPU
Best
Gap
CPU
Best
Gap
CPU
20-5-1
54793
54793
0.00
0.5
54793
0.00
0.5
54793
0.00
0.5
54793
0.00
0.5
20-5-1b
39104
39104
0.00
0.3
39104
0.00
0.3
39104
0.00
0.2
39104
0.00
0.2
20-5-2
48908
48908
0.00
0.5
48908
0.00
0.6
48908
0.00
0.4
48908
0.00
0.4
20-5-2b
37542
37542
0.00
0.3
37542
0.00
0.3
37542
0.00
0.3
37542
0.00
0.2
50-5-1
90111
90111
0.00
3.9
90111
0.00
4.1
90111
0.00
2.9
90111
0.00
2.6
50-5-1b
63242
63242
0.00
1.8
63242
0.00
2.0
63242
0.00
1.9
63242
0.00
1.7
50-5-2
88298
88298
0.00
4.2
88298
0.00
4.3
88298
0.00
3.6
88298
0.00
3.4
50-5-2b
67308
67373
0.10
2.1
67308
0.00
2.1
67449
0.21
1.7
67308
0.00
1.5
50-5-2bis
84055
84055
0.00
3.5
84055
0.00
3.7
84055
0.00
3.1
84055
0.00
2.9
50-5-2bbis
51822
51822
0.00
2.4
51822
0.00
2.5
51822
0.00
2.1
51822
0.00
2.0
50-5-3
86203
86203
0.00
3.9
86203
0.00
4.3
86203
0.00
3.4
86203
0.00
3.1
50-5-3b
61830
61830
0.00
1.9
61830
0.00
1.9
61830
0.00
1.6
61830
0.00
1.6
100-5-1
274814
276096
0.47
28.9
276144
0.48
30.9
275601
0.29
25.8
275598
0.29
22.6
100-5-1b
213615
213654
0.02
14.1
213654
0.02
13.5
213671
0.03
12.2
213654
0.02
10.9
100-5-2
193671
193671
0.00
35.1
193671
0.00
34.4
193671
0.00
26.6
193671
0.00
26.0
100-5-2b
157095
157129
0.02
14.1
157144
0.03
15.2
157110
0.01
13.8
157129
0.02
12.3
100-5-3
200079
200079
0.00
34.3
200079
0.00
34.5
200079
0.00
25.7
200079
0.00
26.8
100-5-3b
152441
152441
0.00
13.8
152441
0.00
13.0
152441
0.00
12.3
152441
0.00
11.3
100-10-1
287695
287688
0.00
31.7
287688
0.00
32.8
287688
0.00
27.4
287688
0.00
25.4
100-10-1b
230989
231608
0.27
17.6
231833
0.37
16.7
231833
0.37
11.1
232222
0.53
13.8
100-10-2
243590
243590
0.00
28.6
243590
0.00
29.2
243590
0.00
24.4
243590
0.00
22.0
100-10-2b
203988
203988
0.00
15.7
203988
0.00
17.4
203988
0.00
15.5
203988
0.00
14.1
100-10-3
250882
252890
0.80
33.8
252890
0.80
33.2
252751
0.74
27.9
252890
0.80
27.2
100-10-3b
204317
204567
0.12
15.8
204567
0.12
15.4
204567
0.12
13.8
204567
0.12
12.9
200-10-1
475294
475770
0.10
268.1
476166
0.18
263.8
476002
0.15
219.6
476722
0.30
190.0
200-10-1b
377043
375820
−0.32
135.0
376313
−0.19
121.4
376662
−0.10
96.7
375836
−0.32
91.0
200-10-2
449006
449037
0.01
250.9
449142
0.03
236.7
449332
0.07
210.4
449110
0.02
132.4
200-10-2b
374280
373882
−0.11
153.0
373973
−0.08
151.1
374039
−0.06
125.8
374093
−0.05
110.6
200-10-3
469433
470780
0.29
247.8
471043
0.34
223.1
471043
0.34
208.2
471073
0.35
124.8
200-10-3b
362653
362276
−0.10
161.2
362349
−0.08
122.0
362596
−0.02
110.0
362640
0.00
113.1
AV
196470
196608
0.06
50.8
196663
0.07
47.7
196667
0.07
41.0
196674
0.07
33.6
MD
196875
0.00
14.9
0.00
15.3
0.00
13.1
0.00
12.6
Bold numbers are the best known solutions. Italic numbers are the minimum value among four obtained solutions. Underscore numbers are the obtained values less than the best known solutions.Table 6
Results for the CLRP instances in Tuzun and Burke.
Set
BKS
TS-SA
QS2-SA
AS-AM
PS-AM
Best
Gap
CPU
Best
Gap
CPU
Best
Gap
CPU
Best
Gap
CPU
P1
1467.68
1467.68
0.00
15.2
1467.68
0.00
15.4
1467.68
0.00
13.0
1467.68
0.00
11.6
P2
1449.20
1448.37
−0.06
20.4
1449.20
0.00
20.1
1449.20
0.00
17.6
1448.37
−0.06
14.7
P3
1394.80
1394.80
0.00
15.1
1394.80
0.00
16.4
1394.93
0.01
14.2
1394.80
0.00
12.3
P4
1432.29
1432.29
0.00
20.7
1432.29
0.00
20.9
1432.29
0.00
17.6
1432.29
0.00
15.4
P5
1167.16
1167.16
0.00
14.5
1167.16
0.00
15.7
1167.16
0.00
13.2
1167.16
0.00
12.0
P6
1102.24
1102.24
0.00
19.0
1102.24
0.00
18.8
1102.24
0.00
16.2
1102.24
0.00
14.5
P7
791.66
791.66
0.00
15.6
791.66
0.00
15.8
791.66
0.00
13.4
791.66
0.00
12.6
P8
728.30
728.30
0.00
17.8
728.30
0.00
17.6
728.30
0.00
15.4
728.30
0.00
12.9
P9
1238.24
1238.49
0.02
16.6
1238.49
0.02
15.9
1238.49
0.02
14.6
1238.49
0.02
13.6
P10
1245.31
1245.31
0.00
23.9
1245.42
0.01
27.6
1245.31
0.00
18.1
1245.31
0.00
15.5
P11
902.26
902.26
0.00
15.3
902.26
0.00
15.4
902.26
0.00
12.9
902.26
0.00
11.9
P12
1018.29
1018.29
0.00
17.9
1018.29
0.00
18.2
1018.29
0.00
15.6
1018.29
0.00
12.7
P13
1866.75
1895.83
1.56
61.8
1895.83
1.56
63.1
1892.17
1.36
53.6
1895.83
1.56
52.9
P14
1823.20
1820.12
−0.17
62.1
1822.69
−0.03
61.3
1822.15
−0.06
53.8
1822.69
−0.03
42.1
P15
1964.30
1965.12
0.04
57.0
1965.12
0.04
57.9
1965.12
0.04
48.9
1965.12
0.04
42.6
P16
1792.80
1792.77
−0.00
70.9
1792.77
−0.00
69.9
1792.77
−0.00
66.9
1792.77
−0.00
55.3
P17
1443.33
1443.32
−0.00
58.6
1443.32
−0.00
64.5
1443.32
−0.00
53.7
1443.32
−0.00
51.3
P18
1434.60
1434.82
0.02
63.0
1433.16
−0.10
64.1
1433.49
−0.08
53.2
1431.24
−0.23
46.6
P19
1204.42
1204.42
0.00
63.5
1204.42
0.00
64.6
1204.42
0.00
57.1
1204.42
0.00
61.7
P20
930.99
927.63
−0.36
64.3
931.28
0.03
65.6
931.28
0.03
54.3
929.26
−0.19
43.8
P21
1694.18
1694.18
0.00
71.3
1694.18
0.00
64.2
1694.18
0.00
55.3
1694.18
0.00
52.1
P22
1392.01
1392.01
0.00
61.6
1392.18
0.01
64.6
1392.01
0.00
53.1
1392.01
0.00
49.3
P23
1198.20
1197.95
−0.02
57.5
1197.95
−0.02
57.2
1197.95
−0.02
48.3
1197.95
−0.02
40.8
P24
1151.80
1151.80
0.00
72.1
1151.80
0.00
73.1
1151.80
0.00
61.2
1151.80
0.00
52.9
P25
2243.40
2237.73
−0.25
136.6
2240.37
−0.14
131.1
2244.64
0.06
91.2
2244.79
0.06
84.9
P26
2138.40
2139.67
0.06
137.9
2139.67
0.06
130.1
2144.49
0.28
102.5
2141.09
0.13
73.2
P27
2209.30
2204.93
−0.20
178.8
2208.48
−0.04
151.4
2209.36
0.00
110.0
2207.69
−0.07
96.1
P28
2222.90
2226.50
0.16
160.4
2223.61
0.03
150.3
2228.27
0.24
113.2
2221.59
−0.06
110.4
P29
2073.70
2074.86
0.06
137.7
2079.96
0.30
130.6
2076.16
0.12
100.4
2077.01
0.16
88.9
P30
1692.17
1685.65
−0.39
135.8
1685.65
−0.39
129.5
1687.38
−0.28
102.6
1685.78
−0.38
80.6
P31
1453.18
1449.96
−0.22
175.1
1449.46
−0.26
153.4
1450.90
−0.16
114.8
1453.89
0.05
100.4
P32
1082.46
1082.46
0.00
167.3
1082.46
0.00
152.6
1082.46
0.00
108.5
1082.46
0.00
111.2
P33
1954.70
1949.29
−0.28
126.3
1950.60
−0.21
127.8
1947.84
−0.35
112.6
1949.38
−0.27
78.6
P34
1918.93
1916.18
−0.14
137.4
1911.73
−0.38
129.6
1917.98
−0.05
91.7
1912.61
−0.33
82.5
P35
1762.00
1760.60
−0.08
155.6
1761.22
−0.04
161.1
1760.04
−0.11
117.3
1760.63
−0.08
113.3
P36
1390.87
1390.87
0.00
167.3
1390.87
0.00
148.2
1390.87
0.00
111.1
1390.94
0.01
117.5
AV
1499.33
1499.32
−0.01
77.6
1499.63
0.01
74.5
1499.97
0.03
59.6
1499.59
0.01
52.5
MD
1439.07
0.00
62.6
0.00
64.4
0.00
53.8
0.00
50.3
Bold numbers are the best known solutions. Italic numbers are the minimum value among four obtained solutions. Underscore numbers are the obtained values less than the best known solutions.For the first three pairs (Table4), the BKSs of instances with less than 150 clients are exploited with average gap at −0.04% for TS-SA, −0.07% for QS2-SA, and −0.05% for AS-AM. Only one BKS cannot be found by the last pair with highest gap at 0.06% and average value at −0.04%. Concerning the median values of gaps to BKS, they take on the value 0. Computing times are on average less than 29, 25, 27, and 17 s, and median values are lower than 6 s even if the largest instances exist. Two new BKS are found by four pairs, obtaining an improvement of over 0.5% for Perl83-318 × 4 by PS-AM and over 0.7% for Perl83-318 × 4-2 by QS2-SA.In the second benchmark (Table5), at least 16 BKS can be found by the four pairs, with difference in finding the Best of 50-5-2b. Four new BKSs in this set are obtained, respectively, reaching an improvement of over 0.3% for 200-10-1b by TS-SA and PS-AM and 0.1% for 200-10-2b and 200-10-3b by TS-SA. Concerning gaps of Best, average values are, respectively, 0.06% for TS-SA and 0.07% for other pairs, and the highest gaps are less than 0.8% for four pairs. Median values equal to 0 for all pairs. Average and median values for CPU are, respectively, 50.8 and 14.9 s for TS-SA, 47.7 and 15.3 s for QS2-SA, 41 and 13.1 s for AS-AM, and 33.6 and 12.6 s for PA-AM.For the Tuzun and Burke benchmark (Table6), TS-SA and PS-AM tie for first place in the number of new BKS found with 13 new BKSs, and QS2-SA tails the winner to take the second place by exploiting 12 new BKSs and AS-AM is in the last place. Concerning the number of solution less than or equal to BKS, TS-SA, PS-AM, and QS2-SA, respectively, rank the first, second, and third with 29, 28, and 27 solutions less than or equal to BKS, and AS-AM ranks the last place with 26 solutions less than or equal to BKS. What surprised us is that the number of new BKS accounts for over 30%, except for AS-AM with 27.8% of 36 instances in this benchmark. Concerning gaps of Best, average values are, respectively, −0.01% for TS-SA, 0.01% for QS2-SA and PS-AM, and 0.03% for SA-AM, and median values are 0 for all pairs. Computing times are on average 77.6, 74.5, 59.6, and 52.5 s, and median values are 62.6, 64.4, 53.8, and 50.3 s.We conduct statistical analysis for obtained results of three CLRP benchmark sets in Tables4–6 through Table 7 based on multiple pairwise comparisons with 95% confidence level (i.e., α = 0.05), namely, Friedman tests. In the Friedman test, the null hypothesis (H0) is only rejected if the Friedman statistic (χ2) is greater than the critical value, looking up in χ2 table through sample size and confidence level, and post hoc test based on Wilcoxon Rank-Sum should be carried out to detect the significant difference among samples, when needed; otherwise, the null hypothesis (H0) is accepted indicating that no significant difference is concerned among four pairs. In Table 7, Friedman statistics (χ2) take the values 3.923 for Barreto et al., 6.750 for Prins et al., and 6.201 for Tuzun and Burke, which are, respectively, lower than 10.117, 18.493, and 23.269, indicating that there is no significant difference among performance of four pairs.Table 7
Friedman’s test results for CLRP benchmark instances (α = 0.05).
Benchmark
Mean ranks for four pairs
Test statistics
Conclusion
TS-SA
QS2-SA
AS-AM
PS-AM
n
χ
2
df
p
Barreto set
2.58
2.42
2.37
2.63
19
3.923
3
0.270
χ
2 < critical value, accept H0
Prins set
2.18
2.58
2.60
2.63
30
6.750
3
0.080
Tuzun and Burke
2.19
2.61
2.65
2.54
36
6.201
3
0.102


### 5.3.3. Experiment on CLRPSPD

The CLRPSPD benchmark instances, which were first converted in Refs. [2, 38], were also used to evaluate the features of the best four pairs. However, this paper only considered the W type of the above sets for the CLRPSPD. The main reason is that the sets of X, Y, and Z types show the same characteristics with the original sets of CLRP, and it is most difficult to obtain BKSs for the instances using W type separation approach. All BKSs were obtained from Ref. [1]. Results for the three CLRPSPD benchmark instances are shown in Tables 8–10. The first column of each table is the name of each instances, followed by the best known solution (BKS), data concerning the first four best pairs which contain best results (Best), gap (in percentage) to the BKS, and average computing time in seconds (CPU). Average (AV) and median values (MD)for gaps or gap and CPU are displayed in the last two rows.Table 8
Results for the CLRPSPD instances in Barreto set.
Instance
BKS
TS-SA
QS2-SA
AS-AM
PS-AM
Best
Gap
CPU
Best
Gap
CPU
Best
Gap
CPU
Best
Gap
CPU
P12-2
243.98
243.98
0.00
0.1
243.98
0.00
0.1
243.98
0.00
0.1
243.98
0.00
0.1
G21-5
528.42
528.42
0.00
0.4
528.42
0.00
0.5
528.42
0.00
0.3
528.42
0.00
0.3
G22-5
653.8
653.80
0.00
0.3
653.80
0.00
0.4
653.80
0.00
0.3
653.80
0.00
0.2
M27-5
3142.02
3142.02
0.00
0.6
3142.02
0.00
0.7
3142.02
0.00
0.5
3142.02
0.00
0.5
G29-5
592.1
592.10
0.00
0.6
592.10
0.00
0.6
592.10
0.00
0.4
592.10
0.00
0.4
G32-5
696.38
696.38
0.00
0.9
696.38
0.00
1.0
696.38
0.00
0.8
696.38
0.00
0.7
G32-5-2
595.27
595.27
0.00
0.7
595.27
0.00
0.8
595.27
0.00
0.6
595.27
0.00
0.6
G36-5
540.37
540.37
0.00
0.9
540.37
0.00
1.0
540.37
0.00
0.7
540.37
0.00
0.7
C50-5
708.37
708.37
0.00
1.9
708.37
0.00
2.0
708.37
0.00
1.5
708.37
0.00
1.4
P55-15
1327.06
1327.06
0.00
3.9
1327.06
0.00
4.0
1327.06
0.00
3.4
1327.06
0.00
3.1
C75-10
1132.8
1132.80
0.00
8.4
1135.61
0.25
8.6
1135.61
0.25
7.2
1137.59
0.42
6.1
P85-7
1855.55
1855.55
0.00
12.2
1855.55
0.00
12.4
1855.55
0.00
10.3
1855.55
0.00
6.3
D88-8
497.6
497.98
0.08
7.1
497.98
0.08
7.4
497.60
0.00
6.4
497.98
0.08
5.8
C100-10
1011.53
1011.53
0.00
13.7
1013.12
0.16
14.0
1011.53
0.00
11.4
1011.53
0.00
10.6
O117-14
12350.2
12350.20
0.00
17.4
12350.20
0.00
17.2
12350.20
0.00
15.3
12350.20
0.00
13.3
M134-8
5913.51
5913.51
0.00
28.5
5922.38
0.15
29.8
5913.51
0.00
24.8
5922.38
0.15
21.2
D150-10
44955.31
44955.31
0.00
46.6
44955.31
0.00
42.2
44960.92
0.01
37.2
44955.31
0.00
35.7
P318-4
4650.09a
4650.85a
0.00
199.7
4650.85a
0.00
144.9
4650.85a
0.00
151.3
4650.85a
0.00
105.0
P318-4-2
6435.73b
6435.73
b
0.00
310.7
6435.73
b
0.00
268.2
5633.50
b
−0.11
259.9
5633.50
b
−0.11
114.6
AV
72362.55
70938.49
0.00
34.5
70939.18
0.03
29.3
70896.69
0.01
28.0
70896.98
0.03
17.2
MD
0.00
3.9
0.00
4.00
0.00
3.4
0.00
3.1
Bold numbers are the best known solutions. Underscore and italic numbers are the obtained values less than the best known solutions.aResults minus 560000. bResults minus 700000.Table 9
Results for the CLRPSPD instances in Prins set.
Instance
BKS
TS-SA
QS2-SA
AS-AM
PS-AM
Best
Gap
CPU
Best
Gap
CPU
Best
Gap
CPU
Best
Gap
CPU
20-5-1
56350
56350
0.00
0.5
56350
0.00
0.5
56350
0.00
0.3
56350
0.00
0.3
20-5-1b
40678
40678
0.00
0.3
40678
0.00
0.3
40678
0.00
0.2
40678
0.00
0.2
20-5-2
49712
49712
0.00
0.5
49712
0.00
0.6
49712
0.00
0.3
49712
0.00
0.3
20-5-2b
38357
38357
0.00
0.3
38357
0.00
0.3
38357
0.00
0.2
38357
0.00
0.2
50-5-1
100240
100240
0.00
4.0
100240
0.00
4.1
100240
0.00
3.4
100240
0.00
3.1
50-5-1b
68993
68993
0.00
1.8
68993
0.00
2.3
68993
0.00
2.1
68993
0.00
1.8
50-5-2
94280
94280
0.00
5.1
94280
0.00
5.2
94280
0.00
4.4
94280
0.00
3.1
50-5-2b
69123
69123
0.00
2.7
69123
0.00
2.7
69123
0.00
2.2
69123
0.00
2.0
50-5-2bis
86349
86349
0.00
4.0
86349
0.00
4.0
86349
0.00
3.5
86349
0.00
3.3
50-5-2bbis
52356
52356
0.00
2.8
52356
0.00
2.6
52356
0.00
2.3
52356
0.00
2.1
50-5-3
90419
90419
0.00
4.9
89737
−0.75
4.7
90419
0.00
3.4
90419
0.00
3.8
50-5-3b
62178
62178
0.00
2.0
62178
0.00
2.1
62178
0.00
1.7
62178
0.00
1.6
100-5-1
290168
290280
0.04
43.5
290280
0.04
46.6
290401
0.08
38.7
290505
0.12
34.1
100-5-1b
219199
223968
2.18
18.9
223966
2.17
18.6
223968
2.18
16.9
223966
2.17
18.0
100-5-2
206049
206170
0.06
32.9
206078
0.01
36.7
206170
0.06
30.2
206308
0.13
29.8
100-5-2b
162077
162083
0.00
15.1
162077
0.00
15.7
162077
0.00
13.4
162077
0.00
12.1
100-5-3
209142
209142
0.00
43.2
209142
0.00
41.5
209142
0.00
34.5
209142
0.00
30.6
100-5-3b
156971
157027
0.04
16.2
157027
0.04
15.9
157027
0.04
14.4
157027
0.04
12.2
100-10-1
326093
326093
0.00
40.5
326093
0.00
40.8
326093
0.00
35.1
326093
0.00
30.8
100-10-1b
272889
272889
0.00
21.8
272889
0.00
21.6
272889
0.00
18.5
272889
0.00
14.1
100-10-2
253074
253609
0.21
39.4
253096
0.01
40.5
253640
0.22
34.1
253074
0.00
29.6
100-10-2b
208941
208941
0.00
20.9
208944
0.00
21.8
208941
0.00
18.9
208941
0.00
16.5
100-10-3
268137
268451
0.12
41.3
268416
0.10
39.0
268531
0.15
35.7
268349
0.08
32.6
100-10-3b
214828
214828
0.00
16.0
214828
0.00
17.9
214828
0.00
15.5
214828
0.00
13.5
200-10-1
529512
498257
−5.90
334.6
498451
−5.87
306.0
499084
−5.75
233.5
498066
−5.94
187.8
200-10-1b
393699
384277
−2.39
195.2
393924
0.06
170.2
385287
−2.14
155.7
385737
−2.02
135.7
200−10-2
463637
463968
0.07
316.4
463913
0.06
282.1
464111
0.10
249.2
464031
0.08
178.3
200-10-2b
380670
380924
0.07
206.4
380833
0.04
173.4
381031
0.09
138.5
380611
−0.02
117.0
200-10-3
485379
485882
0.10
307.9
485946
0.12
304.5
486009
0.13
240.8
486134
0.16
162.3
200-10-3b
369201
369938
0.20
183.3
370303
0.30
171.8
370213
0.27
131.5
370412
0.33
101.6
AV
206192
−0.17
64.1
206485
−0.12
59.8
206283
−0.15
49.3
206241
−0.16
39.3
MD
0.00
17.6
0.00
18.3
0.00
16.2
0.00
13.8
Bold numbers are the minimum value among four obtained solutions. Underscore and italic numbers are the obtained values less than the best known solutions.Table 10
Results for the CLRPSPD instances in Tuzun and Burke.
Case
BKS
TS-SA
QS2-SA
AS-AM
PS-AM
Best
Gap
CPU
Best
Gap
CPU
Best
Gap
CPU
Best
Gap
CPU
P1
1504.45
1504.45
0.00
18.8
1504.45
0.00
19.5
1504.45
0.00
16.5
1504.86
0.03
14.2
P2
1474.33
1474.33
0.00
19.5
1474.33
0.00
18.8
1474.33
0.00
17.2
1474.33
0.00
14.4
P3
1414.35
1414.46
0.01
17.6
1415.13
0.06
17.5
1414.35
0.00
15.4
1414.35
0.00
13.2
P4
1477.49
1481.50
0.27
20.3
1484.29
0.46
19.5
1477.49
0.00
18.2
1477.49
0.00
15.1
P5
1230
1233.69
0.30
18.9
1233.24
0.26
18.6
1227.89
−0.17
16.5
1233.54
0.29
14.7
P6
1123.72
1123.72
0.00
17.9
1123.72
0.00
19.2
1123.72
0.00
16.6
1123.72
0.00
12.2
P7
812.42
812.42
0.00
18.8
812.42
0.00
22.0
812.42
0.00
16.3
812.42
0.00
15.0
P8
752.66
751.89
−0.10
24.0
754.15
0.20
23.3
752.41
−0.03
19.0
759.21
0.87
11.6
P9
1273.3
1273.30
0.00
18.8
1273.30
0.00
19.2
1273.30
0.00
15.8
1273.30
0.00
14.5
P10
1265.1
1265.10
0.00
22.5
1265.02
−0.01
22.8
1266.20
0.09
20.0
1265.10
0.00
17.4
P11
911.52
911.52
0.00
20.3
911.52
0.00
18.4
911.52
0.00
16.8
911.52
0.00
15.4
P12
1033.38
1031.94
−0.14
23.5
1033.38
0.00
22.6
1033.27
−0.01
20.2
1033.38
0.00
18.1
P13
1943.41
1947.92
0.23
59.1
1946.58
0.16
58.5
1949.76
0.33
49.9
1947.98
0.24
41.9
P14
1848.69
1848.69
0.00
66.1
1856.10
0.40
67.4
1859.17
0.57
58.4
1862.25
0.73
46.4
P15
2011.29
2011.32
0.00
67.7
2011.39
0.00
71.3
2016.29
0.25
58.5
2012.29
0.05
49.1
P16
1856.03
1861.73
0.31
63.5
1859.97
0.21
69.8
1862.65
0.36
59.4
1859.32
0.18
47.5
P17
1479.77
1484.97
0.35
69.3
1490.83
0.75
69.3
1483.73
0.27
58.7
1491.36
0.78
48.9
P18
1452.49
1453.05
0.04
67.1
1453.58
0.08
68.4
1452.28
−0.01
58.6
1452.73
0.02
47.8
P19
1228.49
1228.11
−0.03
60.6
1228.52
0.00
61.3
1228.49
0.00
53.9
1228.69
0.02
47.5
P20
949.82
949.82
0.00
68.3
951.62
0.19
68.7
950.06
0.03
58.9
949.82
0.00
45.7
P21
1732.81
1736.52
0.21
60.9
1736.45
0.21
61.9
1737.80
0.29
53.2
1735.63
0.16
42.9
P22
1426.41
1426.45
0.00
76.6
1426.66
0.02
77.4
1427.57
0.08
64.6
1425.37
−0.07
57.6
P23
1238.78
1229.69
−0.73
70.0
1226.08
−1.03
69.6
1229.69
−0.73
59.0
1229.69
−0.73
49.4
P24
1166.8
1166.80
0.00
64.0
1166.80
0.00
66.3
1166.80
0.00
57.0
1166.80
0.00
51.4
P25
2338.89
2343.12
0.18
153.2
2339.54
0.03
146.9
2343.64
0.20
102.4
2351.63
0.54
76.7
P26
2224.86
2226.41
0.07
177.6
2240.00
0.68
173.0
2238.67
0.62
122.9
2228.80
0.18
115.1
P27
2293.85
2298.34
0.20
175.9
2298.04
0.18
178.3
2297.87
0.18
115.3
2302.65
0.38
112.1
P28
2292.91
2303.17
0.45
154.4
2303.63
0.47
147.1
2301.04
0.35
107.2
2307.62
0.64
95.8
P29
2159.62
2163.17
0.16
160.2
2158.57
−0.05
159.8
2159.83
0.01
110.2
2169.93
0.48
89.4
P30
1727.67
1731.95
0.25
175.1
1733.80
0.35
172.7
1729.77
0.12
132.2
1729.04
0.08
103.6
P31
1483.34
1486.36
0.20
172.0
1484.89
0.10
171.2
1484.87
0.10
116.8
1486.35
0.20
114.3
P32
1101.65
1102.31
0.06
149.0
1102.29
0.06
138.4
1103.93
0.21
96.7
1102.44
0.07
100.5
P33
2001.36
2002.82
0.07
154.9
2003.39
0.10
147.4
2002.79
0.07
129.5
2003.16
0.09
75.5
P34
1973.43
1975.63
0.11
164.1
1977.83
0.22
165.5
1981.09
0.39
115.5
1982.10
0.44
107.9
P35
1801.82
1810.44
0.48
177.9
1825.68
1.32
164.5
1826.61
1.38
130.4
1822.02
1.12
148.1
P36
1418.8
1425.63
0.48
151.5
1423.96
0.36
140.0
1422.24
0.24
123.9
1432.10
0.94
101.2
Av.
1541.47
0.10
83.3
1542.53
0.16
82.1
1542.44
0.14
63.9
1543.42
0.21
55.3
MD.
0.05
66.6
0.09
68.6
0.08
58.6
0.08
47.7
Bold numbers are the minimum value among four obtained solutions. Underscore and italic numbers are the obtained values less than the best known solutions. The instances are represented by “PN,” whereN represents the serial number.For the Barreto benchmark set, computing times are on average lower than 35, 30, 29, and 18 s and median values are 3.9, 4, 3.4, and 3.1 s, respectively. Concerning gaps of Best, average values are, respectively, 0, 0.03%, 0.01%, and 0.03%, and median values equal to 0. New BKSs for instance with 318 clients are found with an improvement of 0.11% to previous BKS by AS-AM and PS-AM. Gaps to BKS are very low for all instances with highest gaps lower than 0.08% for the first pair, 0.25% for the second and third pairs, and 0.42% for the last one.Looking at Table9, computing times are on average less than 65, 60, 50, and 40 s, respectively, and median values are, respectively, 17.6, 18.3, 16.2, and 13.8 s. Concerning gaps to BKSs, average and median values are, respectively, −0.17% and 0 for TS-SA, −0.12% and 0 for QS2-SA, −0.15 and 0 for third pair, and −0.16 and 0 for the last pair. From the perspective of gaps to BKSs, we verified the solutions achieved in Ref. [2]. Meanwhile, we obtained four improvements for four instances, i.e., 50-5-3 (QS2-SA), 200-10-1 (four pairs), 200-10-1b (four pairs except for QS2-SA), and 200-10-2b (PS-AM), one of them reaching an improvement of over 5.9% to previous BKSs.As shown in Table10, the computing times are on average less than 84, 83, 64, and 56 s, and median values are 66.6, 68.6, 58.6, and 47.7 s, respectively. As far as gap to BKS is concerned, average/median values are 0.1/0.05%, 0.16/0.09%, 0.14/0.08%, and 0.21/0.08%, respectively. Meanwhile, new BKSs of nine instances were obtained by our proposed algorithms, and the largest improvement was over 1% for P23 obtained by QS2-SA. The AS-AM outperformed others obtaining five new BKSs, followed by TS-SA and QS2-SA, and PS-AM performed the worst. However, the best-performing pairs was TS-SA in terms of average gap to BKSs.Statistical analysis is carried out for obtained results of three sets in Tables8–10 through Table 11 based on Friedman test. In Table 11, Friedman statistics (χ2) take the values 3.279 for Barreto et al., 4.621 for Prins et al., and 4.087 for Tuzun and Burke, which are, respectively, lower than 10.117, 18.493, and 23.269, indicating that there is no significant difference among the performance of four pairs. Therefore, we can strongly conclude that the proposed pairs could achieve high-quality solutions for the CLRPSPD benchmark instances.Table 11
Friedman’s test results for CLRPSPD benchmark instances (α = 0.05).
Benchmark
Mean ranks for four pairs
Test statistics
Conclusion
TS-SA
QS2-SA
AS-AM
PS-AM
n
χ
2
df
p
Barreto set
2.39
2.68
2.37
2.55
19
3.279
3
0.351
χ
2 < critical value, accept H0
Prins set
2.42
2.33
2.77
2.48
30
4.621
3
0.202
Tuzun and burke
2.25
2.51
2.44
2.79
36
4.087
3
0.252Overall, among the four pairs, two types of discussion and conclusions are conducted: one for problem domains and one for hyperheuristic pairs. From perspective of both subjects, the amount of CPU time depends directly on the number of clients (n), depots (m), and vehicle capacity (Q), and the relationship between running time and each of above factors is drawn in Figures 3 and 4 (excluding the outliers) and Figure 5. Several conclusions on running time are reached: (1) running time is affected by the number of clients in exponential way; (2) number of depots has slight impact on the running time, which may be resulted by few depots; (3) computing time increases with the decrease of the vehicle capacity in the form of polynomial; (4) the order of impact of the above factors effecting the running time is n, Q, and m. The first and third conclusions were also shared in Ref. [2]. Moreover, the time complexity and solution quality may depend in part on the complexity of the mathematical model. Figure 6 illustrates the impact of complexity of mathematical model on the running time. More specifically, the average computing time of tackling CLRPSPD instances increases by 4.2–21.5% for Barreto set, 30.6–46.8% for Prins set, and 5.3–10.2% for Tuzun and Burke, respectively, compared with the average running times of tackling CLRP cases. Concerning solution quality and average standard deviation, the complexity of instances is the direct acting factor consisting of the number of clients, depots and vehicles, and the distribution of clients and depots. Furthermore, the complexity of approaches or pairs of selection strategies and acceptance criteria also significantly influence the running time, standard deviation, and solution quality. PS-AM seems to be among the fastest with declining 36, 33, and 20% average running time compared to others, and AS-AM and QS2-SA rank the second and third in aspects of average running time. In terms of solutions quality, there is no significant difference among these four pairs concluded by the above Friedman tests, indicating that PS-AM and AS-AM outperform the others in obtaining a better trade-off solution quality and running time, but all pairs can obtain high solution quality within reasonable running time.Figure 3
Box plots for relationship between computing time and number of clients.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)Figure 4
Box plots for relationship between computing time and number of depots.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)Figure 5
Histogram of computing times of different vehicle capacity.
(a)
(b)
(c)
(d)Figure 6
Histogram of computing times of both subjects.
(a)
(b)
(c)
(d)


### 5.3.4. Comparison and Evaluation

To illustrate advantages of our proposed approaches for CLRP and CLRPSPD, comparisons with the most recent and effective methods in the literature are carried out in Table12, where average gaps (AG) of best found solutions to BKS and average running time of the proposed approaches for the CLRP are provided, and they are, respectively, GRASP + ELS [31], SALRP/SALRP+ [32], ALNS/ALNS+ [33], MACO [35], HGTS [34], GRASP + ILP [25], GVTNS [36], and HGA/HGA+ [37], and for the CLRPSPD, the approaches were BC-SA [38], SA/SA∗ [4], and RP/TS/FRR-MAB/FMT [2].Table 12
Average solutions for CLRP and CLRPSPD benchmark sets.
Algorithm
Barreto set
Prins set
Tuzun and Burke
AG
CPU
AG
CPU
AG
CPU
CLRP benchmark
GRASP + ELS
0.08a
187.6a
1.11
258.2
1.30
606.6
SALRP
0.48
464.1
0.46
422.4
1.49
826.4
SALRP+
0.08
NA
0.08
NA
0.53
NA
ALNS
0.16a
177.2a
0.44
451.1
0.43
829.6
ALNS+
0.06a
1772.0a
0.27
4221.0
0.18
8103.0
HGTS
0.78a
105.2a
0.57
176.4
1.14
392.3
MACO
0.17
191.7
0.40
191.3
1.23
201.9
GRASP + ILP
0.14a
264.3a
0.12
1163.0
0.17
2589.5
GVTNS
0.67a
53.0a
0.37
91.2
0.76
201.2
HGA
0.63
42.4
0.37
73.1
0.86
86.0
HGA+
0.00
429.6
0.32
199.1
0.70
363.6
TS-SA
−0.04
28.4
0.06
50.8
−0.01
77.6
QS2-SA
−0.07
24.6
0.07
47.7
0.01
74.5
AS-AM
−0.05
27.1
0.07
41.0
0.03
58.8
PS-AM
−0.04
16.5
0.07
33.6
0.01
52.5
CLRPSPD benchmark
BC-SA
1.47a
6604.1a
NA
NA
NA
NA
SA
0.48
1460.1
NA
NA
NA
NA
SA∗
0.21
NA
NA
NA
NA
NA
RP
0.08
32.2
0.07
60.2
0.21
83.4
TS
0.02
30.54
0.06
55.2
0.10
77.6
FRR-MAB
0.01
32.46
0.02
62.7
0.08
77.3
FMT
0.00
32.73
0.01
59.8
0.02
78.6
TS-SA
0.00
34.5
−0.17
64.1
0.10
83.3
QS2-SA
0.03
29.3
−0.12
59.8
0.16
82.1
AS-AM
0.01
28.0
−0.15
49.3
0.14
63.9
PS-AM
0.03
17.2
−0.16
39.3
0.21
55.3
aConsidering only (the same) 13 out of the 19 instances.Even though the time execution comparison can be unfair, depending on many factors (computer configuration, programming languages, the number of fitness evaluation, etc.), it is a significant performance indicator for judging the advantage of approaches. As shown in Table12, our four pairs of hyperheuristic seem to be the fastest among the above methods. Furthermore, our approaches are the among best in aspects of solution quality on all CLRP and CLRPSPD benchmark sets with very small gaps. In conclusion, we can strongly conclude that our hyperheuristics are able to outperform the most recent and effective methods in terms of either solution quality or computing time.


## 5.3.1. Experiment on 36 Pairs

The first set of experiment is performed to compare the performance of 36 pairs of hyperheuristics aiming at determining the first four outstanding pairs for the following experiments. Nine CLRP instances in Barreto set with the number of clients ranging from 50 to 318 were used to test performance of each pair, implementing fifty runs on each instance. The maximum number of fitness evaluation is set to 10000. Aiming at comparing and scoring for all pairs, formula (1) scoring system was adopted, which was used to rank the approaches by CHESC (Cross-domain Heuristic Search Challenge) before 2010 (http://www.asap.cs.nott.ac.uk/external/chesc2011/). The top eight approaches are given a score of 10, 8, 6, 5, 4, 3, 2, and 1 point for each problem from the best to the worst, successively [65]. The rest of the methods receive a score of 0. In this paper, the score of 10 points is assigned to the pairs which can exploit the best known solution (BKS), and the scores for the rest of pairs are similar to formula (1) scoring system. Therefore, 90 is the maximum overall score a pair can get.Experiment results are shown in Table3, where the overall scores of the best four pairs, nine selection strategies, and four acceptance criteria are provided. As can be seen from the results, HH performing AS-AM is the best clear winner, and PS-AM, QS2-SA, and TS-SA also outperform other pairs. The hyperheuristic using AS, FRR-MAB-TS, TS, and RP as selection components performs better than others regardless of the acceptance component, and several interesting conclusions can be drawn from the overall scores that (1) TS could promote better performance for selection strategies by excluding the LLHs with poor performance, when compared with the performance of selection strategies without TS, reaching an average improvement about score 25 point; (2) the performance of AS using 0/1 knapsack problem outperforms AS2 applying TSP, in other words, compared to the one laying ant pheromone trails at routes, the mechanism laying ant pheromone trails on vertices (i.e., LLHs) have a greater chance of success in guiding ants to select the promising sequence of LLHs; (3) PS-AM and QS2-SA ranks the second/third place in overall scores of pairings, even if the performance of PS/QS2 is barely satisfactory. From the last four scores of acceptance component regardless of the selection component, AM and SA rank, respectively, the first and second with a score 529 and 518, while the other two receive a score of 473 and 429, respectively.Table 3
The overall formula (1) scores for the top four pairs and strategies.
Pairs
Overall score
AS-AM
73
PS-AM
67
QS2-SA
66
TS-SA
65
RP
222
TS
229
FRR-MAB
204
FMT
233
QS
176
QS2
215
AS
242
AS2
212
PS
216
AM
529
NA
473
GD
429
SA
518Figure2 shows the box plot for the scores of nine selection strategies and four acceptance criteria. In the box plot, the minimum and maximum values obtained (excluding the outliers), the lower and upper quartiles, and median are shown.Figure 2
Box plots of scores for a statistical comparison of (a) selection strategies and (b) acceptance criteria.
(a)
(b)From such analysis and answering the first experiments, we identify AS-AM as the best pair considering most cases and scores, and additional PS-AM, QS2-SA, and TS-SA are also selected to conduct the following experiments.


## 5.3.2. Experiment on CLRP

The first four outstanding pairs were tested performing fifty runs on each instance, from which best found solution, gaps to BKS, and computing time are shown, providing the insufficient page space. Results for three CLRP benchmark instances are shown in Tables4–6. The first column of each table is the name of each instances, followed by BKS, and results concerning four pairs which contain best found results (Best), gap (in percentage) to the BKS, and average computing time in seconds (CPU). Average and median values for gaps and CPU are displayed in the last two rows.Table 4
Results for the CLRP instances in Barreto set.
Set
BKS
TS-SA
QS2-SA
AS-AM
PS-AM
Best
Gap
CPU
Best
Gap
CPU
Best
Gap
CPU
Best
Gap
CPU
P12-2
204.0
204.0
0.00
0.1
204.0
0.00
0.1
204.0
0.00
0.1
204.0
0.00
0.1
G21-5
424.9
424.9
0.00
0.4
424.9
0.00
0.4
424.9
0.00
0.4
424.9
0.00
0.3
G22-5
585.1
585.1
0.00
0.3
585.1
0.00
0.4
585.1
0.00
0.3
585.1
0.00
0.3
M27-5
3062.0
3062.0
0.00
0.6
3062.0
0.00
0.6
3062.0
0.00
0.5
3062.0
0.00
0.5
G29-5
512.1
512.1
0.00
0.6
512.1
0.00
0.6
512.1
0.00
0.5
512.1
0.00
0.5
G32-5
562.2
562.2
0.00
0.7
562.2
0.00
0.7
562.2
0.00
0.6
562.2
0.00
0.6
G32-5-2
504.3
504.3
0.00
0.6
504.3
0.00
0.7
504.3
0.00
0.6
504.3
0.00
0.5
G36-5
460.4
460.4
0.00
0.9
460.4
0.00
0.9
460.4
0.00
0.8
460.4
0.00
0.7
C50-5
565.6
565.6
0.00
2.0
565.6
0.00
2.2
565.6
0.00
1.8
565.6
0.00
1.6
P55-15
1112.1
1112.1
0.00
4.2
1112.1
0.00
5.2
1112.1
0.00
4.6
1112.8
0.06
4.2
C75-10
844.4
844.4
0.00
7.9
844.4
0.00
7.9
844.4
0.00
7.0
844.4
0.00
6.3
P85-7
1622.5
1622.5
0.00
9.6
1622.5
0.00
9.7
1622.5
0.00
8.6
1622.5
0.00
7.7
D88-8
355.8
355.8
0.00
7.0
355.8
0.00
6.3
355.8
0.00
6.5
355.8
0.00
5.9
C100-10
833.4
833.4
0.00
11.4
833.4
0.00
12.3
833.4
0.00
10.6
833.4
0.00
8.3
O117-14
12290.3
12290.3
0.00
18.3
12290.3
0.00
18.4
12290.3
0.00
16.4
12290.3
0.00
14.6
M134-8
5709.0
5709.0
0.00
32.7
5709.0
0.00
33.0
5709.0
0.00
29.9
5709.0
0.00
24.1
D150-10
43919.9
43919.9
0.00
42.7
43919.9
0.00
45.0
43919.9
0.00
38.3
43919.9
0.00
33.1
P318-4
7249.3a
4484.2
−0.50
156.4
4145.9
−0.56
110.0
3966.0
−0.59
126.8
3991.1
−0.58
78.8
P318-4-2
13070.0b
10866.5
−0.33
243.4
8293.0
−0.72
213.0
10269.4
−0.42
260.6
10905.1
−0.33
125.3
AV
68099.3
67837.8
−0.04
28.4
67684.6
−0.07
24.6
67779.1
−0.05
27.1
67813.9
−0.04
16.5
MD
0.00
4.2
0.00
5.2
0.00
4.6
0.00
4.2
Bold numbers are the best known solutions. Italic numbers are the minimum value among four obtained solutions. Underscore numbers are the obtained values less than the best known solutions.aResults minus 550000. bResults minus 650000.Table 5
Results for the CLRP instances in Prins set.
Set
BKS
TS-SA
QS2-SA
AS-AM
PS-AM
Best
Gap
CPU
Best
Gap
CPU
Best
Gap
CPU
Best
Gap
CPU
20-5-1
54793
54793
0.00
0.5
54793
0.00
0.5
54793
0.00
0.5
54793
0.00
0.5
20-5-1b
39104
39104
0.00
0.3
39104
0.00
0.3
39104
0.00
0.2
39104
0.00
0.2
20-5-2
48908
48908
0.00
0.5
48908
0.00
0.6
48908
0.00
0.4
48908
0.00
0.4
20-5-2b
37542
37542
0.00
0.3
37542
0.00
0.3
37542
0.00
0.3
37542
0.00
0.2
50-5-1
90111
90111
0.00
3.9
90111
0.00
4.1
90111
0.00
2.9
90111
0.00
2.6
50-5-1b
63242
63242
0.00
1.8
63242
0.00
2.0
63242
0.00
1.9
63242
0.00
1.7
50-5-2
88298
88298
0.00
4.2
88298
0.00
4.3
88298
0.00
3.6
88298
0.00
3.4
50-5-2b
67308
67373
0.10
2.1
67308
0.00
2.1
67449
0.21
1.7
67308
0.00
1.5
50-5-2bis
84055
84055
0.00
3.5
84055
0.00
3.7
84055
0.00
3.1
84055
0.00
2.9
50-5-2bbis
51822
51822
0.00
2.4
51822
0.00
2.5
51822
0.00
2.1
51822
0.00
2.0
50-5-3
86203
86203
0.00
3.9
86203
0.00
4.3
86203
0.00
3.4
86203
0.00
3.1
50-5-3b
61830
61830
0.00
1.9
61830
0.00
1.9
61830
0.00
1.6
61830
0.00
1.6
100-5-1
274814
276096
0.47
28.9
276144
0.48
30.9
275601
0.29
25.8
275598
0.29
22.6
100-5-1b
213615
213654
0.02
14.1
213654
0.02
13.5
213671
0.03
12.2
213654
0.02
10.9
100-5-2
193671
193671
0.00
35.1
193671
0.00
34.4
193671
0.00
26.6
193671
0.00
26.0
100-5-2b
157095
157129
0.02
14.1
157144
0.03
15.2
157110
0.01
13.8
157129
0.02
12.3
100-5-3
200079
200079
0.00
34.3
200079
0.00
34.5
200079
0.00
25.7
200079
0.00
26.8
100-5-3b
152441
152441
0.00
13.8
152441
0.00
13.0
152441
0.00
12.3
152441
0.00
11.3
100-10-1
287695
287688
0.00
31.7
287688
0.00
32.8
287688
0.00
27.4
287688
0.00
25.4
100-10-1b
230989
231608
0.27
17.6
231833
0.37
16.7
231833
0.37
11.1
232222
0.53
13.8
100-10-2
243590
243590
0.00
28.6
243590
0.00
29.2
243590
0.00
24.4
243590
0.00
22.0
100-10-2b
203988
203988
0.00
15.7
203988
0.00
17.4
203988
0.00
15.5
203988
0.00
14.1
100-10-3
250882
252890
0.80
33.8
252890
0.80
33.2
252751
0.74
27.9
252890
0.80
27.2
100-10-3b
204317
204567
0.12
15.8
204567
0.12
15.4
204567
0.12
13.8
204567
0.12
12.9
200-10-1
475294
475770
0.10
268.1
476166
0.18
263.8
476002
0.15
219.6
476722
0.30
190.0
200-10-1b
377043
375820
−0.32
135.0
376313
−0.19
121.4
376662
−0.10
96.7
375836
−0.32
91.0
200-10-2
449006
449037
0.01
250.9
449142
0.03
236.7
449332
0.07
210.4
449110
0.02
132.4
200-10-2b
374280
373882
−0.11
153.0
373973
−0.08
151.1
374039
−0.06
125.8
374093
−0.05
110.6
200-10-3
469433
470780
0.29
247.8
471043
0.34
223.1
471043
0.34
208.2
471073
0.35
124.8
200-10-3b
362653
362276
−0.10
161.2
362349
−0.08
122.0
362596
−0.02
110.0
362640
0.00
113.1
AV
196470
196608
0.06
50.8
196663
0.07
47.7
196667
0.07
41.0
196674
0.07
33.6
MD
196875
0.00
14.9
0.00
15.3
0.00
13.1
0.00
12.6
Bold numbers are the best known solutions. Italic numbers are the minimum value among four obtained solutions. Underscore numbers are the obtained values less than the best known solutions.Table 6
Results for the CLRP instances in Tuzun and Burke.
Set
BKS
TS-SA
QS2-SA
AS-AM
PS-AM
Best
Gap
CPU
Best
Gap
CPU
Best
Gap
CPU
Best
Gap
CPU
P1
1467.68
1467.68
0.00
15.2
1467.68
0.00
15.4
1467.68
0.00
13.0
1467.68
0.00
11.6
P2
1449.20
1448.37
−0.06
20.4
1449.20
0.00
20.1
1449.20
0.00
17.6
1448.37
−0.06
14.7
P3
1394.80
1394.80
0.00
15.1
1394.80
0.00
16.4
1394.93
0.01
14.2
1394.80
0.00
12.3
P4
1432.29
1432.29
0.00
20.7
1432.29
0.00
20.9
1432.29
0.00
17.6
1432.29
0.00
15.4
P5
1167.16
1167.16
0.00
14.5
1167.16
0.00
15.7
1167.16
0.00
13.2
1167.16
0.00
12.0
P6
1102.24
1102.24
0.00
19.0
1102.24
0.00
18.8
1102.24
0.00
16.2
1102.24
0.00
14.5
P7
791.66
791.66
0.00
15.6
791.66
0.00
15.8
791.66
0.00
13.4
791.66
0.00
12.6
P8
728.30
728.30
0.00
17.8
728.30
0.00
17.6
728.30
0.00
15.4
728.30
0.00
12.9
P9
1238.24
1238.49
0.02
16.6
1238.49
0.02
15.9
1238.49
0.02
14.6
1238.49
0.02
13.6
P10
1245.31
1245.31
0.00
23.9
1245.42
0.01
27.6
1245.31
0.00
18.1
1245.31
0.00
15.5
P11
902.26
902.26
0.00
15.3
902.26
0.00
15.4
902.26
0.00
12.9
902.26
0.00
11.9
P12
1018.29
1018.29
0.00
17.9
1018.29
0.00
18.2
1018.29
0.00
15.6
1018.29
0.00
12.7
P13
1866.75
1895.83
1.56
61.8
1895.83
1.56
63.1
1892.17
1.36
53.6
1895.83
1.56
52.9
P14
1823.20
1820.12
−0.17
62.1
1822.69
−0.03
61.3
1822.15
−0.06
53.8
1822.69
−0.03
42.1
P15
1964.30
1965.12
0.04
57.0
1965.12
0.04
57.9
1965.12
0.04
48.9
1965.12
0.04
42.6
P16
1792.80
1792.77
−0.00
70.9
1792.77
−0.00
69.9
1792.77
−0.00
66.9
1792.77
−0.00
55.3
P17
1443.33
1443.32
−0.00
58.6
1443.32
−0.00
64.5
1443.32
−0.00
53.7
1443.32
−0.00
51.3
P18
1434.60
1434.82
0.02
63.0
1433.16
−0.10
64.1
1433.49
−0.08
53.2
1431.24
−0.23
46.6
P19
1204.42
1204.42
0.00
63.5
1204.42
0.00
64.6
1204.42
0.00
57.1
1204.42
0.00
61.7
P20
930.99
927.63
−0.36
64.3
931.28
0.03
65.6
931.28
0.03
54.3
929.26
−0.19
43.8
P21
1694.18
1694.18
0.00
71.3
1694.18
0.00
64.2
1694.18
0.00
55.3
1694.18
0.00
52.1
P22
1392.01
1392.01
0.00
61.6
1392.18
0.01
64.6
1392.01
0.00
53.1
1392.01
0.00
49.3
P23
1198.20
1197.95
−0.02
57.5
1197.95
−0.02
57.2
1197.95
−0.02
48.3
1197.95
−0.02
40.8
P24
1151.80
1151.80
0.00
72.1
1151.80
0.00
73.1
1151.80
0.00
61.2
1151.80
0.00
52.9
P25
2243.40
2237.73
−0.25
136.6
2240.37
−0.14
131.1
2244.64
0.06
91.2
2244.79
0.06
84.9
P26
2138.40
2139.67
0.06
137.9
2139.67
0.06
130.1
2144.49
0.28
102.5
2141.09
0.13
73.2
P27
2209.30
2204.93
−0.20
178.8
2208.48
−0.04
151.4
2209.36
0.00
110.0
2207.69
−0.07
96.1
P28
2222.90
2226.50
0.16
160.4
2223.61
0.03
150.3
2228.27
0.24
113.2
2221.59
−0.06
110.4
P29
2073.70
2074.86
0.06
137.7
2079.96
0.30
130.6
2076.16
0.12
100.4
2077.01
0.16
88.9
P30
1692.17
1685.65
−0.39
135.8
1685.65
−0.39
129.5
1687.38
−0.28
102.6
1685.78
−0.38
80.6
P31
1453.18
1449.96
−0.22
175.1
1449.46
−0.26
153.4
1450.90
−0.16
114.8
1453.89
0.05
100.4
P32
1082.46
1082.46
0.00
167.3
1082.46
0.00
152.6
1082.46
0.00
108.5
1082.46
0.00
111.2
P33
1954.70
1949.29
−0.28
126.3
1950.60
−0.21
127.8
1947.84
−0.35
112.6
1949.38
−0.27
78.6
P34
1918.93
1916.18
−0.14
137.4
1911.73
−0.38
129.6
1917.98
−0.05
91.7
1912.61
−0.33
82.5
P35
1762.00
1760.60
−0.08
155.6
1761.22
−0.04
161.1
1760.04
−0.11
117.3
1760.63
−0.08
113.3
P36
1390.87
1390.87
0.00
167.3
1390.87
0.00
148.2
1390.87
0.00
111.1
1390.94
0.01
117.5
AV
1499.33
1499.32
−0.01
77.6
1499.63
0.01
74.5
1499.97
0.03
59.6
1499.59
0.01
52.5
MD
1439.07
0.00
62.6
0.00
64.4
0.00
53.8
0.00
50.3
Bold numbers are the best known solutions. Italic numbers are the minimum value among four obtained solutions. Underscore numbers are the obtained values less than the best known solutions.For the first three pairs (Table4), the BKSs of instances with less than 150 clients are exploited with average gap at −0.04% for TS-SA, −0.07% for QS2-SA, and −0.05% for AS-AM. Only one BKS cannot be found by the last pair with highest gap at 0.06% and average value at −0.04%. Concerning the median values of gaps to BKS, they take on the value 0. Computing times are on average less than 29, 25, 27, and 17 s, and median values are lower than 6 s even if the largest instances exist. Two new BKS are found by four pairs, obtaining an improvement of over 0.5% for Perl83-318 × 4 by PS-AM and over 0.7% for Perl83-318 × 4-2 by QS2-SA.In the second benchmark (Table5), at least 16 BKS can be found by the four pairs, with difference in finding the Best of 50-5-2b. Four new BKSs in this set are obtained, respectively, reaching an improvement of over 0.3% for 200-10-1b by TS-SA and PS-AM and 0.1% for 200-10-2b and 200-10-3b by TS-SA. Concerning gaps of Best, average values are, respectively, 0.06% for TS-SA and 0.07% for other pairs, and the highest gaps are less than 0.8% for four pairs. Median values equal to 0 for all pairs. Average and median values for CPU are, respectively, 50.8 and 14.9 s for TS-SA, 47.7 and 15.3 s for QS2-SA, 41 and 13.1 s for AS-AM, and 33.6 and 12.6 s for PA-AM.For the Tuzun and Burke benchmark (Table6), TS-SA and PS-AM tie for first place in the number of new BKS found with 13 new BKSs, and QS2-SA tails the winner to take the second place by exploiting 12 new BKSs and AS-AM is in the last place. Concerning the number of solution less than or equal to BKS, TS-SA, PS-AM, and QS2-SA, respectively, rank the first, second, and third with 29, 28, and 27 solutions less than or equal to BKS, and AS-AM ranks the last place with 26 solutions less than or equal to BKS. What surprised us is that the number of new BKS accounts for over 30%, except for AS-AM with 27.8% of 36 instances in this benchmark. Concerning gaps of Best, average values are, respectively, −0.01% for TS-SA, 0.01% for QS2-SA and PS-AM, and 0.03% for SA-AM, and median values are 0 for all pairs. Computing times are on average 77.6, 74.5, 59.6, and 52.5 s, and median values are 62.6, 64.4, 53.8, and 50.3 s.We conduct statistical analysis for obtained results of three CLRP benchmark sets in Tables4–6 through Table 7 based on multiple pairwise comparisons with 95% confidence level (i.e., α = 0.05), namely, Friedman tests. In the Friedman test, the null hypothesis (H0) is only rejected if the Friedman statistic (χ2) is greater than the critical value, looking up in χ2 table through sample size and confidence level, and post hoc test based on Wilcoxon Rank-Sum should be carried out to detect the significant difference among samples, when needed; otherwise, the null hypothesis (H0) is accepted indicating that no significant difference is concerned among four pairs. In Table 7, Friedman statistics (χ2) take the values 3.923 for Barreto et al., 6.750 for Prins et al., and 6.201 for Tuzun and Burke, which are, respectively, lower than 10.117, 18.493, and 23.269, indicating that there is no significant difference among performance of four pairs.Table 7
Friedman’s test results for CLRP benchmark instances (α = 0.05).
Benchmark
Mean ranks for four pairs
Test statistics
Conclusion
TS-SA
QS2-SA
AS-AM
PS-AM
n
χ
2
df
p
Barreto set
2.58
2.42
2.37
2.63
19
3.923
3
0.270
χ
2 < critical value, accept H0
Prins set
2.18
2.58
2.60
2.63
30
6.750
3
0.080
Tuzun and Burke
2.19
2.61
2.65
2.54
36
6.201
3
0.102


## 5.3.3. Experiment on CLRPSPD

The CLRPSPD benchmark instances, which were first converted in Refs. [2, 38], were also used to evaluate the features of the best four pairs. However, this paper only considered the W type of the above sets for the CLRPSPD. The main reason is that the sets of X, Y, and Z types show the same characteristics with the original sets of CLRP, and it is most difficult to obtain BKSs for the instances using W type separation approach. All BKSs were obtained from Ref. [1]. Results for the three CLRPSPD benchmark instances are shown in Tables 8–10. The first column of each table is the name of each instances, followed by the best known solution (BKS), data concerning the first four best pairs which contain best results (Best), gap (in percentage) to the BKS, and average computing time in seconds (CPU). Average (AV) and median values (MD)for gaps or gap and CPU are displayed in the last two rows.Table 8
Results for the CLRPSPD instances in Barreto set.
Instance
BKS
TS-SA
QS2-SA
AS-AM
PS-AM
Best
Gap
CPU
Best
Gap
CPU
Best
Gap
CPU
Best
Gap
CPU
P12-2
243.98
243.98
0.00
0.1
243.98
0.00
0.1
243.98
0.00
0.1
243.98
0.00
0.1
G21-5
528.42
528.42
0.00
0.4
528.42
0.00
0.5
528.42
0.00
0.3
528.42
0.00
0.3
G22-5
653.8
653.80
0.00
0.3
653.80
0.00
0.4
653.80
0.00
0.3
653.80
0.00
0.2
M27-5
3142.02
3142.02
0.00
0.6
3142.02
0.00
0.7
3142.02
0.00
0.5
3142.02
0.00
0.5
G29-5
592.1
592.10
0.00
0.6
592.10
0.00
0.6
592.10
0.00
0.4
592.10
0.00
0.4
G32-5
696.38
696.38
0.00
0.9
696.38
0.00
1.0
696.38
0.00
0.8
696.38
0.00
0.7
G32-5-2
595.27
595.27
0.00
0.7
595.27
0.00
0.8
595.27
0.00
0.6
595.27
0.00
0.6
G36-5
540.37
540.37
0.00
0.9
540.37
0.00
1.0
540.37
0.00
0.7
540.37
0.00
0.7
C50-5
708.37
708.37
0.00
1.9
708.37
0.00
2.0
708.37
0.00
1.5
708.37
0.00
1.4
P55-15
1327.06
1327.06
0.00
3.9
1327.06
0.00
4.0
1327.06
0.00
3.4
1327.06
0.00
3.1
C75-10
1132.8
1132.80
0.00
8.4
1135.61
0.25
8.6
1135.61
0.25
7.2
1137.59
0.42
6.1
P85-7
1855.55
1855.55
0.00
12.2
1855.55
0.00
12.4
1855.55
0.00
10.3
1855.55
0.00
6.3
D88-8
497.6
497.98
0.08
7.1
497.98
0.08
7.4
497.60
0.00
6.4
497.98
0.08
5.8
C100-10
1011.53
1011.53
0.00
13.7
1013.12
0.16
14.0
1011.53
0.00
11.4
1011.53
0.00
10.6
O117-14
12350.2
12350.20
0.00
17.4
12350.20
0.00
17.2
12350.20
0.00
15.3
12350.20
0.00
13.3
M134-8
5913.51
5913.51
0.00
28.5
5922.38
0.15
29.8
5913.51
0.00
24.8
5922.38
0.15
21.2
D150-10
44955.31
44955.31
0.00
46.6
44955.31
0.00
42.2
44960.92
0.01
37.2
44955.31
0.00
35.7
P318-4
4650.09a
4650.85a
0.00
199.7
4650.85a
0.00
144.9
4650.85a
0.00
151.3
4650.85a
0.00
105.0
P318-4-2
6435.73b
6435.73
b
0.00
310.7
6435.73
b
0.00
268.2
5633.50
b
−0.11
259.9
5633.50
b
−0.11
114.6
AV
72362.55
70938.49
0.00
34.5
70939.18
0.03
29.3
70896.69
0.01
28.0
70896.98
0.03
17.2
MD
0.00
3.9
0.00
4.00
0.00
3.4
0.00
3.1
Bold numbers are the best known solutions. Underscore and italic numbers are the obtained values less than the best known solutions.aResults minus 560000. bResults minus 700000.Table 9
Results for the CLRPSPD instances in Prins set.
Instance
BKS
TS-SA
QS2-SA
AS-AM
PS-AM
Best
Gap
CPU
Best
Gap
CPU
Best
Gap
CPU
Best
Gap
CPU
20-5-1
56350
56350
0.00
0.5
56350
0.00
0.5
56350
0.00
0.3
56350
0.00
0.3
20-5-1b
40678
40678
0.00
0.3
40678
0.00
0.3
40678
0.00
0.2
40678
0.00
0.2
20-5-2
49712
49712
0.00
0.5
49712
0.00
0.6
49712
0.00
0.3
49712
0.00
0.3
20-5-2b
38357
38357
0.00
0.3
38357
0.00
0.3
38357
0.00
0.2
38357
0.00
0.2
50-5-1
100240
100240
0.00
4.0
100240
0.00
4.1
100240
0.00
3.4
100240
0.00
3.1
50-5-1b
68993
68993
0.00
1.8
68993
0.00
2.3
68993
0.00
2.1
68993
0.00
1.8
50-5-2
94280
94280
0.00
5.1
94280
0.00
5.2
94280
0.00
4.4
94280
0.00
3.1
50-5-2b
69123
69123
0.00
2.7
69123
0.00
2.7
69123
0.00
2.2
69123
0.00
2.0
50-5-2bis
86349
86349
0.00
4.0
86349
0.00
4.0
86349
0.00
3.5
86349
0.00
3.3
50-5-2bbis
52356
52356
0.00
2.8
52356
0.00
2.6
52356
0.00
2.3
52356
0.00
2.1
50-5-3
90419
90419
0.00
4.9
89737
−0.75
4.7
90419
0.00
3.4
90419
0.00
3.8
50-5-3b
62178
62178
0.00
2.0
62178
0.00
2.1
62178
0.00
1.7
62178
0.00
1.6
100-5-1
290168
290280
0.04
43.5
290280
0.04
46.6
290401
0.08
38.7
290505
0.12
34.1
100-5-1b
219199
223968
2.18
18.9
223966
2.17
18.6
223968
2.18
16.9
223966
2.17
18.0
100-5-2
206049
206170
0.06
32.9
206078
0.01
36.7
206170
0.06
30.2
206308
0.13
29.8
100-5-2b
162077
162083
0.00
15.1
162077
0.00
15.7
162077
0.00
13.4
162077
0.00
12.1
100-5-3
209142
209142
0.00
43.2
209142
0.00
41.5
209142
0.00
34.5
209142
0.00
30.6
100-5-3b
156971
157027
0.04
16.2
157027
0.04
15.9
157027
0.04
14.4
157027
0.04
12.2
100-10-1
326093
326093
0.00
40.5
326093
0.00
40.8
326093
0.00
35.1
326093
0.00
30.8
100-10-1b
272889
272889
0.00
21.8
272889
0.00
21.6
272889
0.00
18.5
272889
0.00
14.1
100-10-2
253074
253609
0.21
39.4
253096
0.01
40.5
253640
0.22
34.1
253074
0.00
29.6
100-10-2b
208941
208941
0.00
20.9
208944
0.00
21.8
208941
0.00
18.9
208941
0.00
16.5
100-10-3
268137
268451
0.12
41.3
268416
0.10
39.0
268531
0.15
35.7
268349
0.08
32.6
100-10-3b
214828
214828
0.00
16.0
214828
0.00
17.9
214828
0.00
15.5
214828
0.00
13.5
200-10-1
529512
498257
−5.90
334.6
498451
−5.87
306.0
499084
−5.75
233.5
498066
−5.94
187.8
200-10-1b
393699
384277
−2.39
195.2
393924
0.06
170.2
385287
−2.14
155.7
385737
−2.02
135.7
200−10-2
463637
463968
0.07
316.4
463913
0.06
282.1
464111
0.10
249.2
464031
0.08
178.3
200-10-2b
380670
380924
0.07
206.4
380833
0.04
173.4
381031
0.09
138.5
380611
−0.02
117.0
200-10-3
485379
485882
0.10
307.9
485946
0.12
304.5
486009
0.13
240.8
486134
0.16
162.3
200-10-3b
369201
369938
0.20
183.3
370303
0.30
171.8
370213
0.27
131.5
370412
0.33
101.6
AV
206192
−0.17
64.1
206485
−0.12
59.8
206283
−0.15
49.3
206241
−0.16
39.3
MD
0.00
17.6
0.00
18.3
0.00
16.2
0.00
13.8
Bold numbers are the minimum value among four obtained solutions. Underscore and italic numbers are the obtained values less than the best known solutions.Table 10
Results for the CLRPSPD instances in Tuzun and Burke.
Case
BKS
TS-SA
QS2-SA
AS-AM
PS-AM
Best
Gap
CPU
Best
Gap
CPU
Best
Gap
CPU
Best
Gap
CPU
P1
1504.45
1504.45
0.00
18.8
1504.45
0.00
19.5
1504.45
0.00
16.5
1504.86
0.03
14.2
P2
1474.33
1474.33
0.00
19.5
1474.33
0.00
18.8
1474.33
0.00
17.2
1474.33
0.00
14.4
P3
1414.35
1414.46
0.01
17.6
1415.13
0.06
17.5
1414.35
0.00
15.4
1414.35
0.00
13.2
P4
1477.49
1481.50
0.27
20.3
1484.29
0.46
19.5
1477.49
0.00
18.2
1477.49
0.00
15.1
P5
1230
1233.69
0.30
18.9
1233.24
0.26
18.6
1227.89
−0.17
16.5
1233.54
0.29
14.7
P6
1123.72
1123.72
0.00
17.9
1123.72
0.00
19.2
1123.72
0.00
16.6
1123.72
0.00
12.2
P7
812.42
812.42
0.00
18.8
812.42
0.00
22.0
812.42
0.00
16.3
812.42
0.00
15.0
P8
752.66
751.89
−0.10
24.0
754.15
0.20
23.3
752.41
−0.03
19.0
759.21
0.87
11.6
P9
1273.3
1273.30
0.00
18.8
1273.30
0.00
19.2
1273.30
0.00
15.8
1273.30
0.00
14.5
P10
1265.1
1265.10
0.00
22.5
1265.02
−0.01
22.8
1266.20
0.09
20.0
1265.10
0.00
17.4
P11
911.52
911.52
0.00
20.3
911.52
0.00
18.4
911.52
0.00
16.8
911.52
0.00
15.4
P12
1033.38
1031.94
−0.14
23.5
1033.38
0.00
22.6
1033.27
−0.01
20.2
1033.38
0.00
18.1
P13
1943.41
1947.92
0.23
59.1
1946.58
0.16
58.5
1949.76
0.33
49.9
1947.98
0.24
41.9
P14
1848.69
1848.69
0.00
66.1
1856.10
0.40
67.4
1859.17
0.57
58.4
1862.25
0.73
46.4
P15
2011.29
2011.32
0.00
67.7
2011.39
0.00
71.3
2016.29
0.25
58.5
2012.29
0.05
49.1
P16
1856.03
1861.73
0.31
63.5
1859.97
0.21
69.8
1862.65
0.36
59.4
1859.32
0.18
47.5
P17
1479.77
1484.97
0.35
69.3
1490.83
0.75
69.3
1483.73
0.27
58.7
1491.36
0.78
48.9
P18
1452.49
1453.05
0.04
67.1
1453.58
0.08
68.4
1452.28
−0.01
58.6
1452.73
0.02
47.8
P19
1228.49
1228.11
−0.03
60.6
1228.52
0.00
61.3
1228.49
0.00
53.9
1228.69
0.02
47.5
P20
949.82
949.82
0.00
68.3
951.62
0.19
68.7
950.06
0.03
58.9
949.82
0.00
45.7
P21
1732.81
1736.52
0.21
60.9
1736.45
0.21
61.9
1737.80
0.29
53.2
1735.63
0.16
42.9
P22
1426.41
1426.45
0.00
76.6
1426.66
0.02
77.4
1427.57
0.08
64.6
1425.37
−0.07
57.6
P23
1238.78
1229.69
−0.73
70.0
1226.08
−1.03
69.6
1229.69
−0.73
59.0
1229.69
−0.73
49.4
P24
1166.8
1166.80
0.00
64.0
1166.80
0.00
66.3
1166.80
0.00
57.0
1166.80
0.00
51.4
P25
2338.89
2343.12
0.18
153.2
2339.54
0.03
146.9
2343.64
0.20
102.4
2351.63
0.54
76.7
P26
2224.86
2226.41
0.07
177.6
2240.00
0.68
173.0
2238.67
0.62
122.9
2228.80
0.18
115.1
P27
2293.85
2298.34
0.20
175.9
2298.04
0.18
178.3
2297.87
0.18
115.3
2302.65
0.38
112.1
P28
2292.91
2303.17
0.45
154.4
2303.63
0.47
147.1
2301.04
0.35
107.2
2307.62
0.64
95.8
P29
2159.62
2163.17
0.16
160.2
2158.57
−0.05
159.8
2159.83
0.01
110.2
2169.93
0.48
89.4
P30
1727.67
1731.95
0.25
175.1
1733.80
0.35
172.7
1729.77
0.12
132.2
1729.04
0.08
103.6
P31
1483.34
1486.36
0.20
172.0
1484.89
0.10
171.2
1484.87
0.10
116.8
1486.35
0.20
114.3
P32
1101.65
1102.31
0.06
149.0
1102.29
0.06
138.4
1103.93
0.21
96.7
1102.44
0.07
100.5
P33
2001.36
2002.82
0.07
154.9
2003.39
0.10
147.4
2002.79
0.07
129.5
2003.16
0.09
75.5
P34
1973.43
1975.63
0.11
164.1
1977.83
0.22
165.5
1981.09
0.39
115.5
1982.10
0.44
107.9
P35
1801.82
1810.44
0.48
177.9
1825.68
1.32
164.5
1826.61
1.38
130.4
1822.02
1.12
148.1
P36
1418.8
1425.63
0.48
151.5
1423.96
0.36
140.0
1422.24
0.24
123.9
1432.10
0.94
101.2
Av.
1541.47
0.10
83.3
1542.53
0.16
82.1
1542.44
0.14
63.9
1543.42
0.21
55.3
MD.
0.05
66.6
0.09
68.6
0.08
58.6
0.08
47.7
Bold numbers are the minimum value among four obtained solutions. Underscore and italic numbers are the obtained values less than the best known solutions. The instances are represented by “PN,” whereN represents the serial number.For the Barreto benchmark set, computing times are on average lower than 35, 30, 29, and 18 s and median values are 3.9, 4, 3.4, and 3.1 s, respectively. Concerning gaps of Best, average values are, respectively, 0, 0.03%, 0.01%, and 0.03%, and median values equal to 0. New BKSs for instance with 318 clients are found with an improvement of 0.11% to previous BKS by AS-AM and PS-AM. Gaps to BKS are very low for all instances with highest gaps lower than 0.08% for the first pair, 0.25% for the second and third pairs, and 0.42% for the last one.Looking at Table9, computing times are on average less than 65, 60, 50, and 40 s, respectively, and median values are, respectively, 17.6, 18.3, 16.2, and 13.8 s. Concerning gaps to BKSs, average and median values are, respectively, −0.17% and 0 for TS-SA, −0.12% and 0 for QS2-SA, −0.15 and 0 for third pair, and −0.16 and 0 for the last pair. From the perspective of gaps to BKSs, we verified the solutions achieved in Ref. [2]. Meanwhile, we obtained four improvements for four instances, i.e., 50-5-3 (QS2-SA), 200-10-1 (four pairs), 200-10-1b (four pairs except for QS2-SA), and 200-10-2b (PS-AM), one of them reaching an improvement of over 5.9% to previous BKSs.As shown in Table10, the computing times are on average less than 84, 83, 64, and 56 s, and median values are 66.6, 68.6, 58.6, and 47.7 s, respectively. As far as gap to BKS is concerned, average/median values are 0.1/0.05%, 0.16/0.09%, 0.14/0.08%, and 0.21/0.08%, respectively. Meanwhile, new BKSs of nine instances were obtained by our proposed algorithms, and the largest improvement was over 1% for P23 obtained by QS2-SA. The AS-AM outperformed others obtaining five new BKSs, followed by TS-SA and QS2-SA, and PS-AM performed the worst. However, the best-performing pairs was TS-SA in terms of average gap to BKSs.Statistical analysis is carried out for obtained results of three sets in Tables8–10 through Table 11 based on Friedman test. In Table 11, Friedman statistics (χ2) take the values 3.279 for Barreto et al., 4.621 for Prins et al., and 4.087 for Tuzun and Burke, which are, respectively, lower than 10.117, 18.493, and 23.269, indicating that there is no significant difference among the performance of four pairs. Therefore, we can strongly conclude that the proposed pairs could achieve high-quality solutions for the CLRPSPD benchmark instances.Table 11
Friedman’s test results for CLRPSPD benchmark instances (α = 0.05).
Benchmark
Mean ranks for four pairs
Test statistics
Conclusion
TS-SA
QS2-SA
AS-AM
PS-AM
n
χ
2
df
p
Barreto set
2.39
2.68
2.37
2.55
19
3.279
3
0.351
χ
2 < critical value, accept H0
Prins set
2.42
2.33
2.77
2.48
30
4.621
3
0.202
Tuzun and burke
2.25
2.51
2.44
2.79
36
4.087
3
0.252Overall, among the four pairs, two types of discussion and conclusions are conducted: one for problem domains and one for hyperheuristic pairs. From perspective of both subjects, the amount of CPU time depends directly on the number of clients (n), depots (m), and vehicle capacity (Q), and the relationship between running time and each of above factors is drawn in Figures 3 and 4 (excluding the outliers) and Figure 5. Several conclusions on running time are reached: (1) running time is affected by the number of clients in exponential way; (2) number of depots has slight impact on the running time, which may be resulted by few depots; (3) computing time increases with the decrease of the vehicle capacity in the form of polynomial; (4) the order of impact of the above factors effecting the running time is n, Q, and m. The first and third conclusions were also shared in Ref. [2]. Moreover, the time complexity and solution quality may depend in part on the complexity of the mathematical model. Figure 6 illustrates the impact of complexity of mathematical model on the running time. More specifically, the average computing time of tackling CLRPSPD instances increases by 4.2–21.5% for Barreto set, 30.6–46.8% for Prins set, and 5.3–10.2% for Tuzun and Burke, respectively, compared with the average running times of tackling CLRP cases. Concerning solution quality and average standard deviation, the complexity of instances is the direct acting factor consisting of the number of clients, depots and vehicles, and the distribution of clients and depots. Furthermore, the complexity of approaches or pairs of selection strategies and acceptance criteria also significantly influence the running time, standard deviation, and solution quality. PS-AM seems to be among the fastest with declining 36, 33, and 20% average running time compared to others, and AS-AM and QS2-SA rank the second and third in aspects of average running time. In terms of solutions quality, there is no significant difference among these four pairs concluded by the above Friedman tests, indicating that PS-AM and AS-AM outperform the others in obtaining a better trade-off solution quality and running time, but all pairs can obtain high solution quality within reasonable running time.Figure 3
Box plots for relationship between computing time and number of clients.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)Figure 4
Box plots for relationship between computing time and number of depots.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)Figure 5
Histogram of computing times of different vehicle capacity.
(a)
(b)
(c)
(d)Figure 6
Histogram of computing times of both subjects.
(a)
(b)
(c)
(d)


## 5.3.4. Comparison and Evaluation

To illustrate advantages of our proposed approaches for CLRP and CLRPSPD, comparisons with the most recent and effective methods in the literature are carried out in Table12, where average gaps (AG) of best found solutions to BKS and average running time of the proposed approaches for the CLRP are provided, and they are, respectively, GRASP + ELS [31], SALRP/SALRP+ [32], ALNS/ALNS+ [33], MACO [35], HGTS [34], GRASP + ILP [25], GVTNS [36], and HGA/HGA+ [37], and for the CLRPSPD, the approaches were BC-SA [38], SA/SA∗ [4], and RP/TS/FRR-MAB/FMT [2].Table 12
Average solutions for CLRP and CLRPSPD benchmark sets.
Algorithm
Barreto set
Prins set
Tuzun and Burke
AG
CPU
AG
CPU
AG
CPU
CLRP benchmark
GRASP + ELS
0.08a
187.6a
1.11
258.2
1.30
606.6
SALRP
0.48
464.1
0.46
422.4
1.49
826.4
SALRP+
0.08
NA
0.08
NA
0.53
NA
ALNS
0.16a
177.2a
0.44
451.1
0.43
829.6
ALNS+
0.06a
1772.0a
0.27
4221.0
0.18
8103.0
HGTS
0.78a
105.2a
0.57
176.4
1.14
392.3
MACO
0.17
191.7
0.40
191.3
1.23
201.9
GRASP + ILP
0.14a
264.3a
0.12
1163.0
0.17
2589.5
GVTNS
0.67a
53.0a
0.37
91.2
0.76
201.2
HGA
0.63
42.4
0.37
73.1
0.86
86.0
HGA+
0.00
429.6
0.32
199.1
0.70
363.6
TS-SA
−0.04
28.4
0.06
50.8
−0.01
77.6
QS2-SA
−0.07
24.6
0.07
47.7
0.01
74.5
AS-AM
−0.05
27.1
0.07
41.0
0.03
58.8
PS-AM
−0.04
16.5
0.07
33.6
0.01
52.5
CLRPSPD benchmark
BC-SA
1.47a
6604.1a
NA
NA
NA
NA
SA
0.48
1460.1
NA
NA
NA
NA
SA∗
0.21
NA
NA
NA
NA
NA
RP
0.08
32.2
0.07
60.2
0.21
83.4
TS
0.02
30.54
0.06
55.2
0.10
77.6
FRR-MAB
0.01
32.46
0.02
62.7
0.08
77.3
FMT
0.00
32.73
0.01
59.8
0.02
78.6
TS-SA
0.00
34.5
−0.17
64.1
0.10
83.3
QS2-SA
0.03
29.3
−0.12
59.8
0.16
82.1
AS-AM
0.01
28.0
−0.15
49.3
0.14
63.9
PS-AM
0.03
17.2
−0.16
39.3
0.21
55.3
aConsidering only (the same) 13 out of the 19 instances.Even though the time execution comparison can be unfair, depending on many factors (computer configuration, programming languages, the number of fitness evaluation, etc.), it is a significant performance indicator for judging the advantage of approaches. As shown in Table12, our four pairs of hyperheuristic seem to be the fastest among the above methods. Furthermore, our approaches are the among best in aspects of solution quality on all CLRP and CLRPSPD benchmark sets with very small gaps. In conclusion, we can strongly conclude that our hyperheuristics are able to outperform the most recent and effective methods in terms of either solution quality or computing time.


## 6. Conclusion and Future Work

In this study, evolution-based hyperheuristics are proposed to tackle the CLRP and one of its variants, namely, CLRPSPD. Five evolutionary and four nonevolutionary selection strategies are developed as high-level selection strategies to pair up with four acceptance criteria to make a right decision on constructing effective sequences of LLHs at each step, guiding the proposed approaches to achieve the optimal values.The first experiment was carried out to determine the top four pairs which can rightly reflect to performance information of each LLH and quickly respond to select the promising LLHs. Results show that (1) AM and SA as acceptance criteria performed better when compared to the rest two; (2) AS, FRR-MAB-TS, and TS as selection strategies performed better when compared to the rest of the selection strategies; (3) average performance of AS-AM, PS-AM, QS2-SA, and TS-SA as HLHs perform significantly better than the rest of the pairs. The first four outstanding pairs were picked out to implement the remaining two experiments. PS-AM and AS-AM outperform others in terms of obtaining a good trade-off between solution quality and computing time, and all four pairs can achieve solution of high quality within reasonable running time, providing several new BKSs accounted for over 30% in Tuzun and Burke CLRP set. A comparative analysis is also conducted with tailored approaches in the published literature, and the results illustrate that the performance of our proposed approaches outperform the above methods in terms of both solution quality and computing time. As advocated in Ref. [93] for hyperheuristic, the proposed approaches have capability in exploiting good enough, soon enough, and cheap enough solutions.The proposed hyperheuristic (36 pairs) has been already been implemented in a decision-support tool, and we refer the interested readers to consult us about the package. The next research content will focus on the adaptive selection of MHs and other selection strategies of hill climbers, e.g., choice function [5, 47], adaptive pursuit [94], and fair-share method [95]. For bringing CLRP/CLRPSPD closer to the reality, more practical constraints will also be taken into account in future works, such as time windows, dynamic demands, period delivery, and pickup.



---

*Source: 9291434-2020-02-28.xml*