Multi-Commodity Flow

In a single-commodity flow problem, we ship one quantity through a network with arc capacities. In airline operations, however, every scheduled flight leg is typically used by many distinct shipments at once: different passenger origin-destination markets, different fleet types, or different freight classes. The multi-commodity flow model captures this directly.

A multi-commodity flow problem on a directed network $G=(N,A)$ consists of:

• $K$ commodities, indexed $k=1,2,\dots,K$, each with origin $s_k$, destination $t_k$, and demand $d_k$.
• Arc capacities $u_{ij}$ for each $(i,j)\in A$.
• A decision variable $x^k_{ij}\ge 0$ representing the units of commodity $k$ routed on arc $(i,j)$.

Because every commodity competes for the same physical capacity, each arc must obey a bundle (shared-capacity) constraint: the total flow summed across all commodities cannot exceed the arc capacity:

$$\sum_{k=1}^{K} x^{k}_{ij}\;\le\;u_{ij}\qquad\text{for every arc }(i,j)\in A.$$

For example, suppose the arc $(i,j)$ has capacity $u_{ij}=300$ seats and three commodities use it with

$$x^{1}_{ij}=120,\qquad x^{2}_{ij}=90,\qquad x^{3}_{ij}=70.$$

Then the total flow on $(i,j)$ is $120+90+70=280\le 300$, so the bundle constraint is satisfied.