Shortest Path Problem with Resource Constraints (SPPRC)

This is the third part of the tutorial on Column generation. The links to previous parts are Part1 and Part2.

We are now entering the hardest part of the Column Generation algorithm. Let’s put aside the CG and just focus on the subproblem i.e. SPPRC. Fully explaining the SPPRC without using mathematical notation is a challenging task, so I will post links for further reading along the way to anyone interested. We will only look at a dynamic programming-based exact algorithm in this part. The algorithm presented here is only a basic version to give readers a taste of solving SPPRC. There have been numerous past and ongoing research on solving SPPRC for specific types of problems and good results have been reported for vehicle routing problems, pickup-and-delivery problems, crew scheduling problems, etc.

SPPRC has one or more resources that are constrained. Resources can be thought of as any measurable values that change while moving from one node to another. For example, time, load, any precedence requirements in pickup and delivery problems, rest requirements in crew scheduling problems, etc.

To understand the algorithm for solving SPPRC, let us introduce the following terminologies.

1. Nodes: Vertex or endpoints of the graph. This could be customers to be visited or flights in a schedule. There could be a fixed source (denoted by s) and sink node (t), for example, a depot in VRP. Or one may need to create an artificial source and sink node depending upon the problem. From an artificial source node, it is possible to reach any other node except the sink node. And from every node except the source node, one can traverse to the artificial sink node.
2. Arcs: Connection between two nodes. Each arc consumes some resources.
3. Resource Vector: Since we are concerned with more than one resource at each node we need to keep track of a vector of resources used rather than a single resource. A resource vector at a node looks like [time, load, capacity, precedence constraint] for example. For the algorithm we are looking at, let’s assume that at least one resource will have a non-decreasing value. Consider time elapsed for example. Let's denote this vector by R.
4. Labels: For our purpose, we define a label as a combination of (current node, Resource Vector consumed up to the current node, parent node). Let's denote this as L = {c, R_c, p}. With the label and the parent node, one can get the full path later.
5. Dominant labels: At the same current node there could be more than one label created. Let's say we have L1 and L2 at a given node. L1 is said to dominate L2 if each and every resource used in L1 is less than or equal to L2. Dominated labels won't be a part of the final solution and hence can be terminated from further analysis. If L1 does not dominate L2 then the two labels are incomparable, meaning one cannot say either one is better than the other.
6. Set of labels at current node c: Let’s denote this by L_c. One node can have more than one label hence it is a set.
7. Elementary path: A path that contains no cycle. If the resource we are trying to minimize is non-negative, the paths will be elementary. But the violation of non-negativity due to the CG algorithm may introduce non-elementary paths. Nevertheless, for problems like crew scheduling where the graph is directed acyclic, the paths will be elementary. For VRP like problems, non-elementary paths can be an issue. Refinement of the algorithm (not presented here) or other techniques need to be used to treat non-elementary paths. The distinction is important because, for non-elementary paths, there are pseudo-polynomial algorithms available.
8. Set of undominated labels for the whole graph. Let’s denote this by U.
9. Feasible extension of a label: A label can be extended to the next node if doing so does not violate any resource constraint.

With these let's attempt to describe an algorithm to solve for SPPRC. The pseudocode has been adapted from this:

1. Initialize U = [{s, R_s, null}] 
2. While U is not empty do:
    2a. L = remove first label
    2b. c = current node of L
    2c. if no label in L_c dominates L then 
         2c1. Add L to L_c
         2c2. Extend L along all arcs leaving c
         2c3. Add all feasible extension to U
3. return path corresponding to best label in L_t

An Example

Now let us look at a numerical example to see the above algorithm in action. Let us consider three resources distance, load, and time window. The table in figure 3.1 shows the travel distance between two points. For simplicity, we assume the travel time is the same as the travel distance. The number on side of the node numbers represents the following: [(start time, end time), load demand]. Let's assume the capacity of the vehicle is 13 units.

(Note: Since I did the problem with hand, please comment or let me know if you find any mismatch between the algorithm and the numerical problem. Later, I will code the problem and update the result if required).

Figure 3.1: Graph network and cost table

