
==== Front
Sci Rep
Sci Rep
Scientific Reports
2045-2322
Nature Publishing Group UK London

39261633
72242
10.1038/s41598-024-72242-0
Article
A discrete wild horse optimizer for capacitated vehicle routing problem
Fang Chuncheng fcc_168@163.com

12
Cai Yanguang 1
Wu Yanlin 1
1 https://ror.org/04azbjn80 grid.411851.8 0000 0001 0040 0205 School of Automation, Guangdong University of Technology, Guangzhou, 510006 China
2 Department of Mechanical and Electrical Engineering, Jieyang Polytechnic, Jieyang, 522051 China
11 9 2024
11 9 2024
2024
14 2127725 1 2024
5 9 2024
© The Author(s) 2024
2024
https://creativecommons.org/licenses/by-nc-nd/4.0/ Open Access This article is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License, which permits any non-commercial use, sharing, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if you modified the licensed material. You do not have permission under this licence to share adapted material derived from this article or parts of it. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by-nc-nd/4.0/.
The wild horse optimizer (WHO) is a novel metaheuristic algorithm, which has been successfully applied to solving continuous engineering problems. Considering the characteristics of the wild horse optimizer, a discrete version of the algorithm, named discrete wild horse optimizer (DWHO), is proposed to solve the capacitated vehicle routing problem (CVRP). By incorporating three local search strategies-swap operation, reverse operation, and insertion operation-along with the introduction of the largest-order-value (LOV) decoding technique, the precision and quality of the solutions have been enhanced. Experimental results conducted on 44 benchmark instances indicate that, in most test cases, the solving capability of discrete wild horse optimizer surpasses that of basic wild horse optimizer (BWHO), hybrid firefly algorithm, dynamic space reduction ant colony optimization (DSRACO), and discrete artificial ecosystem-based optimization (DAEO). The discrete wild horse optimizer provides a novel approach for solving the capacitated vehicle routing problem and also offers a new perspective for addressing other discrete problems.

Keywords

Discrete wild horse optimizer
Capacitated vehicle routing problem
Meta-heuristic
Discrete combinatorial optimization problem
Subject terms

Engineering
Mathematics and computing
issue-copyright-statement© Springer Nature Limited 2024
==== Body
pmcIntroduction

The vehicle routing problem (VRP) stands as a classic topic in combinatorial optimization, commanding significant attention in both academic and practical engineering domains. Among them, the transportation scheduling problem considering vehicle capacity is particularly critical, known as the capacitated vehicle routing problem (CVRP). It is an NP-hard problem that directly impacts the cost and efficiency of goods transportation.

Traditional solutions to the capacitated vehicle routing problem mainly include heuristic search algorithms (such as genetic algorithm, simulated annealing, etc.), integer programming algorithms (such as branch and bound, cutting-plane methods, etc.), and their approximation algorithms. These algorithms can provide relatively accurate solutions, but due to their high complexity and slow convergence speed, they often fail to adapt to real-world application scenarios.

In 1959, Dantzig1 first introduced the concepte of VRP to solve the optimal transportation cost of delivering gasoline to refueling stations. VRP seeks to identify the lowest cost routes for a vehicle fleet, emanating from a central warehouse to a myriad of geographically scattered customers, all while adhering to capacity restrictions2. Presently, conventional approaches to address CVRP encompass techniques such as genetic algorithm3, ant colony optimization4,5, variable neighborhood searche6, simulated annealing7,8, tabu searche9,10, GRASP11, among others.

Cai et al.5 proposed the dynamic space reduction ant colony optimization (DSRACO) to address the capacitated vehicle routing problem. This algorithm introduces an elite reinforcement mechanism and a large-scale neighborhood search approach. Gao et al.12 proposed a hybrid ant colony optimization based on fireworks algorithm (FWA), incorporating elite ant strategy and integrating the max-min ant system (MMAS) to enhance the attraction of local optimal paths for ants. This approach was similarly applied to address CVRP.

Souza et al.13 introduced a new heuristic algorithm based on the differential evolution algorithm with local search (CDELS) to solve CVRP, which combines local search processes such as exchange operations. Teoh et al.14 devised an improved differential evolution algorithm based on local search (DELS). Their approach encompasses three distinct local search techniques: point swapping, point dropping, and flipping. A hybrid variable neighborhood genetic algorithm for solving the post office delivery problem was developed by Sbai et al.15 It is a typical application of CVRP. Faiz et al.16 proposed a novel perturbation-based variable neighborhood search method. They combined it with an adaptive selection mechanism, referred to as PVNS-ASM. Their method was tested on 21 benchmark instances. Machado et al.17 proposed a hybrid mathematical algorithm for solving CVRP, which incorporates greedy random adaptive search, mathematical modeling, and variable neighborhood search in a two-stage approach.

Pelletier et al.18 introduced and applied a two-stage metaheuristic for solving CVRP. Rezaei et al.19 proposed a multi-population imperialist competitive algorithm with genetic local search (ICAHGS) for solving CVRP. A branch-and-bound technique for CVRP was presented by Rezaei et al.19, revealing that logistical costs can be curtailed by an estimated 5-20% through optimization. Ilhan20 introduced a simulated annealing algorithm with an improved crossover operator to tackle the vehicle routing problem with time windows (VRPTW). Laporte and Semet21 presented a series of crossover improvement strategies. Xiao et al.22 proposed the variable neighborhood simulated annealing (VNSA) algorithm, which is a combination of variable neighborhood search and simulated annealing, and tested it on benchmark instances. Akpinar23 unveiled a hybrid large neighborhood search (LNS) algorithm integrating ant colony optimization’s construction mechanism, termed LNS-ACO, yielding encouraging outcomes. An innovative heuristic algorithm, grounded in tabu search and adaptive large neighborhood search (ALNS), was developed by Kır et al.24 Additionally, a hybrid bat algorithm augmented with path relinking (HBA-PR) was crafted by Zhou et al.25, enriching the optimization framework.

Hosseinabadi et al.26 proposed a novel algorithm called CVRP_GELS, that employs gravitational emulation local search techniques to address the CVRP. Similarly, Altabeeb et al.27 integrated partial mapping crossover with dual mutation operators, combining 2h-opt algorithm and 2-opt algorithm, to introduce a new hybrid firefly algorithm. The algorithm was tested on benchmark instances and yielded promising results.

Qiao et al.28 proposed a modified particle swarm optimization (MPSO) for a vehicle routing problem with soft time windows, introduced an improved adaptive strategy by combining the subtraction function and ladder strategy to adjust inertia weight, and added a jump out mechanism to escape local optimal. Guo et al.29 explored a particle swarm optimization promotion strategy suitable for concrete transport vehicles. Ai and Kachitvichyanukul30 utilized Solution Representation-1 (SR-1) and Solution Representation-2 (SR-2) encoding, employing a particle swarm algorithm to solve CVRP. Tang et al.31 proposed a discrete artificial ecosystem-based optimization (DAEO) for the spherical capacitated vehicle routing problem, incorporating the 2-opt algorithm to simulate the mutation mechanism of organisms within the ecosystem.

In this paper, we introduced a discrete version of the wild horse optimizer (WHO), called the discrete wild horse optimizer (DWHO), specifically designed for solving CVRP. The wild horse optimizer is a novel metaheuristic algorithm conceived by Iraj Naruei and Farshid Keynia to tackle optimization challenges in continuous domains32. While its inception targeted continuous problems, the algorithm has found applications in diverse research areas. Specifically, Ali et al.33 employed the WHO to optimize distributed energy resources within radial distribution networks.

Furthermore, Ali et al.34 harnessed WHO for the management of frequency regulation in hybrid multi-area power systems. In the domain of energy consumption prediction for residential buildings, Vasanthkumar et al.35 leveraged WHO’s capabilities. Moreover, Vasanthkumar et al.36 explored its potential in dynamic energy management for hybrid electric vehicle batteries. To our current understanding, no existing literature has hitherto adapted WHO for discrete problems, especially in CVRP landscape.

This paper is organized as follows. Section “Mathematical modeling of capacitated vehicle routing problem” provides a comprehensive mathematical representation of CVRP. In section “Wild horse optimizer (WHO)”, we elucidate the core principles of WHO. Section “The proposed discrete wild horse optimizer(DWHO)” introduces DWHO combining decoding techniques and local search strategies. In section “Results and discussion”, we present an experimental evaluation of DWHO and engage in a detailed analysis and discussion of the results. We conclude with a summary of our findings and directions for future research in section “Conclusion”.

