There is an allocation problem, while we have to assign logistics routes to multiple candidate carriers.

For simplicity, let's assume there are only two routes, $A$ and $B$, with two candidate carriers, $P$ and $Q$. The total number of orders for route $A$ is $N_a$ and for route $B$ is $N_b$. Carrier $P$ provides unit prices $P_a$ and $P_b$ for routes $A$ and $B$ respectively, while carrier $Q$ provides unit prices $Q_a$ and $Q_b$ for routes $A$ and $B$ respectively. Both carrier $P$ and $Q$ also provide stepped pricing types based on the number of orders they undertake (i.e., order quantity step), with two steps assumed for simplicity.

For carrier $P$, the discount coefficient for the total freight cost is $c_1$ when the number of orders is between $[0, M_1)$, and $c_2$ when the number of orders is $[M_1, inf)$. The problem is how to allocate the orders for these two routes to the two carriers, $P$ and $Q$, in such a way as to minimize the total cost of the freight.

For example, let's say the total order volumes for routes $A$ and $B$ are $N_a = 100$ and $N_b = 200$, respectively, with unit prices of $P_a = 2$ and $P_b = 3$, and unit prices of $Q_a = 3$ and $Q_b = 2$. The step details are $M_1 = 120$, $c_1 = 0.8$, and $c_2 = 0.6$.

Assuming that carrier $P$ is assigned 60 orders for route $A$ and 80 orders for route $B$, while carrier $Q$ is assigned the remaining orders, i.e., 40 orders for $A$ and 120 orders for $B$, the total cost (without discount) for carrier $P$ is calculated as 60 * 2 + 80 * 3 = 360. The total shipment volume is 60 + 80 = 140, which falls in the second step, with a discount factor of 0.6. Therefore, the total freight charge payable to carrier P is 360 * 0.6.

Similar calculations can be made for carrier $Q$.

To formulate this problem, let $I$ be the set of routes and $J$ be the set of carriers. The decision variable $x_{ij}$ represents the quantity of orders assigned from route $i$ to carrier $j$.

The first constraints is $\sum\limits_{j}{x_{ij}} = N_i$.

Then we introduce a binary variable $\mu_{kj}$ to indicates whether the total number of orders assigned to carrier $j$ follows into the $k$th interval, thus we have $\sum\limits_{k}{\mu_{kj}} = 1,\forall j$.

Then the continuous variable $\pi_{kj}$ to indicate the actual number of orders in interval $k$, thus we have $M_{k-1,j}\mu_{kj} \leq \pi_{kj} \leq M_{kj} \mu_{kj}$

The second constraint is $\sum\limits_{i}{x_{ij}} = \sum\limits_{k}{\pi_{kj}},\forall j$, which represent the number of orders undertake by each carrier $j$.

The total freights of carrier $j$ is $\sum\limits_{i}{p_i x_{ij}}$ multiplied by $c_{kj}$, which indicated by $\mu_{kj}$, will introduce the nonlinearity.


1 Answer 1


your $x_{i,j}$ is continuous and $u_{k,j}$ is binary in the expression $ \sum_j p_jx_{i,j}\sum_k c_{j,k}u_{j,k}$ or $ \sum_j \sum_k p_jc_{j,k}x_{i,j}u_{k,j} $. So basically if you wish to linearize $xu$ you can
Introduce a continuous variable (of same domain as $x$), say $z$ and couple of constraint sets

$ 0 \le z_{i,j} \le N_ju_{jk}$: where $N_j$ is total order possible for carrier $j$ or any other bigger constant
$ x_{i,j} + N_j(u_{j,k}-1) \le z_{i,j} \le x_{i,j} + N_j(1-u_{j,k})$

  • $\begingroup$ thanks, I carefully considered and realized that this would require the introduction of a large number of continuous variables, say $z_{ijk}$. The right handside of the last constraint could simplify to $z_{ijk} \leq x_{ij}$ $\endgroup$
    – Ying
    Sep 24, 2023 at 0:45
  • $\begingroup$ Since for each carrier $j$, only one $\pi_{kj} > 0$, others will be 0. Can we use $\pi$ variables (multiplied by $p_j$ and $c_k$) to represent the total freight? $\endgroup$
    – Ying
    Sep 24, 2023 at 3:29
  • $\begingroup$ Yes $\pi$ summed over $k$ is equivalent to $x$ summed over routes $i$. It will work. $\endgroup$ Sep 24, 2023 at 13:56
  • $\begingroup$ Thank you. I wonder $\pi$ variables represent the freight will eliminate the nonlinearity? $\endgroup$
    – Ying
    Sep 25, 2023 at 1:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.