Research And Application Of Vehicle Routing Problem With Time Windows

The vehicle routing problem is the key point about how to optimize the strategy of logistics. The vehicle routing problem has important implications for reducing the cost of transportation and improving the service of logistics companies.This thesis focuses on the vehicle routing problem with time windows. According to the real situation in logistics, we proposes a dual objectives programming model for the vehicle routing problem with time windows. Two goals are considered in this model. The first is to minimize the number of vehicle used for transporting goods to all the customers. The length of tours must be controlled, because of the fuel tank capacity, and the working time. Less vehicles used means less cost of transportation. Besides, all the customers want to receive their goods in their favorite time, so vehicles need to visit customers within their time windows as soon as possible. This is the other goals in this model. Based on this model, this paper proposes a bicriteria approximation algorithm for DVRPTW. The algorithm can give the approximately optimal solution for DVRPTW in polynomial time. Through rigorous theoretical analysis, we finally proves the approximation ratio of the algorithm. Subsequently, we analyzes the efficiency through some experiments.Besides, we designs the vehicle routing system based on the genetic algorithm. The genetic algorithm has been widely used to solve integer programming problems. We introduces the genetic algorithm for the vehicle routing problem and give some experimental analysis. Experimental results show that the genetic algorithm is efficient, and can be applied to the system. Subsequently, we introduces some technologies used to design the system. We chooses 20 hospitals in Shenzhen in order to give a simulation experiment. The system will show the strategy of transportation on Baidu Map.