Mathematical modeling of capacitated vehicle routing problem

The mathematical model for capacitated vehicle routing problem is as follows20. It is represented by a graph G = (N, E), with N denoting nodes as {0, ..., n} and E signifying edges given by {(i,j); i,j∈N}. The depot is symbolized by node 0, while customers are denoted by N\{0}. Each customer i∈N′=N-0has a demand qi , where i = 1, 2, ..., n. Each edge has a cost TDij has a demand qi for i = 1, 2, ..., n. The cost for each edge is given as TDij, representing the travel distance between customers i and j. All vehicles in the set V share a uniform capacity limit Q.

The objective function:1 Minimize∑i=0N∑j=0N∑k=1KTDijXijk

Subject to:2 ∑k=1K∑i=0NXijk=1;∀j∈1,2,⋯,N;i≠j

3 ∑k=1K∑j=0NXijk=1;∀i∈1,2,⋯,N;i≠j

4 ∑i=0N∑j=0NXijk<Q

5 ∑j=0NX0jk=1,∀k∈V

6 ∑i=0NX0ik=1,∀k∈V

7 ∑i=0NXihk-∑i=0NXijk=0,∀h∈N,k∈V

8 Xijk∈0,1,i≠j,∀i,j∈N,k∈V

The decision variable:9 Xijk=1,ifvehiclektravesfromitoj0,otherwise

Where, equation (1) is the objective function aimed at minimizing the cumulative distance covered by the vehicles. Equations (2) through (8) delineate a series of constraints , detailed as follows: (i) Equations (2) and (3) guarantee that customers can only be serviced by a singular vehicle. (ii) Equation (4) mandates that the aggregate demand of any given route remains within the vehicle’s capacity constraints. (iii) Equation (5) asserts that every vehicle route starts and ends at the central depot. (iv) Equations (5) and (6) ascertain that each vehicle is deployed only once. (v) Equation (7) requires that the quantity of vehicles entering and departing from a node is consistent. (vi) Equation (8) stipulates that a variable can only adopt the values of 0 or 1. (vii) Equation (9) represents the binary decision variable.

Wild horse optimizer (WHO)

The wild horse optimizer is inspired by the social behaviors observed in wild horse populations. A typical wild horse herd comprises stable familial units consisting of a stallion (male horse), one or more mares (female horses), and their respective offspring. The stallion assumes a leadership role, guiding the herd in pursuit of suitable habitats. WHO drawing from behaviors such as grazing, mating, dominance, and leadership, serves as an adept optimization technique tailored for problems in continuous systems. The foundational principles of WHO encompass the subsequent five components: Population initialization. Forming horse herd groups, and selection of leaders. An initial population is randomly generated. Subsequently, this population is segmented into distinct groups. Each group consists of a leading stallion, accompanied by one or more mares and their offspring.

Grazing and mating behavior. Foals typically spend most of their time grazing around the herd. In simulating this behavior, the stallion is considered the center of the grazing area, and group members move and search around the leader with different radii, mimicking the grazing behavior of wild horses. A horse from group i departs to join a provisional group, and simultaneously, a horse from group j does the same. Assuming these two horses, being male and female, lack familial connections, mating is plausible. The resultant offspring must vacate the interim group and integrate into a different group, for instance, group k. This sequence encapsulates the natural mating and procreation patterns of horses. All diverse horses undergo this recurrent cycle of departure, mating, and reproduction. Foals’ grazing patterns are quantified by equation (10). 10 Xi,Gj=2Ycos(2πRY)∗(Staj-Xi,Gj)+Staj

Sta denotes the position of the leader(stallion), and R is a random number chosen from the range [-2, 2], primarily regulating the angle between individuals and the leader. Y is formulated by equations (11)–(13). WHO initially involves defining parameters such as the population size (popN), stallion ratio (PS), and mating probability (PC). The positions of stallions and foals are denoted as Xi=(Xi1,Xi2,⋯,Xin), where i∈(1,2,…,popN). Where, Xi represents the i-th individual, while popN∈(N+) signifies the population size, and n signifies the number of customers. The number of stallions, NS, is calculated as popN * PS, and the number of foals, Nf, is calculated as popN * (1 - PS). The path taken by the i-th horse through the customers is represented as: Xi1→Xi2→⋯→Xin→Xi1. The computation of the adaptive mechanism 11 L=R1→<ADP

12 IDX=(L==0)

13 Y=R2ΘIDX+R→3Θ(∼IDX)

14 ADP=1-itermaxiter

Where L is a binary vector composed of 0 and 1 , R1→ and R3→ are random vectors uniformly distributed within the range [0, 1]. R2 is a random number from the range [0, 1]. IDX represents the index value returned by the random vector R1 that satisfies the condition P == 0. Θ denotes the dot product. ADP is the coefficient that linearly decreases from 1 to 0, and iter indicates the number of iterations.

Group leadership. The leader (stallion) guides the group members to move towards more propitious habitats. If the current group dominates the area, they will utilize that region; conversely, if another group dominates the area, they must leave that location. The habitats symbolize the current optimal solutions.

Exchange and selection of leaders. Leadership is determined by fitness values. If there are group members within a group whose fitness is better than that of the current leader, a position swap occurs between the leader and the corresponding group member. The position of the new group leader represents the optimal solution for that group.

Saving the optimal solution. Upon comparing the fitness values across all group leaders, the leader possessing the paramount fitness embodies the global optimal solution. This solution is retained for subsequent iterations.

The mating behavior of foals is represented by equation (15):15 XG,kc=Crossover(XG,ia,XG,jb)i≠j≠k,a=c=endCrossover=Mean

XG,ia represents the position of individual a upon re-entering group i after leaving, while XG,jb represents the position of individual b upon re-entering group j after leaving. XG,kc represents the position of individual c in group k, generated through the mating of individual a from group i and individual b from group j. The positions within the parentheses in equation (15) denote the positions of their respective parents.

The leader directs the group members towards more favorable habitats. If the present group has dominance over an area, they occupy that region. Conversely, if a different group holds dominance, the former group is obliged to vacate the vicinity. This process can be depicted by equation (16).16 StaGi+1=2Ycos(2πRY)∗(WHbest-StaGi)+WHbest,ifR3>0.52Ycos(2πRY)∗(WHbest-StaGi)-WHbest,ifR3≤0.5

Leader exchange and selection: Initially, a leader is randomly chosen to uphold the algorithm’s inherent randomness. As the algorithm progresses, leaders are selected based on their fitness values. If a member within a group exhibits a fitness value surpassing that of the current leader, the positions of both the leader and the respective member undergo updating following equation (17).17 StaGi+1=XGi,ifcost(XGi)<cost(StaGi)StaGi,ifcost(XGi)>cost(StaGi)

Finally, the fitness values of all group leaders are compared, and the one with the best fitness value is deemed the optimal solution for that iteration. The fitness function is defined by equation (18), in which fitness signifies the individual’s fitness value, and L(c) denotes the travel distance.18 fitness=1/L(c)

The pseudocode of WHO is presented as algorithm 1. Algorithm 1 Pseudo-code of WHO

The proposed discrete wild horse optimizer(DWHO)

Discrete wild horse optimizer (DWHO)

To adapt the wild horse optimizer for CVRP, discrete techniques are integrated into WHO to represent solution, enabling the optimizer to tackle discrete problems. Simultaneously, three local search strategies-swap operation, reverse operation, and insertion operation-are introduced. We hereby name it the discrete wild horse optimizer (DWHO). Li and Yin37 introduced the Largest Ranked Value (LRV) method, primarily utilized in job sequencing for workshop scheduling. This method relies on the largest sorted value using random keys for discrete decoding.Figure 1 A 12-dimensional solution route.

Figure 2 Delivery scheme.

Algorithm 2 Pseudo-code of the proposed algorithm DWHO

Ai and Kachitvichyanukul30 introduced two decoding methods, SR-1 and SR-2, both originally designed for vehicle routing problems. SR-1 uses a 2m-dimensional encoding, while SR-2 adopts a 3m-dimensional encoding, dividing the paths. Although they can transform real-number encodings into integer decodings, the path division increases the computational complexity and decoding difficulty . Prins38 introduced the PRINS decoding method, which is also targeted at solving vehicle routing problems. Nonetheless, it also suffers from the drawback of high computational complexity. Qian et al.39 proposed the largest-order-value (LOV) decoding technique. In this approach, continuous values produced by DE are arranged in descending order, assigning integers based on this order. The highest real number value is given the first integer position, whereas the lowest value receives the highest integer rank. In this study, to more accurately represent the wild horse optimizer, we use real number encoding to represent the positions of the wild horses. Additionally, we utilize LOV decoding technique to decode our solutions.Figure 3 Swap operation.

Figure 4 Reverse operation.

Figure 5 Insertion operation.

Figure 6 A-set benchmark instances results obtained by DWHO.

Figure 7 P-set benchmark instance results obtained by DWHO.

Solution representations

To clarify the significance of the representation of CVRP solution, we explain it using a 12-dimensional solution vector, denoted as 1→2→3→4→5→6→7→8→9→10→11→12, as depicted in Fig. 1. Assuming the solution refers to a transportation plan, it is carried out by three vehicles, with each vehicle representing a sub-path. The start and end points of the sub-path are denoted by “0”, while other numbers indicate the customers to be served by each vehicle. The three sub-paths are illustrated in Fig. 2a. The overall delivery scheme is shown in Fig. 2b.

Initial population

In the initialization stage, the key parameters for the algorithm are defined, including the population size (popN), stallion ratio (PS), mating probability (PC), maximum number of iterations (MI), and distance matrix. These parameters play a critical role in shaping the behavior and performance of the algorithm throughout its execution. The population size, popN, dictates the number of potential solutions under consideration, and a thoughtful selection of this value can influence the diversity and convergence speed of the optimization process. The stallion ratio, PS, determines the proportion of leaders guiding the groups within the population, influencing the distribution of search efforts among the potential solutions. The mating probability, PC, governs the likelihood of two individuals mating to produce offspring, impacting the exploration and exploitation balance of the algorithm. The maximum number of iterations, MI, serves as a termination criterion, setting the limit for how many times the optimization process will iteratively refine the solutions. In combination, these parameters define the algorithm’s behavior, influence its performance, and shape its ability to find best known solutions or near best known solutions for the given problem.

Local search strategy

To enhance the algorithm’s local search capability, a variable neighborhood search strategy is introduced. This strategy incorporates three distinct types of neighborhood search operations: swap operation, reverse operation, and insertion operation. By employing these operations, the algorithm is able to effectively explore and exploit the solution space, thereby improving its ability to find best known solutions or near best known solutions. The pseudocode of DWHO is presented as algorithm 2.

Swap operation

For a path involving 7 customers, as demonstrated by the sequence 1→2→3→4→5→6→7, two positions are randomly selected for a swap operation. Specifically, the 2nd and 6th customers. This yields the modified path: 1→6→3→4→5→2→7. A schematic representation of this operation is provided in Fig. 3.

Reverse operation

Using the same 7-customer path, 1→2→3→4→5→6→7, two positions are randomly selected to initiate the reverse operation. Choosing the segment between the 2nd and 6th customers, the modified path becomes 1→6→5→4→3→2→7. Figure 4 illustrates the reverse operation.

Insertion operation

Given the path 1→2→3→4→5→6→7, two customers are randomly selected for an insertion operation. If the 2nd customer is chosen to be inserted after the 6th, the resultant path is 1→3→4→5→6→2→7. The insertion operation’s schematic is depicted in Fig. 5.Table 1 Comparison results of A-set benchmark instances.

		DWHO	BWHO	Hybrid firefly
algorithm	DSRACO	DAEO	
Instance	BKS	BS	Mean	Gap(%)	BS	Mean	BS	BS	BS	
A-n32-k5	784	784*	790.75	0.00	1371	1555.85	784	784	784	
A-n33-k5	661	661*	664.95	0.00	1101	1251.65	662	661	661	
A-n33-k6	742	742*	743.00	0.00	1091	1248.60	742	742	742	
A-n34-k5	778	778*	779.90	0.00	1337	1439.50	778	778	778	
A-n36-k5	799	799*	807.30	0.00	1388	1559.85	800	799	799	
A-n37-k5	669	669*	672.45	0.00	1225	1349.10	669	669	669	
A-n37-k6	949	950	968.05	0.11	1524	1667.15	954	949	949	
A-n38-k5	730	730*	733.20	0.00	1390	1504.05	739	730	732	
A-n39-k5	822	822*	824.30	0.00	1461	1587.20	822	822	822	
A-n39-k6	831	833	840.55	0.24	1490	1684.70	838	832	831	
A-n44-k6	937	937*	941.60	0.00	1706	1916.10	944	938	938	
A-n45-k6	944	952	957.80	0.85	1855	2088.15	965	953	951	
A-n46-k7	914	915	917.65	0.11	1801	1907.90	918	914	915	
A-n48-k7	1073	1073*	1095.55	0.00	2046	2208.85	1112	1075	1109	
A-n53-k7	1010	1013*	1024.35	0.30	2214	2352.30	1018	1013	1017	
A-n54-k7	1167	1067*	1181.70	0.00	2325	2512.20	1171	1167	1168	
A-n60-k9	1354	1363	1378.85	0.66	2626	2847.10	1365	1356	1362	
A-n63-k10	1314	1329	1344.25	1.14	2621	2841.90	1341	1316	1337	
A-n65-k9	1174	1178*	1198.15	0.34	2729	2905.85	1217	1178	1195	
A-n80-k10	1763	1783	1801.65	1.13	3968	4195.70	1822	1778	1791	

Table 2 Comparison of CPU computation times on A-set benchmark instances.

Instance	DWHO	BWHO	Hybrid firefly
algorithm	DSRACO	DAEO	
A-n32-k5	179.90	9.48	865.76	756.58	934.97	
A-n33-k5	595.53	9.94	852.87	785.02	984.78	
A-n33-k6	222.41	10.54	901.95	833.78	958.23	
A-n34-k5	220.04	9.73	959.46	847.27	1052.58	
A-n36-k5	331.14	10.19	705.90	922.30	1988.15	
A-n37-k5	231.17	9.91	1138.60	907.14	1518.48	
A-n37-k6	1141.95	9.92	1122.42	936.97	1205.51	
A-n38-k5	843.99	10.69	1131.73	874.89	1227.59	
A-n39-k5	260.99	10.09	1169.42	980.69	1250.25	
A-n39-k6	135.97	10.73	1110.46	943.51	1280.44	
A-n44-k6	432.67	10.37	1747.36	1241.72	1444.91	
A-n45-k6	624.79	10.02	1328.35	932.24	1518.48	
A-n46-k7	448.42	10.51	1443.90	1294.92	1605.48	
A-n48-k7	1085.85	10.44	1536.31	1216.80	1703.76	
A-n53-k7	448.24	10.69	1831.94	1199.11	1978.63	
A-n54-k7	1806.04	10.90	1742.13	1446.63	2320.62	
A-n60-k9	2140.09	10.98	1948.91	1304.45	2320.62	
A-n63-k10	1832.02	11.13	2308.13	1453.48	2401.92	
A-n65-k9	1607.52	11.72	2165.56	1229.31	2394.17	
A-n80-k10	3007.99	11.56	3082.98	1613.03	3218.99	

Table 3 Comparison results of P-set benchmark instances.

		DWHO	BWHO	Hybrid firefly
algorithm	DSRACO	DAEO	
Instance	BKS	BS	Mean	Gap(%)	BS	Mean	BS	BS	BS	
P-n16-k8	450	450*	450.00	0.00	453	481.80	450	450	450	
P-n19-k2	212	212*	212.00	0.00	288	337.50	212	212	212	
P-n20-k2	216	216*	216.00	0.00	304	359.30	216	216	216	
P-n21-k2	211	211*	211.00	0.00	297	364.20	211	211	211	
P-n22-k2	216	216*	216.00	0.00	307	383.35	216	216	216	
P-n22-k8	603	590**	596.60	-2.16	637	687.05	603	590	590	
P-n23-k8	529	529*	530.40	0.00	607	650.50	529	529	530	
P-n40-k5	458	458*	458.10	0.00	847	953.45	458	458	458	
P-n45-k5	510	510*	511.75	0.00	1033	1139.85	510	510	510	
P-n50-k7	554	554*	555.30	0.00	1054	1185.90	558	555	557	
P-n50-k8	631	636	645.95	0.79	1106	1181.30	644	635	641	
P-n50-k10	696	700	710.70	0.57	1203	1269.85	722	698	719	
P-n51-k10	741	741*	753.10	0.00	1270	1371.10	787	741	751	
P-n55-k7	568	568*	570.20	0.00	1177	1279.50	568	568	568	
P-n55-k8	588	577**	585.05	-1.87	1178	1288.05	588	591	588	
P-n55-k10	694	698	707.60	0.58	1223	1357.40	729	695	698	
P-n55-k15	989	956**	985.30	-3.34	1433	1547.85	1045	989	989	
P-n60-k10	744	746*	754.65	0.27	1389	1536.80	760	747	751	
P-n60-k15	968	974	997.75	0.62	1601	1720.90	1032	972	972	
P-n65-k10	792	801	814.80	1.14	1601	1698.05	820	795	797	
P-n70-k10	827	841	856.10	1.69	1635	1825.80	850	827	829	
P-n76-k4	593	593*	594.95	0.00	1756	1875.20	599	595	593	
P-n76-k5	627	627*	627.35	0.00	1761	1887.30	632	630	630	
P-n101-k4	681	681*	682.05	0.00	2360	2548.70	686	683	683	

Table 4 Comparison of CPU computation times on P-set benchmark instances.

Instance	DWHO	BWHO	Hybrid firefly
algorithm	DSRACO	DAEO	
P-n16-k8	34.78	9.82	185.28	303.45	205.55	
P-n19-k2	46.16	9.24	230.92	564.01	262.47	
P-n20-k2	54.36	9.10	262.47	622.82	331.30	
P-n21-k2	57.46	9.40	291.92	692.86	340.44	
P-n22-k2	69.30	9.72	337.67	739.25	349.93	
P-n22-k8	12.67	9.90	410.03	568.13	439.31	
P-n23-k8	79.34	10.09	959.46	734.94	465.87	
P-n40-k5	240.28	10.34	1166.36	937.27	1332.24	
P-n45-k5	298.47	10.73	1384.09	1174.22	1484.83	
P-n50-k7	736.98	11.35	1614.62	1018.94	1620.48	
P-n50-k8	1430.13	10.94	1696.13	997.05	1706.76	
P-n50-k10	1627.44	11.57	1698.12	1076.04	1798.66	
P-n51-k10	1138.99	11.64	1747.36	1272.26	1957.01	
P-n55-k7	471.27	10.59	1799.88	1062.26	1965.95	
P-n55-k8	246.72	10.83	1744.86	1097.10	1911.45	
P-n55-k10	996.01	11.07	2010.33	1055.15	1817.32	
P-n55-k15	468.03	11.17	2159.18	1040.32	2405.00	
P-n60-k10	2112.22	10.72	2193.79	1227.57	2261.24	
P-n60-k15	2529.33	11.39	2488.45	1286.31	2488.45	
P-n65-k10	2492.11	11.13	2127.34	1331.13	2444.15	
P-n70-k10	2698.85	11.27	2580.25	1428.65	2581.86	
P-n76-k4	314.31	11.05	2535.39	1295.68	3206.03	
P-n76-k5	413.44	11.68	2555.33	1431.83	3044.85	
P-n101-k4	502.66	12.13	3525.47	1809.46	4363.99	

Table 5 Wilcoxon test comparison results of A-set benchmark instances.

Instance	DWHO	BWHO	FA	DSRACO	DAEO	
A-n32-k5	7.91E+02±6.62E+00	1.56E+03±8.55E+01+	8.01E+02±1.30E+01+	7.88E+02±3.59E+00=	7.93E+02±9.54E+00=	
A-n33-k5	6.65E+02±5.22E+00	1.25E+03±6.45E+01+	6.67E+02±5.11E+00+	6.63E+02±2.04E+00=	6.81E+02±7.18E+00+	
A-n33-k6	7.43E+02±1.26E+00	1.25E+03±5.11E+01+	7.51E+02±9.61E+00=	7.44E+02±1.36E+00=	7.54E+02±9.64E+00+	
A-n34-k5	7.80E+02±3.63E+00	1.44E+03±4.66E+01+	7.81E+02±2.72E+00+	7.82E+02±5.50E+00=	7.94E+02±9.16E+00+	
A-n36-k5	8.07E+02±6.59E+00	1.56E+03±7.19E+01+	8.04E+02±3.55E+00=	8.05E+02±6.24E+00=	8.19E+02±1.38E+01+	
A-n37-k5	6.72E+02±3.91E+00	1.35E+03±5.73E+01+	6.74E+02±6.94E+00=	6.74E+02±3.15E+00=	6.73E+02±3.91E+00=	
A-n37-k6	9.68E+02±9.81E+00	1.67E+03±6.90E+01+	9.67E+02±1.09E+01=	9.54E+02±1.04E+01-	9.67E+02±1.59E+01-	
A-n38-k5	7.33E+02±6.76E+00	1.50E+03±6.24E+01+	7.57E+02±1.33E+01+	7.34E+02±5.61E+00=	7.50E+02±1.72E+01+	
A-n39-k5	8.24E+02±2.00E+00	1.59E+03±6.63E+01+	8.30E+02±8.64E+00=	8.27E+02±4.96E+00=	8.32E+02±9.61E+00+	
A-n39-k6	8.41E+02±1.29E+01	1.68E+03±6.45E+01+	8.54E+02±1.01E+01+	8.37E+02±6.70E+00-	8.39E+02±9.33E+00-	
A-n44-k6	9.42E+02±4.47E+00	1.92E+03±7.17E+01+	9.60E+02±1.07E+01+	9.42E+02±8.65E+00=	9.49E+02±9.54E+00+	
A-n45-k6	9.58E+02±7.28E+00	2.09E+03±7.13E+01+	9.88E+02±2.74E+01=	9.59E+02±7.60E+00+	9.71E+02±1.50E+01=	
A-n46-k7	9.18E+02±8.22E+00	1.91E+03±6.25E+01+	9.60E+02±3.10E+01+	9.18E+02±5.28E+00=	9.45E+02±2.07E+01+	
A-n48-k7	1.10E+03±2.28E+01	2.21E+03±9.51E+01+	1.13E+03±1.47E+01+	1.08E+03±5.57E+00=	1.12E+03±9.90E+00+	
A-n53-k7	1.02E+03±9.76E+00	2.35E+03±7.05E+01+	1.03E+03±1.43E+01+	1.02E+03±3.65E+00=	1.04E+03±9.44E+00+	
A-n54-k7	1.18E+03±1.01E+01	2.51E+03±9.15E+01+	1.18E+03±7.82E+00=	1.17E+03±6.67E+00-	1.20E+03±1.83E+01+	
A-n60-k9	1.38E+03±1.58E+01	2.85E+03±1.11E+02+	1.37E+03±6.37E+00=	1.36E+03±4.48E+00-	1.38E+03±1.78E+01=	
A-n63-k10	1.34E+03±1.33E+01	2.84E+03±9.83E+01+	1.35E+03±1.04E+01+	1.32E+03±5.95E+00-	1.39E+03±2.93E+01+	
A-n65-k9	1.20E+03±1.96E+01	2.91E+03±8.62E+01+	1.24E+03±1.79E+01+	1.18E+03±6.58E+00=	1.21E+03±1.56E+01+	
A-n80-k10	1.80E+03±1.23E+01	4.20E+03±1.30E+02+	1.85E+03±2.42E+01+	1.79E+03±8.50E+00-	1.81E+03±1.26E+01+	
+/=/-		20/0/0	12/8/0	1/13/6	14/4/2	

Table 6 Wilcoxon test comparison results of P-set benchmark instances.

Instance	DWHO	BWHO	FA	DSRACO	DAEO	
P-n16-k8	4.50E+02±0.00E+00	4.82E+02±1.11E+01+	4.50E+02±0.00E+00=	4.51E+02±1.51E+00+	4.50E+02±0.00E+00=	
P-n19-k2	2.12E+02±0.00E+00	3.38E+02±2.61E+01+	2.12E+02±0.00E+00=	2.13E+02±2.01E+00+	2.12E+02±0.00E+00=	
P-n20-k2	2.16E+02±0.00E+00	3.59E+02±3.16E+01+	2.16E+02±0.00E+00=	2.17E+02±9.12E-01+	2.16E+02±0.00E+00=	
P-n21-k2	2.11E+02±0.00E+00	3.64E+02±3.13E+01+	2.11E+02±0.00E+00=	2.13E+02±2.81E+00+	2.11E+02±0.00E+00=	
P-n22-k2	2.16E+02±0.00E+00	3.83E+02±3.25E+01+	2.16E+02±0.00E+00=	2.18E+02±1.69E+00+	2.16E+02±0.00E+00=	
P-n22-k8	5.97E+02±5.50E+00	6.87E+02±2.48E+01+	6.03E+02±0.00E+00+	5.93E+02±2.94E+00+	5.97E+02±4.63E+00=	
P-n23-k8	5.30E+02±7.54E-01	6.51E+02±1.90E+01+	5.36E+02±1.08E+01=	5.32E+02±2.95E+00=	5.32E+02±7.05E+00=	
P-n40-k5	4.58E+02±4.47E-01	9.53E+02±3.92E+01+	4.69E+02±1.63E+01+	4.62E+02±4.18E+00+	4.63E+02±6.65E+00+	
P-n45-k5	5.12E+02±1.86E+00	1.14E+03±4.40E+01+	5.16E+02±4.76E+00+	5.15E+02±3.83E+00=	5.15E+02±3.21E+00+	
P-n50-k7	5.55E+02±2.05E+00	1.19E+03±4.76E+01+	5.71E+02±1.05E+01+	5.60E+02±5.74E+00=	5.74E+02±1.15E+01+	
P-n50-k8	6.46E+02±6.03E+00	1.18E+03±3.53E+01+	6.59E+02±1.09E+01+	6.44E+02±8.90E+00-	6.78E+02±1.65E+01+	
P-n50-k10	7.11E+02±1.04E+01	1.27E+03±3.76E+01+	7.35E+02±1.30E+01+	7.03E+02±4.17E+00-	7.39E+02±1.67E+01+	
P-n51-k10	7.53E+02±1.22E+01	1.37E+03±4.11E+01+	8.04E+02±1.50E+01+	7.56E+02±1.11E+01=	7.87E+02±1.78E+01+	
P-n55-k7	5.70E+02±3.74E+00	1.28E+03±3.38E+01+	5.77E+02±1.48E+01=	5.72E+02±2.35E+00=	5.79E+02±8.81E+00+	
P-n55-k8	5.85E+02±3.36E+00	1.29E+03±4.00E+01+	5.94E+02±6.90E+00+	6.00E+02±8.50E+00+	5.94E+02±6.22E+00+	
P-n55-k10	7.08E+02±9.22E+00	1.36E+03±4.78E+01+	7.51E+02±1.63E+01+	7.00E+02±4.59E+00-	7.05E+02±8.68E+00-	
P-n55-k15	9.85E+02±1.54E+01	1.55E+03±6.71E+01+	1.07E+03±1.26E+01+	9.93E+02±1.95E+00+	9.98E+02±1.51E+01+	
P-n60-k10	7.55E+02±8.85E+00	1.54E+03±4.75E+01+	7.79E+02±1.06E+01+	7.51E+02±4.27E+00=	7.63E+02±8.35E+00+	
P-n60-k15	9.98E+02±1.67E+01	1.72E+03±6.77E+01+	1.05E+03±1.25E+01+	9.78E+02±1.01E+01-	9.84E+02±1.52E+01-	
P-n65-k10	8.15E+02±8.66E+00	1.70E+03±5.65E+01+	8.40E+02±2.03E+01+	8.02E+02±5.18E+00-	8.02E+02±8.59E+00-	
P-n70-k10	8.56E+02±1.03E+01	1.83E+03±6.12E+01+	8.72E+02±2.15E+01+	8.34E+02±1.11E+01-	8.48E+02±1.72E+01-	
P-n76-k4	5.95E+02±2.19E+00	1.88E+03±5.63E+01+	6.22E+02±2.07E+01+	6.00E+02±2.67E+00+	6.01E+02±8.34E+00+	
P-n76-k5	6.31E+02±4.17E-01	1.89E+03±5.77E+01+	6.54E+02±1.42E+01+	6.36E+02±5.71E+00+	6.37E+02±6.63E+00+	
P-n101-k4	6.82E+02±1.50E+00	2.55E+03±7.20E+01+	7.18E+02±1.73E+01+	6.89E+02±4.69E+00	6.91E+02±7.44E+00+	
+/=/-		24/0/0	17/7/0	11/7/6	13/7/4	

Results and discussion

Parameter setting

In this section, we carry out extensive experiments to verify the performance of DWHO. The experiments encompassed the benchmark instances A-set and P-set40. We compared the experimental results with four algorithms: basic wild horse optimizer(BWHO), hybrid firefly algorithm27, dynamic space reduction ant colony optimization(DSRACO)5 and discrete artificial ecosystem-based optimization(DAEO)31, to validate the effectiveness of DWHO. BWHO is a basic wild horse optimizer that only performs discretization on the obtained results without incorporating optimization and local search strategies. The solving effectiveness is moderate. The hybrid firefly algorithm integrates 2-opt, accelerating the algorithm’s solution speed and enhancing the optimization capability of the firefly algorithm. In DSRACO, ACO is integrated with a dynamic space reduction method, an elite enhanced mechanism, and large-scale neighborhood search methods to improve the solution. The DAEO uses five local search operators to discretize the position update formula of the original AEO algorithm and introduces the 2-opt algorithm to simulate the mutation mechanism of organisms in the ecosystem.

The computational configurations are listed as follows.OS: Windows 10 (x64)

CPU: Intel Core i5-11400 (2.60 GHz)

RAM: 16GB

Language: Matlab 2016B

The following are the relevant parameter settings for DWHO.Population size: popN=50

Stallion ratio: PS=0.2

Mating probability: PC=0.13

Maximum number of iterations: MI=1500

Number of Stallions: NS=popN*PS=10

Number of foals: Nf=popN*(1-PS)=40

For the sake of fairness in comparison, we set the number of iterations to 1500. Each experiment is conducted 20 times. The experiments terminate upon either reaching the maximum number of iterations or obtaining an early optimal solution. Concurrently, the Gap is defined by the equation (19). All algorithms were calculated on the same machine.19 Gap=(BS-BKS)/BKS∗100%

Where BS denotes the optimal solution achieved by the DWHO, BKS represents the best known solution for the benchmark instance, and Gap signifies the error of BS.

To enhance the diversity of the algorithm’s search space, we introduced swap, reverse, and insertion operations in our experiments. The inclusion of local search strategies also improves the algorithm’s solving capability. During each swap operation, two nodes are randomly selected for swapping. Similarly, for the reverse operation, two nodes are randomly selected, and the points between them are reversed. For the insert operation, two nodes are randomly selected. Each type of operation is performed 50 times.

Comparison results of A-set benchmark instances

The experimental results of DWHO, BWHO, hybrid firefly algorithm, DSRACO, DAEO are compared using A-set benchmark instances as the experimental dataset.The comparison results are shown in Table 1. From Table 1, DWHO matches or closely approximates BKS in numerous instances, it is evident that for small scale instances, the solutions of DWHO are equivalent to the best known solutions. For medium scale and large scale instances, the solution Gaps of DWHO are relatively small, mostly around 1%. Compared with BWHO, DWHO exhibits significant advantages across all instances, greatly enhancing solution accuracy. In comparison with hybrid firefly algorithm, DWHO also holds a notable advantage, as the solutions of most instances outperform those of hybrid firefly algorithm. When compared to DSRACO, DWHO similarly demonstrates outstanding performance, with only a slightly weaker solving capability for large scale instances. In Table 1, data marked with * and highlighted in bold signify solutions obtained by DWHO that are either equivalent to the best known solutions or the best among the five algorithms. Similarly, the solving capability of DWHO is remarkable compared to DAEO. On small-scale instances, both algorithms perform comparably, while on medium and large-scale instances, DWHO significantly outperforms DAEO. We also compared the CPU runtime of each algorithm on the A-set benchmark instances, measured in seconds, summarized in Table 2. As shown in Table 2, BWHO has the shortest runtime due to the lack of local search strategies. DWHO demonstrates a clear advantage over the other three algorithms on small and medium-scale instances. Although it is not as fast as DSRACO on large-scale instances, it shows a noticeable advantage over hybrid firefly algorithm and DAEO.

As depicted in Fig. 6, the route diagrams for A-n32-k5, A-n33-k6, A-n55-k9, and A-n64-k9 indicate that the paths derived using DWHO for these instances are rational and clear.

Comparison results of P-set benchmark instances

By utilizing P-set benchmark instances as the experimental dataset, a thorough examination of the experimental outcomes of DWHO is conducted in comparison with BWHO, hybrid firefly algorithm , DSRACO, and DAEO. The outcomes of this comparative analysis are showcased in Table 3. Just as observed from Table 3, it becomes evident that, particularly for small scale instances, DWHO consistently secures optimal solutions that align precisely with the best known solutions. For instances of medium scale and larger scale, DWHO effectively minimizes solution discrepancies, predominantly within the narrow margin.

In P-set benchmark instances, DWHO consistently demonstrates a pronounced advantage, substantially enhancing solution accuracy. The solution precision of DWHO distinctly surpasses the solution capabilities of BWHO, consistently producing superior results across all P-set benchmark instances. Relative to hybrid firefly algorithm, DWHO retains a significant edge; in most instances, its solutions outperform those of hybrid firefly algorithm. When juxtaposed with DSRACO, DWHO maintains commendable performance, particularly in larger scale instances. For instance, in large-scale problems such as P-n76-k4, P-n76-k5, and P-n101-k4, DWHO’s problem-solving prowess evidently outshines DSRACO. Similarly, DWHO exhibits superior solving capability over DAEO on most medium- and large-scale instances. Additionally, in instances like P-n22-k8, P-n55-k8, and P-n55-k15, the results achieved surpass the best known solutions. It is particularly noteworthy that for the large scale instance P-n101-k4, while other algorithms under comparison fail to ascertain the best known solution, DWHO succeeds, attesting to the efficacy of our introduced DWHO algorithm. In Table 3, data marked with * and highlighted in bold signify solutions obtained by DWHO that are either equivalent to the best known solutions or the best solutions among the five algorithms, while data marked with ** and highlighted in bold indicate solutions that are superior to the best known solutions. On the P-set benchmark instances, the CPU runtime of DWHO, compared to other algorithms, is significantly faster than the other three algorithms, except for BWHO. This also demonstrates the effectiveness of our proposed algorithm. The results are shown in Table 4.

As shown in Fig. 7, from the route diagrams of P-n22-k2, P-n45-k5, P-n55-k7, and P-n101-k4, it can be inferred that DWHO effectively retrieves their optimal solutions.

Effectiveness verification

There are five involved algorithms in this experiment. The experiment is conducted on the A-set benchmark instances and P-set benchmark instances, and each instance is run 20 independent times, and the mean value and standard variation are recorded as the final results. To make the comparison results statistically sound, we use the Wilcoxon’s rank sum test, a nonparametric statistic test, for a single-instance analysis, the significance level α is set to 0.05. The symbols “+”, “=”, and “-” denote that DWHO is significantly better than, similar to, and significantly worse than its competitor on an instance, respectively, according to the p value. The final results of the above five involved algorithms are shown in Tables 5 and 6.

As shown in Table 5, DWHO significantly outperforms BWHO, hybrid firefly algorithm and DAEO on A-set benchmark instances, and it is comparable to DSRACO. When compared to DSRACO, DWHO is only slightly weaker on a few instances. Table 5 demonstrates that DWHO completely outperforms BWHO. In comparison with hybrid firefly algorithm, DWHO shows superiority in 12 instances, equivalence in 8 instances, and no instances of inferiority. When compared to DSRACO, DWHO is superior in 1 instance, equivalent in 13 instances, and slightly inferior in 6 instances. Against DAEO, DWHO excels in 14 instances, is equivalent in 4 instances, and is inferior in 2 instances. Similarly, Table 6 demonstrates that DWHO consistently outperforms BWHO in all evaluated instances of the p-set. When compared to the hybrid firefly algorithm, DWHO exhibits superior performance in 17 instances, is equivalent in 7, and does not perform inferiorly in any instance. In contrast to DSRACO, DWHO shows superiority in 11 instances, similarity in 7, and is relatively inferior in 6 instances. Compared to DAEO, DWHO is superior in 13 instances, equivalent in 7, and inferior in 4 instances. As observed from the data, DWHO demonstrates superior performance compared to the other four compared algorithms on both A-set and P-set benchmark instances. This assertion is grounded on a rigorous assessment that incorporated wilcoxon’s rank and sum test.

Conclusion

In this paper, we incorporate the wild horse optimizer from the engineering domain to propose a discrete wild horse optimizer for solving CVRP. Based on the foundation of WHO, three neighborhood local search strategies - swap operation, reverse operation, and insertion operation - are applied to enhance both the search capability and solving capability of DWHO for CVRP. Moreover, a decoding technique is introduced to allow DWHO solutions to represent vehicle routing schemes. Experiments on 44 benchmark instances were conducted, and the results indicate that DWHO with decoding technique can effectively address discrete combinatorial optimization problems, especially CVRP, with satisfactory performance. DWHO was compared with BWHO, hybrid firefly algorithm, DSRACO, and DAEO. The comparative results revealed that DWHO possesses robust problem-solving abilities. It significantly outperforms BWHO, and generally, the solutions from DWHO are superior to those obtained from hybrid firefly algorithm, DSRACO and DAEO. In A-set benchmark instances, DWHO achieves the best known solutions for most medium scale and small scale instances. For larger sclae instances, the solution deviations are relatively minor. As for P-set benchmark instances, not only does DWHO attain the best known solutions for medium scale and small scale instances, but it also accomplishes this for the large sclae instance P-n101-k4, a feat the other four compared algorithms could not achieve. This highlights the efficacy and superiority of our proposed algorithm. In future work, we will explore the potential of DWHO in solving other discrete combinatorial optimization problems, aiming to further broaden the applicability of the algorithm.

Author contributions

Chuncheng Fang: Conceptualization, Methodology, Writing original draft, Writing review editing. Yanguang Cai: Methodology,Software, Data curation, Writing review editing. Yanlin Wu: Formal analysis, Writing review editing.

Data availability

The datasets generated during and/or analysed during the current study are available from the corresponding author on reasonable request.

Code availability

Due to the confidentiality period of the code associated with this research, we are currently unable to make it publicly available. However, researchers interested in the code for collaborative purposes can contact the corresponding author.

Competing interests

The authors declare no competing interests.

Publisher's note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

These authors contributed equally: Yanguang Cai and Yanlin Wu.
==== Refs
References

