Transportation Problem with Sortation Centers

by
Gerald Senarclens de Grancy
last update: 2017-06-08

To speed up real world delivery, it is possible to add intermediate sortation centers between the fulfillment center and the end customer. The transportation problem with sortation centers essentially solves the same problem as crossdocking does. A popular user of this technique is Amazon.com.

A set of fulfillment centers $N$ is supposed to ship products to a set of demand nodes $M$. The transportation to each of the customers $m$ shall not be split. Inbetween the fulfillment centers and customers is a set of sortation centers $S$ which may receive any number of goods from the fulfillment centers. The actual last mile delivery is done from the sortation centers. The used decision variables are

$x_{ns}$
amount of goods shipped from $n$ to $s$ (integral)
$y_{sm}$
delivery to customer $m$ is done by sortation center $s$ (binary)

This problem's parameters are

$c_{ns}$
cost of shipping one unit from $n$ to $s$
$d_{sm}$
cost of fulfilling $m$'s order from sortation center $s$
$u_n$
units available at fulfillment center $n$ (supply)
$u_m$
units demanded by customer $m$

A straight-forward mixed-integer formulation of this problem is

$$\begin{align} \min \quad & \sum_{n \in N} \sum_{s \in S} x_{ns} * c_{ns} + \sum_{s \in S} \sum_{m \in M} y_{sm} * d_{sm} & \label{eq:objective}\\ s.t. \quad & \sum_{s \in S} y_{sm} = 1 & \forall m \in M\label{const:single_delivery}\\ & \sum_{m \in M} y_{sm} \cdot u_m = \sum_{n \in N} x_{ns} & \forall s \in S \label{const:sortation_supply}\\ & \sum_{s \in S} x_{ns} \leq u_n & \forall n \in N\label{const:supply} \end{align}$$

In the above model, the objective function \eqref{eq:objective} minimizes the cost of fulfilling all customer orders. Constraints \eqref{const:single_delivery} ensure that all customer orders are fulfilled with a single delivery. Constraint set \eqref{const:sortation_supply} guarantees that the correct amount of goods are shipped to each sortation center. Finally, constraints \eqref{const:supply} ensure that the fulfillment centers do not run out of goods.

PuLP

To implement the above model, I recommend using Python's PuLP package. I've prepared a small example input file with 3 fulfillment centers, 3 sortation centers and 5 customers. The solution provided milp.py is overkill for the size of the given problem. However, it nicely shows how

All of the above techniques are useful when implementing large models.