The classical Vehicle Routing Problem (VRP) tries to minimise the cost of dispatching goods from depots to customers using vehicles with limited carrying capacity. As a generalisation of the TSP, the problem is known to be NP-hard and several authors have proposed heuristics and meta-heuristics for obtaining good solutions. The authors present genetic algorithm-based approaches for solving the problem and compare the results with available results from other papers, in particular, the hybrid clustering based genetic algorithm. The authors find that the proposed methods give encouraging results on all these instances. The approach can be extended to solve multi depot VRPs with heterogeneous fleet of vehicles.
Paper
Full text
An Improved Genetic Algorithm for Solving Multi Depot Vehicle Routing Problems
Semantic Scholar · Computer Science · 2019
Abstract
The classical Vehicle Routing Problem (VRP) tries to minimise the cost of dispatching goods from depots to customers using vehicles with limited carrying capacity. As a generalisation of the TSP, the problem is known to be NP-hard and several authors have proposed heuristics and meta-heuristics for obtaining good solutions. The authors present genetic algorithm-based approaches for solving the problem and compare the results with available results from other papers, in particular, the hybrid clustering based genetic algorithm. The authors find that the proposed methods give encouraging results on all these instances. The approach can be extended to solve multi depot VRPs with heterogeneous fleet of vehicles.