2
$\begingroup$

Assume that you are the CEO of a milk delivery company and want to deliver $k$ litres of milk to one of your customers. You can buy milk from another company. Then you should use an arbitrary path to reach your customer.
These paths are given to you as a graph $G=(V,E)$. At first, you are at vertex $p$. The objective is to reach vertex $q$. But there are some rules.

Assume that $u$ and $v$ are to arbitrarily chosen vertices. When you go from vertex $u$ to $v$, You should pay $C_{uv} \gt 0$ per each litre of milk. Also, For example if before going from $u$ to $v$, the amount of milk was $m$ litres, after going from $u$ to $v$, this amount becomes $m \times Y_{uv}$ such that $0 \lt y_{uv} \le 1$.

Assume that the cost of buying $1$ litre of milk is $\alpha$.

Notice that at the end, there should be $k$ litres of milk remained that can be delivered to the customer.

Question:

Find an algorithm to deliver $k$ litres of milk to the customer, with the minimum cost.

Note1 (The meaning of cost):

Assume that you want to go from vertex $a$ to vertex $b$, $\alpha=2$ and the amount of milk you want to deliver is $1$ litre. There are $2$ paths from $a$ to $b$:
1. Going directly from $a$ to $b$:
You should buy $1$ litre of milk, Which costs $2$ units. Then you should go from $a$ to $b$ which costs $C_{ab}=10$. Also, if $Y_{ab}=1$, The amount of milk doesn't change. So, the total cost becomes $2+10=12$
2. Going from $a$ to $c$, and then from $c$ to $b$:
You should buy $3$ litres of milk, Which costs $6$ units. Then, you should go from $a$ to $c$. If we assume that $Y_{ac}=0.5$, Then the amount of milk becomes $1.5$ litres. Also, If $C_{ac}=5$, then we should pay $5 \times 3 = 15$ units for going from $a$ to $c$. Then we go from $c$ to $b$. When we reach $c$, there are $1.5$ litres of milk remained. Also, If $C_{cb}=6$, Then the price of going from $c$ to $b$ will be $6 \times 1.5 = 9$ units. Also, $Y_{cb}= \frac{2}{3}$. Thus, $1$ litre of milk remains at the end. So, the total cost will be $6+15+9=30$ units.

Note2 (What my problem is):

First, i thought of labeling the edges with their costs. I thought that Kruskal's algorithm would solve the problem. But, There is a huge difference here! We are not sure about the costs! They depend on the amount of milk remained after each choice of vertices! That's where i'm stuck! Its like finding a minimum spanning tree, In a graph with edges having dynamic weights!

$\endgroup$
2
  • $\begingroup$ Blood is all you need in this situation $\endgroup$
    – SAJW
    Commented Mar 26, 2017 at 14:09
  • $\begingroup$ @Alucard excuse me, What?! Are you kidding me? :D $\endgroup$ Commented Mar 26, 2017 at 14:10

1 Answer 1

2
$\begingroup$

You can use Kruskal's algorithm with a slight modification. You need $k$ liters at $q$. Everything will scale with $k$, so we might as well just ask for $1$ liter at $q$. Now go to each of the vertices that is connected to $q$. You can compute the amount you would have to have at that vertex and the cost of transport when you start with that amount, so you get a pair of values to assign to each vertex connected to $q$. Now go through each of these vertices and trace the edges to the next tier of vertices. You can figure out the amount of milk you need and the cost of transport for the new set of vertices. You might have a new vertex that can get to $q$ in more than one way, which will give you more than one pair of values to assign. If both values of a pair are lower that the values of another pair, it dominates and you can ignore the higher pair. If they are one high and one low you need to keep both pairs as one will force bringing more milk, which can be expensive, but transport it onward less expensively. Keep working backwards until you find the optimum route.

$\endgroup$
4
  • $\begingroup$ Thanks! Can you please explain the part of "assigning more than one pair of values" and the things you wrote after it? it seems ambiguous to me... Maybe if you give an example with real numbers, it would be better... $\endgroup$ Commented Mar 26, 2017 at 15:45
  • $\begingroup$ You might have two paths from $p$ to $q$. One reduces the milk by a factor $10$ but costs nothing for transit. The other leaves the milk the same but costs $10$ per liter for transport. One pair for $p$ would be $(0.1,0)$ and the other would be $(1,10)$. Then if you have a single path from the source $r$ to $p$ the path from $p$ to $q$ you should select depends on the costs of the $r$ to $p$ leg. If transport is very expensive between $r$ and $p$ you want to move as little milk as possible, so should take the $(1,10)$ choice from $p$ to $q$. If transport from $r$ to $p$ is cheap $\endgroup$ Commented Mar 26, 2017 at 16:05
  • $\begingroup$ you don't mind so much carrying the extra milk and might want to take the $(0.1,0)$ choice. A path from $p$ to $q$ with $ (0.05,20)$ would be dominated by either of the others and could be ignored. $\endgroup$ Commented Mar 26, 2017 at 16:06
  • $\begingroup$ Thank you :) It really helped :) $\endgroup$ Commented Mar 26, 2017 at 16:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .