Vehicle routing problems based on Harris Hawks optimization

Urban expansion and the growth of cities in particular has led to an increase in factory activity and consequently an increase in various transportation services as companies in a variety of sectors strive to meet the economic and commercial needs as well as the service requirements of the urban population [1].This trend has generated an increase in logistical research aimed at ensuring that transportation services are both time-efficient and cost-effective in order to improve geographical coverage, speed of service and customer satisfaction [2‐4].

One of the most important approaches that has been adopted to try to enhance the efficiency and growth of distribution systems is the vehicle routing problem (VRP), which was first proposed by Dantzig and Ramser in 1959 [5]. The VRP emerged from an existing optimization problem, namely, the traveling salesman problem (TSP) [6] and remains the most structured and researched transport model available. The VRP model attempts to discover how to deliver goods to customers by using a fleet consisting of a predefined number of vehicles.

The vehicle routing problem (VRP) is a catch-all term for a group of issues involving “vehicles” completing visits to “customers.” The basic practical difficulty of distributing products to geographically dispersed consumers utilizing a number of trucks operating out of a single goods depot gives rise to these problems [7]. The challenge is to route the cars in such a way that the overall distance traveled (or time spent, money incurred, etc.) is kept to a minimum [8].

The VRP, also described as “vehicle scheduling,” “vehicle dispatching,” or simply “delivery,” emerges frequently in real-world circumstances that are not directly connected to the delivery of commodities [9‐11]. Collection of mail from mailboxes, pick-up of children by school buses, house-call tours by a doctor, preventive maintenance inspection tours, laundry delivery, and so on are all VRPs in which the “delivery” operation can be a collection, collection and/or delivery, or neither; and in which the “goods” and “vehicles” can take a variety of forms, some of which may not even be of a physical nature [12].

The key goal is to find the minimum-length route that starts and ends in a depot, taking into account a number of variants such as the time window, service time, and vehicle capacity among others [13]. The VRP is a combinatorial optimization and NP-hard problem [14, 15] and several algorithms have been proposed in order to solve it, yet it remains an incredibly important challenge in the field of combinational optimization [16]. The only small-scale VRP technology yet discovers the ultimate global solution [17].The expertise of stream VRP algorithms is divided into exact and heuristics algorithms [18].

Classical heuristics for the VRP can be split into constructive heuristics and improvement heuristics [19]. The origin heuristics forever, progress from a solution to a best one in its neighborhoods [20].Heuristic methods execute a comparatively limited exploration of the search space and typically require a short computation time to output solutions that have good fitness [21]. Classification heuristics for the VRP include the savings algorithm, route-first cluster-second, cluster-first route-second, and insertion heuristics. Two kinds of improvement algorithms are suitable for the VRP, namely, intra-route heuristics and inter-route heuristics [22].

Metaheuristics are also widely used in optimization problems including the VRP [23‐25].These smart algorithms are suitable for solving hard optimization problems that require a large amount of time because they are able to reach optimal solutions in a fast time [26, 27], which is largely due to their utilization of random search instead of full search when exploring the search space [28].

The major goal of developing metaheuristic algorithms is to address complicated optimization issues where previous optimization approaches have failed. These techniques are now widely regarded as some of the most practical approaches to solve a wide range of real-world issues. Metaheuristic could be used to solve any problem that can be expressed as a problem of optimization technique. Also, They are ease of implementation as well as they are efficiency and flexibility [29].

Many metaheuristic algorithms have been applied to optimization problems, such as the mine blast algorithm [30], monarch butterfly algorithm [31], and many others [32‐36]. The metaheuristic algorithms that have been applied specifically to the VRP include artificial bee colony (ABC) [37], practical swarm optimization(PSO) [38], Ant Colony Optimization (ACO)[39],harmony search [40],genetic algorithm [41] and others [42‐49]. In line with the literature, this paper uses the Harris hawks optimization (HHO) algorithm to solve the VRP [50], as this algorithm has been shown to have scientific strength in the area of complex optimization problems [51].

The cooperative behavior and pursuit manner of Harris' hawks in nature, known as surprise pounce, is the fundamental inspiration for HHO. Several hawks work together to attack on a victim from different directions in an attempt to catch it off guard. Based on the dynamic nature of events and the prey's escape behaviors, Harris hawks can display a variety of pursuit patterns. To design an optimization method, this work mathematically duplicates such dynamic patterns and behaviors [50, 52, 53]. As an outcome, the Harris hawks optimization (HHO) algorithm was used to solve the VRP in this paper.