1. Dantzig GB Ramser JH The truck dispatching problem Manage. Sci. 1959 6 80 91 10.1287/mnsc.6.1.80
Dantzig, G. B. & Ramser, J. H. The truck dispatching problem. Manage. Sci. 6, 80–91. 10.1287/mnsc.6.1.80 (1959).10.1287/mnsc.6.1.80
2. Laporte G Fifty years of vehicle routing Transp. Sci. 2009 43 408 416 10.1287/trsc.1090.0301
Laporte, G. Fifty years of vehicle routing. Transp. Sci. 43, 408–416. 10.1287/trsc.1090.0301 (2009).10.1287/trsc.1090.0301
3. Nazif H Lee LS Optimised crossover genetic algorithm for capacitated vehicle routing problem Appl. Math. Model. 2012 36 2110 2117 10.1016/j.apm.2011.08.010
Nazif, H. & Lee, L. S. Optimised crossover genetic algorithm for capacitated vehicle routing problem. Appl. Math. Model. 36, 2110–2117. 10.1016/j.apm.2011.08.010 (2012).10.1016/j.apm.2011.08.010
4. Wang X Choi T-M Liu H Yue X Novel ant colony optimization methods for simplifying solution construction in vehicle routing problems IEEE Trans. Intell. Transp. Syst. 2016 17 3132 3141 10.1109/TITS.2016.2542264
Wang, X., Choi, T.-M., Liu, H. & Yue, X. Novel ant colony optimization methods for simplifying solution construction in vehicle routing problems. IEEE Trans. Intell. Transp. Syst. 17, 3132–3141. 10.1109/TITS.2016.2542264 (2016).10.1109/TITS.2016.2542264
5. Cai J Wang P Sun S Dong H A dynamic space reduction ant colony optimization for capacitated vehicle routing problem Soft. Comput. 2022 26 8745 8756 10.1007/s00500-022-07198-2
Cai, J., Wang, P., Sun, S. & Dong, H. A dynamic space reduction ant colony optimization for capacitated vehicle routing problem. Soft. Comput. 26, 8745–8756. 10.1007/s00500-022-07198-2 (2022).10.1007/s00500-022-07198-2
6. Kytöjoki J Nuortio T Bräysy O Gendreau M An efficient variable neighborhood search heuristic for very large scale vehicle routing problems Comput. Oper. Res. 2007 34 2743 2757 10.1016/j.cor.2005.10.010
Kytöjoki, J., Nuortio, T., Bräysy, O. & Gendreau, M. An efficient variable neighborhood search heuristic for very large scale vehicle routing problems. Comput. Oper. Res. 34, 2743–2757. 10.1016/j.cor.2005.10.010 (2007).10.1016/j.cor.2005.10.010
7. Chiang W-C Russell RA Simulated annealing metaheuristics for the vehicle routing problem with time windows Ann. Oper. Res. 1996 63 3 27 10.1007/BF02601637
Chiang, W.-C. & Russell, R. A. Simulated annealing metaheuristics for the vehicle routing problem with time windows. Ann. Oper. Res. 63, 3–27. 10.1007/BF02601637 (1996).10.1007/BF02601637
8. Van Breedam A Improvement heuristics for the vehicle routing problem based on simulated annealing Eur. J. Oper. Res. 1995 86 480 490 10.1016/0377-2217(94)00064-J
Van Breedam, A. Improvement heuristics for the vehicle routing problem based on simulated annealing. Eur. J. Oper. Res. 86, 480–490. 10.1016/0377-2217(94)00064-J (1995).10.1016/0377-2217(94)00064-J
9. Gendreau M Hertz A Laporte G A Tabu search heuristic for the vehicle routing problem Manage. Sci. 1994 40 1276 1290 10.1287/mnsc.40.10.1276
Gendreau, M., Hertz, A. & Laporte, G. A Tabu search heuristic for the vehicle routing problem. Manage. Sci. 40, 1276–1290. 10.1287/mnsc.40.10.1276 (1994).10.1287/mnsc.40.10.1276
10. Toth P Vigo D The granular Tabu search and its application to the vehicle-routing problem INFORMS J. Comput. 2003 15 333 346 10.1287/ijoc.15.4.333.24890
Toth, P. & Vigo, D. The granular Tabu search and its application to the vehicle-routing problem. INFORMS J. Comput. 15, 333–346. 10.1287/ijoc.15.4.333.24890 (2003).10.1287/ijoc.15.4.333.24890
11. Prins C Prodhon C Calvo RW Solving the capacitated location-routing problem by a grasp complemented by a learning process and a path relinking 4or 2006 4 221 238 10.1007/s10288-006-0001-9
Prins, C., Prodhon, C. & Calvo, R. W. Solving the capacitated location-routing problem by a grasp complemented by a learning process and a path relinking. 4or 4, 221–238. 10.1007/s10288-006-0001-9 (2006).10.1007/s10288-006-0001-9
12. Gao Y Wu H Wang W A hybrid ant colony optimization with fireworks algorithm to solve capacitated vehicle routing problem Appl. Intell. 2023 53 7326 7342 10.1007/s10489-022-03912-7
Gao, Y., Wu, H. & Wang, W. A hybrid ant colony optimization with fireworks algorithm to solve capacitated vehicle routing problem. Appl. Intell. 53, 7326–7342. 10.1007/s10489-022-03912-7 (2023).10.1007/s10489-022-03912-7
13. Souza IP Boeres MCS Moraes REN A robust algorithm based on differential evolution with local search for the capacitated vehicle routing problem Swarm Evol. Comput. 2023 77 101245 10.1016/j.swevo.2023.101245
Souza, I. P., Boeres, M. C. S. & Moraes, R. E. N. A robust algorithm based on differential evolution with local search for the capacitated vehicle routing problem. Swarm Evol. Comput. 77, 101245. 10.1016/j.swevo.2023.101245 (2023).10.1016/j.swevo.2023.101245
14. Teoh BE Ponnambalam SG Kanagaraj G Differential evolution algorithm with local search for capacitated vehicle routing problem Int. J. Bio-Inspired Comput. 2015 7 321 342 10.1504/IJBIC.2015.072260
Teoh, B. E., Ponnambalam, S. G. & Kanagaraj, G. Differential evolution algorithm with local search for capacitated vehicle routing problem. Int. J. Bio-Inspired Comput. 7, 321–342. 10.1504/IJBIC.2015.072260 (2015).10.1504/IJBIC.2015.072260
15. Sbai I Krichen S Limam O Two meta-heuristics for solving the capacitated vehicle routing problem: the case of the Tunisian post office Oper. Res. 2022 10.1007/s12351-019-00543-8
Sbai, I., Krichen, S. & Limam, O. Two meta-heuristics for solving the capacitated vehicle routing problem: the case of the Tunisian post office. Oper. Res.[SPACE]10.1007/s12351-019-00543-8 (2022).10.1007/s12351-019-00543-8
16. Faiz A Subiyanto S Arief UM An efficient meta-heuristic algorithm for solving capacitated vehicle routing problem Int. J. Adv. Intell. Inform. 2018 4 212 225 10.26555/ijain.v4i3.244
Faiz, A., Subiyanto, S. & Arief, U. M. An efficient meta-heuristic algorithm for solving capacitated vehicle routing problem. Int. J. Adv. Intell. Inform. 4, 212–225. 10.26555/ijain.v4i3.244 (2018).10.26555/ijain.v4i3.244
17. Machado AM Mauri GR Boeres MCS de Alvarenga Rosa R A new hybrid matheuristic of grasp and vns based on constructive heuristics, set-covering and set-partitioning formulations applied to the capacitated vehicle routing problem Expert Syst. Appl. 2021 184 115556 10.1016/j.eswa.2021.115556
Machado, A. M., Mauri, G. R., Boeres, M. C. S. & de Alvarenga Rosa, R. A new hybrid matheuristic of grasp and vns based on constructive heuristics, set-covering and set-partitioning formulations applied to the capacitated vehicle routing problem. Expert Syst. Appl. 184, 115556. 10.1016/j.eswa.2021.115556 (2021).10.1016/j.eswa.2021.115556
18. Pelletier S Jabali O Laporte G The electric vehicle routing problem with energy consumption uncertainty Transp. Res. B: Methodol. 2019 126 225 255 10.1016/j.trb.2019.06.006
Pelletier, S., Jabali, O. & Laporte, G. The electric vehicle routing problem with energy consumption uncertainty. Transp. Res. B: Methodol. 126, 225–255. 10.1016/j.trb.2019.06.006 (2019).10.1016/j.trb.2019.06.006
19. Rezaei B Guimaraes FG Enayatifar R Haddow PC Combining genetic local search into a multi-population imperialist competitive algorithm for the capacitated vehicle routing problem Appl. Soft Comput. 2023 142 110309 10.1016/j.asoc.2023.110309
Rezaei, B., Guimaraes, F. G., Enayatifar, R. & Haddow, P. C. Combining genetic local search into a multi-population imperialist competitive algorithm for the capacitated vehicle routing problem. Appl. Soft Comput. 142, 110309. 10.1016/j.asoc.2023.110309 (2023).10.1016/j.asoc.2023.110309
20. İlhan İ An improved simulated annealing algorithm with crossover operator for capacitated vehicle routing problem Swarm Evol. Comput. 2021 64 100911 10.1016/j.swevo.2021.100911
İlhan, İ. An improved simulated annealing algorithm with crossover operator for capacitated vehicle routing problem. Swarm Evol. Comput. 64, 100911. 10.1016/j.swevo.2021.100911 (2021).10.1016/j.swevo.2021.100911
21. Laporte, G. & Semet, F. Classical heuristics for the capacitated vrp. In The vehicle routing problem, 109–128, 10.1137/1.9780898718515.ch5 (SIAM, 2002).
22. Xiao Y Zhao Q Kaku I Mladenovic N Variable neighbourhood simulated annealing algorithm for capacitated vehicle routing problems Eng. Optim. 2014 46 562 579 10.1137/1.9780898718515.ch5
Xiao, Y., Zhao, Q., Kaku, I. & Mladenovic, N. Variable neighbourhood simulated annealing algorithm for capacitated vehicle routing problems. Eng. Optim. 46, 562–579. 10.1137/1.9780898718515.ch5 (2014).10.1137/1.9780898718515.ch5
23. Akpinar S Hybrid large neighbourhood search algorithm for capacitated vehicle routing problem Expert Syst. Appl. 2016 61 28 38 10.1016/j.eswa.2016.05.023
Akpinar, S. Hybrid large neighbourhood search algorithm for capacitated vehicle routing problem. Expert Syst. Appl. 61, 28–38. 10.1016/j.eswa.2016.05.023 (2016).10.1016/j.eswa.2016.05.023
24. Kır S Yazgan HR Tüncel E A novel heuristic algorithm for capacitated vehicle routing problem J. Ind. Eng. Int. 2017 13 323 330 10.1007/s40092-017-0187-9
Kır, S., Yazgan, H. R. & Tüncel, E. A novel heuristic algorithm for capacitated vehicle routing problem. J. Ind. Eng. Int. 13, 323–330. 10.1007/s40092-017-0187-9 (2017).10.1007/s40092-017-0187-9
25. Zhou Y Luo Q Xie J Zheng H A hybrid bat algorithm with path relinking for the capacitated vehicle routing problem Metaheuristics Optim. Civil Eng. 2016 10.1155/2013/392789
Zhou, Y., Luo, Q., Xie, J. & Zheng, H. A hybrid bat algorithm with path relinking for the capacitated vehicle routing problem. Metaheuristics Optim. Civil Eng.[SPACE]10.1155/2013/392789 (2016).10.1155/2013/392789
26. Hosseinabadi AAR Rostami NSH Kardgar M Mirkamali S Abraham A A new efficient approach for solving the capacitated vehicle routing problem using the gravitational emulation local search algorithm Appl. Math. Model. 2017 49 663 679 10.1016/j.apm.2017.02.042
Hosseinabadi, A. A. R., Rostami, N. S. H., Kardgar, M., Mirkamali, S. & Abraham, A. A new efficient approach for solving the capacitated vehicle routing problem using the gravitational emulation local search algorithm. Appl. Math. Model. 49, 663–679. 10.1016/j.apm.2017.02.042 (2017).10.1016/j.apm.2017.02.042
27. Altabeeb AM Mohsen AM Ghallab A An improved hybrid firefly algorithm for capacitated vehicle routing problem Appl. Soft Comput. 2019 84 105728 10.1016/j.asoc.2019.105728
Altabeeb, A. M., Mohsen, A. M. & Ghallab, A. An improved hybrid firefly algorithm for capacitated vehicle routing problem. Appl. Soft Comput. 84, 105728. 10.1016/j.asoc.2019.105728 (2019).10.1016/j.asoc.2019.105728
28. Qiao J A modified particle swarm optimization algorithm for a vehicle scheduling problem with soft time windows Sci. Rep. 2023 13 18351 10.1038/s41598-023-45543-z 37884636
Qiao, J. et al. A modified particle swarm optimization algorithm for a vehicle scheduling problem with soft time windows. Sci. Rep. 13, 18351. 10.1038/s41598-023-45543-z (2023).37884636 10.1038/s41598-023-45543-z
29. Guo Z-G Liu Y-F Ao C-J A solution for the rational dispatching of concrete transport vehicles Sci. Rep. 2022 12 16770 10.1038/s41598-022-21011-y 36202889
Guo, Z.-G., Liu, Y.-F. & Ao, C.-J. A solution for the rational dispatching of concrete transport vehicles. Sci. Rep. 12, 16770. 10.1038/s41598-022-21011-y (2022).36202889 10.1038/s41598-022-21011-y
30. Ai TJ Kachitvichyanukul V Particle swarm optimization and two solution representations for solving the capacitated vehicle routing problem Comput. Ind. Eng. 2009 56 380 387 10.1016/j.cie.2008.06.012
Ai, T. J. & Kachitvichyanukul, V. Particle swarm optimization and two solution representations for solving the capacitated vehicle routing problem. Comput. Ind. Eng. 56, 380–387. 10.1016/j.cie.2008.06.012 (2009).10.1016/j.cie.2008.06.012
31. Tang J Luo Q Zhou Y Discrete artificial ecosystem-based optimization for spherical capacitated vehicle routing problem Multim. Tools Appl. 2024 83 37315 37350 10.1007/s11042-023-16919-0
Tang, J., Luo, Q. & Zhou, Y. Discrete artificial ecosystem-based optimization for spherical capacitated vehicle routing problem. Multim. Tools Appl. 83, 37315–37350. 10.1007/s11042-023-16919-0 (2024).10.1007/s11042-023-16919-0
32. Naruei I Keynia F Wild horse optimizer: A new meta-heuristic algorithm for solving engineering optimization problems Eng. Comput. 2022 38 3025 3056 10.1007/s00366-021-01438-z
Naruei, I. & Keynia, F. Wild horse optimizer: A new meta-heuristic algorithm for solving engineering optimization problems. Eng. Comput. 38, 3025–3056. 10.1007/s00366-021-01438-z (2022).10.1007/s00366-021-01438-z
33. Ali MH Kamel S Hassan MH Tostado-Véliz M Zawbaa HM An improved wild horse optimization algorithm for reliability based optimal dg planning of radial distribution networks Energy Rep. 2022 8 582 604 10.1016/j.egyr.2021.12.023
Ali, M. H., Kamel, S., Hassan, M. H., Tostado-Véliz, M. & Zawbaa, H. M. An improved wild horse optimization algorithm for reliability based optimal dg planning of radial distribution networks. Energy Rep. 8, 582–604. 10.1016/j.egyr.2021.12.023 (2022).10.1016/j.egyr.2021.12.023
34. Ali M Kotb H AboRas MK Abbasy HN Frequency regulation of hybrid multi-area power system using wild horse optimizer based new combined fuzzy fractional-order pi and tid controllers Alex. Eng. J. 2022 61 12187 12210 10.1016/j.aej.2022.06.008
Ali, M., Kotb, H., AboRas, M. K. & Abbasy, H. N. Frequency regulation of hybrid multi-area power system using wild horse optimizer based new combined fuzzy fractional-order pi and tid controllers. Alex. Eng. J. 61, 12187–12210. 10.1016/j.aej.2022.06.008 (2022).10.1016/j.aej.2022.06.008
35. Vasanthkumar P Improving energy consumption prediction for residential buildings using modified wild horse optimization with deep learning model Chemosphere 2022 308 136277 10.1016/j.chemosphere.2022.136277 36058376
Vasanthkumar, P. et al. Improving energy consumption prediction for residential buildings using modified wild horse optimization with deep learning model. Chemosphere 308, 136277. 10.1016/j.chemosphere.2022.136277 (2022).36058376 10.1016/j.chemosphere.2022.136277
36. Vasanthkumar P Improved wild horse optimizer with deep learning enabled battery management system for internet of things based hybrid electric vehicles Sustain. Energy Technol. Assess. 2022 52 102281 10.1016/j.seta.2022.102281
Vasanthkumar, P. et al. Improved wild horse optimizer with deep learning enabled battery management system for internet of things based hybrid electric vehicles. Sustain. Energy Technol. Assess. 52, 102281. 10.1016/j.seta.2022.102281 (2022).10.1016/j.seta.2022.102281
37. Li X Yin M A hybrid cuckoo search via lévy flights for the permutation flow shop scheduling problem Int. J. Prod. Res. 2013 51 4732 4754 10.1080/00207543.2013.767988
Li, X. & Yin, M. A hybrid cuckoo search via lévy flights for the permutation flow shop scheduling problem. Int. J. Prod. Res. 51, 4732–4754. 10.1080/00207543.2013.767988 (2013).10.1080/00207543.2013.767988
38. Prins C A simple and effective evolutionary algorithm for the vehicle routing problem Comput. Oper. Res. 2004 31 1985 2002 10.1016/S0305-0548(03)00158-8
Prins, C. A simple and effective evolutionary algorithm for the vehicle routing problem. Comput. Oper. Res. 31, 1985–2002. 10.1016/S0305-0548(03)00158-8 (2004).10.1016/S0305-0548(03)00158-8
39. Qian B Wang L Huang D-X Wang W-L Wang X An effective hybrid de-based algorithm for multi-objective flow shop scheduling with limited buffers Comput. Oper. Res. 2009 36 209 233 10.1016/j.cor.2007.08.007
Qian, B., Wang, L., Huang, D.-X., Wang, W.-L. & Wang, X. An effective hybrid de-based algorithm for multi-objective flow shop scheduling with limited buffers. Comput. Oper. Res. 36, 209–233. 10.1016/j.cor.2007.08.007 (2009).10.1016/j.cor.2007.08.007
40. Augerat, P., Belenguer, J. M., Benavent, E., Corberan, A. & Rinaldi, G. Computational results with a branch and cut code for the capacitated vehicle routing problem. Rapport de recherche - IMAG 495 (1995).
