A feasible path Shortest Paths with Resource Constraints Technische Universität München
irnich

What path fulfills all time constraints and has the least overall cost?

Shortest path problem with resource constraints (SPPRC)

Introduction and Problem Description

The shortest path problem with resource constraints (SPPRC) seeks a shortest (cheapest, fastest) path in a directed graph 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 s to t 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 and j are visited on a path, then i must be visited before j
  • 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 are visited more than once, the problem can be solved in pseudopolynomial time. A central aspect is that two (partial) paths in an SPPRC can be incomparable, contrary to the SPP without resource constraints. This makes the SPPRC similar to a multi-criteria decision problem.

A recent survey on the problem is:
Irnich, S.; Desaulniers, G. (2005):
Shortest Path Problems with Resource Constraints
in:
Desaulniers, G.; Desrosiers, J.; Solomon, M. (eds.) (2005):
Column Generation
Springer, New York, pp. 33–65

The present document cannot give a complete introduction to SPPRCs. To get a thorough understanding of the problem, the reader is referred to the above paper. However, to understand the algorithm and its implementation, it is necessary to explain some fundamental ideas and point out the differences to a labelling algorithm for the shortest path problem without resource constraints (SPP).

The standard solution technique for SPPRCs is a labelling algorithm based on dynamic programming. This approach uses the concepts of resources and resource extension functions. A resource is an arbitrarily scaled one-dimensional piece of information that can be determined or measured at the vertices of a directed walk in a graph. Examples are cost, time, load, or the information ‘Is a vertex i visited on the current path?’. A resource is constrained if there is at least one vertex in the graph where the resource must not take all possible values. The resource window of a resource at a vertex is the set of allowed values for the resource at this vertex.

A resource extension function is defined on each arc in a graph for each resource considered. A resource extension function for a resource maps the set of all possible vectors (in a mathematical sense, not to be confused with a std::vector) of resource values at the source of an arc to the set of possible values of the resource at the target of the arc. This means that the value of a resource at a vertex may depend on the values of one or more other resources at the preceding vertex.

Labels are used to store the information on the resource values for partial paths. A label in an SPPRC labelling algorithm is not a mere triple of resident vertex, current cost and predecessor vertex, as it is the case in labelling algorithms for the SPP. A label for an SPPRC labelling algorithm stores its resident vertex, its predecessor arc over which it has been extended, its predecessor label, and its current vector of resource values. The criterion to be minimized (cost, travel time, travel distance, whatsoever) is also treated as a (possibly unconstrained) resource. It is necessary to store the predecessor arc instead of the predecessor vertex, because, due to the resource constraints, one can not assume that the underlying graph is simple. Labels reside at vertices, and they are propagated via resource extension functions when they are extended along an arc. An extension of a label along an arc (i, j) is feasible if the resulting label l at j is feasible, which is the case if and only if all resource values of l are within their resource windows.

To keep the number of labels as small as possible, it is decisive to perform a dominance step for eliminating unnecessary labels. A label l1 dominates a label l2 if both reside at the same vertex and if, for each feasible extension of l2, there is also a feasible extension of l1 where the value of each cardinally scaled resource is less than or equal to the value of the resource in the extension of l2, and where the value of each nominally scaled resource is equal to the value of the resource in the extension of l2. Dominated labels need not be extended. A label which is not dominated by any other label is called undominated or Pareto-optimal. The application of the dominance principle is optional—at least from a theoretical perspective.

The implementation is a label-setting algorithm. This means that there must be one or more resources whose cumulated consumption(s) after extension is/are always at least as high as before. This is similar to the Dijkstra algorithm for the SPP without resource constraints where the distance measure must be non-negative. It is sufficient if there is one resource with a non-negative resource consumption along all arcs (for example, non-negative arc lengths or non-negative arc traversal times).

source: Boost C++ library documentation

Irnich

