Approximation algorithms for solving the trip-constrained vehicle routing cover problems

In this paper, we address the trip-constrained vehicle routing cover problem (theTcVRC problem). Specifically, given a metric complete graphG=(V,E;w)with a set D(subset of V)of depots, a setJ(=V\D)of customer locations, each customerhaving unsplittable demand 1, andkvehicles with capacityQ, it is asked to find a setC={C-i|=1,2,...,k}ofktours forkvehicles to service all customers, each tourfor a vehicle starts and ends at one depot inDand permits to be replenished at someother depots inDbefore continuously servicing at mostQcustomers, i.e., the numberof customers continuously serviced in per trip of each tour is at mostQ(except thetwo end-vertices of that trip), where each trip is a path or cycle, starting at a depot andending at other depot (maybe the same depot) inD, such that there are no other depotsin the interior of that path or cycle, the objective is to minimize the maximum weightof suchktours inC, i.e., minCmax{w(C-i)|i=1,2,...,k}, wherew(Ci)is thetotal weight of edges in that tourCi. Consideringkvehicles whether to have commondepot or suppliers, we consider three variations of the TcVRC problem, i.e., (1) the trip-constrained vehicle routing cover problem with multiple suppliers (the TcVRC-MSproblem) is asked to find a setC={Ci|i=1,2,...,k}ofktours mentioned-above,the objective is to minimize the maximum weight of suchktours inC; (2) the trip-constrained vehicle routing cover problem with common depot and multiple suppliers(the TcVRC-CDMS problem) is asked to find a setC={Ci|i=1,2,...,k}ofk tours mentioned-above, where each tour starts and ends at same depotvinD, eachvehicle having its suppliers at some depots inD(possibly includingv), the objectiveis to minimize the maximum weight of suchktours inC; (3) the trip-constrainedk-traveling salesman problem with non-suppliers (the TckTS-NS problem, simply theTckTSP-NS) is asked to find a setC={C-i=1,2,...,k}of k tours mentioned-above, where each tour starts and ends at same depotvinD, each vehicle havingnon-suppliers, the objective is to minimize the maximum weight of suchktours inC. As for the main contributions, we design some approximation algorithms to solvethese three aforementioned problems in polynomial time, whose approximation ratiosachieve three constants 8-2/k,7/2-1/kand 5, respectively