Genetic Algorithm based Solution Model for Multi-Depot Vehicle Routing Problem with Time Windows

Abstract: We present a novel Ordered Distance Vector (ODV) based Equi-begin with Variable-diversity (EV) Technique for the exact solution of a variation of the vehicle routing problem with time windows in which the transportation fleet is made by vehicles with different capacities and fixed costs, based on different depots. The Multi- Depot Vehicle Routing Problem with Time Windows (MDVRPTW) is a generalization of the standard Vehicle Routing Problem (VRP). The VRPTW is NP-Complete. The MDVRPTW problem is addressed using an efficient Genetic Algorithm (GA). Genetic algorithm is a powerful optimization technique to solve NP-Complete problems. In GA different initial population seeding techniques were used to find out the performance of an individual. In this paper, we are analyzing the performance of Gene Bank technique with a proposed novel Ordered Distance Vector (ODV) based EV Technique in terms of convergence rate (%), quality solution and convergence diversity. Different authors provided different bench mark instances for MDVRPTW in neo research group. In order to compare the effectiveness and performance of the proposed population seeding technique, we are using Cordeau‟s benchmark instances; it contains 20 different instances of MDVRPTW obtained from VRPLIB were experimented using MATLAB software.

Keywords: Multi-Depot Vehicle Routing Problem with Time Windows, ODV-EV Technique, Convergence, Performance, Diversity, Genetic algorithm, VRPLIB, MATLAB