The new approaches for solving hierarchical Chinese postman problem with stochastic travel times

1.1 Literature survey

In this section, firstly, studies related to HCPP in the literature were discussed, and then studies related to stochastic parameters of CPP, STT-SVRP, and STT-TSP were examined, respectively.

HCPP was first proposed by Dror et al. by addressing a network of arcs divided into classes in which precedence relationships were described [5]. They demonstrated that the issue can be resolved in polynomial time if the precedence relationships are linear, and all sub-graphs are entangled in the hierarchy classes. In general, they proved that the problem is in the NP-hard class. In [6], the authors addressed a more rational scenario in which subgraphs are not entangled in hierarchical classes. In their study, they proposed an approach to the heuristic solution for HCPP that can be especially used in snow shoveling. In [7], the author developed a new heuristic method for the combination of disconnected hierarchical classes. It was claimed that this method established in the study accomplished better results than the heuristic model of Alfa and Liu [6]. In [8], the authors suggested an algorithm that needs less computational work and offers a clear solution in a shorter period than earlier studies. In this study, the first algorithm which provides a precise solution for HCPP was discussed. In [9], the authors established a method for converting the HCPP into an equivalent Rural Postman Problem. They suggested a splitting heuristic for unidirectional HCPP with linear precedence relations. The converted problem was subjected to a branch and cut algorithm to overcome HCPP, which has two objectives, namely, the hierarchical purpose and production time. In [10], the authors developed an existing algorithm that solves HCPP in their work and they reduced the time complexity of the original algorithm with their optimistic technique to the O(kn⁴) (where k is the number of layers in the graph and n is the number of nodes). Under such an algorithm, each sub-network’s distinct minimum cost routes were determined according to precedence levels. In [7], the authors established a heuristic approach that offers improved lower HCPP bound values compared to CPP. With this lower bound value, it was decided that in algorithms that provide exact solutions such as branch and bound algorithms, the optimum solution was achieved in a shorter period. In [11], the authors suggested a recent algorithm focused on the methodology of cell separation for efficient coverage of a defined location packed with random obstacles. First, the cells were separated into pieces in this hierarchical method, then, the CPP was resolved to determine a Euler tour that travels through these cells. In [12], the authors proposed a new method to eliminate the time complexity of algorithm O (kn⁵) (by Dror in [5]) and used the Kruskal method to reduce the number of edges in a network that has a time complexity of O (k²n²). In [13], the authors discussed the hierarchical mixed RPP in their study. A branch and cut algorithm offering a certain solution to the problem was presented in the study, and it has been shown that the results achieved with the algorithm were more effective and efficient than other existing methods. In [14], the authors discussed time-dependent HCPP when travel time changes according to the time of the day. A mixed-integer mathematical model for problem-solving was established in the research, and the genetic algorithm (GA) and hybrid simulated annealing were suggested as a solution approach to large-scale problems.

To the best of our knowledge, there are no studies in the literature concerned with stochastic travel times concerning HCPP. On the other hand, there is a very limited number of studies on the stochastic parameters of CPP. In [15], the authors addressed the CPP in the studies of networks with stochastic travel times. They proposed an algorithm as a solution. In [16], the authors studied three uncertain programming models for CPP with uncertain weights. They claimed that these models could be transformed into deterministic equivalent models. They used Dijkstra’s algorithm and Fleury’s algorithm to solve the problem. In [17], the authors proposed multi-objective CPP under the framework of uncertainty theory for an undirected connected network. They presented an expected value model as a solution approach.

There has been no prior research on STT-HCPP, as far as we know. However, a review of the related literature indicates that research on STT-SVRP and STT-TSP is present. Studies in this field were reached by entering the word group “stochastic routing problems” into the Web of Science (WoS) database. Keyword network analysis was performed using the VOSviewer (Version 1.6.9) package program. According to the bibliometric analysis made using the VOSviewer program, the most used keywords are those shown in Fig. 1.

OPEN IN VIEWER

Fig. 1

Keyword network analysis (VOSviewer).

