Solving optimization problems simultaneously: the variants of the traveling salesman problem with time windows using multifactorial evolutionary algorithm

The TSPTW and TRPTW literature

The Traveling Salesman Problem with Time Windows (TSPTW) (Gendreau et al., 1998; Silva & Urrutia, 2010; Ohlmann & Thomas, 2007), and Traveling Repairman Problem with Time Windows (TRPTW) (Ban & Nghia, 2017; Ban, 2021; Heilporna, Cordeaua & Laporte, 2010) are combinatorial optimization problems that have many practical situations. The TRPTW wants to minimize the sum of travel durations between a depot and customer locations, while the TSPTW aims to minimize the total time to visit all customers. In the two problems, the deliveries are made during a specific time window given by the customers. Due to time window constraints, the TSPTW and TRPTW are much harder than the traditional Traveling Salesman Problem (TSP) and Traveling Repairman Problem (TRP).

The Travelling Salesman Problem with Time Windows (TSPTW) is a popular NP-hard combinatorial optimization problem studied much in the literature (Dumas, Desrosiers & Gélinas, 1995). The algorithms include exact and metaheuristic approaches. Langevin et al. (1993) introduced a two-commodity flow formulation to solve the problem. Dumas, Desrosiers & Gélinas (1995) then used a dynamic programming approach. Similarly, Gendreau et al. (1998) brought constraint programming and optimization techniques together. Most recently, Dash et al. (2012) propose a method using an IP model based on the discretization of time. The results are extremely good: several benchmark instances are solved first. Gendreau et al. (1998) then proposed an insertion heuristic that generated the solution in the first step and improved it in a post-phase using removal and reinsertion of vertices. Ohlmann & Thomas (2007) developed simulated annealing relaxing the time windows constraints by integrating a variable penalty method within a stochastic search procedure. In this work, they developed a two-phase heuristic. In the first phase, a feasible solution was created by using a Variable Neighborhood Search (VNS) (Mladenovic & Hansen, 1997). In the post phase, this solution was improved by using a General VNS. Generally speaking, the results from this approach are very promising.

In the Travelling Repairman Problem with Time Windows (TRPTW), there is an exact algorithm and three metaheuristics algorithms in the literature: (1) Tsitsiklis (1992) proposed a polynomial algorithm when several customers are bounded; (2) Heilporna, Cordeaua & Laporte (2010) then developed an exact algorithm and heuristic algorithm to solve the problem; (3) Ban & Nghia (2017) and Ban (2021) proposed two metaheuristic algorithms based on Variable Neighborhood Search (VNS) scheme. Their experimental results showed the efficiency of the metaheuristic approach.

These above algorithms are the state-of-the-art metaheuristics in current. However, they are designed to solve each problem independently. That means they cannot solve both two problems well simultaneously. In Salehipour et al. (2011) also showed that a good algorithm for this problem might not be good for the other problem. Therefore, developing an algorithm solving both problems well simultaneously is our aim in this work.

The MFEA literature

To date, the MFEA framework (Dash et al., 2012; Gupta, Ong & Feng, 2016; Xu et al., 2021) has been introduced in the literature. Using a unified search space for multiple tasks can exploit good transferrable knowledge between optimization tasks. In addition, although solving many tasks simultaneously, the flow of the MFEA framework is sequential. Therefore, the MFEA is suitable in a system with limited computation.

Several close variants of the MFEA (Ban & Pham, 2022; Osaba et al., 2020; Yuan et al., 2016) are developed to solve permutation-based optimization problems such as the TSP and TRP. Therefore, they are direct references to our research. Yuan et al. (2016) firstly developed evolutionary multitasking in permutation-based optimization problems. They tested it on several popular combinatorial problems. The experiment results indicated the good scalability of evolutionary multitasking in many-task environments. Osaba et al. (2020) then proposed a dMFEA-II framework to exploit the complementarities among several tasks, often achieved via genetic information transfer. Their dMFEA-II controls the knowledge transfer by adjusting the crossover probability value. The technique allows good knowledge to transfer between tasks. Although the results are promising, the drawback of the above two algorithms (Osaba et al., 2020; Yuan et al., 2016) is that there is a lack of a mechanism to exploit the good solution space explored by MFEA. Therefore, these algorithms cannot effectively balance exploration and exploitation (we visualize their issue in “Comparison with the previous MFEA algorithms” in more detail). Recently, Ban & Pham (2022) have successfully applied the MFEA with RVNS to solve two problems such as TSP and TRP. Their algorithms maintain the exploration and exploitation better than the others in Osaba et al. (2020) and Yuan et al. (2016). Its performance encourages us to use this combination to solve the TSPTW and TRPTW. This article considers these works as a baseline for our research.

