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.
