One of the most known nature inspired algorithms based on the marriage behaviour of the bees is the Honey Bees Mating Optimization (HBMO) algorithm which simulates the mating process of the queen of the hive [1]. In this paper, as there are not any competitive nature inspired methods based on HBMO algorithm for the solution of the Vehicle Routing Problem with Stochastic Demands (VRPSD), at least to our knowledge, we would like to propose such an algorithm and to test its efficiency compared to other nature inspired and classic metaheuristic algorithms. The proposed algorithm adopts the basic characteristics of the initially proposed HBMO algorithm and, simultaneously, uses a number of characteristics of the HBMO based algorithms that were used for the solution of other Vehicle Routing Problem variants. A novelty of the proposed algorithm is the replacement of the crossover operator with a Path Relinking (PR) procedure in the mating phase in order to produce more efficient broods. Finally, a Variable Neighborhood Search (VNS) algorithm is used for the local search phase of the algorithm. The algorithm is compared with a number of algorithms from the literature and with two versions of the HBMO algorithm, the one presented by Abbass in [1] (HBM01) and the other presented by Marinakis et al. in [2] (HBM02). The two versions of the HBMO have been modified accordingly by the authors in order to be suitable for their application in the VRPSD. The VRPSD is a NP-hard problem, where a vehicle with finite capacity leaves from the depot with full load and has to serve a set of customers whose demands are known only when the vehicle arrives to them. As in the most VRP variants, the vehicle begins from the depot and visits each customer exactly once and returns to the depot. This is called an a priori tour [3], which is a template for the visiting sequence of all customers. In most of the algorithms used for the solution of the problem, a preventive restocking strategy [3] is used where although the expected demand of the customer is less than the load of the vehicle, it is chosen the return of the vehicle to the depot for replenishment. This happens in order to avoid the risk of the vehicle to go to the next customer without having enough load to satisfy him (route failure). For analytical formulation of the VRPSD please see [3]. The results of the algorithm with and without the preventive restocking strategy and comparisons with other algorithms from the literature are presented in the following Table.
展开▼