The rest of this paper is organized as follows: In "Related works", the related works on VRP are described. Then, in "Harris Hawks optimization", the HHO algorithm is discussed in detail. This is followed by a demonstration of the proposed method of using HHO for VRP in "Proposed method: HHO for VRP". After that, in "Experimental results", the experimental results are presented and analyzed. Finally, in "Conclusion" some conclusions are made and some possible directions for future improvements are suggested.

In recent times, metaheuristic algorithms have become an important part of the methods that have been developed to solve the VRP, largely because these algorithms have the ability to find optimal solutions due to their robust local and global search capabilities. Several previous studies have used these algorithms to solve the VRP, including Szeto, et al. [54], who presented a heuristic ABC for the capacitated VRP (CVRP). To improve the original heuristic for solving the CVRP, an improved version of the ABC heuristic was developed. Computing tests revealed that the improved heuristic ABC is capable of providing significantly stronger solutions for the CVRP than the original ABC and that it also consumes less computing energy.

On the other hand, Wang, et al. [55] addressed the periodic VRP with time window and service selection issue by building a heuristic algorithm based on improved ant colony optimization (IACO) and simulated annealing (SA), which they named multi-objective simulate annealingant colony optimization (MOSA-ACO). Also using SA, Rabbouch et al. [56] proposed an empirical-type SA to solve the CVRP. Their approach works incrementally by exploiting the last component of the worst practicable option. The results showed that their method has high search precision, optimal quicker entry, and the ability to classify all optimal rates while increasing the SA algorithm’s convergence speed. In another SA-based research study, Ilhan [57] proposed using the population-based SA algorithm to solve the CVRP. Three operators were used to build the process: swap, inclusion and return. In fact, the algorithm used has been evaluated on 63 occasions. The research findings demonstrated that the proposed method has the ability to evaluate the best pathways for 23 instances, along with the presence of the percentage error value and the run time.

Another type of VRP was addressed in [58], where the author suggested an optimization algorithm for a hybrid ant colony and applied it to the multi-depot VRP (MDVRP). The suggested algorithm is based on a mixture of probabilistic techniques that are based on the normal actions of ants when foraging for food as well as on specific techniques that are based on the computational concepts of annealing. The experimental results showed the proposed algorithm is superior to other methods as it is able to produce the smallest mean error. Also, in [59], the authors recommended a way to minimize the MDVRP in terms of both distance traveled and time consumed by using inferential GAs. In their method, the proposed algorithm assigns each depot to its nearest customer and allows each customer to draw one customer at a time before all customers are allocated to drive. In addition, the algorithm uses Dijkstra’s shortest path to evaluate each depot’s closest customer. The findings showed that the suggested algorithm was calculated from distance and time of travel and thus confirmed its efficacy.

On the other hand, Sethanan and Jamrus [60] suggested the use of both an integer linear programming formulation and a novel hybrid differential evolution algorithm involving a fuzzy logic controller genetic operator to solve the backhaul and heterogeneous fleet routing problem for multi-trip vehicles. In their work, the objective was to minimize the cumulative cost associated with the distance traveled by using the traditional method of differential evolution and differential evolution with a selected genetic operator and real-settings fuzzy logic controller.

Meanwhile, in [61], the authors suggested a mathematical model to deal with the issue of the electric VRP (EVRP), taking into account the demands of electrical charging in the operations. To solve this optimization problem, the authors built a dedicated tabu search (TS) algorithm. The results of the improvement the VRP using this approach has obtained more reliable results than other methods. In another hybrid approach, Akbar and Aurachmana [62] also used a TS algorithm, in this case with a GA, in order to refine the CVRP with time windows (CVRPTW). One of the shortcomings of their work is its lack of animation by which to visualize the outcome and thereby encourage future studies. Nevertheless, their findings indicated that the proposed hybrid algorithm not only successfully minimizes the current route, but also estimates the optimal number of homogeneous fleets.

Based on the foregoing review of related works, it can be seen that several different metaheuristic algorithms have been used to solve the VRP and its variants. The results obtained by previous research studies showed that these smart algorithms can find the best routes for vehicles to reach customers in the least possible time. The success of these algorithms is due to the precision of their random search mechanism. and to the balance they achieve between the local and global search processes. It therefore seemed logical to investigate whether HHO would be able to find optimal solutions for the VRP.

