|
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.
|
| |
|
