Research And Application Of Vehicle Routing Problem

Marco Dorigo’s ant algorithm(1991) is based on the behavior of real ants communicate information concerning food sources via pheromone to find the shortest route. Although ant algorithm is a heuristic approach, many researches still use it to solve the Vehicle Routing Problem(VRP) because of its properties of multiphase searching and quick convergence. And the performance of Ant Algorithm is better than general heuristic approaches.In practice, the goals of VRP are minimizing cost, enhancing service quality and service allowance, and so on. Thus, the Vehicle Routing Problem with Time Window(VRPTW) is closer to real world than simple VRP.In the past, the time variables(including vehicle transit time and time window) are viewed as the explicit numbers. In fact, the time variables are variable and uncertain. Thus,we use fuzzy theory to transfer time variables into fuzzy variables and then search the shortest vehicle route by ant algorithm.Our research is focus on the express company and we simulate the customer requirements(including customer number, site of customer, customer demand, and time window) based on the company’s vehicle information(including site of company,distribution range, and vehicle capacity). After studying, we find that setting service level between 70% and 90% has the better result. Besides, the analysis of route and the interval of time window have great impact on the result of route planning.