Multi-depot Vehicle Routing Problem with Time Windows and Multi-type Vehicle Number Limits and Its Genetic Algorithm

摘要

According to the situation that modern large enterprise builds multiple depots and multi-type vehicles with the limited number are in the depots, multi-depot vehicle routing problem with time windows (MDVRPTW) where limited number of vehicles and multi-type vehicle limits is given. Mathematical model of the above problem is constructed, which reflects the feature of the multi-type vehicle limit and the limited number of vehicles, compatible with MDVRPTW. An improved chromosome representation is proposed on the basis of customer, which can denote the vehicle sent by depot, path and the customer unserviced. The genetic algorithm for the problem and the population initialization algorithm are constructed. A new handling constraint method based on genetic algorithm is designed, avoiding the difficulty of selecting the penalty factor in penalty strategy and making the handling constrain simplify. The validity of the algorithm to MDVRPTW with the abovementioned conditions is proved by the experiments.