Transportation Problem

The Transportation Problem minimizes the shipping costs while satisfying the demand at each destination. The decision variables are how many units at each source node will be shipped to each destination node. Each source node has a supply, which is the upper limit on how many units can be shipped from that node. Each destination node has a demand, which is the required amount at each destination node.

The main constraints ensure that all supply is used from the source nodes, and that all demand is met at the destination nodes. This type of problem arises often, with notable examples being supply chain management and online order shipments.

Definitions

Sets

  • Sources - A set of nodes where the units are shipped from

    • i in Sources or \(i \in I\)

  • Destinations - A set of nodes where the units are shipped to

    • j in Destinations or \(j \in J\)

Parameters

  • Supply - measure of number of units available at Source i

    • Supply[i] for i in Sources or \(S_i \enspace \forall i \in I\)

  • Demand - measure of number of units required at Destination j

    • Demand[j] for j in Destinations or \(D_j \enspace \forall j \in J\)

  • ShippingCost - measure of the cost of shipping one unit from Source i to Destination j

    • ShippingCost[i, j] for i in Sources for j in Destinations or \(C_{i,j} \enspace \forall i \in I\text{, }j \in J\)

Decision Variables

  • Flow - number of units to ship from Source i to :py:obj`:Destination j`

    • Flow[i, j] for i in Sources for j in Destinations or \(X_{i,j} \enspace \forall i \in I\text{, }j \in J\)

Objective

Minimize shipping costs from sources to destinations.

\[\text{Min} \sum_{i \in I} \sum_{j \in J} C_{i,j}X_{i,j}\]

Constraints

  • The total supply must be equal to the total demand. Currently, this constraint must be met by the user changing their data. See the Notes section of the API docs for more details.

  • All of the supply at each node must be shipped to the destination nodes.

\[\sum_{j \in J}X_{i,j} = S_i \quad \forall i \in I\]
  • All of the demand at each node must be met by the source nodes.

\[\sum_{i \in I}X_{i,j} = D_j \quad \forall j \in J\]
  • The decision variables must be greater than or equal to zero and integer.

\[X_{i,j} \geq 0\text{, int} \enspace \forall i \in I\text{, }j \in J\]

API Reference

See the corresponding section in the API Library Reference to learn more about how to use the API for this problem class.