Emmanuel Oluwatobi Asani ,Aderemi Elisha Okeyinka ,Sunday Adeola Ajagbe ,Ayodele Ariyo Adebiyi ,Roseline Oluwaseun Ogundokun,2,7,⋆ ,Temitope Samson Adekunle ,Pragasen Mudali and Matthew Olusegun Adigun
1Department of Computer Science,Landmark University,Omu Aran,251103,Nigeria
2SDG 11 Group,Landmark University,Omu Aran,251103,Nigeria
3Department of Computing,MiVA University,Abuja,900211,Nigeria
4Department of Computer Science,Ibrahim Badamasi Babangida University,Lapai,911101,Nigeria
5Department of Computer Science,University of Zululand,Kwadlangezwa,3886,South Africa
6Department of Computer&Industrial Production Engineering,First Technical University,Ibadan,200243,Nigeria
7Department of Multimedia Engineering,Kaunas University of Technology,Kaunas,LT-44249,Lithuania
8Department of Computer Science,Colorado State University,Fort Collins,80523,USA
ABSTRACT The study presents the Half Max Insertion Heuristic(HMIH)as a novel approach to solving the Travelling Salesman Problem(TSP).The goal is to outperform existing techniques such as the Farthest Insertion Heuristic(FIH)and Nearest Neighbour Heuristic(NNH).The paper discusses the limitations of current construction tour heuristics,focusing particularly on the significant margin of error in FIH.It then proposes HMIH as an alternative that minimizes the increase in tour distance and includes more nodes.HMIH improves tour quality by starting with an initial tour consisting of a‘minimum’polygon and iteratively adding nodes using our novel Half Max routine.The paper thoroughly examines and compares HMIH with FIH and NNH via rigorous testing on standard TSP benchmarks.The results indicate that HMIH consistently delivers superior performance,particularly with respect to tour cost and computational efficiency.HMIH’s tours were sometimes 16%shorter than those generated by FIH and NNH,showcasing its potential and value as a novel benchmark for TSP solutions.The study used statistical methods,including Friedman’s Non-parametric Test,to validate the performance of HMIH over FIH and NNH.This guarantees that the identified advantages are statistically significant and consistent in various situations.This comprehensive analysis emphasizes the reliability and efficiency of the heuristic,making a compelling case for its use in solving TSP issues.The research shows that,in general,HMIH fared better than FIH in all cases studied,except for a few instances(pr439,eil51,and eil101)where FIH either performed equally or slightly better than HMIH.HMIH’s efficiency is shown by its improvements in error percentage(δ)and goodness values(g)compared to FIH and NNH.In the att48 instance,HMIH had an error rate of 6.3%,whereas FIH had 14.6%and NNH had 20.9%,indicating that HMIH was closer to the optimal solution.HMIH consistently showed superior performance across many benchmarks,with lower percentage error and higher goodness values,suggesting a closer match to the optimal tour costs.This study substantially contributes to combinatorial optimization by enhancing current insertion algorithms and presenting a more efficient solution for the Travelling Salesman Problem.It also creates new possibilities for progress in heuristic design and optimization methodologies.
KEYWORDS Nearest neighbour heuristic;farthest insertion heuristic;half max insertion heuristic;tour construction;travelling salesman problem
Various methods exist to solve the Travelling Salesman Problem(TSP),including exact solutions and heuristics [1].Finding the shortest tour involves determining the optimal route through a set of cities,ensuring each city is visited exactly once before returning to the starting point [1–4].This completed tour is known as the Hamiltonian Cycle.It is assumed that the cost of the distance between any pair of cities is predefined.The cost often relates to distance but may represent other notions,such as time or money.A Hamiltonian cycle,as depicted in Fig.1,refers to a graph cycle that traverses all the graph’s vertices exactly once before returning to its starting vertex.The Travelling Salesman must traverse cities 1to nin a Hamiltonian cycle,that is,start from city 1,traverse the remainingn-1 cities in a specified order and then connect back to the starting city,having touched each of the cities only once at a minimal cost.
Figure 1: A Hamiltonian weighted graph
The TSP is simple to define,but the complexity can easily expand exponentially as the solution space increases;thus,it is classified as an NP-Hard problem[1].
Exact techniques involve the explicit enumeration of the solution space;they try out all possible permutations of the solution.Thus,they have a complexity ofO(n!)[2–5].Exact techniques such as Dijkstra or Bellman-Ford algorithms may be deployed to effectively solve TSPs with a small degree of search space [6];others include Branch-and-Bound,Dynamic Programming Algorithms,Cutting Plane techniques and so on.Exact algorithms guarantee optimal solutions,at least hypothetically.However,the computational complexities of exact techniques are exponential [7];thus,the time required to provide their solutions grows exponentially with its solution space[6–10].Consequently,exact solutions are often impracticable and especially unsuitable for NP-hard problems with large solution space.For instance,the solution renowned as the best-performing exact technique is based on dynamic programming with a complexity ofOthus making TSPs impracticable to solve with the exact approach as the search space expands[11].These limitations of the precise method have driven the design,development,and deployment of heuristics.
Unlike precise methods [12–15],heuristics offer rough solutions while operating within a polynomial time limit.These methods are known for their reliance on probabilities and specific rules to solve problems[16–18].For an iterative procedure,heuristics can be used when an optimal solution is guaranteed to obtain the solution quickly or make a decision within an exact process.In other words,using heuristics to solve the TSP and problems related to the TSP provides acceptable results that are not too far from the optimal yet computationally affordable.
There are different classifications of heuristics based on the atomicity of their solution procedures,such as Tour Construction,Improvement/Local Search Heuristics,and Compound Heuristics [19–21].The Tour Construction heuristics are techniques that independently create solutions sequentially following predefined procedures within the problem space.These procedures outline the steps in the Initialization,Selection,and insertion stages.The focus of this study is on construction heuristics.Construction techniques generate reasonable approximate solutions for TSP and are equally central to the performance of the other classes of heuristics,such as improvement techniques,compound heuristics,and metaheuristics.Construction heuristics serve as a seed for the development of some heuristics and can be used to build initial solutions for high-performing techniques[22–25].Construction heuristics generally generate better initial solutions in high-performing improvement methods/metaheuristics than random initial solutions,thereby enhancing the quality of solutions[26–29].
Construction heuristic techniques have been widely utilized in addressing traditional combinatorial optimization challenges.Various methods,such as the Nearest Neighbour Heuristic (NNH),Nearest Insertion(NIH),Cheapest Insertion,Random Insertion,Addition heuristics,Savings Heuristics,and more are commonly used.Existing tour construction methods typically fall short by between 10–30% in terms of solution quality with a worst-case complexity ofT(n)=OThe Nearest Neighbour Heuristic,for instance,is fast,flexible,and simple to implement;it,however,solves the Travelling Salesman Problem using a greedy approach and suffers immensely from the “curse of dimensionality”phenomenon[30].The Farthest Insertion,on the other hand,renowned as the bestperforming lower-order complexity heuristic[31],suffers from a high upper bound of error with farther distance[32].According to Huang et al.[32],the probability of attaining an optimal tour is higher if the distance can be reduced.
Some well-known constructive heuristic methods are described briefly in Table 1.
Table 1: Description of some well-known tour construction heuristics
The Nearest Neighbour Heuristic can efficiently solve the TSP,albeit with slightly lower solution quality.The Nearest Neighbour Heuristic is a popular choice in research due to its quick implementation and straightforward approach.Experimentally,fs/fOPT≈1.26.
Recent research has highlighted the importance of using the Nearest Neighbor Heuristic in ways such as integrating it into methods [21–23] or utilizing it as an initial step in metaheuristics to create starting solutions [7,38].While the Nearest Neighbor Heuristic is valued for its speed and simplicity,its strategy of selecting nodes with the lowest cost can lead to what is known as the“curse of dimensionality.” This means that outliers become apparent as the search space and nodes grow.The term“curse of dimensionality”is commonly used to explain how increasing dimensions result in a search space,causing data sparsity and outlier occurrences.Fischer et al.[39]described the Quadratic Traveling Salesman Problem (QTSP) as an expansion of the Traveling Salesman Problem (TSP).To solve the QTSP,they utilized a total of nine algorithms: Three exact algorithms (a polynomial transformation-based exact approach to a TSP,branch-and-bound algorithm,and branch-and-cut algorithm),seven approximate algorithms (Cheapest-Insertion Heuristic (CI),Nearest-Neighbour Heuristic(NN),Two-Directional Nearest-Neighbor Heuristic(2NN),Assignment-Patching Heuristic(AP),Nearest-Neighbour-Patching Heuristic (NNP),Two-Directional Nearest-Neighbour-Patching Heuristic (2NNP),and Greedy Heuristic (GR),and Nearest-Neighbour Heuristic (2NN) were utilized.Within around ten minutes,the branch-and-cut approach could tackle complicated real-world problems with as many as one hundred nodes in an efficient manner,successfully reaching optimality.Heuristics could handle the most complex cases in ten seconds or less,which was far faster than the running times of exact algorithms,which were acceptable.In terms of processing speed,the various iterations of the Nearest Neighbour algorithm worked well;nevertheless,when it came to the correctness of their solutions,they were not as good as the exact applications.
Lity et al.[22]modelled the product ordering process of the incremental Software Product Line(SPL)analysis as a Travelling Salesman Problem(TSP).The aim was to optimize product orders and improve the overall SPL analysis.Products were modelled as nodes in a graph,and the solution-space information defined edge weights between product nodes.Existing graph route-finding heuristics were used to obtain the path with minimal costs.The first heuristic deployed was the Nearest Neighbour heuristic.The nodes were analyzed according to their similarity,so the NNH path was built by adding the product (node) most similar to the last node.However,it was observed that the approximation quality was poor because it first greedily added all the similar nodes and later suffered the curse of dimensionality when not-so-similar nodes were to be added.To circumvent this,a lookup was introduced to examine the next node to be added to the computed path.Thereafter,two insertion heuristics,namely Nearest Insertion and Farthest Insertion,were deployed to insert the remaining product into the existing path created by the Nearest Neighbour Heuristic.The proposed method was simulated on a prototype and evaluated for applicability and performance;a significantly more optimized SPL process was reported.
In implementing the Iterated Local Search technique,Bernardino et al.[40] used a modified version of the Nearest Neighbor heuristic to obtain an initial answer.The Family Travelling Salesman Problem(FTSP),a famous version of the Travelling Salesman Problem(TSP),was the focus of their research efforts.The first thing they did was model the FTSP,aiming to traverse a certain number of nodes in each cluster to the lowest possible cost.After that,the FTSP sub tour was designed in both a non-compact form.Three compact models were created:The Single Commodity Flow model(SCF),the Family Commodity Flow model (FCF),and the Node Commodity Flow model (NCF),for the compact variations options such as the Connectivity Cuts(CC)model,Rounded Visits(RV)model and Rounded Family Visits(RFV)model were considered.These models were compared using experiments carried out in the C++programming language.Implementing Iterative Local Search(ILS)in C++aimed to establish limits for situations beyond what direct methods could handle.During the first phase of constructing the ILS,an initial solution was constructed using a modified version of the Nearest Neighbor heuristic.Subsequently,a local search was run to arrive at a local optimum.As a further step,they used a perturbation to break out of the local optimum,and finally,they applied removal criteria to harvest the accumulated excess nodes.A well-known research hypothesis that construction tour heuristics create excellent first solutions was verified by the International Land Survey(ILS)performance.Experiments were carried out on benchmark instances that were accessible to the general public,and the results of the experiments were recorded.Results showed that noncompact models did better than their counterpart compact ones.
In the study by Kitjacharoenchaia [41],the Nearest Neighbour and two other heuristics were used to build an initial solution for their proposed model.Motivated by the increasing adoption of drones to achieve fast and flexible delivery,they conducted a study to simulate a drone delivery system formulated as a multiple Travelling Salesman Problem(mTSP)to minimize time.They implemented Mixed Integer Programming (MIP) to solve the problem and proposed a new technique called the Adaptive Insertion Algorithm (ADI).The ADI was implemented in two phases.An initial solution on only truck tours was built using three heuristics(namely the Nearest Neighbour Heuristic,Genetic Algorithm,and Random Cluster/tour).ThemTSPsolution was generated from the initial tour in the second phase.The method was then experimented on a single truck,multiple trucks,and a single truck and drone system,and the solution was compared with the existing MIP solution.The system reported a promising,competitive performance.It could be deduced that solutions generated from the initial solution by heuristics,such as Nearest Neighbour,hold promising performances.
Víctor et al.[42]solved the Euclidean TSPs of small and large data sizes with an efficient heuristic that is based on the Girding Polygon,which does not take up much computer memory space and produces approximate results that are near-optimal.The computational performance of the proposed approximate heuristic was compared to that of NNH,which is another approximate heuristic.It was noticed that the proposed heuristic outperformed NNH with an average error of 16.89% while that of NN was 26.55%;it also had standard deviations of 0.05%,and NNH had 0.04%.Even though the proposed algorithm did not produce optimal solutions for the instances used,it gave an approximate solution significantly better than NNH’s.
Insertion heuristics starts from an arbitrary point to form a sub-tour or partial circuit.Nodes not already in the sub-tour are then inserted based on predefined criteria such that the increment to the total distance of the sub-tour is minimized [23,32].Suppose that nodexis to be added to the edge(xi,xj),and given the cost functionc(xi,xj,x),then,c(xi,xj,x)=d(x,xi)+d(x,xj)-d(xi,xj).Each insertion technique method aims to add a node to an edge(that is,between two nodes)at a minimal cost.Given the sub-tourTi,and given thatxis the next node to be inserted,the insertion technique insertsxbetweenandinTi.Accordingly:
Insertion techniques are desirable because of their speed,ease of implementation,quality of solutions,and the fact that they can be easily modified to handle complex constraints[43].There are four generally known insertion techniques:Nearest Insertion,Cheapest Insertion,Random Insertion,and Farthest Insertion.Others include Priciest Insertion,quick insertion,and greatest angle insertion[36–44].
Insertion techniques can be used to get a good tour construction solution[45–47];according to Rosenkrantz et al.[33],insertion techniques findO(logn)approximate solutions.Insertion techniques are also used as an initial solution for improvement heuristics and metaheuristics;insertion techniques have been proven to significantly improve the performance of 2-Opt methods when used as initial solutions[46].Other researchers have presented new insertion techniques,either as a modification of state-of-the-art methods or as novel efforts.
Experimentally,the Farthest Insertion Heuristic has been known to outperform the Random Insertion,the Cheapest Insertion,and the Nearest Insertion in that order[33–47].
The proposed technique is an insertion method referred to in this study as the Half Max Insertion Heuristic (HMIH).The motivation was to explore some strategies with the possibility of improved tour accuracy.The design of the HMIH was motivated by two observations in literature: One,the superior solution quality of insertion techniques based on the use of polygons as an initial tour[23–42]and secondly,the limitation of the FIH’s accuracy due to the distance between its initial circuits and the next node to be inserted.Huang et al.[32]argued that although FIH performs relatively well,the distance between its circuit and new nodes to be inserted impedes its accuracy.
The insertion heuristics randomly pick one node fromQbyinit(Q) and create a partial circuit which is expanded with every iteration.The partial circuit is made up of a minimum polygon pointu,v,w.
LetTirepresent the partial circuit across nodes of sizeidefined asTi=(π1,π2,...,πi,π1).During the(i+1)thiteration,the insertion aims to add one node into the current circuit while minimizing the increment in the overall circuit distance.The objective is to determine how to select a node,x,fromQTiand determine how to insertxintoTito obtainTi+1.
Consider an insertion of a nodex(/∈Ti)betweenu,vandwinTi:
The method first determines the longest distance.dmaxof any node from either ofuorvand computeIt then find a nodewnot in the sub tour whose distance from eitheru or v≈Determine an edge(u,v)of the sub-tour to which the insertion ofwgives the smallest increase of length,i.e.,for which Δf=cux+cxv+cwx-cuvwis smallest.Insertxbetweenu,vandw.This process is iterated until a Hamiltonian cycle is formed.
The procedure is as follows:
The HMIH searches requireO(n)time;therefore,the time complexity of the algorithm isO(n2).The procedure is further depicted in the following flowchart in Fig.2.
Figure 2: Flowchart of the half max insertion heuristic
In implementing the proposed technique,the JAVA programming language version 13.0.1.was used,while GNUplot 5.2 and patch-level eight were used to plot the path graph.The heuristic was implemented on Intel Pentium Core i7 3 GHz,Windows 10(64 bit).
We experimented with the HMIH,together with two State-of-the-art heuristics(namely Nearest Neighbour Heuristic (NNH) and Farthest Insertion Heuristic (FIH)) on ten publicly available benchmark instances from TSPLIB made available by Heidelberg University on http://comopt.ifi.uniheidelberg.de/software/TSPLIB95/tsp/.There were three groups of instances tested.Group one was instances whose nodes were less than 100.Group two:Instances whose nodes are more than 100 but less than 1000.Group three:Instances whose nodes are more than or equal to 1000.The implementation module generated three outputs.The first is the computation time in milliseconds(ms).Millisecond is one millionth of a second.Evidently,the accuracy of time is improved at that level of granularity.The second output is the tour cost,the distance taken to generate the tour.This is necessary for the performance evaluation of the heuristic.The third output is the tour path,the order in which the nodes join the tour.Table 2.shows the computational speed of the NNH,FIH and the proposed HMIH on the ten benchmark instances considered.Table 3 shows the tour cost of each of the three heuristics on the TSP instances.
Table 2: The computational speed of NNH,FIH and HMIH on ten benchmark instances
Table 3: Tour cost of NNH,FIH and HMIH on ten benchmark instances
It is evident from Table 3 that the proposed HMIH has a shorter tour cost and is closer to the optimal tour cost in terms of solution quality than both FIH and NNH.FIH,however,compares more favourably with HMIH than NNH.
The FIH and HMIH tour graph for some benchmark instances is presented in Figs.3–6.Fig.3 displays the path graph of FIH and HMIH for theatt48.Fig.4 shows the path graph of FIH and HMIH for theeil51.Fig.5 displays the path graph of FIH and HMIH for theeil101,and Fig.6 displays the path graph of FIH and HMIH for thech150.
Figure 3: Path graph of FIH and HMIH for att48
Figure 4: Path graph of FIH and HMIH for eil51
Figure 5: Path graph of FIH and HMIH for eil101
Figure 6: Path graph of FIH and HMIH for ch150
Non-parametric analysis was conducted using Friedman’s test to validate the superior performance of the HMIH solutions for both NNH and FIH,which are classic tour construction heuristics.The test was conducted for all the ten instances considered in this study.The Friedman ranking was conducted based on the tour cost of the three algorithms,as presented in Table 3.The mean ranking for HMIH,NNH and FIH across all instances shown in Table 4 revealed a significant difference between the performance of HMIH and that of NNH and FIH.
Table 4: Freidman mean ranking for the Heuristics across all instances
These rank scores indicate that,on average,the HMIH algorithm(with the least score)performed best,followed by FIH and NNH.
Given the rank,as presented in Table 4,Freidman’s test was then conducted using the following equation:
where:
nis the number of instances=10
kis the number of TSP solutions,which in this case is 3
Riis the sum of ranks for thei-thalgorithm
The test was premised on the following hypothesis
-Null Hypothesis(H0):There is no significant difference among the algorithms.
-Alternative Hypothesis(H1):There is a significant difference among the algorithms.
Thus,Friedman’s test on the given data instances for the three TSP heuristics(NNH,FIH,HMIH)yielded a test statistic of approximately 15.37 and ap-value of about 0.00046.Since thep-value is less than 0.05,the null hypothesis that there is no significant difference in the performance of these algorithms is therefore rejected.This indicates that the HMIH performs significantly differently from the others.
Friedman’s analysis revealed that the HMIH technique exhibits a statistically significant superiority to NNH and FIH in performance.
Table 2 shows that the Nearest Neighbour Heuristic had the fastest computational speed,followed by the Farthest Insertion Heuristic and then the proposed HMI technique in all the instances.It should be noted that the proposed HMIH compared favourably with the FIH in this regard.This is consistent with literature findings that insertion techniques require more computational time than the NNH to complete tours [48–50].Additionally,the increased computational time of the proposed HMIH can be attributed to the additional computation of thehalf-maxinsertion criteria.This is consistent with works by[47–49,51],which suggest that computational speed is affected by the insertion criteria computations.
The quality of the heuristic’s solution was assessed using the following factors:
Percentage Error (δ):the percentage error of the heuristics’solution quality is the percentage deviation of the solution from the optimal tour solution.This is computed as×100%,wheresolηis the solution cost obtained by each heuristic,andoptis the optimal solution cost.This is equivalent to the performance ratio for suboptimal heuristics.
Quality impr. (Σ):this involves enhancing the solution quality of the HMI method with NNH and FIH.This is computed by ENNH/FIH-EHMIH,where ENNH/FIHis the error in percentage of the NNH or FIH and EHMIHis the error in the percentage of the HMIH.
Goodness Value( ):this is also known as accuracy.This is the inverse of error and is computed as
Table 5 displays thepercentageerror,qualityimprandgoodnessvaluefor all the heuristics on the ten benchmark instances.
Table 5: Percentage error,qualityimpr and goodness value for all the heuristics on the ten benchmark instances
From Table 5,HMIH outperformed FIH in all the instances exceptpr439,eil51andeil101.FIH outperformed HMIH for pr439,while FIH and HMIH had equal tour costs foreil51andeil101.The quality of the NNH tour was,on average,24.51% lower than the quality of the highest-quality trip.Regarding the examples that were considered,the FIH average performance was 16.24%of the Held-Karp lower limit.At its highest point,the Nearest Neighbour Heuristic attained a value of 32%,while its lowest point was 17.8%.At its highest point,the Farthest Insertion Heuristic achieved a value of 26.3%,while its lowest point was 6.7%.There is a correlation between these performances and the results that have been published in the literature about NNH and FIH[47–49].Conversely,the performance of HMIH was 12.1%lower than the ideal tour duration.This was a significant difference.The HMIH that has been presented has a quality improvement of 4.14%points on average compared to the FIH.This chart,seen in Fig.7,illustrates the percentage of departure that NNH,FIH,and HMIH have from the ideal tour length.
Figure 7: Percentage error of NNH,FIH and HMIH on the ten benchmark instances
The shaded area of the chart denotes the quality improvement of the HMIH over the FIH.
The proposed Half Max Insertion Heuristic consistently outperformed the Farthest Insertion.As seen by the shaded region of quality improvement in Fig.7,the heuristic was applied throughout a broad spectrum of benchmark examples,and it had a statistical significance of up to sixteen percent at one point.A comparison was made between the proposed HMIH and the Farthest Insertion,which had an average goodness value of 81.7%,and the Nearest Neighbour Heuristic,which had an average goodness value of 74.5%.This means the proposed HMIH has a higher accuracy than FIH and NNH(see Fig.8).It is worthy of note that the Farthest Insertion is considered the best-performing Insertion technique and among other lower-order complexity heuristics[31,47–50].
Additionally,while the Farthest Insertion is faster,the computation speed of the proposed HMIH is within the same range,and since the HMIH searches were conductedO(n) times,HMIH has the same complexity ofO(n2) as the FIH and NNH.The computational speed performance of HMIH appears to follow a trend among lower-order complexity heuristics where the performing method tends to take longer computation time,perhaps owing to a more intricate process involved in getting better performance.Except for Random Insertion,which requires no computation effort to add new nodes,the better the performance,the longer the time of computation tends to be[47–52].
Acknowledgement:The authors gratefully acknowledge the support of the Landmark University Center for Research Innovation and Development (LUCRID) for access to research repositories,literary materials,useful insights from affiliate researchers and funding.
Funding Statement:This research is supported by the Centre of Excellence in Mobile and e-Services,the University of Zululand,Kwadlangezwa,South Africa.
Author Contributions:The authors confirm their contribution to the paper as follows: Study conception and design: E.O.Asani,A.E.Okeyinka;data collection: A.A.Adebiyi,E.O.Asani,and R.O.Ogundokun;methodology: A.E.Okeyinka,A.A.Adebiyi,and E.O.Asani;validation and visualization:E.O.Asani,R.O.Ogundokun,T.S.Adekunle,P.Mudali,and M.O.Adigun;analysis and interpretation of results:E.O.Asani,S.A.Ajagbe,T.S.Adekunle,P.Mudali,and M.O.Adigun;draft manuscript preparation:R.O.Ogundokun,E.O.Asani,S.A.Ajagbe.All authors reviewed the results and approved the final version of the manuscript.
Availability of Data and Materials:The data used for the implementation of this study is publicly available benchmark instances from TSPLIB made available by Heidelberg University on http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/.
Conflicts of Interest:The authors declare that there is no conflict of interest regarding the publication of this paper.
推荐访问:Solution Insertion Travelling