How to write distance specific constraint?

Suppose there are a few plants (p) and few customers (c). The supply (Sp), distance (Dpc), cost (COSTpc) and demand (DEMANDc) between them is given. I have a constraint that 90% of total demand of all customers should be satisfied by plants which are located within 100 miles of customers location. How should I write this type of constraint?

• What are your decision variables? Sep 12 '20 at 16:52
• Number of units shipped from plant to customer (Xpc), basically a simple transportation problem where we have few plants with supply and few customers with demand. But the key requirement is that I should supply from only those plants which are located within 100 miles to customers. Sep 13 '20 at 1:47
• @RituRathore, One possible way is that you can define a table based on your specific distance ($100$ miles) and use that as a filter in your problem formulation. Sep 13 '20 at 3:53

The formulation of Leonid Kantorovich On the translocation of masses has a simple expression in case of discrete optimal transportation problem. This formulation will be the starting point to answer to the question.

Let $$c_{i,j}$$ be the unitary cost of transportation for one unit of good from plant $$i$$ to customer $$j$$.

$$x_{i,j}$$ designates the quantity of goods which will be shipped from i-th plant to j-th customer. We do assume divisibility of goods so that $$x_{i,j}$$ is a non-negative real number.

The optimization of the following objective function gives the best “routes” which minimize the total cost of transportation while the demand is met at every customers location.

$$\min Z = \min \sum_{i=1}^p \sum_{j=1}^c c_{i,j} \cdot x_{i,j}$$

subject to

$$\left\{ \begin{array}{l} \sum_{j=1}^c x_{1,j} \leq Sp_1 \\ \vdots \\ \sum_{j=1}^c x_{p,j} \leq Sp_p \\ \sum_{i=1}^p x_{i,1} \geq DEMAND_1 \\ \vdots \\ \sum_{i=1}^p x_{i,c} \geq DEMAND_c \\ x_{ij} \geq 0 i=1,2, … ,p ; j=1,2,…, c \\ \end{array} \right.$$

We wish to meet the 90% of total demand of all customers by means of plants which are located within 100 miles far from customers location. So, we can write:

$$\left\{ \begin{array}{l} 0,90 \cdot \sum_{j=1}^c DEMAND_j \leq \sum_{i=1}^p \sum_{j=1}^c x_{i,1} \\ z_{1,1} \cdot D_{1,1} \leq 100 \\ \vdots \\ z_{1,c} \cdot D_{1,c} \leq 100 \\ \vdots \\ z_{p,1} \cdot D_{p,1} \leq 100 \\ \vdots \\ z_{p,c} \cdot D_{p,c} \leq 100 \\ z_{i,j} \leq x_{i,j} \\ z_ij binary \\ \end{array} \right.$$

We have introduced $$pc$$ auxiliary Boolean variables which will permit us to formulate the two following implications:

1. If $$x_{i,j}=0 \implies z_{i,j}=0$$
2. If $$x_{i,j}>0 \implies z_{i,j}=1$$

The feasible region designating the above logic implications is defined as

$$\min Z’ = \min (Z + \sum_{i=1}^p \sum_{j=1}^c z_{i,j})$$

$$\left\{ \begin{array}{l} x_{i,j} \leq M \cdot z_{i,j} \\ z_{ij} binary \\ \end{array} \right.$$

Note that if $$x_{i,j}=0$$ then $$x_{i,j} \leq M \cdot z_{i,j}$$ is verified for $$z_{i,j} =0$$ or $$z_{i,j} =1$$. But, inserting $$z_{i,j}$$ in the objective function $$Z$$ permits us to force $$z_{i,j}$$ to assume the zero value by optimality.

Because of $$z_{i,j}$$ is a Boolean variable whose value is 1 if $$x_{i,j} > 0$$ and is 0 if if $$x_{i,j} = 0$$, we are able to select the i-th plant which is located within 100 miles far from j-th customer by means of constraint such as

$$z_{i,j} \cdot D_{i,j} \leq 100$$

Whenever $$z_{i,j} \cdot D_{i,j} \leq 100$$ is violated, this means that $$z_{i,j}=0$$. But, $$z_{i,j}=0 \implies x_{i,j}=0$$, therefore $$x_{i,j}$$ is not selected as optimal route.

The proposed model selects as optimal solution the routes minimizing the total cost of transportation while the 90% of total demand is served by plants located within 100 miles far from customers location. This means that model is unfeasible if there are not sufficiently plants “near” the customer meeting the 90% of total demand.

$$\min Z’ = \min (Z + \sum_{i=1}^p \sum_{j=1}^c z_{i,j})$$

$$\left\{ \begin{array}{l} \sum_{j=1}^c x_{i,j} \leq Sp_i \forall i\\ \sum_{i=1}^p x_{i,j} \geq DEMAND_j \forall j\\ z_{i,j} \cdot D_{i,j} \leq 100 \forall i,j\\ x_{i,j} \leq M \cdot z_{i,j} \forall i,j\\ x_{ij} \in R_0^+ \forall i,j\\ z_{ij} binary \forall i,j\\ \end{array} \right.$$

The total demand is $$\sum_c \text{DEMAND}_c$$, and the amount satisfied by close enough plants is $$\sum_{\substack{p,c:\\D_{p,c}\le 100}} X_{p,c},$$ so your desired constraint is $$\sum_{\substack{p,c:\\D_{p,c}\le 100}} X_{p,c} \ge 0.9 \sum_c \text{DEMAND}_c$$

Declare a binary variable (say, $$z_i$$), that equals 1 if customer $$i$$ is within 100 miles of an open plant. For example, let $$a_{ij}$$ be a parameter (input) that equals 1 if customer $$i$$ and plant $$j$$ are within 100 miles of each other. Then the constraint says $$z_i \le \sum_j a_{ij}x_j \quad \forall i,$$ where $$x_j$$ is a decision variable that indicates whether plant $$j$$ is open. (This is similar to a coverage-type model.)

Then write a constraint that says at least 90% of total customer demand must be within 100 miles of a plant, i.e., must have $$z_i=1$$: $$\sum_i h_iz_i \ge 0.9\sum_i h_i,$$ where $$h_i$$ is the demand of customer $$i$$.

• Hmm, I don't think a close plant being open is enough. There needs to actually be a shipment. Sep 14 '20 at 4:01
• In that case, the right-hand side of my first constraint can be replaced with $\sum_j a_{ij}y_{ij}$, where $y_{ij}=1$ if plant $j$ serves customer $i$ -- essentially the same as your $X_{p,c}$ variables, I think. Sep 14 '20 at 16:04