Solving the hierarchical windy postman problem with variable service costs using a math-heuristic algorithm

The HCPP has been defined over three decades ago in the seminal paper of Dror et al. (1987). The authors dealt with a CPP in which the edges of the underlying network are roads characterized by a hierarchical precedence relation. Even though their HCPP defined on an undirected graph is NP-hard, they succeeded to solve for the special class HCPP(c,l) in O(kn⁵), where n is the cardinality of the nodes set and k is the number of hierarchies in the network. Later on, several studies have focused on reducing the complexity of Dror et al. (1987)’s algorithm by trying to improve its features.

Ghiani and Improta (2000) developed an exact approach for the HCPP(c,l) having complexity O(k³n³) by constructing an alternative auxiliary graph. In this same direction, Korteweg and Volgenant (2006) reduced the complexity of Dror et al. (1987)’s algorithm to O(kn⁴) but rather than focusing on building a different auxiliary graph, they employed post-optimality techniques to improve the matching in the resulting auxiliary graph. Given the complexities of both the above exact approaches, the selection of the most appropriate algorithm depends on the characteristics of the instance to be solved, i.e., the value assumed by the number of nodes n compared to that of number of hierarchies k (Korteweg 2002).

Similar to Ghiani and Improta (2000), Cabral et al. (2004) developed an exact solution approach but for the HCPP(l) that was based on the idea of transforming the HCPP into a Rural Postman Problem (RPP) and solving it by a branch-and-cut technique (see also Ghiani et al. 2005, 2008).

The attention of the researchers in solving the HCPP has been directed even toward developing heuristic approaches. The first heuristic method, proposed by Alfa and Liu (1988), was defined for a directed network with weak precedence relation and without any connectivity restrictions on the arcs belonging to the same hierarchy. Their method consists in connecting and balancing the nodes that are endpoints of arcs belonging to the same hierarchy and then producing a single CPP tour based on the hierarchy-wise tours. Later on, Alfa and Liu’s method was outperformed by another heuristic suggested by Damodaran et al. (2008) which was based on a more efficient way of combining the unconnected subnetworks. Damodaran et al. (2008) focused on proposing good quality lower bounds for the HCPP with the aim of defining an efficient heuristic method. Colombi et al. (2017a) employed a math-heuristic to solve the HCPP starting from the exact solution of a Mixed RPP defined on an auxiliary graph for each hierarchy, whereas Colombi et al. (2017b) performed a polyhedral analysis of a hierarchical mixed rural postman problem and developed a branch-and-cut algorithm for its exact solution. For the sake of completeness, it is worth noting that meta-heuristic approaches, namely a genetic algorithm and a hybrid simulated annealing, have also been employed by Çodur and Yılmaz (2020).

The last family of approaches defined to solve the HCPP is based on solving the minimum spanning tree problem. Sayata and Desai (2015) implemented an efficient heuristic based on the use of Kruskal’s algorithm to reduce the number of edges in the underlying auxiliary graph. More recently, Colombi et al. (2017a) tackled the HCPP with mixed graph and employed a minimum spanning tree problem to identify an initial feasible solution and then embedded it within a tabu search procedure in order to improve and diversify the generated solutions.

As mentioned above, one of the novel aspects of our work is related to considering a particular variant of the HWPP in which a variable service cost scheme is implemented, i.e., the V-HWPP. Most of the scientific literature in the context of routing optimization has focused on variable service cost expressed in terms of time varying models. Interested readers may refer to the excellent review of Gendreau et al. (2015), in which the authors highlighted the scarcity of contributions related to the time varying ARPs, compared to their node routing counterpart. Few works appeared after Gendreau et al.’s review to deal with the time-dependent ARP in general (such as Sun et al. (2015) and Vidal et al. (2021)) and one is specifically dealing with the time-dependent HCPP (Çodur and Yılmaz 2020). However, our contribution here is not related to the variable service cost from the traversal time viewpoint, but rather to the service cost that decreases with the number of server passages. To the best of our knowledge there are only two papers that have adopted this particular variable cost scheme in the context of the windy CPP. The first is due to Dussault et al. (2013) who solved a snow plowing problem in which the cost of traversing a street varies based on its order within the plowing tour. Specifically, the authors considered that the cost of serving the roads decreases after the first pass by the plowing vehicle. The second paper, by Keskin and Yılmaz (2019), generalizes variable service cost scheme by assuming that each server pass will contribute to reducing further the roads’ service cost. This assumption seems to be very realistic and intuitive in a wide range of applications in which the multi-passing through roads and/or the learning process by the server contribute to decreasing the deadhead cost. For instance, the postman is expected to learn the roads better as the number of passes increases in the post-delivery application. Similarly, if each pass on the edges represents the shoveling of the accumulated snow on a specific edge, then the cost of the shoveling should not increase by the number of the passes on that edge as the snow becomes less and less at each pass of the snowplow vehicle. Our study will, thus, adopt the variable cost scheme of Keskin and Yılmaz (2019) and will implement it for the first time in the framework of the HWPP. On the other hand, it is a common practice to differentiate the service cost of the arcs from deadheading cost of the arcs as it is done for instance in Perrier et al. (2008). Similarly, Aráoz et al. (2013) associate prizes to arcs rather than costs and also differentiate between service and deadheading prizes, namely they take deadheading prize as zero.

This study will specifically focus on solving the V-HWPP, a particular variant of the HWPP in which is defined over an asymmetric network whose service cost decreases with the number of edge passes. Moreover, we restrict our attention here to the variant of the problem characterized by a linear precedence order of hierarchies and by a connected subgraph within each hierarchy.

From the above analyses it results evident that the above V-HWPP has never been addressed in the scientific literature. The objective of this study is to fill in this gap and to provide the practitioners and academic researchers with a new methodology that can contribute to solving the several real-life applications that arise in this specific ARP context.

The paper is organized as follows. Section 2 will formally introduce the problem and will propose an original formulation for the V-HWPP. Then an ad hoc math-heuristic approach based on the concept of layer algorithm and computational experiments are discussed in Sects. 3 and 4, respectively. Finally, some concluding remarks and future research suggestions are provided in Sect. 5.

We assume that the set of nodes and the set of edges connecting the nodes are, respectively, denoted by \(N\) and \(E\). Indices \(i\) and \(j\) are used to represent nodes of N and an edge connecting nodes \(i\) and \(j\) is denoted by edge \((i, j)\). \(H\) represents the set of hierarchies and index \(h\) is used to specify a hierarchy. The set of edges that belongs to hierarchy \(h\) is denoted as \({E}^{h}\). \(T\) stands for the set of steps while indices \(t\) and \(m\) are used to refer to specific steps while \(|T|\) represents the maximum number of steps. By the way, a step is used as a measurement tool to track the transition of the vehicle from one node to another. In other words, at each step, the vehicle passes from one node to another. For instance, if a route of a vehicle consists of nodes 1, 5, 3, 2, 5, 1, then we say that the vehicle is at the starting node 1 at the beginning of step 1 and it goes from node 1 to node 5 at step 1, it is at node 5 at the beginning of step 2 and it goes from node 5 to node 3 at step 2, then it is at node 3 at the beginning of step 3 and it goes from node 3 to node 2 at step 3, etc. Note that, the duration of the steps may change from step to another and from a vehicle to another as the distances between the node-pairs do not have to be identical. Finally, \(K\) is the set of number of passes and the index \(k\) is used to point out the members of \(K\).

The service cost parameters used in the formulation depend on the above-described sets and indices. \({c}_{ijk}\) denotes the \(k\) ^th service cost of edge \((i, j)\) if the service is through the direction from \(i\) to \(j\). Note that we assume an undirected graph implying that edges can be traversed through either direction. However, if an edge is served (independently from the service direction), the cost of the service reduces for both directions which also makes sense for real-life applications. For instance, if a road is served for a snowplow operation then the cost of the next service reduces for both directions. In addition, we assume that \({c}_{ij{k}_{1}}\ge {c}_{ij{k}_{2}}\) if \({k}_{1}<{k}_{2}\). That is, service costs do not become costlier as the number of the passes increases. Note that for each edge \((i, j)\) we also define \({c}_{jik}\) in the same manner to define the service cost for the direction from \(j\) to \(i\). Finally, parameter \({|E}^{h}|\) represents the number of edges belonging to set \({E}^{h}\).

There are five sets of decision variables in our model. \({\theta }_{ht}\), \({x}_{ijt}\), \({y}_{ijt}\), and \({\alpha }_{ijtk}\) are the binary variables of the model. \({\theta }_{ht}\) shows whether all edges of hierarchy \(h\) are served before step \(t\), or not. \({x}_{ijt}\) (similarly \({x}_{jit}\)) indicates whether or not edge \(\left(i, j\right)\) is served at step \(t\) through direction from \(i\) to \(j\) (through direction from \(j\) to \(i\)), and \({y}_{ijt}\) takes value 1 if edge \((i, j)\) is served before or exactly at step \(t\) independently from the passage direction, and it is 0 otherwise. Finally, \({\alpha }_{ijtk}\) is 1 if edge \((i, j)\) is served exactly \(k\) times before or at step \(t\) independently from the direction, and it is 0 otherwise. Our model results to be an integer nonlinear program since the objective function involves a multiplication of the binary variables \({\alpha }_{ijtk}\) and \({x}_{ijt}\) (\({\alpha }_{ijtk}\) and \({x}_{jit}\)). For the sake of convenience, a summary of all the sets, parameters and variables used along our formulation are provided in Table 1.

Our integer nonlinear program abbreviated as V-HWPPF (Variable HWPP Formulation) is given as:s.t.

The objective function (1) minimizes the total service cost. Constraint (2) and constraint (3) ensure that vehicle leaves the first node (depot) at step 1 and goes back to the same node at the last step, \(|T|\). Note that \(|T|\) is an upper limit value for the number of steps that can be considered in any day (we selected its value as the number of edges times twice the number of hierarchies). In order to avoid forcing the vehicle to perform exactly \(|T|\) steps on each day, we added a dummy arc that connects the starting node to itself and that has a traversal cost equal to 0. Thus, if on any day the vehicle needs to return to the starting point with fewer steps than \(|T|\), it can return to the starting node at the end of step \(|T|\) by traversing the dummy arc at 0 cost during the remaining steps. This ensures the satisfaction of constraint (3) for that day. Constraint (4) guarantees that the vehicle travels through a single edge at each step. By constraint (5) we make sure that each edge is traversed at least once independently from the direction of the passing. Constraint (6) ensures that the vehicle leaves any node \(i\) at step \(t+1\) if it entered to it at the previous step \(t\), and moreover it cannot leave node \(i\) at step \(t+1\) if it did not enter it at the previous step \(t\). Constraint (7) determines the value of each variable \({\alpha }_{ijtk}\) that takes value 1 depending on the number of travels through each edge before or at step \(t\). The constraint ensures that if \({\alpha }_{ijtk}\) is 1, then the number of travels through the edge (independent of the direction of the passing) is equal to \(k\). Note that only one of the \({\alpha }_{ijtk}\) variables existing on the left-hand side of the constraint will be 1 in the optimal solution, although it is possible to satisfy the constraint by setting more than one \({\alpha }_{ijtk}\) variables to 1. This is because the objective is a minimization function and the variable service costs are chosen to decrease by each pass. For instance, suppose that the number of total passes of an edge \(\left(i, j\right)\in E\) before or step \(t\) is 5. Hence, the right-hand side of constraint (7) written for edge \(\left(i, j\right)\) and for period \(t\) will be 5. It is possible to assign, for instance, both \({\alpha }_{ijt2}\) and \({\alpha }_{ijt3}\) to 1 (and all other \({\alpha }_{ijtk}\) variables to 0) which will make the left-hand side of the constraint as \(2\times {\alpha }_{ijt2}+3\times {\alpha }_{ijt3}\) which is equal to 5. Another alternative is, of course, to set only \({\alpha }_{ijt5}\) variable to 1, making the left-hand side of the constraint as \(5\times {\alpha }_{ijt5}\) which is also equal to 5. Since the cost of the latter alternative in the objective function, which is \({c}_{ij5}\), is lower than the cost of the first alternative, which is \({c}_{ij2}+{c}_{ij3}\), the solver will naturally choose the latter alternative. Note that if an edge, say \(\left(i, j\right),\) is traversed through \(i\) to \(j\), then the next passage cost should be decreased not only for the passage direction from \(i\) to \(j\) but also for the passage direction from \(j\) to \(i\). Hence, if an edge \(\left(i, j\right)\in E\) is traversed for instance 4 times in total independent of the passage direction, its fifth passage cost will be \({c}_{ij5}\) if the passage direction is from \(i\) to \(j\) and \({c}_{ji5}\) if the passage direction is from \(j\) to \(i\). Constraints (8) and (9) define the relationship between \({x}_{ijt}\), \({x}_{jit}\) variables and \({y}_{ijt}\) variable. Namely, if the number of travels through an edge is zero until a particular step, i.e., \(\sum_{m=1}^{t}\left({x}_{ijm}+{x}_{jim}\right)=0\), then \({y}_{ijt}=0\) follows. On the contrary, if \({y}_{ijt}=1\), then \(t\ge \sum_{m=1}^{t}\left({x}_{ijm}+{x}_{jim}\right)>0\) must hold. Constraint (10) defines the variable \({\theta }_{ht}\), i.e., it guarantees that \({\theta }_{ht}\) variable is equated to 0 if if any edge belonging to hierarchy \(h\) is not traversed before or during step \(t\). Similarly, constraint (11) avoids traversing edges belonging to hierarchy \(h+1\) if all the edges of hierarchy \(h\) are not traversed yet. Finally, constraint (12) puts the usual binary restrictions.

The above nonlinear model can be easily linearized by introducing a new continuous variable \({\mu }_{ijkt}\) (\({\mu }_{jikt}\)) to replace each multiplication \({\alpha }_{ijtk}{x}_{ijt}\) (\({\alpha }_{ijtk}{x}_{jit}\)). We also introduce seven new sets of constraints, which are linear and force \({\mu }_{ijtk}\)(\({\mu }_{jitk}\)) to be equal to \({\alpha }_{ijtk}{x}_{ijt}\) (\({\alpha }_{ijtk}{x}_{jit}\)). These constraints are given in the following.

As can be understood, if \({\alpha }_{ijtk}\) and \({x}_{ijt}\) (\({x}_{jit}\)) take value 1, then \({\mu }_{ijtk}\) is equated to 1 by means of constraints (13), (15) and (17) (constraints (14), (16) and (18)). Similarly, if \({\alpha }_{ijtk}\) or \({x}_{ijt}\) (\({\alpha }_{ijtk}\) or \({x}_{jit}\)) is zero, \({\mu }_{ijtk}\) (\({\mu }_{jitk}\)) is set to zero by means of constraints (13), (15) and (19) (constraints (14), (16) and (19)). This implies that the nonlinear multiplication \({\alpha }_{ijtk}{x}_{ijt}\) (\({\alpha }_{ijtk}{x}_{jit}\)) can be replaced by \({\mu }_{ijtk}\) (\({\mu }_{jitk}\)) after adding constraints (13)–(19) to the model.

Note that if there is only one hierarchy and if the cost parameters are taken as constant then the V-HWPP reduces to the WPP which is known to be an NP-Complete problem. Hence, V-HWPP is also a difficult problem and the solution time for formulation (1)–(19) will increase exponentially with the size of the instances which is characterized by the number of nodes, edges and hierarchies. For this reason, we will propose in the next section a heuristic method that is able to tackle even large-scale instances.

Given that problem V-HWPP and its formulation are being introduced for the first time in this study, there are no test instances related to such problem in the existing scientific literature. We generate, thus, a total of 84 test instances having 10, 20, 30, 40, 50, 75, and 100 nodes each with three different edge numbers varying from 13 to 3300 and four different levels of hierarchies. If \(n\) is the number of nodes, then the three different numbers of generated edges are defined as \(\lceil\frac{n\times (n-1)}{3}\rceil, \lceil\frac{n\times (n-1)}{5}\rceil,\lceil\frac{n\times (n-1)}{7}\rceil\), respectively. For example, for a 10-node test problem, we generate three different instances having \(\lceil\frac{10\times 9}{3}\rceil=30, \lceil\frac{10\times 9}{5}\rceil=18,\lceil\frac{10\times 9}{7}\rceil=13\) edges. We then randomly assign a number of edges to each level of hierarchy so that they sum up to the total edges number. For instance, if the number of edges is 13 and the number of hierarchies is 3, then the number of edges in hierarchies 1, 2 and 3 can take the values of 3, 6 and 4, respectively. In order to literally create the edges, we randomly select two nodes and form an edge and assign its hierarchy (starting from the first hierarchy) if the edge is connected to the previously generated edges belonging to the same hierarchy. If the created edge is not connected to the previously generated edges belonging to the same hierarchy, then we delete the edge and repeat the procedure until the number of edges belonging to the hierarchy reaches the assigned number of edges for that hierarchy. We then proceed to generate the edges of the next hierarchy. For instance, if the number of edges in hierarchy 1 is 3, then the first edge is created randomly between two randomly selected nodes and its hierarchy is assigned as 1. We then keep randomly generating the next edges until we find an edge that is connected to the first edge and assign its hierarchy as 1 too. We repeat the same procedure for edge 3 and assign its hierarchy as 1 and then proceed for generation of edges of hierarchy 2, and so on. Moreover, the first edge of a given hierarchy is forced to be connected to at least one of the higher hierarchy edges. In this way, we ensured that hierarchies are interconnected and that the edges within each hierarchy show the linear relationship. The number of hierarchies are selected as two, three, four and five, implying that we have four different number of hierarchies.

