Approximation And Polynomial Algorithms For Multi-Depot Capacitated Arc Routing Problems

With the rise of modern logistics industry,enterprises pay more and more attention to the study of vehicle routing problem(VRP)in order to reduce transportation costs.The arc routing problem(ARP),like the VRP,has important practical significance and research value.The difference between the two is that VRP takes point as the service object while ARP takes edge as the service object.The classical arc routing problem has only one depot,but many problems in practical applications need to use the arc routing problem with multiple depots to establish a mathematical model.Therefore,in this thesis,we study the capacitated arc routing problem with multiple depots(MCARP),and extend the CARP to the more realistic multi-depot case.For different variants of the MCARP,we propose approximation and polynomial algorithms.This thesis is divided into the following seven chapters.In chapter 1,we show the research background,briefly describe the combinatorial optimization problem,and introduce the latest research progress of related problems.In chapter 2,we describe some symbols and concepts used in this paper.In chapter 3,we introduce the nonfixed destination multi-depot capacitated arc routing problem(NMCARP).Given a depot set D,each vehicle can start from any depot and finally return to any depot.The objective is to find several walks that serves the required edge set R and minimize the total length of the walks.The nonfixed destination multi-depot capacitated vehicle routing problem(NMCVRP)is extended to obtain the approximation algorithm of NMCARP.In chapter 4,we discuss the fixed destination MCARP.Given a depot set D,each vehicle starts from any depot and finally returns to the depot.The target is to find several closed walks that serve the demand edge set R and make the total length of the closed walks minimized.We generalize the fixed destination MCVRP and obtain the approximation algorithm of the fixed destination MCARP.In chapter 5,we deal with the multi-depot rural postman problem(MRPP),which is a restricted case of the MCARP with infinite capacity.There is a depot set D(?)V with |D|=k.The goal is to determine k closed walks covering all required edges of R such that the total length of the closed walks is minimized.In addition,we also study a variant of MRPP aiming at minimizing the longest closed walk,which is called min-max rural postmen cover problem,and give an improved approximation algorithm.In chapter 6,we treat the MCARP defined on a line graph.When the demands are uniform,we prove the problem is polynomial solvable.What’s more,we also discuss the MCVRP defined on a line graph,and give an approximation algorithm.In chapter 7,we summarize this thesis and give some future research directions.