# How to solve a minimum cost flow problem with time constraints

In the following picture, the decision-maker has to make deliveries to node $$V=\{1,2,3,4,5,6\}$$. He has two options: use cars or bikes. In both cases, he has to make a stop at a relay point where the order is taken by another car for the last miles deliveries. If he chooses a car to get to the relay point, he uses the arc $$(0-11)$$, therefore the node $$11$$ is the relay point if using cars. Otherwise, he uses $$(0-12)$$, making the node $$12$$ the relay point if using bikes. The two options are not mutually exclusive, as the transportation cost using bike is lesser than that of using car, but using cars makes it faster.

The DM assigns the flows based on the delivery deadlines of each customer (expressed in number of days from $$t_0$$). The decision variable is the flow of good ($$y_{ij}$$) to be transported to each customer, and the DM minimizes its transportation costs ($$c_{ij}$$) based on the time (the number of days) it takes to traverse the arcs ($$t_{ij}$$) and the delivery deadline for each customer ($$d_{j}$$).

The problem would not thus be a path selection problem, but a minimum cost flow problem, but how would I define the mathematical formulation of the constraint(s) related to the respect of the delivery deadline? I tried finding similar problems online, i.e., minimum cost flow problems with time constraint, but to no avail.

(NB: The image is not mine, I just use it for the purpose of this question)

• Thanks for the answer. I take it that if for customer 1, I have: $t_{012}$+$t_{121}$>$d_{1}$, then $t_{011}$+$t_{111}$ $≤$ $d_{1}$, but how do I formalize it. The idea is to have a formula in the case I have several relay points.
• For any relay point $i$ and customer $j$ for which $t_{0,i}+t_{i,j}>d_j$, omit arc $(i,j)$. Nov 13 '21 at 20:56
• Does the more complex network still have, for each relay point, a unique $2$-arc path to each customer? Nov 14 '21 at 13:29