Approximation Algorithms for the Maximum Profit Pick-up Problem with Time Windows and Capacity Constraint

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α{\sqrt{10+p}}) ε) \log T$, where: (i) $ε> 0$ and $T$ are constants; (ii) The maximum quantity supplied is $q_{max} = O(n^p) q_{min}$, for some $p > 0$, where $q_{min}$ is the minimum quantity supplied; (iii) $α> 0$ is a constant such that the optimal number of vehicles is always at least $\sqrt{10 + p} / α$. The second algorithm has an approximation ratio of $\simeq 46 (1 + ε+ \frac{(2 + α) ε}{\sqrt{10 + p}}) \log T$. Finally, the third algorithm has an approximation ratio of $\simeq 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.