The first passage (or service) cost of each edge \((i, j)\) is generated randomly according to the expression \({c}_{ij1}=30+70\times rand\left(0, 1\right)\) where \(rand(0, 1)\) is a uniform random number generated from \((0, 1)\) interval. \({c}_{ji1}\) values for each edge \((i, j)\) are also calculated in a similar manner. Hence, the first passage costs are random values within the interval \((30, 100)\) for all edges. The values of the other cost parameters, i.e., \({c}_{ijk}\) and \({c}_{jik}\) values for each \(\left(i, j\right)\in E, k>1\), are generated using the formulas \({c}_{ijk} = \frac{{c}_{ij(k-1)}}{2} +\mathrm{rand}(\frac{{c}_{ij(k-1)}}{2})\) and \({c}_{jik} = \frac{{c}_{ji(k-1)}}{2} +\mathrm{rand}(\frac{{c}_{ji(k-1)}}{2})\) where \(\mathrm{rand}(m)\) denotes a real number randomly generated within the interval \((0,m)\). Note that the resulting \({c}_{ijk}\) and \({c}_{jik}\) values naturally have a non-increasing structure, and they are all positive due to the employed generation mechanism.

In this section, we assess the performance of the layer algorithm by comparing the minimum distances found by the WLA heuristic with the distances and the minimum possible lower bound values reported by the state-of-the-art MILP commercial solver Gurobi (2020) on the generated test sets. We code the WLA in Visual Studio environment with C# language and we carry out all experiments using a single Intel i7-8750H core. We let Gurobi run for at most three hours for each of the test instances and the minimum objective function values and the lower bound values found in the allowed computation times are reported. However, although Gurobi is able to produce feasible solutions for all instances with 10 nodes, it cannot produce feasible solution for any instance having more than 10 nodes. In addition, Gurobi is not able to produce even a lower bound larger than zero for four instances with 10 nodes and for none of the instances having 20 nodes. On the other hand, WLA produces feasible solutions for all the instances even for the largest instances having 100 nodes. The objective function values and the lower bound values found by Gurobi, and the objective function values found by WLA are reported in Table 3 (in the Appendix). For all the instances for which Gurobi was not able to produce an upper bound and/or a feasible solution, we used the notation NA (for non-applicable) in the related cell.

The first and second columns of Table 3 specify the number of nodes and number of edges, respectively, while the third column reports the number of hierarchies. The fourth and fifth columns report the lower bounds and minimum cost values obtained by Gurobi while the sixth column reports the minimum cost values found by WLA. Seventh and eighth columns represent respective percentage differences between the minimum costs found by WLA and Gurobi, and between the minimum cost found by WLA and the lower bound reported by Gurobi. The percentage difference values are calculated as \(100\times \left(\frac{{{c}_{G}-c}_{WLA}}{{c}_{WLA}}\right)\) and \(100\times \left(\frac{{c}_{WLA}-LB}{{c}_{WLA}}\right)\) where \({c}_{WLA}\) and \({c}_{G}\) represent the cost values reported by WLA and Gurobi, respectively, while \(LB\) stands for the lower bound value produced by Gurobi. Finally, the nineth and tenth columns represent the computation times (in seconds) needed by Gurobi and WLA to reach the obtained solution, respectively.

