Load-planning problem

From Supply Chain Management Encyclopedia

Description of the problem and its solution are based on the method of dynamic programming and Bellman's optimality principle.

Dynamic Programming Method

Dynamic programming is widely used in optimal control and planning problems as well as various technical problems.

Suppose that the process of control of a system $\, X$ goes $\, n$ steps. Given a state space $\, P$ and control space $\, Q$ with elements $\, p$ and $\, q$ respectively. It is assumed that the initial state $\, p_0$ is known. Consider a function $\, T$ :

$\, P\times Q\to P$ , i.e. $\, T(p,q)=p',\, \, \, (p,q)\in P\times Q,\, \, p'\in P$ .

Function $\, T$ is often referred to as a function of dynamics of the controlled process.

Multi-step guided process is realized as follows (see Fig. 1.)

Step 1. The system is in the state $\, p_ {0} \ in P$ . In this state the following control is used $\, q_ {1} \ in Q$ . Mapping $\, T$ sets the system into a new state $\, T (p_ {0}, q_ {1}) = p_ {1}$ .

Step 2. The system is in the state $\, p_ {1} \ in P$ . In this state the following control is used $\, q_ {2} \ in Q$ so $\, T (p_ {1}, q_ {2}) = p_ {2}$ .

Step k'. The system is in the state $\,p_{k-1} \in P$ . In this state the following control is used $\,q_{k} \in Q$ , then $\,T(p_{k-1} ,q_{k} )=p_{k}$ .

Stepn. The system $\,X$ is in the state $\, p_{n-1} \in P$ . When the control $\,q_{n} \in Q$ is chosen we have $\,T(p_{n-1} ,q_{n} )=p_{n}$ . The process ends.

Fig. 1. The implementation of the multi-step control process.

We denote $\, q = (q_ {1} ,..., q_ {k} ,..., q_ {n}), \, \, \, \, q_ {k} \ in Q, \, \, \, \, k = \overline {1, n}$ - multistep control process. Then this initial state $\, p_ {0}$ and control $\, q$ corresponds to a trajectory $\, p = (p_ {0} ,..., p_ {k-1}, p_ {k}, p_ {k +1} ,..., p_ {n})$ , where $\, p_ {k} = T (p_ {k-1} , q_ {k})$ , $\, k = \overline {1, n}$ .

Assume that on control $\, q$ and trajectory $\, p$ is given an additive function:

$\, \bar{K}(p,q)=f_{1} (p_{0} ,q_{1} )+...+f_{i} (p_{i-1} ,q_{i} )+...+f_{n} (p_{n-1} ,q_{n} )+f_{n+1} (p_{n} )= \sum _{i=1}^{n}f_{i} (p_{i-1} ,q_{i} ) +f_{n+1} (p_{n} )$ .

Denote

$\, K(p_{0} ,q)=\sum _{i=1}^{n}f_{i} (p_{i-1} ,q_{i} ) +f_{n+1} (p_{n} )$ .

value of the function $\, \ bar {K} (p, q)$ on the trajectory of the process from the initial state $\, p_ {0}$ in $\, q$ .

Now we can formulate the discrete optimal control problem. Find the optimal control $\, q ^ {*}$ , which is the solution of the following problem:

$\, \mathop{\max }\limits_{q} K(p_{0} ,q)=\max \left[\sum _{i=1}^{n}f_{i} (p_{i-1} ,q_{i} ) +f_{n+1} (p_{n} )\right]$ .

under dynamic constraints:

