> Teach Dynamic Programming Add-in - Path Problems

When trying to find an optimal path through a network it is natural to use dynamic programming because the optimization problem can be represented explicitly in graphical form.  We begin with the grid network depicted the figure and define what is called the simple path problem.  Nodes represent locations and are identified by their coordinate vector x = (x1, x2) while arcs represent transportation links between nodes.  A traveler at a particular node is permitted to move up to the node with the next higher x2-coordinate (and the same x1-coordinate) or move right to the node with the next higher x1-coordinate (and the same x2-coordinate).  The direction traveled will be indicated by the variable d.  We take d = 0 to mean that travel is up and d = 1 to mean that travel is to the right.  Clearly, all arcs are one-way.  Each arc has a known length given by a(x, d) where x describes the node at which the arc begins and d indicates the direction of travel.  We assume that the traveler starts at node (1,1) and wants to travel to node (n, n) using the shortest possible route -- the problem objective.

The dynamic programming model is straightforward, as defined below.

 To make a model of this class, click the Grid option on the dialog. The fields accept the number of rows and columns in the grid. The example uses 10 for both. Data form 2 provides two tables for the up and right lengths. The arc lengths as follows a(s, d) = |s1 – s2| for d = 0, 1 where s1 and s2 are the coordinates of the current node.  Thus arcs that originate at nodes along the main diagonal have length 0, arcs that originate at nodes one removed from the main diagonal have length 1, and so on. The tables below were constructed with this cost function.

 Part of the Excel DP model is shown to the left. The model requires two state variables to identify the location of the path. A single decision variable indicates whether the path is to go up or to the right. The sequence decisions along the minimum length path.

The optimal path is shown below where the numbers in parentheses along the arcs are their lengths.  The path has a total length of 9.  Of course, this is not a surprising solution given the arc length definition; however, dynamic programming does not take advantage of symmetry.  The solution is obtained as easily for arbitrary arc lengths as for this special case.

Turn Penalties

There are a number of variations of the simple path problem that illustrate the power of dynamic programming.  For instance, consider the case where a penalty is assessed for turning left and a penalty for turning right.  To evaluate a movement from one state to the next, we need to know the last direction traveled as well as the location.  This model, requires an additional state variable to indicate the direction last traveled.

 Part of the Excel DP model is shown to the left. The model requires three state variables. The first two identify the current location on the path, and a third indicates the direction last traveled. A single decision variable indicates whether the path is to go up or to the right. Statistics for the DP algorithm are below. The third state variable doubles the number of states.

The solution for the example 10 ´ 10 grid with a left-turn penalty of 10 and right-turn penalty of 5 is shown in the table below and in the figure. The solution has migrated away from the diagonal to escape excessive turn penalties.  The total arc length is now 27.  Adding to this 10 for each turn gives a total path value of 47.

Network

 Clicking the Network button on the model dialog constructs a model for the general shortest path network model on an acyclic graph. The dialog calls for the construction of a network with 10 nodes and 20 arcs. The arc data structure (Data Form 1) is a list of arcs each with an origin node, a terminal node and a cost. The arcs are arbitrarily ordered.

The figure shows the data for the example using Data Form 2. The arc data shows the origin node, terminal node and cost for each arc. The node data indicates the set of arcs originating at each node. The Start is the index of the first arc originating at a node, and the End is the index of the last arc leaving the node. For example node 6 originates arcs 8 through 10.

The solution for the example is below. The shortest path has a length of 22 and it passes through nodes 1, 2, 3, 4, 6 and 10.

Operations Research Models and Methods
Internet
by Paul A. Jensen