One can extract from Table 3 that the mathematical model results found by Gurobi outperforms WLA (by 2.24%, %0.68, and %0.47, respectively) only for three instances having 10 nodes, which are, respectively, the instances with 13 edges and five hierarchies, 18 edges and four hierarchies, and 18 edges and five hierarchies. For the one with 13 edges and five hierarchies, Gurobi’s result is also the optimal solution. Both methods are able to find the optimal solutions for two instances with 10 number of nodes, and for another two instances both methods produced the same result that is higher than the lower bound found by Gurobi. Finally, WLA is better than the mathematical model (respectively, by 4.42, 18.18, 10.26, 18.63, and 13.47%) for five of the instances with 10 nodes. In summary, the objective function values of WLA and Gurobi results for the instances with 10 nodes are similar but slightly in favor of WLA. The percentage difference between the average results for the instances with 10 nodes is 5.13% in favor of WLA. More interestingly, the average computation time used by Gurobi is 8390.97 s to reach these results while WLA spends only 1.43 s on average. Hence, for the smallest instances with 10 nodes, WLA is able to produce results that are at least as successful as the model’s results found by Gurobi but using much less computation time. On the other hand, Gurobi is not able to produce a feasible solution for any instance having at least 20 nodes, although it uses the entire allotted time which is three hours. We denote in the sequel as the Gurobi instances those instances for which Gurobi is able to produce a feasible solution. For a better general view of the results, we report in Table 2 the average values (extracted from Table 3) and also visualize the same objective function values for Gurobi instances in Fig. 4.

Besides, we also report the LB values found by Gurobi in order to better assess the quality of WLA results. Nevertheless, Gurobi is able to produce a lower bound larger than zero for eight instances with 10 nodes and it is not able to produce any lower bound larger than zero for the instances with at least 20 nodes. This implies that Gurobi is not able to solve even the linear relaxation of the problem for those instances within the given three hours time limit. The instances for which Gurobi is able to produce a lower bound larger than zero is called as Gurobi lower bound instances. We illustrate WLA results and the lower bound values for the Gurobi lower bound instances in Fig. 5 below.

As can be seen from Fig. 5, WLA produces almost the same LB values for the relatively small instances having 13 edges. Indeed, the average percentage difference between WLA results and the LB values are only 4.76% for the instances with 10 nodes and 13 edges. However, the average difference increases to 81.12% for the instances with 18 edges and for the remaining instances Gurobi is run (that is the instances with 10 nodes and 30 edges and the instances with 20 nodes) Gurobi reports zero as a lower bound implying that the percentage difference to be 100%. However, this does not directly indicate the deterioration of WLA performance with the increase in the instance size since even the lower bound values found by Gurobi worsen as the problem sizes increases. As a matter of fact, WLA is able to produce feasible solutions for much larger instances, reaching 100-node networks, whereas lower bounds larger than zero cannot be found by Gurobi for instances with 10 nodes and 30 edges and for all instances with 20 nodes. This may indicate that the capability of Gurobi in generating lower bounds is very sensitive to the increase in the instances size. For instance, it is possible to observe a rapid decrease in the lower bounds provided by Gurobi when the number of edges is increased from 13 to 18 for the instances having 10 nodes, whereas the objective function values of WLA possess a smooth linear-like structure increasing nearly at a constant rate. Hence, the increase in the percent deviation between WLA results and Gurobi’s lower bounds cannot be attributed to the bad quality of WLA results but rather to the rapid deterioration in the reported Gurobi lower bound values as the instances size gets larger.

In addition, Fig. 6 reports the average computational times employed by Gurobi and WLA. One may note that the average time spent by WLA is so small for all instances with 10, 20 and 30 nodes so that they are almost at negligible level compared to the average times spent by Gurobi (this is the reason for which there is no visible average computation time of WLA for those instances). Another observation is that WLA also uses negligible amount of time (around 0.5 min) for all instances with 30 nodes on the average while it, respectively, uses around 2, 5 and 20, minutes for instances with 40, 50 and 75 nodes on the average. Finally, the average time spent for 100-node instances is around 56 min. On the other hand, the average computation time used by Gurobi, respectively, for 10-, and at least 20-node instances are 8390.97 and 10,800.00 s. Hence, Gurobi uses all the allotted computation time for all the instances with at least 20 nodes. In summary, it is possible to claim that not only WLA is more accurate than the mathematical model solved by the commercial solver Gurobi, in the sense that the costs of the routes generated by WLA are much lower than Gurobi instances, but also that WLA is more efficient in generating the routes in much less computation times.

Finally, we observe that the running time of WLA exceeds three hours for only one instance (with 100-node instances and 1980 edges). For this reason, we avoided to test our WLA on larger instances since we think that we have achieved already significant results while solving instances that can be met in several real-life applications. The objective function values found by WLA for all the instances are depicted, for convenience, in Fig. 7, where it is clear that the objective function values increase in a smooth manner, which is another indicator of persistent achievement of WLA.