prob040: A Distribution Problem with Wagner-Whitin Costs

proposed by

Modelling

A variable, X_ijt, can be used to represent the amount ordered for stocking point i in level j at period t. The lower bound of each X_ijt is 0. A conservative upper bound on X_ijt is found simply by summing the demands at all leaves under this stocking point from now until the end of the planning horizon. This is equivalent to assuming that all necessary stock for the remaining periods will be ordered immediately.

Orders for period t are assumed to be made (and fulfilled, there is a 0 lead time assumption) before period t begins. Inventory levels for period t refer to the end of period t. There are two common methods of representing the inventory remaining after each period, as discussed below.

Inventory in the Conventional Model

In the conventional model, a variable, I_ijt, is used to represent the amount of stock held at stocking point i in level j after period t.

The objective can now be expressed:

Minimise: sum_{t=1..T} sum_{j=1..L} sum_{i=1..N_j} (c_ij I_ijt + c0_ij (X_ijt > 0))

where N_j denotes the number of nodes in level j. Note that the objective as expressed above involves the reification of (X_ijt > 0). This expression can be bound to an explicit 0/1 variable (δ_ijt, the approach commonly adopted in the MIP model of this problem) and the δ variables used for branching.

Further constraints govern how inventory is supplied between stocking points:

I_ijt = I_ij(t-1) + X_ijt - sum_{m in W(i,j,j-1)} (X_mt)

where W(i,j,j-1) denotes the children of the ith stocking point in level j. In short, the above expression specifies that the closing inventory for I_ijt is the closing inventory for the same stocking point in the previous period, plus the amount ordered, minus the amount supplied.

Inventory in the Echelon Model

An alternative model views the supply-chain structure in echelons. An echelon is a stocking point and all of its descendants, as follows:

Ech6*****************************  Level
*                  |            *
*                  V            *
*                +---+          *
*                | F |          *    3
*                +---+          * 
*            ___/     \___      *
*           /             \     *
*Ech4******V********** Ech5V*****
**       +---+       * * +---+ **
**       | D |       * * | E | **    2
**       +---+       * * +---+ **
**     _/     \_     * *   |   **
**    /         \    * *   |   **
**   V           V   * *   V   **
**Ech1***     Ech2**** *Ech3*****
***+---+*     *+---+** **+---+***
***| A |*     *| B |** **| C |***    1
***+---+*     *+---+** **+---+***
*****|***********|**** ****|*****
     V           V         V

A variable, E_ijt, represents the amount of stock held at the end of period t in the echelon whose highest node is the ith node in level j. The conventional holding cost per unit of inventory is replaced by an echelon holding cost, e_ij, defined as follows:

e_ij = c_ij - c_iW(i,j,j+1)

where W(i,j,j+1)denotes the parent of the ith stocking point in level j. Recall the assumption that a parent always has a smaller holding cost than any of its children. Hence, e_ij can be thought of as the incremental cost of holding a unit of inventory at stocking point ij instead of its parent.

The objective can now be expressed:

Minimise: sum_{t=1..T} sum_{j=1..L} sum_{i=1..N_j} (e_ij E_ijt + c0_ij (X_ijt > 0))

The constraints governing how inventory is supplied between stocking points are as follows:

E_ijt = E_ij(t-1) + X_ijt - sum_{m in V(i,j)} (d_mt)

where V(i, j) denotes the leaves descended from stocking point i in level j, and d_i1t is the demand at leaf i in period t. That is, inventory held in an echelon at the end of period t is the inventory in the same echelon in the previous period plus the inventory ordered minus the demand at the leaves associated with that echelon.

One further set of constraints relate an echelon whose highest stocking point is stocking point i in level j and the echelons whose highest stocking points are the children of stocking point ij:

E_ijt >= sum_{m in W(i,j,j-1)} (E_mt)

where again W(i,j,j-1) denotes the children of the ith stocking point in level j.

Implied Constraints

A variety of implied constraints can be used to improve these basic models.

In an optimal solution, clearly the inventory for every stocking point at the end of the last period must be 0. In both models, therefore, the inventory variables for the last period can be pre-set.
In an optimal solution, if a node in a higher level places an order, at least one of its children must also. This can be seen by considering that if no children make an order, the higher node incurs a holding cost that can be removed by delaying the order until a subsequent period when at least one child does place an order.
An upper bound can be derived for the inventory variables in the conventional formulation by considering that it is only worth holding stock at a node if it is cheaper than ordering it at the next period. That is:
- I_ijt c_ij <= c0_ij + I_ijt c_W(i,j,j+1)
which simplifies to:
- I_ijt <= (c0_ij)/(c_ij-c_W(i,j,j+1))
This can easily be applied to the echelon model by substituting in the equality:
- I_ijt = E_ijt - sum_{m in G(i,j)} (I_mt)
where G(i,j) is the set of all descendents of stocking point i in level j
Similarly, an upper bound can be derived for the order variables at the leaf nodes. The principle is the same: it is only worth ordering stock not absorbed by demand at the current period if it is cheaper than waiting and ordering in a subsequent period. Consider first a bound based on deferring an order into the next period:
- (X_i1t-d_i1t)c_i1 <= c0_i1+c_m(X_i1t-d_i1t)
which can be re-arranged:
- X_i1t <= d_i1t + (c0_i1)/(c_i1-c_m)
This can be generalised to consider deferring an order into any of the following periods up to the planning horizon:
- X_i1t <= min_{t' = t .. T} sum_{i=t..t'} (d_i1t) + (c0_i1)/((t'-t+1)(c_i1-c_m))
In an optimal solution, an order is only made at a node when the inventory is 0. This can be seen by considering that if an order is made at a node with some stock at period t, the cost incurred by holding that stock from period t-1 to t can be removed by increasing the size of the order at period t.
The domains of the order (X) variables can be reduced by exploiting the fact that, in an optimal solution, the sizes of all orders made are composed from the demands of the children of the associated node for a continuous stretch of time from between the current period to the end of the planning horizon. It is therefore possible to enumerate the domain elements for each X variable, replacing the simple upper/lower bounds representation. The time complexity of this process is exponential in the number of leaves beneath the order node in question, but can usefully be applied when the number of leaves is small.

Back