Heuristic initialized stochastic memetic algorithm for MDPVRP with interdependent depot operations

Abstract

The Vehicle Routing Problem (VRP) is a widely studied combinatorial optimization problem. We introduce a variant of the Multi-Depot and Periodic Vehicle Routing Problem (MDPVRP) and propose a heuristic initialized stochastic memetic algorithm (HISMA) to solve it. The main challenge in designing such an algorithm for a large combinatorial optimization problem is to avoid premature convergence by maintaining a balance between exploration and exploitation of the search space. We employ intelligent initialization and stochastic learning to address this challenge. The intelligent initialization technique constructs a population by a mix of random and heuristic generated solutions. The stochastic learning enhances the solutions' quality selectively using simulated annealing with a set of random and heuristic operators. The hybridization of randomness and greediness in the initialization and learning process helps to maintain the balance between exploration and exploitation. Our proposed algorithm has been tested extensively on the existing benchmark problems and outperformed the baseline algorithms by a large margin. We further compared our results with that of the state-of-theart algorithms working under MDPVRP formulation and found a signi cant improvement over their results.