The SPPRC was introduced in the Ph.D. dissertation of Desrochers (1986) as a sub- problem of a bus driver scheduling problem. It consists of finding a shortest path among all paths that start from a source node, end at a sink node, and satisfy a set of constraints defined over a set of resources. A resource corresponds to a quantity, such as the time, the load picked-up by a vehicle, or the duration of a break in a work shift, that varies along a path according to functions, called resource extension functions (REFs)

The two-resource SPPRC, better known as the shortest path problem with time windows (SPPTW), was first studied in Desrosiers et al. (1983) and Desrosiers et al. (1984). The resource cost is unconstrained while the resource time is restricted by corresponding time windows.

This applet presents a simple label-setting algorithm, which solves the two dimensional SPPTW with resources time and cost. No negative cycles are allowed

What do you want to do first?


SVG Download

Legende

node node
edge edge with capacity cap

Legende

Which graph do you want to execute the algorithm on?

Start with an example graphs:

Modify it to your desire:

  • To create a node, make a double-click in the drawing area.
  • To create an edge, first click on the output node and then click on the destination node.
  • The edge weight can be changed by double clicking on the edge.
  • Right-clicking deletes edges and nodes.

Download the modified graph:

Download

Upload an existing graph:

A

occured when reading from file:

the contents:

                    

What next?

SVG Download

Legende

node node with exess flow and height function
node current node
node active nodes
edge edge with flow ≤ cap
edge s-t flow

Legende

Algorithm status

ms

First choose a source node

Click on a node to select it as the source/starting node s

Shortest Path Problem with Time Windows Label Setting Algorithm/h3>

Now the algorithm can begin. Click on next to start it

Initialize

The algorithm is initialized with U = {trivial label/path} and P = &empty

Main loop

As long as the queue containing the unprocessed labels isn’t empty pop the first label l from the front of the queue.

Path extension step 1/2: extend the label

Extend the current path with label l=(~,v) along the edge e=(v,w) to get a new extended path with label l'=(l,w)

The accumulated resource consumption of this label is given by r(l') = max(r_lower(w),r(l)+r(e))

Path extension step 2/2: check feasability

Check if the extended path with label l'=(l,w) is feasible in w, meaning that the accumulated resource consumption r(l') along the path is not larger than the upper resource constraint at its end node w.

l' ∈ FEASIBLE(w) ⇔ r(l') ≤ r_upper(w)

If it is feasible, add l' to the set Q of unprocessed labels/paths

Label processed

In the absence of cycles of negative length, a label which has once been fully extended will never be touched again, which is why we speak of a Label Setting algorithm.

Thus, the current label l is now moved to the set of processed labels P, which we will later search for for our solution

Dominance step

For all the paths which end in some node v, prune the paths/labels which are striclty dominated in both sets U and P

l_1=(~,v) dominates l_2=(~,v) ⇔ time(l1) < time(l2) AND cost(l1) < cost(l2)

Finished

The algorithm terminated since there are no more unprocessed labels to extend

Filtering step

Hover over a node to see the set of all feasible paths ending in it

s ← pick(v)

BEGIN

(* Initialize *)

U ← {(ε,s)}, P ← ∅

(* Main Loop *)

WHILE ∃ l=(~,v) ∈ U

(* Path extension step *)

FORALL e=(v,w) ∈ E

l'=(l,w) ← EXTEND(l,e)

IF l' ∈ FEASIBLE(w)

U ← U ∪ {l'}

P ← P ∪ {l}

(* Dominance step *)

U,P ← REMOVE-DOMINATED(U,P)

END

(* Filtering step *)

t ← hover(v)

FORALL l=(~,t) ∈ P

highlight(l)

Variable status

l' U l P
- -

Log of algorithm execution

Beim Wechsel des Tabs wird der Algorithmus abgebrochen.

Du kannst die Anwendung in einem anderen Browserfenster öffnen, um parallel einen anderen Tab zu lesen.