Research Of Split Delivery Capacitated Arc Routing Problem

Split delivery capacitated arc routing problem is a combinatorial optimization problem. Itis one of the attractive area in the circles of Operations Research. It has wide real-worldapplications such as winter gritting, urban waste collection and post delivery.Usually the transportation cost of vehicles is a major component of the total cost forcapacitated arc routing problem. Therefore it can not only effectively reduce cost but alsoimprove service levels. At the same time, it can reduce the scattered freight rate through theoptimization of vehicle routing.In most study of capacitated arc routing problem，a condition has always been definedthat one customer must be serviced by only one vehicle. Of course，in this problem thedemand of one customer is less than the capacity of one vehicle. However， sometransportation cost saving could be obtained by splitting the demand of customers with theservice requirement satisfied in real society，especially when a majority of customers havemuch demand. So we choose the study of split delivery capacitated arc routing problem(SDCARP) as the topic of this paper.The existing work was unable to find the global optimal solutions in polynomial timebecause the complexity of the problem itself. The development of improved constructiveheuristics for CARP is still an important research area even though the application of meta-heuristics to CARP has led to improved solutions.The solution obtained by the constructive heuristics can be used as the initial solutions toensure that the performance of meta-heuristics is superior to the constructive heuristics. In aword，the constructive heuristics are used to solve the SDCARP in this paper to find theinitial solution. It provides convenience to use meta-heuristics to solve the problem in the nextwork.Based on extensive and thorough reading of the literature both at home and abroad，theresearch on SDCARP in this thesis is composed of analysis，modeling and the heuristicssolving. The most important part is heuristic. The gist is as follows:First and foremost, a brief introduction of the origin and history of evolution ofcapacitated arc routing problem and split delivery vehicle routing problem. A summarizationof the solution of the two problems will also be presented. I establish an integer programmodel and a model with relaxed constraints of SDCARP. Then I analyze the properties of thefeasible solution and proving two important properties. At the same time, I analyze simply themeaning for splitting demand. Secondly， a systematic and detailed introduction of the fundamental theories andmethods of the three constructive heuristics. Based on the relax integer program model，using three heuristic algorithms to solve the SDCARP and give the results and analysis onbenchmark test collections which is generally accepted in the international public.Finally, I summarize the main achievement of this paper and point out the futureresearch direction.