The prize collecting shortest path problem (PCSPP) is a special case of the prize collecting Steiner tree problem (PCSTP) (PCSPP is the PCSTP with only two terminal vertices, namely the source and sink nodes of the PCSPP). I am aware of quite some work on the PCSTP (by Ivana Ljubic amongst others) but I have never seen specialized algorithms for the PCSPP. Do such algorithms exist?
$\begingroup$
$\endgroup$
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
You can make the graph directed, push the prizes into the arcs and solve a shortest path problem with negative lengths (i.e. for an undirected graph $G=(V,E)$ with distances $d_e\geq 0$, $e\in E$ and prizes $p_v\geq 0$, $v\in V$, construct a directed graph $G'=(V,A)$, where $A$ is obtained by replacing each edge $e=\{u,v\}\in E$ of length $d_e$ by two arcs $(u,v)$ of length $d_e-p_v$ and $(v,u)$ of length $d_e-p_u$.)
So as a partial answer, specialized algorithms for the (general) SPP apply.
$\begingroup$
$\endgroup$
I think there is some work on this, for the context of vehicle routing problem solvers using branch and price. The subproblem (or pricing) becomes an price collecting path problem.
A good starting point for references for that might be Chapter 3.5 of "Vehicle Routing: Problems, Methods, and Applications" by Paolo Toth and Danielle Vigo.
$\begingroup$
$\endgroup$
As others already said, the PCSPP described resorts to a simple SPP with potentially negative costs. It would still be solvable in poly time if no cycles of negative weight are present. Otherwise, you could impose elementary constraints and solve it as an elementary shortest path problem which, however, is NP-hard, and for which several algorithms exist already (B&C or Dyn Prog most notably).
