A Glowworm Swarm Optimization algorithm for the Vehicle Routing Problem with Stochastic Demands. (15th March 2016)

• Record Type: Journal Article
• Authors: Marinaki, Magdalene; Marinakis, Yannis
• Is Part Of: Expert systems with applications. Volume 46(2016)
• Page Start: 145
• Page End: 163
• Publication Date: 2016-03-15
• Subjects: Glowworm Swarm Optimization -- Path relinking -- Combinatorial Neighborhood Topology -- Variable Neighborhood Search -- Vehicle Routing Problem with Stochastic Demands; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2015.10.012
• Languages: English
• ISSNs: 0957-4174

Abstract

Highlights: A hybridized version of the Glowworm Swarm Optimization algorithm is presented. We solve the Vehicle Routing Problem with Stochastic Demands (VRPSD) with the proposed algorithm. We modify the algorithm in order to be suitable for combinatorial optimization problems. We compare the algorithm with a number of algorithms from the literature. The obtained results denoted the efficiency of the algorithm. Abstract: The Glowworm Swarm Optimization (GSO) algorithm is a relatively new swarm intelligence algorithm that simulates the movement of the glowworms in a swarm based on the distance between them and on a luminescent quantity called luciferin. This algorithm has been proven very efficient in the problems that has been applied. However, there is no application of this algorithm, at least to our knowledge, in routing type problems. In this paper, this nature inspired algorithm is used in a hybrid scheme (denoted as Combinatorial Neighborhood Topology Glowworm Swarm Optimization (CNTGSO)) with other metaheuristic algorithms (Variable Neighborhood Search (VNS) algorithm and Path Relinking (PR) algorithm) for successfully solving the Vehicle Routing Problem with Stochastic Demands. The major challenge is to prove that the proposed algorithm could efficiently be applied in a difficult combinatorial optimization problem as most of the applications of the GSO algorithm concern solutions of continuous optimization problems. Thus, two different solution vectors are used, the one in the continuous space (which is updated as in the classic GSO algorithm) and the other in the discrete space and it represents the path representation of the route and is updated using Combinatorial Neighborhood Topology technique. A migration (restart) phase is, also, applied in order to replace not promising solutions and to exchange information between solutions that are in different places in the solution space. Finally, a VNS strategy is used in order to improve each glowworm separately. The algorithm is tested in two problems, the Capacitated Vehicle Routing Problem and the Vehicle Routing Problem with Stochastic Demands in a number of sets of benchmark instances giving competitive and in some instances better results compared to other algorithms from the literature.