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

Abstract

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{\alpha }{\sqrt{10+p}})\epsilon )\log T$, where: (i) $\epsilon >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) $\alpha >0$ is a constant such that the optimal number of vehicles is always at least $\sqrt{10+p}/\alpha$. The second algorithm has an approximation ratio of $\simeq 46(1+\epsilon +\frac{(2+\alpha )\epsilon }{\sqrt{10+p}})\log T$. Finally, the third algorithm has an approximation ratio of $\simeq 11(1+2\epsilon )\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.

15 pages, 5 figures

Cited by in corpus (2)

• An APX for the Maximum-Profit Routing Problem with Variable Supply
• Maximum-Profit Routing Problem with Multiple Vehicles per Site