The Study Of Logistics Vehicle Routing Problem With Split Demand

Vehicle routing problem (VRP) is a basic issue in logistics and transportation management. The enterprise could reduce the transportation cost and improve the service level by optimizing the vehicle routing and scheduling as the transportation cost is often the largest part of logistics cost.In most of VRP research, a condition has always been defined that one customer must be serviced by one vehicle. Of course, in this problem the demand of the customer is less than the capacity of the vehicle. However, some cost saving could be obtained by spliting the customer demand in real operations, especially when a majority of customer have heavy demand. So we choosed the study of split delivery vehicle routing problem (SDVRP) as the topic of this paper.In this paper, the research on SDVRP is composed of analysis, modeling and the heuristics design. The most important part is heuristics design.Firstly, we read a lot of literature and try to find out the general situation of the research on SDVRP. We also realize the panorama of VRP. And all these are the basic of the research in this paperSecondly, we establish a general model and a integer programs model of SDVRP. Then we reserch the property of the feasible solution and prove three important criterion.Thirdly, based on the integer programs model, we design a algorithm using tabu search to solve th SDVRP. In this tabu search algorithm, the most important issue is the design of neighborhood search method, we call it as 1 to n exchange method. We also design a self-adapt neighborhood search strategy to imporve the efficiency of tabu search. At last, this tabu search algorithm is validated by a test example.Fourthly, we look the SDVRP integer model as a VRP with one unit demand customer and design a genetic algorithm to solve this VRP. In this design, we put forword a special operator which is called as feasible operator to solve the tendency of over-split. At last, this genetic algorithm is validated by a test example.Finally, we summerize the main achievement of this paper and pointout the future research direction.