Research for the Multi-trip Vehicle Routing Problem based on Genetic Algorithm

This paper studies the solution of the Multi-trip Vehicle Routing Problem (MVRP), in which a set of customers have to be served by the same type vehicle. Each vehicle needs to service multiple trips in one working day. The objective is to minimize the total cost with vehicle capacity, service time constraints. The MVRP is a typical NP-Hard problem. And the general accurate algorithm can not find the optimal exact solution, therefore, this paper builds a mathematical model and uses Genetic Algorithm to solve the problem. In order to verify the effectiveness of the Genetic Algorithm, it is applied to the company A and is compared with Mileage Saving Method. The results show that compared with Mileage Saving Method, the Genetic Algorithm has better results, including lower cost and more reasonable route.