The HHO algorithm is a new swarm intelligence optimization algorithm that was proposed by Heidari et al. in 2019 [50]. The algorithm has been shown to perform efficiently in the optimization domain relative to other metaheuristic algorithms. Moreover, the algorithm can be extended to solve multiple types of optimization problems successfully, exhibiting a good level of performance [63]. Centered on the effects of such an algorithm in problems of intricacy optimization, the study uses it to increase the efficiency related to the VRP [50].

The basic notion behind the improved algorithm is derived from how Harris hawks hunt for food under desert conditions which are characterized by a scarcity of food [64]. To find their prey, Harris hawks engage in a variety of complex processes of mutual hunting and coordination to find, encircle, flush out and ultimately strike a possible target or prey. The HHO algorithm mimics the behavior of these hawks that monitor and catch their prey by means of a “surprise pounce”, which is also known as the “seven kills” strategy [50].In this strategy, many hawks collaboratively target a single prey, such as a rabbit that is out in the open rather than hiding under cover of vegetation for example, by using different techniques and they ultimately converge on this prey [65].

The attack can be terminated promptly by catching the shocked target in just a few seconds. However, depending on the prey’s escape capability and habits, the hawks may need to undertake several, short-length, swift dives that are likely to be in the vicinity of the prey for several minutes [51] before they are successful in executing the seven kills strategy. Harris hawks display a variety of types of chasing, which depends not only on the prey’s escape habits, but also on a diverse range of environmental circumstances. For instance, in a swooping chase scenario, the most successful hawk (leader) swoops at the prey to capture it, but it can miss the prey (i.e., not find the target solution) because in essence the search and attack is carried out by a single member of the group. By increasing its vulnerability, Harris hawks proceed to locate an exhausted rabbit. In the end, when only one hawk, usually the most seasoned and strongest, can easily catch the exhausted rabbit and share it with the extant members, it cannot run away from the team besiege [66].

The HHO algorithm consists of three phases: (1) discovery or exploration (global search), (2) transformation from exploration to exploitation, and (3) exploitation (local search) [64]. For the intention of finding and investigating all aspects relevant to these propositions, the discovery phase reflects the change to many locations and a new venue. In addition, this phase illustrates a new technique for studying. The transformation from discovery to exploitation phase is regarded as crucial to the success of metaheuristic algorithms. In HHO, in order to transform the specified phases, the escape energy of the rabbit prey is used. The utilization process, on the other hand, reflects the installation and use of such sites and enables the available resources to be completely implemented [67].

In this paper, we suggest using HHO to construct a routing strategy by focusing on minimizing the number of vehicles in two steps:

To provide a fair scientific examination, the experiments used the same work settings and situations. The proposed method was performed on a Notebook that had a Windows 10 operating system, An Intel^® CoreTM i7-6006U processor operating at 2.00 GHz (four CPUs) and 2.0 GHz, with 8 GB of RAM, powers the software and its operation. The model was created using Matlab R2016a.

Since the input variables play an essential role in the consistency of the solutions. The input parameters were set in the experiments due to the obvious results as in [65]. In order for the outcomes of the experiment to be identical, the configurations of the algorithms are equivalent. The final set of parameters is specified in Table 1.

The VRP is an NP hard real-world problem, which many researches are still trying to provide the best solutions to solve it. In this paper, we proposed a model using HHO algorithm to solve the VRP. The performance of HHO was assessed according to three criteria: the minimum objective function obtained, the minimum number of iterations required, and the satisfaction of capacity constraints. Compared with two well-known methods, namely, SA and ABC, the results showed that HHO was clearly superior in terms of both the minimum objective function obtained and the minimum number of iterations required. This is likely due to the advanced exploitative capabilities of HHO as well as its ability to achieve better integration between the local and global search processes.

On the other hand, HHO like other metaheuristic algorithms, cannot prove optimality and it cannot probably reduce the search space, as well as it is hard to guarantee the consistency of optimization outcomes acquired with the same initial condition settings. In the future, to achieve better results, HHO could be employed in a hybrid model with another metaheuristic algorithm, or its global search mechanism could be modified through the use of several methods such as a crossover operator.