Our contributions

This article introduces the first algorithm combining the MFEA framework and RVNS to solve two tasks simultaneously. The combination is to have positive transferrable knowledge between tasks from the MFEA and the ability to exploit good solution spaces from RVNS. The major contributions of this work are as follows:

• We propose a new selection operator that balances skill-factor and population diversity. The skill-factor effectively transfers elite genes between tasks, while diversity in the population is important when it meets a bottleneck against the information transfer.

• Multiple crossover schemes are applied in the proposed MFEA. They help the algorithm have good enough diversity. In addition, two types of crossover (intra- and inter-) are used. It opens up the chance for knowledge transfer through crossover-based exchange between tasks.

• The combination between the MFEA and the RVNS is to have good transferrable knowledge between tasks from the MFEA and the ability to exploit good solution spaces from the RVNS. However, focusing only on reducing cost function maybe lead the search to infeasible solution spaces like the algorithms (Ban & Pham, 2022; Osaba et al., 2020; Yuan et al., 2016). Therefore, the repair method is incorporated into the proposed algorithm to balance finding feasible solution spaces and reducing cost function.

• Numerical experiments show that the proposed algorithm reaches nearly optimal solutions simultaneously in a short time for two problems. Moreover, it obtains better solutions than the previous MFEA algorithms in many cases.

The rest of this article is organized as follows. Sections 1 and 2 present the literature and preliminary, respectively. Section 3 describes the proposed algorithm. Computational evaluations are reported in Section 4. Section 5 presents the conclusions and future work.

The formulation

