The Fixed-Charge Shortest-Path Problem

Consider a network N = (N, A) and associate with each arc e is an element of A a fixed cost c(e) for using arc e, an interval [l(e), u(e)] (l(e), u(e) is an element of Z) specifying the range of allowable resource consumption quantities along arc e, and a per-unit cost (c) over bar (e) for resource consumed along e. Furthermore, for each node n is an element of N, let U-n is an element of N be the maximum amount of resource consumption a path can accumulate before visiting node n. Given a source node n(s) is an element of N and sink node n(t) is an element of N, the fixed-charge shortest-path problem (FCSPP) seeks to find a minimum-cost-feasible path from n(s) to n(t). When resource consumption is simply additive, the resource-constrained shortest-path problem (RCSPP) is a special case of FCSPP. We develop a new dynamic programming algorithm for FCSPP. The algorithm uses solutions from labeling and dominance techniques for standard RCSPPs on slightly modified problems, and it combines these solutions by exploiting the structure provided by certain classes of knapsack problems to efficiently construct an optimal solution to FCSPP. Computational experiments demonstrate that our algorithm is often several orders of magnitude faster than naive dynamic programming procedures.