# How to linearize stepped pricing in a route assignment problem

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.

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})$$

• 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}$
– Ying
Sep 24, 2023 at 0:45
• 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?
– Ying
Sep 24, 2023 at 3:29
• Yes $\pi$ summed over $k$ is equivalent to $x$ summed over routes $i$. It will work. Sep 24, 2023 at 13:56
• Thank you. I wonder $\pi$ variables represent the freight will eliminate the nonlinearity?
– Ying
Sep 25, 2023 at 1:38