[graph] Proposal: Algorithm for the Shortest Path Problem with Resource Constraints
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 NP-hard problem. The algorithm is basically a label-setting 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 NP-hard 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. 33--65 (available online via www.dpor.rwth-aachen.de/de/publikationen/pdf/or_2004-01.pdf) Regards, Michael D.
On Dec 6, 2005, at 1:59 PM, Michael Drexl wrote:
is there any interest in including an algorithm for solving the shortest path problem with resource constraints (SPPRC) in the Boost Graph library?
Yes!
I've implemented an exact algorithm for this NP-hard problem. The algorithm is basically a label-setting 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).
Interesting. We're always interested in growing the BGL with new and interesting algorithms. When you think your implementation is ready to go into Boost, please send it to the list or to me privately. We usually go through a quick round of review (or two) to make sure it fits well with the BGL style, then it'll go in the next release. I'm looking forward to seeing this algortihm! Cheers, Doug
On Wed, Dec 07, 2005 at 09:38:28AM -0500, Douglas Gregor wrote:
On Dec 6, 2005, at 1:59 PM, Michael Drexl wrote:
is there any interest in including an algorithm for solving the shortest path problem with resource constraints (SPPRC) in the Boost Graph library?
Yes!
I would second it; many more algorithms are needed.
I've implemented an exact algorithm for this NP-hard problem. The algorithm is basically a label-setting 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).
For such hard problems there is an enormous design space (and an even bigger algorithm space) to be considered, so a good dose of genericity in the implementation would be appreciated (hopefully it comes with concepts?). Since it's NP-hard, it would be good to have also a reduction from some well-known NP-complete problem to SPPRC (for example graph colouring), which would be very useful for testing (using some established implementation for that NP-complete problem). Oliver
Thank you for your interest and your comments.
For such hard problems there is an enormous design space (and an even bigger algorithm space) to be considered, so a good dose of genericity in the implementation would be appreciated (hopefully it comes with concepts?).
Hm, I don't know what exactly you would consider a "good dose of genericity", but it may well be that I have made some design decisions that you'll find too restrictive/not generic enough. I'll post the code I propose - after some re-naming and re-formatting and the like to comply with the Boost standards - to the sandbox vault, then you can see for yourself.
Since it's NP-hard, it would be good to have also a reduction from some well-known NP-complete problem to SPPRC (for example graph colouring), which would be very useful for testing (using some established implementation for that NP-complete problem).
As for the testing, I use the algorithm as a subroutine in a solution procedure for the Vehicle Routing Problem (VRP), and I have an alternative exact solution procedure for the VRP. Both procedures consistently yield the same solutions. Moreover, I've tested it against the BGL algorithms for the SPP without resource constraints (which is an SPPRC with one resource constraint with no upper bound on the consumption of this resource), and achieved the same results there, too. Finally, I've solved Shortest Path Problems with Time Windows (two resources: cost and time) with my algorithm and with an MIP solver (CPLEX), and this gave correct results as well. Regards, Michael
Douglas Gregor wrote:
We're always interested in growing the BGL with new and interesting algorithms. When you think your implementation is ready to go into Boost, please send it to the list or to me privately.
Thank you for your interest. To comply with the Boost programming, formatting and naming conventions, I'll have to do quite some rearranging of files and re-naming and re-formatting, which I did not want to do before having received some "We're interested"-feedback from list members. By "send it to the list" you mean "post it to the Sandbox Vault", don't you? Regards, Michael
participants (3)
-
Douglas Gregor -
Michael Drexl -
Oliver Kullmann