2016/12/04 by Armaselu, Bogdan, Daescu, Ovidiu
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1612.01038
In this paper, we study the Maximum Profit Pick-up Problem with Time Windows and Capacity Constraint (MP-PPTWC). Our main results are 3 polynomial time algorithms, all having constant approximation factors. The first algorithm has an approximation ratio of ~46 (1 + (71/60 + \fracα√(10+p)) ε) log T, where: (i) ε> 0 and T are constants; (ii) The maximum quantity supplied is qmax = O(np) qmin, for some p > 0, where qmin is the minimum quantity supplied; (iii) α> 0 is a constant such that the optimal number of vehicles is always at least √(10 + p) / α. The second algorithm has an approximation ratio of ≃ 46 (1 + ε+ ((2 + α) ε)/(√(10 + p))) log T. Finally, the third algorithm has an approximation ratio of ≃ 11 (1 + 2 ε) log T. While our algorithms may seem to have quite high approximation ratios, in practice they work well and, in the majority of cases, the profit obtained is at least 1/2 of the optimum.