A genetic-based optimization for multi-depot vehicle routing problems

Multi-depot vehicle routing problem (MDVRP) is well-known as a combinatorial optimization problem and it is NP-completed. Existing methods are commonly heuristics, and hence the solutions are suboptimal. In this paper, with a novel design of chromosome structure, a multiple objective genetic algorithm is proposed to tackle with this problem, such that two objectives, namely the total travel distances and total travel time, are to be minimized. The effectiveness of the algorithm is demonstrated with simulation results. Moreover, its uses in real-world applications based on the support of geographical information are also briefly discussed.