2021/09/12 by Armaselu, Bogdan
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2109.05404
We consider the Maximum-Profit Routing Problem (MPRP), a variant of pick-up routing problem introduced in \citeArmaselu-arXiv-2016, Armaselu-PETRA, in which the goal is to maximize total profit. The original MPRP restricts vehicles to visit a site at most once. In this paper, we consider extensions of MPRP, in which a site may be visited by a vehicle multiple times. Specifically, we consider two versions: one in which the quantity to be picked up at each site is constant in time (MPRP-M), and one with time-varying supplied quantities, which increase linearly in time (MPRP-VS). For each of these versions, we come up with a constant-factor polynomial-time approximaltion scheme.