A discrete spider monkey optimization for the vehicle routing problem with stochastic demands

The Vehicle Routing Problem (VRP) is a classical NP-hard combinatorial optimization problem. In recent years, a lot of heuristic algorithms have been proposed for optimizing the problem, and many simulation and practical experiments are performed to evaluate and verify the effectiveness of different heuristic algorithms. In this paper, we focus on the Vehicle Routing Problem with stochastic demands (VRPSD) in which the customer demands follow known probability distributions. A hybrid algorithm called DSMO-GA which combines discrete spider monkey algorithm (SMO) with genetic algorithm (GA) is proposed for solving the VRPSD problem. In the proposed DSMO-GA for VRPSD, the individuals are coded as sets and sequences, and a conflict elimination method is designed to cancel the infeasible codes. Accordingly, a non adjacent 2-OPT is designed to enhance population diversity. The proposed DSMO-GA effectively integrates the advantages of DSMO and GA to further balance the global exploration and local exploitation capacity. Five groups of different experiments are conducted and the results show that DSMO-GA is valid for the VRPSD. Furthermore, the impact of various parameters on the performance of DSMO-GA are also investigated. (C) 2021 Elsevier B.V. All rights reserved.