As can be seen from Fig. 1, among the most used keywords in stochastic routing problems are “stochastic programming”, “vehicle routing”, and “stochastic demand”. In addition, it is seen that metaheuristic algorithms such as GA and simulated annealing used for the solution of large-scale problems are among these keywords. Some of the studies related to fuzzy routing problems were given in this section. In [2], the author discussed the TSP with stochastic travel time (STT-TSP) for the first time. In this research, a dynamic programming-dependent heuristic algorithm was suggested for problem-solving. In [18], the authors established generalized dynamic programming for STT-TSP, which even in the absence of uniformity, guarantees an optimum level. In [19], the authors conducted a study on stochastic travel and service time-based VRP. A banking example was examined in this study. For the issue under discussion, they proposed three separate models including the chance-constrained model. For the solution of these models, they proposed the branch and cut algorithm. In [20], the authors focused on SVRP on a network with random travel and service times in the study. Two stochastic programming models have been developed in the study. The first model minimizes the estimated delivery period, while the second model maximizes the likelihood of project completion at a specified period. In [21], the authors addressed the topic of vehicle routing in a stochastic network, utilizing real-time traffic information. A decision-making process was built in this research, based on the Markov decision procedure (MDP). In [22], the authors worked with the planning of truck routes within stochastic networks. A methodology for forecasting the arrival times of the customers was suggested in the process described in this study since travel and service times are uncertain. An approximate solution based on dynamic programming was provided using the estimated time of arrival. In [23], the authors studied vehicle routing with soft time windows and erlang travel times. In this research, travel times fit the gamma distribution. A tabu search algorithm was developed to solve the problem. In [24], the authors studied a TSP traveling with time windows and stochastic and dynamic travel time. In the research, it was presumed that arrival times in nodes were normally distributed, and a heuristic method for solving the problem was established. In [25], the authors addressed VRP with uncertain demand and travel time parameters to mitigate unmet demand. In the study, a chance-constrained programming technique was used, and a tabu search heuristic method was proposed to solve the model. In [26], the authors suggested a stochastic programming model that would take stochastic demand and travel time into account and introduced a GA created to solve this problem In [27], the authors examined a VRP with time windows and stochastic travel and service times in their study. The problem was modeled according to two different approaches namely the chance-constrained model and the two-stage stochastic programming with recourse model. A heuristic method based on tabu search which takes into account the stochastic nature of the problem was presented to overcome both models effectively. In [28], the authors have studied VRP with hard time windows and stochastic service times. In the study, it was accepted that the service times fit symmetrical triangular distribution and the chance-constrained stochastic programming model was used. In [3], the authors analyzed the VRP with stochastic travel times including soft time windows and service costs. The gamma distribution was used for travel time in the study. For the model’s solution, a tabu search method was suggested. In [29], the authors addressed the issue of stochastic vehicle orientation with soft time windows under uncertain travel and service time. They introduced a new stochastic programming model to reduce the carrier’s total expense, thus guaranteeing the likelihood of arrival to every customer in the minimum time. A recursive tabu search heuristic was developed to solve the problem. In [30], the authors examined VRP with hard time windows and stochastic service times. They used chance-constrained programming to model the problem. The study results indicated that the approach proposed is effective and that a stochastic chance-constrained model has benefits over deterministic models. In [31], the authors suggested a memetic algorithm for solving a VRP with time windows and stochastic travel and service times. The effects of the proposed Multipurpose Memetic Algorithm and the Multi-objective Recursive Local Search algorithms were contrasted, and their efficacy was demonstrated. In [32], the authors studied the problem of vehicle routing with a time window and stochastic travel times. A method for estimating the distribution of the initial service times and arrival times was suggested in the research. The results of the research demonstrate how solutions are influenced by adjusting customer care standards, distribution of travel time, and different parameter settings. In [33], the authors discussed VRPs with stochastic service and travel times. In the study, the mentioned time was examined concerning the triangular distribution. The model was first approached using a branch and cut algorithm or a Lagrange parsing method, and then, a heuristic method was used to create the solution. In [34], the authors studied the problem of VRP with hard time windows and stochastic travel and service time in their study. Travel and service times were regarded as parameters with normal distribution in this research, but it was noted that arrival times with normal distribution were not well modeled. A meta-heuristic based on Recursive Local Search was proposed for the solution to the problem. In [35], the authors focused on solving the stochastic VRP with time windows under uncertainty. In the research, given the complicated nature of chance-constrained stochastic programming, some measures were recommended for the uncertainties in the specific problem. Suggested suitable steps to solve the problem were introduced into an existing heuristic method of tabu-search. In [36], the authors studied the problem of multi-objective VRP with hard time windows and stochastic travel time and service time. Travel and service times were modeled as normal distribution in the study. Two separate algorithms were suggested for the solution to the problem, namely the Memetic Algorithm and Recursive Local Search, and the results were compared. In [37], the authors introduced some constrained covering solid TSPs in their study. In real-life situations, since some parameters cannot be expressed with crisp values, traveling costs are regarded as rough variables in their study. Covering distance is considered both a fuzzy and a rough variable. A new heuristic algorithm was suggested as a solution approach. In [38], the authors discussed the uncertain multi-objective multi-item fixed charge solid transportation problem with budget constraints. In the model suggested, many variables such as transportation costs, and transportation times were assumed as uncertain variables. In the uncertain model, the parameters were treated as zigzag and normal uncertain variables. Under the uncertainty theory, three different models, namely the expected value model, the chance-constrained model, and the dependent chance-constrained model were developed. Equivalent deterministic transformations of these models were generated, and they were solved through three different methods, which are the fuzzy programming method, linear weighted method, and global criterion method. In [39], the authors presented a new approach to the solution of open VRP. In this new method, the GA and modified Kruskal’s method were hybridized. This suggested approach is adaptable to real-life cases, and the obtained results of the suggested method have been compared with evolutionary methods. In [40], the authors examined the route-based MDP framework for stochastic dynamic routing problems. In this study, modeling techniques and solution methods used in the literature were compared. In [41], the authors have studied VRP with a makespan objective incorporating both stochastic and correlated travel times. A new method for solving the problem has been developed and the effect of the different correlation levels on the value of the objective function has been demonstrated. In [42], the authors examined the capacitated VRP under an uncertain paradigm. A fuzzy model was constructed for uncertain travel time and cost. As a solution approach, a hybrid metaheuristic algorithm based on GA and bacteria foraging optimization algorithm was designed. In [43], the authors discussed the Time Capacitated Arc Routing Problem with stochastic demands. To solve the problem, a strategic oscillation simheuristic algorithm was proposed. In [44], the authors presented a stochastic service network design model with an integrated VRP. A sample average approximation approach was proposed to solve the problem and combined with an iterated local search heuristic. In the study, a case study based on data for transport orders of a German freight forwarding company was discussed. In [45], the authors discussed a time-dependent VRP with soft time windows and stochastic factors. A Hybrid Algorithm was developed to solve the model. The sweep Algorithm and Improved Particle Swarm Optimization were combined. In [46], the authors addressed the issue of flying sidekick TSP with stochastic travel time. The problem was formulated as an MDP. The deep Q-network and Advantage Actor-Critic algorithms were proposed for the solution of MDP formulation.