$\, \left\{\begin{array}{l} {p_{i} =T(p_{i-1} ,q_{i} ),\, \, \, q_{i} \in Q,\, \, \, i=\overline{1,n}} \\ {p_{0} =p^{0}} \end{array}\right.$

where $\, p_{0}$ - given initial state of the process.

Note that when the control $\, q_ {i}$ is being choosing in step $\, i$ we know the state of the process $\, p_ {i-1}$ in the previous step, and the knowledge of $\, (p_ {i-1}, q_ {i})$ defines the future state of the process and the value of the functional. It is therefore natural to consider functions $\, q_ {i} = q_ {i} (p_ {i-1})$ , $\, i = \overline {1, n}$ and set of functions

(1) $\, q(\cdot )=(q_{1} (\cdot ),...,q_{k} (\cdot ),...,q_{n} (\cdot ))$

where $\,q_{k} (\cdot ): q_{k} =q_{k} (p_{k-1} )$ . Such set of functions $\,q(\cdot )$ is called a strategy.

Bellman's Optimality Principle

Optimal strategy

$\, q^{*} (\cdot )=(q_{1}^{*} (\cdot ),...,q_{k}^{*} (\cdot ),...,q_{n}^{*} (\cdot ))$

has the property that whatever the initial state $\, p$ and the initial control is chosen $\, q_ {1}$ , it remains the best strategy in the process with $\, n-1$ steps, which starts at the state $\, p_ {1} = T (p, q)$ .

From Bellman's optimality principle can be derived recurrence functional Bellman equation, which is the basis of computational procedures for dynamic programming.

Denote $\, F_n (p)$ - the maximum functional value in $\, n$ - steps problem from the initial state $\, p$ . Function $\, F_n (p)$ is often called the Bellman’s function. From the principle of optimality we have the following equation.

The Bellman Equation

(2) $\, F_{n} (p)=\mathop{\max }\limits_{q_{1} \in Q} [f_{1} (p,q_{1} )+F_{n-1} (T(p,q_{1} ))$

with the boundary condition

$\, F_{0} (p)=f_{n+1} (p).$

The general scheme of dynamic programming

Consider the idea of dynamic programming in the following example. Find:

(3) $\, \mathop{\max }\limits_{x_{1} ...x_{n} } \sum _{j=1}^{n}f_{j} (x_{j} )$ ,

$\, x_{j} \ge 0$ , $\,x_{j}$ - integer, $\,j=\overline{1,n}$ .

Because the variables $\, x_ {j}$ , $\, j = \overline {1, n}$ are independent, then

$\, \mathop{\max }\limits_{x_{1} ,...,x_{n} } \sum _{j=1}^{n}f_{j} (x_{j} ) =\mathop{\max }\limits_{x_{n} } \left[f_{n} (x_{n} )+\mathop{\max }\limits_{x_{1} ,...,x_{n-1} } \sum _{j=1}^{n-1}f_{j} (x_{j} ) \right]$ ,

(4) $\, \sum _{j=1}^{n-1}a_{j} x_{j} \le b-a_{n} x_{n}$

Denote $\, \mathop {\ max} \ limits_ {x_ {1} ,..., x_ {n-1}} \ sum _ {j = 1} ^ {n} f_ {j} (x_ {j})$ in the condition (4) through $\, F_ {n-1} (b-a_ {n} x_ {n})$ , then

(6) $\, \mathop{\max }\limits_{x_{1} ,...,x_{n} } \sum _{j=1}^{n}f_{j} (x_{j} ) =\mathop{\max }\limits_{x_{n} } \left[f_{n} (x_{n} )+F_{n-1} (b-a_{n} x_{n} )\right]$

Denote $\, \mathop{\max }\limits_{x_{1} ,...,x_{k} } \sum _{j=1}^{k}f_{j} (x_{j} ) =F_{k} (\xi )$ under condition $\, \sum _{j=1}^{k}a_{j} x_{j} \le \xi$ .

$\, x_{j} \ge 0$ , $\,x_{j}$ - integer, $\,j=\overline{1,n}$ .

After transformations we obtain the following fundamental recurrence relation of dynamic programming

(7) $\, F_{k} (\xi )=\mathop{\max }\limits_{x_{k} } \left[f_{k} (x_{k} )+F_{n-1} (\xi -a_{n} x_{n} )\right],\, \, \, k=\overline{1,n}$

subject to $\,0\le x_{k} \le \frac{\xi }{a_{k} }$ .

Use (7) to define calculation process:

Construction of Bellman’s function.

Step 1. Compute

(8) $\,F_{1} (\xi )=\mathop{\max }\limits_{x_{1} } f_{1} (x_{1} ),\, \, \, x_{1} \le \xi$ ,

where $\,\xi =\overline{0,b}$ - a parameter of the process. Fill the table 1 by values $\,F_{1} (\xi )$ , $\,x_{1}^{0} (\xi )$ , for $\,\xi =\overline{0,b}$ $\,x_{1}^{0} (\xi )$ - optimal solution of the problem (8).

Step 2. Compute

(9) $\, F_{2}(\xi )=\mathop{\max }\limits_{0\le x_{2} \le \frac{\xi }{a_{2}}} \left[f_{2}(x_{2})+F_{1}(\xi-a_{2} x_{2})\right]$

Values $\, F_ {1} (\ xi-a_ {2} x_ {2})$ for different values of the argument $\, \ xi-a_ {2} x_ {2}$ select from Table. 1. Fill in the table 2 with the following results: $\, F_ {2} (\ xi)$ , $\, x_ {2} ^ {0} (\ xi)$ , where $\, x_ {2} ^ {0} (\ xi)$ - the optimal solution of problem (9).

Step k. $\,(1\le k\le n-1)$ . Compute

(10) $\, F_{k}(\xi )=\mathop{\max }\limits_{0\le x_{k} \le \frac{\xi}{a_{k}}} \left[f_{k}(x_{k})+F_{k-1}(\xi-a_{k}x_{k})\right]$

Fill in the table of values $\, F_ {k} (\ xi)$ , $\, x_ {k} ^ {0} (\ xi)$ , $\, \ xi = \overline {0, b}$ , where $\, x_ {k} ^ {0} (\ xi)$ - the optimal solution of problem (10).

Optimal solution computation.

Assuming $\, \ xi = b$ and $\, k = n$ find $\, F_ {n} (b)$ and $\, x_ {n} ^ {0} = x_ {n} ^ {0} (\ xi)$ .

Calculate in (10) the optimal value $\, x_ {n} ^ {0} = x_ {n} ^ {0} (\ xi)$ and assume $\, \ xi_ {1}, {0} = b-a_ {n} x_ {n} ^ {0}$ . Then, using the value of $\, \ xi _ {1} ^ {0}$ of the table step $\, n-1$ , determine the optimal values of other variables $\, x_ {n-1} ^ {0} (\ xi _ {1} ^ {0})$ . Then determine the values $\, x_ {n-2} ^ {0} (\ xi_ {1} ^ {0}), \ dots, x_ {1} ^ {0} (\ xi _ {1} ^ {0})$ .

$\,\xi$	$\,F_{1}(\xi)$	$x_{1}^{0} (\xi )$
$\, 0$	$\, F_{1}(0)$	$\, x_{1}^{0}(0)$
$\, 1$	$\, F_{1}(1)$	$\, x_{1}^{0}(1)$
$\, \ldots$	$\, \ldots$	$\, \ldots$
$\, b-1$	$\, F_{1} (b-1)$	$\, x_{1}^{0} (b-1)$
$\, b$	$\, F_{1} (b)$	$\,x_{1}^{0}(b)$

Table 1. Table for the first iteration

$\,\xi$	$\,F_{2}(\xi )$	$\, x_{2}^{0}(\xi)$
$\, 0$	$\, F_{2}(0)$	$\, x_{2}^{0}(0)$
$\, 1$	$\, F_{2}(1)$	$\, x_{2}^{0}(1)$
$\, \ldots$	$\, \ldots$	$\, \ldots$
$\, b-1$	$\, F_{2} (b-1)$	$\, x_{2}^{0} (b-1)$
$\, b$	$\, F_{2} (b)$	$\,x_{2}^{0}(b)$

Table 2. Table for the second iteration

To apply dynamic programming method the following conditions are to be satisfied:

The decision-making process should allow an interpretation as a multi-step process;

For each step it should be defined a set of state parameters $\, \ xi$ , which do not depend on the number of steps;

Optimal solution in step $\, k$ depends only on the current state and does not depend on the prehistory of the process.

Aircraft Loading Problem

An aircraft is loaded by objects $\, N$ of various types. Each object type $\, i$ has weight $\, F_ {i}$ and insurance cost $\, v_ {i}$ , ( $\ , i = \overline {1, N}$ ). Maximum load capacity of the aircraft is $\, W$ . It is required to determine the maximum value of the goods whose weight must not exceed maximum permissible carrying capacity of aircraft. For definiteness, assume that $\, W = 5$ and there are three types of objects, details of which are listed in the table below:

$\, \, \, \, i \, \, \,$	$\, \, \, \, F_{i}\, \, \,$	$\, \, \, \, v_{i} \, \, \,$
$\, 1$	$\, 2$	$\, 65$
$\, 2$	$\, 3$	$\, 80$
$\, 3$	$\, 1$	$\, 30$

Consider the problem in general formulation. Denote the number of items such as $\, i$ by $\, k_ {i}$ . Then the problem of loading the aircraft can be written as:

$\, \max z=\max (v_{1} k_{1} +v_{2} k_{2} +...+v_{N} k_{N} )$

$\, \left\{\begin{array}{l} {F_{1} k_{1} +F_{2} k_{2} +...+F_{n} k_{n} \le W,} \\ {k\ge 0,\, \, i=\overline{1,N,}} \end{array}\right.$

where $\, k$ are integer.

If it were possible to discard the requirement of integrality, it was a linear programming problem and it could be solved with the simplex method.

Consider three main elements of a dynamic model.

1. Step $\, j$ is associated with type $\, j, j = 1,2 ,...,$

2. State $\, y_j$ on stage $\, j$ is the total weight of items, loaded on the previous stages $\, j, j + 1, \ dots, \ textit {N}$ . The variable $\, y_j$ can be $\, 0,1, \ dots, W$ in $\, j = 1,2, \ dots, N$ .

3. Solutions. Values $\, k_ {j}$ on stage $\, j$ describe the type of items $\, j$ . Value $\, k_ {j} \ in [0, [W / F_ {j}]]$ , where $\, [W / F_ {j}]$ is the integral part of $\, W / F_ {j}$ .

Let $\, f_ {j} (y_ {j})$ is maximum total value of items loaded in phases $\, j, j +1, .., N$ for a given state $\, y_ {j}$ .

The recurrence relation is the following:

$\,f_{N} (y_{N} )=\mathop{\max }\limits_{\begin{array}{l} {k_{N} \in \{ 0,1,...,N\} ,} \\ {v_{N} =0,1,...,W} \end{array}} \{ v_{N} y_{N} \}$

$\,f_{j} (y_{j} )=\mathop{\max }\limits_{\begin{array}{l} {k_{j} =0,1,...,[W/F_{j} ]} \\ {v_{j} =0,1,...,W} \end{array}} \{ v_{j} y_{j} +f_{j+1} (y_{j} -F_{j} k_{j} )\} ,\, \, \, \, j=1,2,...,N-1$

The maximum value $\, k_ {j}$ is bounded by $\, W / F_ {j}$ .

Example

For our example, calculations begin with the third stage and are performed as follows.

Stage 3.

$\,f_{3} (y_{3})=\mathop{\max }\limits_{k_{3}} (30k_{3}), \max k_{3}=[5/1]=5$

Stage 2.

$\,f_{2} (y_{2} )=\mathop{\max }\limits_{k_{2} } (80k_{3} +f_{2} (y_{2} +3k_{2} )), \max k_{2} =[5/3]=1$

Values in columns are obtained using the recurrence relations. For example, the value in the column $\, v_ {2} k_ {2} = 0$ in $\, y_ {2} = 1$ is obtained as follows:

$\,f_{2} (y_{2} )=\mathop{\max }\limits_{k_{2} } (80\cdot 0+f_{3} (1+3\cdot 0))=0+f_{3} (1)=0+30$ ,

because from the table of step 3, $\, f_ {3} (1) = 30$ .

Stage 1.

$\,f_{1} (y_{1} )=\mathop{\max }\limits_{k_{1} } (65k_{1} +f_{2} (y_{1} +2k_{1} )), \max k_{1} =[5/2]=1$

For a given $\, y_ {1} = W = 5$ the optimal solution is $\, (k_ {1 }^{*}, k_ {2 }^{*}, k_ {3} ^ {*}) = (2,0,1)$ , and the total value of goods is equal to 160.