The source and sink node have the time window of (0, inf) meaning that the earliest time the vehicle can leave/reach source/sink is 0, and the latest time is infinity. Source and sink have the demand of 0 units.

To initialize we will start with U = [{s, (0,0,0), null}]. The resource vector of (0,0,0) represents that the vehicle is ready at s at time 0, the total distance traveled till s is 0, and the load on the vehicle until s is 0. This is step 1 of the algorithm.

In step 2, since U is not empty, we remove the only label from U. Then L becomes {s, (0,0,0), null}. Since there are no labels in L_c, L is not dominated. L is now added to L_c. Now L can be extended to nodes 1,2,3,4. Now the following labels get added to U.

{1, (3,3,5), s}; {2, (3,3,8), s}; {3, (3,3,7), s}; {4, (4,3,5), s}

Note that the ready time at 4 is 4 and not 3 as the earliest start time at 4 is 4, so the vehicle needs to wait until 4. The parent node will be s for all these labels.

Next, remove the label {1, (3,3,5), s} from U. Add the label to L_1. Extend the label to all feasible extension nodes. Following labels get added to U.

{t, (6,6,5), 1}; {4, (8,8,10), 1}

Next, label {2, (3,3,8), s} gets removed from U. Note that the algorithm can be implemented as a depth-first or breadth-first depending upon the stack vs heap implementation of the container U. Instead of using the LIFO or FIFO removal technique, one can also use other smarter techniques like bucket concepts (refer to this) to improve the worst time complexity of the algorithm.

Next, label {t, (6,6,5), 1} gets removed from U. The label will be added to L_t. Since no arcs are leaving from t, no new labels are created from this label.

Let us fast forward a few steps and look at the case when we reach the step where {4, (8,8,10), 1} will be removed from U. At this point, L_4 will already have {4, (4,3,5), s}. Label {4, (8,8,10), 1} will be dominated by {4, (4,3,5), s} since every resource in later is less than or equal to the resources in the former. Therefore, the new label doesn’t get created from the dominated label. Without the use of the dominance rule, the algorithm would enumerate all possible paths and would be a brute force algorithm.

Once the set U becomes empty, the algorithm terminates. At this point, we will have a set of labels for each node. To get the shortest path, one needs to select the best path from L_t. Notice that there is no logic in the algorithm to prevent the node that is already visited to be visited again. Therefore, one may end up having a non-elementary path depending upon the length of the time windows. Since we have a finite time window, the length of the non-elementary path will be finite (no infinite looping is possible).

Keep in mind the algorithm described here would have exponential running time in the worst-case. Therefore, the algorithm in the current state may not be suitable for the large network in the CG framework without some “clever” modifications. The clever techniques may be specific to the problem at hand (see this for example). The exponential worst-case run time for solving SPPRC should not discourage readers from using the CG. One does not need to solve the SPPRC fully (and optimally) at every iteration of CG. SPPRC can be prematurely stopped after a certain number of columns with negative reduced costs are generated. Also, instead of adding one shortest path at an iteration, adding more than one column speeds up the CG algorithm. The use of heuristics is also highly effective to solve SPPRC.

Lastly, let me mention that there are few libraries available for solving network graphs in python and C++. For python, Networkx is the graph library I am aware of, and C++ has Boost Graph Library (BGL). BGL also has an implementation for the SPPRC problem. With these libraries, one doesn’t need to do all the heavy lifting for creating the graphs in an efficient manner.

Hope this gives readers a flavor of the dynamic programming used to solve SPPRC. Like I said in earlier posts, solving CG (specially SPPRC) is an art and there is no right or wrong way to it. You may design specific rules and heuristics to solve your SPPRC (subproblem) and may get better results. Also, the algorithm designed for one problem class may not be suitable for another problem class. Therefore, having one size that fits all is still a long way. One can also make use of machine learning-based algorithms to solve SPPRC and generate columns that will supplement the CG algorithm.

Now since we have the building blocks to solve the CG problem, in the next series we will look at some coding exercises. We will also take a look at some of the questions raised in the previous posts and provide more intuition to some of the concepts, especially how dual values help in the CG algorithm.