The Round-Trip p-Center and Covering Problem on a Tree

A task performed by a vehicle consists of picking up goods at a given client and delivering it to another client. The round-trip distance is the distance traveled by the vehicle between the departure from and the return to its depot. The round-trip p-center problem is to locate p depots with respect to a finite number of pairs of clients so as to minimize the maximum round-trip cost, which is defined as a nonlinear increasing function of the round-trip distance from the nearest depot. The round-trip covering problem is to find the minimum number of depots such that each round-trip cost is no more than a given constant. For both problems a dual problem is defined and in case the underlying network is a tree a strong duality result is proved. We give algorithms to solve both tree round-trip location problems in polynomial time.