When reviewing the HCPP studies in the literature, it was found that several of these studies do not take into consideration the travel times between nodes but acknowledge the distances between nodes. In addition, there was no research on this topic that deals stochastically with travel times. In order to fill this gap in the literature with this study, HCPP with Stochastic Travel Times (STT-HCPP), which is a new problem form, was taken into account. It was agreed in the analysis that travel times, which represent randomness, were normally distributed.

2.1 Stochastic programming

Difficulties were generally experienced while trying to determine the values of model parameters (c _j ,a_i,j, b _i ) used in modeling real-life problems with linear programming. In this context, taking the parameter values as exact values by utilizing existing evidence or past studies is not a correct approach since it may impact the study’s impartiality. Moreover, model parameters do not necessarily have exact values but are represented with random variables. Problems that contain some or all of the parameters of their model as random variables are named stochastic programming problems (SPP) [47]. Concerning the Stochastic programming that George Dantzig first proposed in the 1950 s, substantial improvement has been achieved in understanding model properties and developing algorithmic methods to solve them [48].

Stochastic programming is one of the most commonly employed techniques for routing problems, where parameter values are hard to express as exact values. And also, the amount of garbage to be collected before the vehicle reaches the specific places cannot be identified precisely in real-life issues, in a garbage collection process. Likewise, even though the vehicle is always traveling on the same road path, the duration of the travel cannot be described with exact values, since the arrival times can vary due to weather and environment. Again, the punctuality of a flight can vary depending on weather conditions.

SVRP occurs when some parameters of Classic VRP are random. The most common examples of this are stochastic travel time and stochastic demands [49].

