2
$\begingroup$

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)

enter image description here

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

If I understand correctly, you can enforce the time constraint implicitly by omitting arcs. For each customer, there is a unique path by car and a unique path by bike. If the bike is too slow to meet a customer’s deadline, omit the arc from the bike relay point to that customer. After performing this preprocessing for all customers, solve a pure minimum-cost network flow problem.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – Bree
    Nov 13, 2021 at 19:01
  • $\begingroup$ For any relay point $i$ and customer $j$ for which $t_{0,i}+t_{i,j}>d_j$, omit arc $(i,j)$. $\endgroup$
    – RobPratt
    Nov 13, 2021 at 20:56
  • $\begingroup$ You don't need any binary variables or big-M constraints. Just omit the ineligible arcs. $\endgroup$
    – RobPratt
    Nov 14, 2021 at 4:21
  • $\begingroup$ If I have to make a mathematical formulation of the delivery constraints for a more complex network, simply omitting the ineligible arcs would be a very tedious task, wouldn't it? $\endgroup$
    – Bree
    Nov 14, 2021 at 8:20
  • $\begingroup$ Does the more complex network still have, for each relay point, a unique $2$-arc path to each customer? $\endgroup$
    – RobPratt
    Nov 14, 2021 at 13:29

Your Answer

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

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