We consider an example that describes the difference between two problems in a specific instance. If we use the optimal solution of n40w160.002 instance for the TSPTW (https://lopez-ibanez.eu/tsptw-instances), the objective function cost (using the function cost of the TRPTW) of this solution for the TRPTW is 7,519, while the known-best cost for this instance for the TRPTW is 6,351 (the known-best cost is found by our algorithm). Thus, the difference between the two objective function costs is 15.5%. It implies that a good metaheuristic algorithm for the TSPTW does not produce a good solution for the TRPTW and vice versa. The above algorithms are the best algorithms for two problems. However, they only solve each problem independently but cannot simultaneously produce good solutions for two problems.

We have a complete graph $K_n=(V,E)$, where $V=v_1,v_2,...,v_n$ is a set of vertices showing the starting vertex and customer locations, and E the set of edges connecting the customer locations. Suppose that, in a tour $T=(v_1=s,v_2...,v_n)$, each edge $(v_i,v_j)\in E$ connecting the two vertices $v_i$ and $v_j$ there exists a cost $c(v_i,v_j)$. This cost represents the travel time between vertex $v_i$ and $v_j$. Each vertex $v_i\in V$ has a time window $[e_i,l_i]$ indicating when starting service time at vertex $v_i$. This implies that a vertex $v_i$ may be reached before the start of $e_i$, but the service cannot start until $e_i$ and no later than $l_i$ of its time window. Moreover, to serve each customer, the salesman spends an amount of time. Let $D(v_i),S(v_i)$ be the time at which service begins and the service time at vertex $v_i$. It is calculated as follows: $D(v_i)=max\{A(v_i),e_i\}$, where $A(v_k)=D(v_{i-1})+S(v_{i-1})+c(v_{i-1},v_i)$ is the arrival time at vertex $v_i$ in the tour. A tour is feasible if and only if $A(v_i)\le l_i$ for all vertices. The objective functions of the two problems are defined as follows:

• In the TSPTW, the salesman must return to $s$. Therefore, the cost of the tour T is defined as: ${\sum }_{i=1}^{n}c(v_i,v_{i+1})$. Note that: $v_{n+1}\equiv s$

• In the TRPTW, we also define the travel duration of vertex $v_i$ as the difference between the beginning of service at vertex $v_i$ and the beginning of service at s: $t_i=D(v_i)-D(s)$. The cost of the tour T is defined: ${\sum }_{i=2}^n{t}_i.$

Two problems consist of determining a tour, starting at the starting vertex $v_1$, minimizing the cost of the tour overall vertices while respecting time windows. First, note that: the man must start and end at vertex $v_1$.

Our methodology

For NP-hard problems, we have three approaches to solve the problem, specifically, (1) exact algorithms, (2) approximation algorithms, and (3) heuristic (or metaheuristic) algorithms:

• The exact approaches find the optimal solution. However, they are exponential time algorithms in the worst case.

• An $\alpha$-approximation algorithm generates a solution that has a factor of $\alpha$ of the optimal solution.

• Heuristic (metaheuristic) algorithms perform well in practice and validate their performance through experiments. This approach is suitable for a problem with large sizes.

Previously, several metaheuristics have been proposed to solve the TSPTW (Dumas, Desrosiers & Gélinas, 1995; Focacci, Lodi & Milano, 2002; Gendreau et al., 1998; Ohlmann & Thomas, 2007; Yuan et al., 2016) and the TRPTW (Ban & Nghia, 2017; Ban, 2021; Heilporna, Cordeaua & Laporte, 2010; Tsitsiklis, 1992). However, they are developed to solve each problem independently and separately. Therefore, they cannot solve both two problems well simultaneously. When we run the two best algorithms for two tasks independently, there is no transferrable knowledge between tasks, and we cannot improve solution quality.

This article proposes an MFEA approach to solve two problems simultaneously. Our MFEA solves two tasks simultaneously: the first task is the TRPTW, and the second is the TSPTW. Experiment results indicate its efficiency: (1) for small instances, the proposed algorithm obtains the optimal solutions in both two problems; (2) for large ones, our solutions are close to the optimal ones, even much better than those of the previous MFEA approaches.

The MFEA framework introduction

The overview of multifactorial optimization is introduced in Dash et al. (2012) and Gupta, Ong & Feng (2016). Assume that k optimization problems are needed to be performed simultaneously. Without loss of generality, tasks are assumed to be minimization problems. The $j$-th task, denoted $T_i$, has objective function $f_j:X_j\Rightarrow R$, in which $x_j$ is solution space. We need to be found $k$ solutions $\{x_1,x_2,...,x_{k-1},x_k\}=min\{f_1(x),f_2(x),....,f_{k-1}(x),f_k(x)\}$, where $x_j$ is a feasible solution in $X_j$. Each $f_j$ is considered an additional factor that impacts the evolution of a single population of individuals. Therefore, the problem also is called the $k-$ factorial problem. For the problem, a general method to compare individuals is important. Each individual $p_i(i\in \{1,2,...,|P|\})$ in a population P has a set of properties as follows: Factorial Cost, Factorial Rank, Scalar Fitness, and Skill Factor. These properties allow us to sort and select individuals in the population.

• Factorial Cost $c_j^i$ of the individual $p_i$ is its fitness value for task $T_j$ $(1\le j\le k)$.

• Factorial rank $r_j^i$ of $p_i$ on the task $T_j$ is the index in the set of individuals sorted in ascending order in terms of $c_j^i$.

• Scalar-fitness ${\varphi }_i$ of $p_i$ is given by its best factorial rank overall tasks as ${\varphi }_i={\displaystyle \frac{1}{{min}_{j\in 1,...,k}{r}_j^i}}$.

• Skill-factor ${\rho }_i$ of $p_i$ is the one task, amongst all other tasks, on which the individual is most effective, i.e., ${\rho }_i=argmi{n}_j\{r_j^i\}$ where $j\in \{1,2,...,k\}$.

The pseudo-code of the basic MFEA is described in Algorithm 1 (Ban & Pham, 2022): We first build the unified search space that encompasses all individual search spaces of different tasks to have a shared background on which the transfer of information can take place. We then initialize SP individuals (SP is the size of population) in the unified search space and then evaluate it by calculating the skill-factor of each individual. After the initialization, the iteration begins to produce the offsprings and assign skill-factors to them. Selective evaluation guarantees that the skill-factor of each new offspring is selected randomly among those of the parents. The offspring and the parent are merged in a new population with $2\times SP$ individuals. The evaluation for each individual is taken only on the assigned task (in the step, the best solution for each task is updated if it is found. This best solution for each task is the output). After evaluation, the individuals of the population receive new skill-factors. The Elitist strategy keeps the SP solutions with the best skill-factors for the next generation.

Figure 1 (Ban & Pham, 2022) also shows the differences between the traditional EA and MFEA. The crossover and mutation operators in the MFEA are like the traditional EA. However, there are two different important aspects: (1) the parents’ skill-factor and (2) random mating probability (rmp). Specifically, the child is created using crossover from parents with the same skill-factor. Otherwise, the child is generated by a crossover with a rmp value or by a mutation when parents own different skill-factors. A large rmp value generates more information exchanging between tasks. Also, in the traditional GA, the fitness of child is evaluated directly, while the skill-factor is assigned to it in the MFEA.

The MFEA is also unlike multiobjective optimization. In multiobjective optimization, we have one problem with many objective functions. On the other hand, the MFEA solves many tasks at the same time. In addition, multiobjective optimization generally uses a single representative space, while the MFEA unifies multiple representative spaces for many tasks.

Running two algorithms for two tasks independently is not the idea of the MFEA approach. When two algorithms run independently, each task is represented by its own search space. There is no transferrable knowledge between tasks. Otherwise, in the MFEA, two tasks use the unified search space, and transferrable knowledge between tasks is done. It can increase convergence and improve the quality of solutions for multitasks. Lian et al. (2019) then provided a novel theoretical analysis and evidence of the efficiency of the MFEA. This study theoretically explains why some existing the MFEAs perform better than traditional EAs. In addition, the MFEA also can be useful in a system with limited computation.

Creating unified search space-USS

In the literature, various representations are proposed for two problems. Among these representations, the permutation representation shows efficiency compared to the others. In the permutation, each individual is coded as a set of $n$ vertices $(v_1,v_2,...,v_k,...,v_n)$, where $k$ is the $k-$th index. Figure 3 demonstrates the encoding for two problems.

Initializing population

Each feasible solution is created from the RVNS to take a role as an individual in the population. Therefore, we have S_p individuals in the initial population for the genetic step.

Algorithm 3 describes the constructive step. The objective function is the sum of all positive differences between the arrival time $(D(v_i))$ and its due time $(l_i)$ on each vertex. Specifically, it is $min\sum _{i=1}^{n}max(0,D(v_i)-l_i)$. The algorithm runs until it finds a feasible solution. Restricted Candidate List (RCL) is created by ordering all non-selected vertices based on a greedy function that evaluates the benefit of including them in the solution. One vertex is then chosen from RCL randomly. Since all vertices are visited, we receive a solution. If this solution is a feasible one, it is an initial solution, and this step stops. Conversely, a repair procedure based on the RVNS with many neighborhoods (Johnson & McGeoch, 2003) is invoked, and the procedure iterates until a feasible solution is reached. The solution is shaken to escape from the current local optimal solution. The RVNS is then applied to create the new solution. If it is better than the best-found solution, it is set to the new current solution. The level is increased by one if the current solution is not improved, or reset to 1, otherwise. The repair procedure is described in Algorithm 4.

In this article, some neighborhoods widely applied in the literature (Johnson & McGeoch, 2003). We describe more details about seven neighborhoods as follows:

• move moves a vertex forward one position in T.

• shift relocates a vertex to another position in T.

• swap-adjacent attempts to swap each pair of adjacent vertices in the tour.

• exchange tries to swap the positions of each pair of vertices in the tour.

• 2-opt removes each pair of edges from the tour and reconnects them.

• Or-opt: Three adjacent vertices are reallocated to another position of the tour.

Evaluating for individuals

The scalar-fitness function demonstrates the way of evaluating individuals. Scalar-fitness then are calculated for each individual. The larger and larger the scalar-fitness value is, the better and better the individual is.

Selection operator

In the original tournament (Ban & Pham, 2022; Talbi, 2009), the fitness is the only criterion in choosing parents. This article adapts this selection for the MFEA algorithm balancing scalar-fitness and population diversity. It means the selection mechanism simultaneously promoting both diversity and scalar-fitness. For each solution, we count its scalar-fitness and its diversity in a set of solutions as follows:

(1) $$R(T)=(1-\alpha )\times (SP-RF(T)+1)+\alpha \times (SP-RD(T)+1)$$where SP, $\alpha \in [0,1]$, $RF(T)$, and $RD(T)$ are the population size, threshold, the rank of T in the P based on the scalar-fitness, and the rank of T in the P based on its diversity, respectively.

(2) $$\overline{d}(T)={\displaystyle \frac{{\sum }_{i=1}^{n}d(T,T_i)}{n}}$$

The metric distance between two solutions is the minimum number of transformations from one to another. We define the distance $d(T,T_i)$ to be n (the number of vertices) minus the number of vertices with the same position on T and $T_i$. Similarly, $\overline{d(T)}$ is the average distance of T in the population. The larger $\overline{d}(T)$ is, the higher its rank is. The larger R is, the better solution T is.

The selection operator selects individual parents based on their R values to mate. We choose the tournament selection operator (Talbi, 2009) because of its efficiency. A group of NG individuals is selected randomly from the population. Then, two individuals with the best R values in the group are chosen to become parents. The selection pressure can be increased by extending the size of the group. On average, the selected individuals from a larger group have higher R values than those of a small size. The detail in this step is described in Algorithm 5.

Crossover operator

The crossover is implemented with the predefined probability (rmp) or if the parents have the same skill-factor. When parents have the same skill-factor, we have inter-crossover. Otherwise, the intra-crossover is applied to parents with different skill-factor. It opens up the chance for knowledge transfer by using crossover-based exchange between tasks. In Otman & Jaafar (2011), the crossovers are divided into three main types. We found no logical investigation showing which operator brings the best performance in the literature. In a preliminary study, we realize that the algorithm’s effectiveness relatively depends on selected crossover operators. Since trying all operators leads to computationally expensive efforts, our numerical analysis is conducted on randomly selected operators for each type. The following operators are selected from the study to balance solution quality and running time.

• The first type is related to the position of certain genes in parents (PMX, CX).

• The second selects genes alternately from both parents, without genes’ repetition (EXX, EAX).

• The third is an order-based crossover (SC, MC).

Initially, we select a crossover randomly. If any improvement of the best solution is found, the current crossover operator is continued to use. Otherwise, if the improvement of the best solution is not found after the number of generations (NO), another crossover operator is replaced randomly. Using multiple crossovers helps the population be more diverse than one crossover. Therefore, these operators prevent the algorithm from premature convergence. If the offsprings are infeasible, the fix procedure is invoked to convert them to feasible ones. The offsprings’ skill-factors are randomly set to the one of the father or mother. The detail in this step is described in Algorithm 6.

Mutation operator

A mutation is used to keep the diversity of the population. Some mutations are used in the proposed algorithm:

• The Inversion Mutation picks two vertices at random and then inverts the list of vertices between them. It preserves most adjacency information and only breaks two links, leading to the disruption of order information.

• The Insertion Mutation removes the vertex from the current index and then inserts it in a random index on the solution. The operator preserves most of the order and the adjacency information.

• Swap Mutation selects two vertices at random and swaps their positions.

It preserves most of the adjacency information, but links broken disrupt order more. We randomly select one of three operators when this mutation is performed. After the mutation operator, two offsprings are created from the parents. If the offsprings are infeasible, the repair procedure converts them to feasible ones. Their skill-factors are set to those of parents, respectively. The detail in the mutation is described in Algorithm 7.

RVNS

The combination between the MFEA and the RVNS allows good transferrable knowledge between tasks from the MFEA and the ability to exploit good solution spaces from RVNS. We select some best solutions in the current population to feed into the RVNS. In the RVNS step, we convert a solution from unified representation to separated representation for each task. The RVNS then applies to each task separately. Finally, the output of the RVNS is represented in the unified space. The improved solution will be added to the population.

For this step, we use popular neighborhoods such as move, shift, swap-adjacent, exchange, 2-opt, and or-opt in Johnson & McGeoch (2003) and Reeves (1999). In addition, the pseudocode of the RVNS algorithm is given in Algorithm 8.

Elitism operator

Elitism is a process that ensures the survival of the fittest, so they do not die through the evolutionary processes. Researchers show the number (Talbi, 2009) (usually below 15%) of the best solutions that automatically go to the next generation. The proposed algorithm selects Sp individuals for the next generation, in which about 15% of them are the best solutions in the previous generation, and the remaining individuals are chosen randomly from P.

The stop condition

After the number of generations $(Ng)$, if the best solution has not been improved, then the proposed algorithm stops.

Evaluating the efficiency of selection

In this experiment, a new selection operator for the MFEA+RVNS algorithm effectively balances knowledge transfer and diversity. Due to being too expensive in computation, we choose some instances to evaluate the efficiency of this operator. In Table 2, the column MFEA-NR results from the MFEA+RVNS with the selection-based scalar-fitness only, while column MFEA+RVNS is the results of the MFEA+RVNS with both scalar-fitness and diversity. The $diff[\mathrm{\%}]$ column is the difference between the MFEA+RVNS and MFEA-NR in percentage.

In Table 2, the MFEA+RVNS outperforms the MFEA-NR in all cases. The selection operation that considers both scalar-fitness and diversity to pick parents is more effective than the one with scalar-fitness only. The fitness-based criterion promotes “survival of the fittest”, which is good for transferring elite genes between tasks, and good individuals are kept in each task, implying an accumulation of good genes. However, population diversity is important since it becomes a bottleneck. Our selection ensures that selection recognizes both diversity contribution and fitness in choosing the best individuals for reproduction.

Evaluating the balance between exploration and exploitation

Generally speaking, algorithms get stuck into local optimum because there is a lack of balance between exploration and exploitation. Exploration helps the search to explore extension spaces on a global scale, while exploitation helps the search to focus on local space by exploiting the information that a current solution is reached in this space. In this experiment, the balance between exploration and exploitation is considered. We run the MFEA with or without the RVNS on the same selected instances. In Table 3, the MFEA-NLS column is the MFEA without the RVNS, while the MFEA+RVNS column is the MFEA with the RVNS. The $diff[\mathrm{\%}]$ column is the difference between the MFEA+RVNS and MFEA-NLS.

In Table 3, the MFEA+RVNS obtains much better solutions than the MFEA-NLS in all cases. It indicates that the combination between the MFEA and RNVS has a good balance between exploration and exploitation. To study the ability to balance exploration and exploitation of the search space, we implement an experimental study on the distribution of locally optimal solutions. We choose two instances (n20w100.002 and n40w100.002) to perform one execution of our algorithm and record the distinct local optima encountered in some generations. We then plot the normalized tour’s cost vs its average metric distance to all other local minima (the distance metric and its average is defined in “Selection operator”). The results are illustrated in Figs. 4–7. The black “x” points indicate the result of the MFEA, while the red “x” points show the results of the RNVS. The normalized cost can be used as follows:

(4) $$\overline{f_j}={\displaystyle \frac{(f_j-f_j^{min})}{(f_j^{max}-f_j^{min})},}$$where $j=1,2$ is the $j$-task and $f_j^{min},f_j^{max}$ are the minimum and maximum cost values for all runs, respectively.

Figures 4–7 show that the black “x” points are spread quite widely, which implies that the proposed algorithm has the power to search over a wide region of the solution space. It is the capacity for exploration. On the other hand, the red points describe the search tends to exploit the good solution space explored by the MFEA. It is the capacity for exploitation. As a result, the algorithm maintains the right balance between exploration and exploitation.

Comparisons with the TSPTW and TRPTW algorithms

In Table 9, the average difference with the optimal solution for the TSPTW is 0.56%, even for instances with up to 200 vertices. It shows that our solutions are near-optimal for the TSPTW. In addition, the proposed algorithm reaches the optimal solutions for the instances with up to 80 vertices for the TSPTW. In Table 8, for the TRPTW, our MFEA+RVNS is better than the previous algorithms such as Ban & Nghia (2017), Ban (2021) and Heilporna, Cordeaua & Laporte (2010) in the literature when the average gap is −0.28% (note that: Ban et al.’s and Heilporna et al.’s (2010) algorithms is developed to solve the TRPTW only). The obtained results are impressive since it can be observed that the proposed algorithm finds not only near-optimal solutions but also the new best-known ones for two problems simultaneously. It also indicates the efficiency of positive transferrable knowledge control techniques between optimization tasks in improving the solution quality.

It is impossible to expect that the MFEA+RVNS always outperform in comparison with the state-of-the-art metaheuristic algorithms for the TSPTW and TRPTW in all cases because their algorithms are designed to solve each problem independently. Table 10 shows that the efficient algorithms for the TSPTW may not be effective for the TRPTW and vice versa. On average, the optimal solution for the TSPTW with the TRPTW objective cost is about 9.7% worse than the optimal one for the TRPTW. Similarly, the known best solution for the TRPTW using the TSPTW objective function is 20.6% worse than the optimal solution for the TSPTW. We conclude that if the proposed MFEA simultaneously reaches good solutions that are close to the optimal solutions for both problems and even better than the state-of-the-art algorithms in many cases, we can say that the proposed MFEA+RVNS for multitasking is beneficial.

Comparison with the previous MFEA algorithms

We adopt the proposed algorithm in the experiment to solve the TSP and TRP problems. Otherwise, we also use three algorithms (Ban & Pham, 2022; Osaba et al., 2020; Yuan et al., 2016) to solve the TSPTW and TRPTW.

Tables 11–13 compare our results to those of three algorithms (Ban & Pham, 2022; Osaba et al., 2020; Yuan et al., 2016) for some instances in both the TSP and TRP problems. The results show that the proposed algorithm obtains better solutions than the others in all cases. The difference between our average result and the optimal value is below 2.59%. It shows that our solution is the very near-optimal one. In addition, our algorithm reaches the optimal solution for the instance with 76 vertices. Obviously, the proposed algorithm applies well in the case of the TSP and TRP.

Statistical tests are used to check whether the difference between the proposed algorithm and the remaining ones is significant or not. A non-parametric test (Friedman and Quad test) is carried out in the group of the algorithms to check if a significant difference between them is found. The output of the Friedman test in Table 14 illustrates the rankings achieved by the Friedman and Quade tests. The results in this table strongly indicate considerable differences between the algorithms. Because the YA and OA have the largest ranking, the MFEA+RVNS is selected as the control algorithms. After that, we compare the control algorithms with YA and OA by statistical methods. Table 15 shows the possible hypotheses of comparison between the control algorithm and other algorithms. The statistical result shows that the MFEA+RVNS outperforms YA and OA with a level of significance $\alpha =0.05$.

Figures 8–13 describe the normalized tour’s cost vs its average metric distance to all other local minima of two algorithms (YA and OA). The black and red points are still the results of the MFEA and RVNS, respectively. Their algorithm explores widely in the solution space, implying a good capacity for exploration. However, exploitation capacity is not good enough. Figures 12 and 13 show that the RVNS exploits good solution spaces explored by the MFEA much better. It is understandable when the proposed algorithm reaches better results than theirs.

Moreover, Table 16 compares our results to those of three algorithms (Ban & Pham, 2022; Osaba et al., 2020; Yuan et al., 2016) in both the TSPTW and TRPTW problems. The results show that three algorithms (Ban & Pham, 2022; Osaba et al., 2020; Yuan et al., 2016) cannot find feasible solutions while the proposed algorithm reaches feasible ones in all cases. It is understandable because these algorithms drive the search for solution spaces that maybe not contain feasible solutions. Otherwise, the proposed algorithm guides the search process to feasible solution spaces. It is an important contribution because finding a feasible solution for the TSPTW, and TRPTW is even NP-hard (Ban, 2021).

Convergence trend

The normalized objective cost (see formulation 4) can be used to analyze the convergence trends of our MFEA+RVNS algorithm. The convergence trend of the two strategies is described in Figs. 4 and 5 for n40w40 and n80w80 instances. The x-axis describes the number of generations, while the y-axis illustrates the normalized objective value. The less and less the normalized objective value is, the better and better the algorithm is. In Figs. 14 and 15, Single-tasking (ST) converges better than multitasking (MT) in the whole evolutionary process while avoiding premature convergence to sub-optimal solutions by exchanging knowledge among tasks. That means, in general, multitasking converges to a better objective value.

When multitasking is run with the same number of generations as single-tasking, on average, it only consumes ${\displaystyle \frac{1}{K}}$ computational effort for each task (K is the number of tasks). Therefore, we consider the worst-case situation when the number of generations for multitasking is K times the one for single-tasking. If multitasking obtains better solutions than single-tasking in this case, we can say that multitasking saves computational efforts. The experimental results are described in Table 17. In Table 17, the first row shows the average gap of single-task for the TSPTW and TRPTW, while the second shows the average gap of multitasking with 100 generations. The result shows that multitasking consumes only ${\displaystyle 1/2}$ computational efforts to obtain better solutions than single-tasking.

In short, the efficiency of multitasking is better in comparison with single-tasking because of the process of transferring knowledge during multitasking. It is an impressive advantage of the evolutionary multitasking paradigm.