1
$\begingroup$

I have a Problem with an Optimal Loading a Hopping Airplane example . This is the Part of Minimum Cost Flow Problem.. .. I dont understand a Picture at all. I should to make one example with numbers and i need to show, how could i send flow along the Airline with bigger Revenue und possible smallest cost... Thank you for your Attending..enter image description here

enter image description here

$\endgroup$
  • 1
    $\begingroup$ Can you credit the original source of the problem? $\endgroup$ – Apass.Jack Dec 29 '18 at 12:54
  • $\begingroup$ Yes! I found it there and this is complete unclear for me... In file this is page 9 (Optimal Loading of a Hopping Airplane.). google.com/… $\endgroup$ – Dmitry Uvarov Dec 29 '18 at 13:03
1
$\begingroup$

One approach to understand some complicated situation is to figure out some simplest but still meaningful situations.

In the current situation, let us check a situation when there are only two hops, hop 0 and hop 1. The simpler situation when there is only one hop is too trivial to be instructive, sine there will be no passenger to pick up.

Picking up your pen (or pencil or stylus or your finger), draw the following reduced version of Figure 9.4 in the reference provided.

enter image description here

The above direct network means

  • there are up to $b_{12}$ passengers at node 1-2 who can be picked up at node 1 (hop 1) and who should be dropped at node 2 (hop 2)
  • The cost of the arc from node 1-2 to node 1 is $-f_{12}$, where $f_{12}$ is the fare per passenger from node 1 to node 2. That means every passenger picked up will pay $f_{12}$.
  • The capacity of arc from node 1 to node 2 is $p$. There is no associated cost.
  • The arc from node 1-2 to node 2 is the imaginary flight with no cost associated nor any capacity limit.
  • There should be $b_{12}$ passengers reaching node 2. They either take the flight from node 1 to node 2 physically or take the arc from node 1-2 to node 2 virtually without paying any fare.

The minimum cost flow problem for this simple directed network is the following, where $x_{a,b}$ means the number of passengers (the flow) on the arc from $a$ to $b$.

$$\text{Minimize }\ \ z(x)= (-f_{1-2, 1})x_{1-2,1} + 0x_{1,2} + 0x_{1-2, 2}$$ subject to $$x_{1-2,1} + x_{1-2,2} = b_{12}$$ $$x_{1,2} - x_{1-2,1} = 0$$ $$-x_{1-2,2} - x_{1,2} = -b_{12}$$ $$ 0\le x_{1-2, 1}$$ $$ 0\le x_{1, 2}\le p$$ $$ 0\le x_{1-2,2}$$

Why do we want to minimize $z(x)$? Because the total fare collected is $-z(x)$.

All the conditions in the end just means, $x_{1-2,1}\le b_{12}$ and $x_{1-2,1}\le p$. We can solve this problem minimum cost flow easily by letting $x_{1-2,1}=\min(b_{12},p)$, the most passengers available not exceeding the airplane capacity.

Hopefully the above explanation is detailed enough to enable you to further understand the full minimum cost flow formulation for the problem of optimally loading a hopping airplane. You can establish a one-to-one correspondence between feasible passenger routings and feasible flows in the minimum cost flow formulation of the problem.

$\endgroup$
  • $\begingroup$ Wow ! I Think i have understood this Problem, can you check please if my solution right? $\endgroup$ – Dmitry Uvarov Jan 1 at 11:30
  • $\begingroup$ But iam not sure should i every cost multiply then with number of passengers? $\endgroup$ – Dmitry Uvarov Jan 1 at 11:32
  • $\begingroup$ They either take the flight from node 1 to node 2 physically or take the arc from node 1-2 to node 2 virtually without paying any fare. MEANS THAT THEY DONT BOUGHT A TICKET AND TAKE NOT AN AIRPLANE? $\endgroup$ – Dmitry Uvarov Jan 1 at 14:11
  • $\begingroup$ Yes, they do not buy a ticket and take no airplane.You can also imagine that each passenger is either a person or a bird. When he/she take the airplane, he/she becomes a person and pay fare. When he/she do not take the airplane, he/she becomes a bird magically and fly by themselves. In this way, we can make sure we will have equalities. What is important are those who take the airplane and pay fares. As long as our equations represent them accurately, we are good to go. $\endgroup$ – Apass.Jack Jan 1 at 15:13
  • $\begingroup$ Sorry, I have so much time on this question that I will not check your computation. $\endgroup$ – Apass.Jack Jan 1 at 15:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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