
Boost : 
From: Michael Drexl (michael_at_[hidden])
Date: 20051206 13:59:26
Hi,
is there any interest in including an algorithm for solving the shortest
path problem with resource constraints (SPPRC) in the Boost Graph library?
I've implemented an exact algorithm for this NPhard problem. The
algorithm is basically a labelsetting algorithm based on dynamic
programming. It is parameterized on the graph type (of course) and the
type of the resource container (data structures specifying what
resources there are and how they are to be managed in the course of the
algorithm).
Some remarks on the underlying problem:
The SPPRC seeks the shortest (fastest, cheapest) path in a network with
arbitrary arc lengths (travel times, costs) from an origin node to a
destination node subject to one or more resource constraints. For
example, one might seek a path of minimum length from o to d subject to
the constraints that
 the total travel time must not exceed some upper bound and/or
 the total amount of some good that has to be picked up at the vertices
along the path be less than or equal to some capacity limit and/or
 if two vertices i_1 and i_2 are visited on a path, then i_1 must be
visited before i_2
 etc.
The problem is NPhard in the strong sense. If the path need not be
elementary, i.e., if it is allowed that vertices or arcs are visited
more than once, the problem can be solved in pseudopolynomial time.
A recent survey on the problem is:
Desaulniers, G.; Irnich, S. (2005):
Shortest Path Problems with Resource Constraints
in:
Desaulniers, G.; Desrosiers, J.; Solomon, M. (eds.) (2005):
Column Generation
Springer, New York, pp. 3365
(available online via
www.dpor.rwthaachen.de/de/publikationen/pdf/or_200401.pdf)
Regards,
Michael D.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk