0

There is a fulfillment problem in the e-commerce logistics field, where the fulfillment of each order is composed of a main transport (from City A to City B, referred to as a route) and an end transport (from City B to Site c, also referred to as a route).

To solve for the optimal fulfillment days for main transport carriers on each route and for each end transport carrier on each route, in order to maximize the fulfillment accuracy of all orders.

In constructing the mathematical model, we can introduce three sets of binary variables. If the main transport carrier has a fulfillment day of $t$ on route $i$, then $y_{it}$ = 1. If the end transport carrier has a fulfillment day of $t'$ on route $j$, then $z_{jt'}$ = 1. For each order, which is comprised of route $i$ and route $j$ fulfilled by the main transport carrier and end transport carrier respectively, with a fulfillment day of $t$, we have $x_{ijt}$ = 1.

For example, if the trajectory of a certain order is City A - City B - Site c, with a total fulfillment day of 4, then possible combinations for the fulfillment days of the main transport and end transport could be: 1 day for main transport and 3 days for end transport; 3 days for main transport and 1 day for end transport; or 2 days for both main and end transport.

The possible formulation is

$$\max \sum\limits_{i,j}{\sum\limits_{t}{a_{ijt}x_{ijt}}}$$ s.t. $$\sum\limits_{i,j}{\sum\limits_{t}{b_{ijt}x_{ijt}}} \geq M$$ $$\sum\limits_{t}{x_{ijt}} = 1 \;\;\;\; \forall i,j$$ $$\sum\limits_{t}{y_{it}} = 1 \;\;\;\; \forall i$$ $$\sum\limits_{t}{z_{jt}} = 1 \;\;\;\; \forall j$$

if $y_{it} = 1$ and $z_{jt'}=1$ then $x_{ij,t+t'}=1$.

We can use the variable $x$ to represent the overall accuracy, but how can we establish the relationship between variable $x$ and auxiliary variables $y$ and $z$?

RobPratt
  • 32,006
  • 1
  • 44
  • 84
Ying
  • 105
  • 6
  • Maybe it would be easier if you could work with $x_{itjt'}$ and define this variable only for $t<t'$. – PeterD Jan 26 '24 at 10:32
  • @PeterD Thans for the advice, I have thought a lot but still had no idea how to define this variable. Can you describe the meaning of $x_{itjt'}$, especially what does $t'$ refer to? – Ying Jan 27 '24 at 08:22
  • I see, you mean if $x_{itjt'}=1$ then the fulfillment day for route $i$ is $t$, and the fulfillment day for route $j$ is $t'$. The question is how to retrieve the total fulfillment day for this order? – Ying Jan 27 '24 at 08:44

1 Answers1

1

You want to linearize the logical relationship $$(y_{it} = 1 \land z_{jt'} = 1) \iff x_{ij,t+t'} = 1.$$ Equivalently, you want to linearize $$y_{it} z_{jt'} = x_{ij,t+t'}.$$

See How to linearize the product of two binary variables?

In your updated question, you want to linearize the logical relationship $$(y_{it} = 1 \land z_{jt'} = 1) \implies x_{ij,t+t'} = 1.$$ Rewriting in conjunctive normal form somewhat automatically yields a linear constraint: $$ (y_{it} \land z_{jt'}) \implies x_{ij,t+t'} \\ \lnot (y_{it} \land z_{jt'}) \lor x_{ij,t+t'} \\ \lnot y_{it} \lor \lnot z_{jt'} \lor x_{ij,t+t'} \\ (1-y_{it}) + (1-z_{jt'}) + x_{ij,t+t'} \ge 1 \\ y_{it} + z_{jt'} - x_{ij,t+t'} \le 1 \\ $$

RobPratt
  • 32,006
  • 1
  • 44
  • 84
  • The formula is not equivalent, I suppose. For example, $y_{i3} = 1$ and $z_{j2}=1$ may contribute to $x_{ij5} = 1$; however, $x_{ij5}$ may also result from $y_{i2} = 1$ and $z_{j3} = 1$. Meanwhile, if $y_{i3} = 0$ and $z_{j2} = 0$, the value of $x_{ij5}$ can be equal to 1. – Ying Jan 28 '24 at 00:29
  • So the constraints should be imposed are: $$y_{it} + z_{jt'} \leq x_{ij,t+t'} + 1$$ and $$ y_{it} \leq x_{ij,t+t'}$$ and $$z_{jt'} \leq x_{ij,t+t'}$$ – Ying Jan 28 '24 at 01:18
  • No, just the first one. – RobPratt Jan 28 '24 at 01:19
  • Right, the next two constraints mean that if $x_{ij5} = 0$ then $y_{i2}= 0, z_{j3} = 0$ and $y_{i3} = 0, z_{j2}=0$, which is wrong, since $y_{i2} = 1, z_{j2}=1$ may satisfy – Ying Jan 28 '24 at 01:22