Among the SVRP studies which were analyzed, some have explored creating a suitable mathematical model and approaches to solutions. In some studies, it was aimed to suggest algorithms for the solution of SVRP. Looking once again at the literature studies when building the mathematical model, it is shown that SVRP’s chance-constrained stochastic programming and stochastic programming with recourse approaches were used [50]. For example, in [51] the authors suggested some reduction methods for type-2 fuzzy variables in a transportation problem, and the proposed models were reduced to chance-constrained programming problems with different credibility labels.

For the HCPP belonging to the NP-hard problem class, paths/arcs are divided into classes and a precedence relationship is defined in these classes [5]. Therefore, in HCPP the order in which the paths/arcs are to be followed is set beforehand. The object of this type of problem is to establish the shortest tour/tours considering the precedence relationships and by traveling through each arc/path at least one time in a hierarchical network. Snow removal and salt dumping activities, where roads are categorized according to their importance (urban or rural, main road, secondary road, etc.) are one of the best examples that can be offered for HCPP in real life. Concerning these procedures, when the aforementioned procedures are performed on the main roads of the first precedence class firstly, and all the main roads are completed, we may pass to other roads.

One of the most important assumptions belonging to linear programming is the fact that model parameters have a deterministic structure. The classical mathematical model of HCPP is very useful in this context. However, these parameters take place in an uncertain way in most real-life problems. This uncertainty resulting from different factors can’t be represented with mathematical models. Therefore, chance-constrained stochastic programming has been used in this study to include this uncertainty in mathematical models. Most of the data excepted as exhibiting normal distribution since it would be more suitable for real life in terms of statistics. Therefore, within the scope of this study, c _ij objective function coefficients that show the travel time between two nodes in HCPP were considered random variables with normal distribution characteristics, and the model was transformed into STT-HCPP by making use of “the case where the only coefficients of c _j are random variables” which are explained in Section 2.1.1.1.

Let’s consider a G (V,E) network where V represents the set of nodes and E is a non-directional set of arcs (paths). This network is divided into m different sub-networks, each of these representing a hierarchical level. In this case, a hierarchical network is shown as; G (V,E) = G₁(V₁,E₁) ∪ G₂(V₂,E₂) ∪. . .  ∪ G_m(V_m,E_m) [56]. Here, G_m is the mth sub-network showing the arcs/ roads that will be traveled on the mth order.

The indexes, sets, parameters, and decision variables used in the HCPP integer linear programming model are shown below under respective titles [14].

Indexes;

i,j: Nodes on the network

t: Number of the edge traversal in the route (steps)

h: Hierarchical levels.

Sets;

i, j / V: Set of vertices i, j = {1, 2, . . . , n},

h / H: Set of hierarchies {1, 2, . . . , h},

t≤L: Number of steps L = 2 ∥E∥

E _h : Set of edges of h^th hierarchy class

E: Set of all edges in the network, E = {E ₁ ∪ E ₂ ∪...∪ E _h }

∥E∥: The total number of edges of h^th hierarchy class

δ_h(i): The edges of E _h set that exist from node i, δ_h (i) ={ j^|(i,j) ∈ E_h }.

δ(i): Set of all edges that exist from node i, δ (i) =⋃  _hɛH δ _h  (i) = { δ₁ (i) ∪ δ₂ (i) ∪ … ∪ δ _h  (i) }

Parameters;

C _ij : Distance matrix of the edge (i, j)

B _ij : Connection matrix of the edge (i, j)

O _ij : Precedence matrix of the edge (i, j)

M: Is a sufficiently large number

n: The total number of nodes in the graph.

Variables;

