An APX for the Maximum-Profit Routing Problem with Variable Supply

Abstract

In this paper, we study the Maximum-Profit Routing Problem with Variable Supply (MPRP-VS). This is a more general version of the Maximum-Profit Public Transportation Route Planning Problem, or simply Maximum-Profit Routing Problem (MPRP), introduced in \cite{Armaselu-PETRA}. In this new version, the quantity $q_i(t)$ supplied at site $i$ is linearly increasing in time $t$, as opposed to \cite{Armaselu-PETRA}, where the quantity is constant in time. Our main result is a $5.5\log T(1+\epsilon )(1+\frac{1}{1+\sqrt{m}}{)}^2$ approximation algorithm, where $T$ is the latest time window and $m$ is the number of vehicles used. In addition, we improve upon the MPRP algorithm in \cite{Armaselu-PETRA} under certain conditions.

12 pages, 1 figure

References in corpus (1)

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

Cited by in corpus (1)

• Maximum-Profit Routing Problem with Multiple Vehicles per Site