x ij t = { 1 0 if traversed from node i to node j at t^th step1, otherwise 0.

y ij t = { 1 0 if traversed from node i to node j at t^th step for the first time 1, otherwise 0.

φ ht = { 1 0 if traversed from all edges of h^th hierarchy in t^th step completed 1, otherwise 0.

Using this information, HCPP’s mixed-integer linear programming model can be written as follows [14]. This model is deterministic. The general aim of the paper is to handle the problem stochastically in order to make this deterministic model found in the literature more suitable for a real-life problem. In the mathematical model formulation, the arrival time between the nodes was taken as the basis instead of the distance in the objective function and it was aimed to minimize these times. Because, it is not always possible to express travel times with crisp values due to uncertain weather conditions, environmental conditions, or traffic conditions. Even on the same day, travel times between centers may vary due to different reasons such as accidents or construction-repair works that will prevent transportation. Stochastic programming is used to express these uncertainties arising from various reasons in the HCPP mathematical model. In this model; when the objective function coefficients of c _ij are considered as random variables with normal distribution characteristics, the problem transforms into STT-HCPP. As a matter of fact, the only parameter that can be considered stochastic due to the nature of HCPP is the objective function coefficients c _ij , which represent the travel times between nodes. Therefore, when the objective function coefficients are considered as random variables with c _ij normal distribution, the objective function z will also display normal distribution. Let the mean of the objective function z be expressed as E(z). In this case, the deterministic objective function that has the expected value model (E-model) equivalent to the HCPP probabilistic linear programming problem will be as in Equation (7). Here E(c _ij ) is the mean value of c_ij . So the mixed integer linear programming model of STT-HCPP becomes as follows. Min E ( z ) ∑ i = 1 2 ∑ j = 1 n ∑ t = 1 T E ( c ij ) x ij t(7)

Subject to; ∑ t = 1 L ( x ij t + x ji t ) ⩾ 1 ∀ ( i , j ) ∈ E(8) ∑ i x ij t - 1 = ∑ s x js t ∀ j , t t > 1 i , j , s ∈ V(9) ∑ ( i , j ) x ij 1 ⩾ 1 ( i , j ) ∈ δ 1 ( i 0 )(10) ∑ j x ji t ⩾ 1 ∀ t = t end , i = i 0(11) ∑ ( i , j ) ∈ E x ij t = 1 ∀ t(12) x ij t + x ji t ⩾ y ij t ∀ i , j , ti < j(13) ∑ t ′ < t ( x ij t ′ + x ji t ′ ) ⩽ M * ( 1 - y ij t ) ∀ i , j , t i < j(14) ∑ t = 1 L y ij t = 1 ∀ ( i , j ) ∈ E i < j(15) ∑ t ′ ⩽ t ∑ ( i , j ) ∈ E h y ij t ′ ⩾ ∥ E h ∥ * φ ht ∀ h , t(16) ∑ t 1 ⩽ t ∑ ( i , j ) ∈ E h + 1 ( x ij t ′ + x ji t ′ ) ⩽ M * φ ht ∀ t , h = 1 , . . , H – 1(17) x ij t , y ij t , φ ht ∈ { 0 , 1 } ∀ i , j , t , h(18)

Equation (7) expresses the deterministic objective function with the expected value model that aims to minimize the total tour time. Equation (8) is restriction representing the traveling from all roads on the graph at least once, Equation (9) is the provision of continuity among the nodes, Equation (10) is traveling from any one of the roads belonging to the 1st hierarchy that can be traveled from the i₀ start node in the first step (t = 1), Equation (11) is the return to the start node (I₀ = 1) at the last step, Equation (12) the travel from only one road in each step, Equation (13–15) is the assignment of value to the y ij t variable defining the step on which the (i, j) arc is traveled firstly. Equation (16) checks whether all the roads belonging to the h hierarchy have been traveled from in the t ^th step. Equation (17) shows that without completing the roads in the h^th hierarchy, the roads of the (h + 1)^th hierarchy are not passed from, and Equation (18) presents that the road usage variables must have integer values {0,1} [14].

3.1 Main steps of the proposed heuristic algorithm

The heuristic algorithm built within the framework of this study was based on a GSA algorithm and its logic can be stated as follows: by complying with the hierarchies, the list of roads that are not yet traveled will be recorded beginning from the starting node for the vehicle. This process occurs at two levels:

If there is an element in this list, the vehicle selects the closest road with minimal duration/distance between those roads which were not traveled before. To understand whether the arc selected in the algorithm has already been used, a matrix was generated that contains the visit information. If the value of an arc in the visit data is 0, it means that this arc has not been used, but if the value in the visit data is 1 or more, it means that the mentioned arc has been used before. Instant location updates are provided depending on the overall distance/time value and the node chosen.

In either of these two levels, a node or arc will be selected. The selected node is then added to the route, and the selected arc’s cost value is applied to the overall cost value. Besides, an update is provided which shows that the selected arc is being used. Some controls are performed after reaching the new location. Firstly, if the algorithm has traveled all the arcs within all hierarchies and if its position is 1, we end the study. In other terms, where there is no path remaining on the network for all hierarchies and the vehicle returns from the current point to the starting point. The flow scheme concerning the developed algorithm is provided in Fig. 2. Also the pseudo-code of the heuristic algorithm developed using the programming language Matlab-2019b is illustrated in Algorithm 1.

OPEN IN VIEWER

Fig. 2

Flow chart of the heuristic algorithm.

In this study, HCPP with Stochastic Travel Times (STT-HCPP), which is a new problem type, was taken into consideration. The proposed meta-heuristic algorithm was coded using the Matlab-2019b programming language.

Initial State: There are three parameters in the study that should be defined firstly: number of ants, number of iterations, and ant data table size.

The number of ants is one of the important parameters. More ants can deliver better outcomes and enhance the approach by increasing the chance. However, providing more ants raises the number of iterations, particularly in large-scale problems, causing the working period to be extended. According to the sensitivity analysis performed on the developed meta-heuristic, the number of ants was determined as 300. The number of iterations is the number of steps taken to obtain the optimum result. The low number of iterations might not be sufficient to achieve the outcome, but the high number of iterations often raises the calculation difficulties and thus, the working time [58]. According to the sensitivity analysis performed on the developed meta-heuristic, the number of iterations was determined as 1000. Besides, there is a visit matrix for each ant in the algorithm. This matrix of the visit indicates how many occasions the ant used a path on the routes it was traveling along. The general aim is to maintain these numbers in related visit data as low. As when we use these paths less, we will have the chance to keep the length of the route shorter. Unlike TSP, this new algorithm built for HCPP doesn’t depend on the amount of ant pheromone. In this type of problem, there is a possibility to cross a path more than one time. The usage aim of the algorithm’s visit data can be described as follows: reducing the cost, to prevent traveling at a constant local minimum.

There are two different route values of ants in the algorithm. The first of these is the general route. The general route is a path value that records the nodes the ant has visited beginning from the first node and following the rules of the hierarchy until it returns to the first node again. Another route value is the one in which the route of each hierarchy is recorded one by one.

Step 1. In the first iteration, each of the ants fills its visit matrix with “random choices, although it is likely to pursue the nearest node or the shortest path"

After the number of ants and iterations, the third parameter to be defined is the size of the ant data table. Two columns for each hierarchy are provided in the data table (1st hierarchy route is in the 1st column; while in the 2nd column, 1st hierarchy route length is provided). In the variable named “route capacity,” the value of rows in the table or how many ants’ data would be stored is established.

In the initial state, all data values were zero in the visit matrix since no location was visited. After the ant completes the whole path, a matrix is generated which is called “temporary visit data.”

Since there are 300 ants, there will be 300 matrices. These matrices are summed up with the mathematical logic and each value is divided by the number of ants to calculate the mean value for each path. With the equation below, in the temporary visit data matrix, we gathered the values for each ant.

temporary visit data = temporary visit data + k th visit data ;(19)

The mean value of these 300 matrices was determined and reported at the end of the first iteration, as it is only applicable to the 1st iteration. Since we don’t have any other details on the visit because ants have not traveled them before. In other iterations, a ratio including the amount of evaporation or the coefficient of forgetting has been used. At this phase, 80% of the old mean data is taken and the 20% becomes evaporated, and the newest one is summed up with the mean value of the ants of that iteration and the mean value is measured. Therefore, both the past visit data were used, and the mean of the visit data obtained by the ant in this iteration was summed up and as a result, the mean of the values obtained was determined.

In this way; this data was also included in the arc data’s third element, which belongs to a 3-dimensional matrix, the first element being hierarchy values and the second element being distance/time values. With this step, we move to the 2nd iteration.

Step 2. (Selection process of the ant): The ant conducts the selection process in three different ways which are by looking at the routes in the database, looking at a single route, or looking at the visit data.

The Ant will start from the 1st node and will conduct step by step the procedures mentioned below. All of those procedures mentioned are repeated on every node in the same way. In a sense, a copy of the route database matrix is transmitted to the ant before beginning operations, which keeps all the good routes in the past.

1. Before making a selection when in the 1st or any node, it is initially tested at this moment if there are any other arcs in the hierarchy that have not been visited. If there is no arc, we move on without doing something, in other words, if all the paths in that hierarchy have been traveled, this time, the level of the ant’s arc, namely the level of the hierarchy it will traverse, would be increased by 1 point.

With this procedure, it is checked whether there is an arc that has not been traveled yet. If the ant is already in the max hierarchy and the arrived node is the first one, the ant has found a route and exits. If not, the arc level is increased by 1 point and the ant moves on to the next hierarchy. Furthermore, if the ant is in the max hierarchy and has not yet reached the first node even if it has traveled all the arcs, it can proceed to travel without doing anything as per the methods described below.

2. If it continues, it implies it also has to be navigated within the framework of the graph. Now it’s verified if there are any not visited arcs, on the condition that they’re in the same hierarchy. If any arcs are meeting this condition, only their list is recorded. In other words, if 1–3 arcs have been used before, this arc will not be included in the list. Only the list of unused arcs is included.

3. In the 3rd step, firstly, it is checked whether the ant is on the “new route” or not.

Selection by the database:

The “options” matrix is created for the possible targets that can be present in the second step. This matrix consists of 3 rows and n number of columns. The value n is the number of targets that are present in the second step. In the rows of the options matrix. In the first row, the possible targets that are present in the second step are provided, in the second row, the mean values of pheromones are stated, and in the third row, probability values are presented.

In this selection, the calculation of pheromones is performed as follows. The one with the best value (the lowest) among the shortest distance/time paths is selected from the node where the ant is placed and divided into a value such as 10000. The purpose of this step is to determine a value as the probability value. When the same procedure is finished with all the targets it can travel, the probability of choosing the path would rise with the higher value mentioned above.

Hereinafter, we can discuss the pheromone effect and distance effect parameters. As mentioned earlier, what is called the pheromone effect in this algorithm is essentially the effect of visit data, which is logically contrary to the pheromone effect in the ACO. However, it is called in the algorithm as a pheromone effect, just for the sake of clarity. The distance effect is the parameter that decides how the distance value would influence the likelihood of selecting the arc. Within the scope of the study, these values were regarded as Equation (20) and probability values are calculated using Equation (21). pheromoneEffect = 4 ; distanceEffect = 0.3(20)

Probability Value = ( 1 distance ) distanceEffect + ( 1 pheromoneMean ) pheromoneEffect(21)

Then the probability values are determined and the 3rd row of the matrix options are generated as well. Those probability values are normalized by leveling down to a value between 0–1. Then they are put on the roulette table when determining the value to be chosen, and a random number between 0–1 is obtained. This number is measured in terms of scale with the probability value, and the selection procedure is created accordingly.

After the node is selected, a different control mechanism is conducted. This control is about knowing whether there is another route in the database which matches the route generated after the target node has been selected.

By proceeding in this manner, eventually at some point, there will be only one route or no route will remain. If there is just one route remaining, the ant’s “one route” function is enabled, and the only path remaining is transferred to the ant from that database. After that, there will be no need to look at the database until you proceed to a new hierarchy.

Selection by single route:

If the ant follows this last remaining route, the probability to deviate from the route is modified. The brief checking takes place accordingly; “Should I select the next target on this one remaining route or should I quit this route?"

The probability of deviating from the route is determined as 0,003. A random number between the first node and the remaining number of nodes is determined up to 2 times the value of the remaining number of nodes in the test problems addressed within the scope of the research. This method aims to try to deviate as much as possible from a location to complete the route, that is to say, at least to follow a different path when the end of the route is attained. In this way;

If the value generated is less than or equivalent to 3, the target node is chosen in that single route as well as the single route is discarded. If abandoned, we will act with the visit data as we no longer have a database or route.

Selection based on visit data

Now we’ll look at the visit details as we get to the next method of selection. Yet again, as stated before, if there are nodes not chosen before and if all the nodes that the ant might go to have already been traveled, both of their list would appear in the matrix named “options”. In other terms, if there is even a single arc that was not previously used in that node, the arc is chosen without taking into consideration the arcs traveled before. No other negligence can be observed in probability calculations. But if there’s more than one unused arc, a selection is created among them this time. The previously visited arcs are not included in the process. Thus, irrespective of the selection process, the matrix of the target options to which the ant can go is established in this way. The four criteria listed below are used as per the visit data in the selection phase:

Alpha: It is the effect of the final pheromone (visit data) on the selection and its value is regarded as 0,7.

Beta: It is the coefficient that determines the effect of the arc length or cost on selection, and its value was calculated as 0,3.

Theta: The effect of the global pheromone (visit data) on the selection was regarded as 0,6.

Gamma: The effect value of the local pheromone (visit data) on the selection was regarded as 0,4.

The values calculated within the study scope are not of considerable significance, and their total is 1 because they are probabilities. Only theta must be selected as 0.6 since we seek to draw the best value to the global visit data. And the ant depends mostly on the memory of ants who completed their route.

There are two different visit data used here. The first of these, the global visit data, is the mutual matrix where the mean score of visit data of all ants is calculated and a certain amount of it becomes evaporated. The amount of local pheromone or visit data reflects the visit data obtained up to now by the current ant. Therefore, the ant focuses on both the number of instances itself used this path previously and how much it was used by other ants on average when deciding in this manner.

The final amount of pheromone (FAP) is the value to be derived from a calculation of the global and local visit data. The FAP and probability values of being selected are calculated as follows:

FAP = ( amount of local pheromone ∧ gamma ) * ( amount of global pheromone ∧ theta )(22) value = ( ( 1 / FAP ) ∧ alpha ) * ( ( 1 / distance ) ∧ beta )(23)

By evaluating the node choices from where the ant is positioned, according to the cases described above, the arc states of these nodes are determined with the variable named “value”. The probability of being chosen is then determined using these values and a random number between 0–1 is created by putting certain probability values on the roulette table using the same logic described in the previous sections. This probability value is taken into consideration and controlled and the selection is performed.

This is how the selection process ends. The node is chosen in three different ways which are by looking at the routes in the database, looking at a single route, or looking at the visit data.

Step 3. (Updates and ending): No matter how the node is chosen here, the following 3 procedures are applied:

The local visit data relating to the arc used by the ant (the matrix of the ant’s visit) is adjusted. The existing value is increased by 1 point to show that this arc has been used.

The ant’s hierarchical route information passes through the following steps respectively. New information is added to the values which carry the best hierarchical routes in the matrix.

Firstly, it is checked whether the capacity of this table is full or not. In this way, how many routes the table will contain is determined in the algorithm by creating a variable called “route capacity”. If the route capacity has not been met yet, the ant’s hierarchical route data are respectively incorporated as it is.

With these procedures, the aim is to enable the table to maintain the best of each route of the hierarchy. These procedures are repeated after each ant completes its route. The iteration ends after all the ants finish their routes. At the end of the iteration, visit data are collected and updated. These procedures are carried out in the same way as defined in the preceding sections.

The algorithm’s pseudo code developed within the study scope and its detailed steps are shown in Algorithm 2.

Last but not least, distance values have been used directly for the HCPP solution in both algorithms in the objective function, but instead of the distance values for STT-HCPP, durations with defined mean and standard deviation values, which showed normal distribution characteristics have been used. Thus, the “random function” that generates random values for time values is applied in the algorithms.

Sensitivity analyses were performed on the developed ACO-based meta-heuristic according to different ant number and iteration number parameters. A sensitivity analysis was conducted to show the changes in the main output related to the changes in different important parameters [42]. This analysis was performed for all test problems. As an example, results were provided for Rnd_inst61 with 50 nodes and 350 edges. The sensitivity is depicted in Fig. 8 and Fig. 9. In Fig. 8, assuming the ant number along the horizontal axis and the objective function value (O ^GSA ) along the vertical axis, and in Fig. 9, taking the horizontal axis as the iteration number and the vertical axis as the objective function value (O ^GSA ); two different graphs are plotted.

OPEN IN VIEWER

Fig. 6

The objective function of the suggested algorithms.

OPEN IN VIEWER

Fig. 7

Computational times for the suggested algorithms.

OPEN IN VIEWER

Fig. 8

The sensitivity analysis results for the number of ants.

OPEN IN VIEWER

Fig. 9

The sensitivity analysis results for the number of iterations.

Here, the change in the objective function was observed by changing the ant number parameter between 150 and 400 and the iteration number parameter between 250-1250. It can be noticed from Fig. 8 that keeping the ant count constant at 300 provides the best cost for Rnd_inst61. At this point (O ^GSA ) remains almost the same. Likewise, as can be seen in Fig. 9, the best cost value was obtained since the number of iterations was set to 1000.