Loading
Notes
Study Reminders
Support
Text Version

Maximum Flow Model

Set your study reminders

We will email you at these times to remind you to study.
  • Monday

    -

    7am

    +

    Tuesday

    -

    7am

    +

    Wednesday

    -

    7am

    +

    Thursday

    -

    7am

    +

    Friday

    -

    7am

    +

    Saturday

    -

    7am

    +

    Sunday

    -

    7am

    +

Welcome to “Modelling and Analytics for Supply Chain Management”! We are into Week 3, Module 3 of the program and our topic is „transportation modelling for supply chain analytics‟. Now, we had dealt with two types of transportation modelling up to till now. What are they? One is cost model, means we had some suppliers or warehouses and we had some markets or factories; means from the supply point to the markets they have to, the products have to reach from the supply point to the market or from the supply point to the factory or from warehouse to the market the products have to reach. So, basically it has a origin and a destination. And the cost from each origin to each destination was given. Our objective was to minimize the total cost of transportation. What problem happened in this process? The problem happened in this process was there are multiple routes that are possible, multiple options that are possible. Some options were taken; some options were not taken because my objective was to minimize cost. So, I took only those options where my cost was, cost per unit of transportation multiplied by number of units that was less. But in that process what happened? Many routes were not used, basically were shut down. But it might happen that the routes that my mathematical model recommended me, one of these routes might not function after some time, may be some natural catastrophe, that route is closed; may be the suppliers who are supplying at that particular node, those suppliers become non-functional. So, there are many reasons why, depending on only one route or two routes is not recommended for an organization. So the organization might tell you that look, the minimum cost model is fine but then we are willing to incur some extra amount, we are willing to incur some extra amount but then I want more number of routes, more number of possible routes so tomorrow if one route is shut down I can use another route. So, in that case we had used the Min-max and Max-min problem. In that my cost increased a bit but in that process 2-3 more routes were opened up. Now another benefit for this is, sometimes some routes that are opened up, there may, a new markets may grow in those routes also. So, it should not be taken as a cost model only. It should also be taken as an opportunity model. The next problem that we ended up with telling you was that like, there is a supplier at one end of the city and there is a factory at the other end of the city and the factory operates in a just-in-time environment; so supplier at one end, factory at the other end and the factory operates in a just-in-time environment. In a every hour the factory needs, let us say 1600 kgs of a product or tonnes of a product, let us say tonnes, metric tonnes; 1600 tonnes of a product the factory needs every hour and the factory operates in a just-in-time system. So ideally the travel time from these two end points, that is supplier end point till the market end point; supplier end point till the market end point, this travel time should be 1 hour or in another way in 1 hour they should be able to transport 1600 kgs of material. So, this travel time should be 1 hour or in 1 hour they should be able to transport 1600 kgs. So, what is the maximum possible vehicle movement that is the other way to say is – what is the maximum possible vehicle movement in 1 hour time from origin to destination; that we will have to find out? The maximum possible vehicle movement is 16 trucks. Each truck is carrying 1000 kg of material so we are getting 16000 kg of raw material. If 16 trucks can travel in 1 hour from origin to destination each truck carrying 100 units of product so 1600 units of the product required in the factory so my demand is met. If however 16 trucks cannot travel in 1 hour from the origin to the destination point then I will have to think of alternate modes of transport also because my factory is running in JIT and my existing road systems or existing vehicular planning is not able to satisfy that 1600 kg demand in 1 hour then I will have to plan a different transportation system. So our job today is to find out what is the maximum number of vehicles that can ply from one end of the city to another, within a given span of time. Now you will say that what is so rocket science in that? There is a long road. Measure the length of the road. Measure the speed of the vehicles and measure the carrying capacity. Measure the length of the truck. Measure the gap between two vehicles. So basically passenger car unit, and then calculate. But life is not that easy. What happens is if it is a big truck it might not be able to go on a small route, on a small road, narrow road. If it is a small vehicle it might be able to go anywhere. But small vehicle has less carrying capacity. In some cases there are one-way restrictions on the roads. So you can go but you cannot come back on the same road. So you will have to take a detour. Portions of the road, you have to take a detour so that you can reach the destination. In some cases during particular hours of the day, right particularly from morning till late night big vehicles are not allowed. So this maximum flow, calculating the maximum flow is not as simple as we might be thinking of it. It has so many other complications also. So today we will learn how to find out the maximum number of vehicles that can pass through within a given amount of time. There is a JIT movement as we are mentioning from a supplier plant to the mother plant, the required quantity per hour by the mother plant from the supplier plant is x. The distance between the supplier plant and mother plant is covered by a network of roads. Total vehicle handling capacity of all the roads in the network put together per hour is y. So basically required quantity is x. Distance between the supplier plant and mother plant is covered. Total vehicle handling capacity is y. Within the network there are different categories of roads, heavy vehicles, medium, some less commercial vehicles, et cetera. As such the vehicle handling capacity of the roads handling different types of vehicles also differ; this all that we have mentioned already. The objective is to find out the maximum number of vehicles that can move from the supply point to the factory in an hour using the network of roads. If vehicles movement per hour into load per vehicle less than equal to requirement of materials per hour, then alternate transport modes have to be thought of. Let us look at the mathematical problem and we have to find out the maximum number of vehicles from origin road crossing 1 to destination road crossing 7. So origin is 1, road crossing 1, destination road is road crossing 7 and you will have to find out the maximum number of vehicles that can flow from the supplier to the manufacturer in an hour. This is the problem. What it says is, road crossing 1 to road crossing 2, 5 vehicles can move in an hour. Road crossing 1 to road crossing 3, 6 vehicles can move in an hour. Road crossing 1 to road crossing 4, 5 vehicles can move in an hour. In this way all the crossings, how many vehicles can move from one point to another is given. So basically what are crossings? These are basically traffic signals. From this traffic signal to this traffic signal in 1 hour 5 vehicles can move. From this traffic signal to this traffic signal in 1 hour, how many vehicles can move? 6 vehicles! From this traffic signal to this traffic signal how many vehicles can move in 1 hour? 5. So this and these are my road crossings; crossing 1, crossing 2, crossing 3. So, this is what is meant by this 5, 6, 5, 2, 3, 2, etc. So road crossing 1, 2, 3 this is the vehicle movements. So what it is saying is, from crossing 1 to crossing 2 in 1 hour, 5 vehicles can move. From crossing 1 to crossing 3, may be in 1 hour, 6 vehicles are moving; then 5 vehicles are moving from the next signal point to the other. So this is basically the vehicle movement from one point to other, right? So, what to do? First step is to draw the diagram. If you see, if you can map this, if you can map this and if you see the notations what we are saying is let X1 vehicles, let this 5 be, 5 vehicles can move, let this distance be X1. And this is the diagram for this. This is crossing 1, crossing 2, crossing 3, crossing 4, 5, 6 and 7. So, from crossing 1 to crossing 2, 5 cars can move, 5 trucks can move in 1 hour; crossing 2 to crossing 3, 2 trucks can move; 6, 5, 3, 4, etc. So, whatever was been given to you has been converted into a network diagram. No rocket science, it is simple drawing. It is simply drawing the problem. It is a simple drawing of the problem, simple drawing of the problem. Now what we were saying is, we this was original drawing. We are saying we will draw another line that links up crossing 7 to crossing 1. This was the original drawing; this was the original drawing. We are linking up from crossing 7 to crossing 1, another imaginary road that has no signals, no crossings in between, a direct road from 7 to 1. What is the idea? The idea is, all the vehicles that are moving from point 1 to point 7 through so many traffic signals, all the vehicles that are moving from point 1 to point 7 with so many traffic signals and reaching point 7 has to come back. So basically at 7, how many vehicles are waiting or garaged? 0. So, whatever is coming in to 7 has to move out. Similarly, at 1 also if you can look at it that way, whatever is coming back to 1 has to go back to 7 because these are trucks which will take the full load to 7, come back empty and again take the full load back. So, basically there is no storing at any of these nodes. So, the vehicles that have gone, the vehicles that have gone are coming back. Similarly, whatever is coming back has to go again. So, basically this 7 to 1 is the maximum number of vehicles that can move in this route. So, if you can draw this 7 to 1, whatever value of x comes, whatever value of x comes, this is the maximum number of vehicles that can ply in this route; because 7 does not store anything. It is like morning all the vehicles are moving from 1 to 7. Let us take the public transportation system. Let us take the rail system. What happens? All the vehicles go and at night, at another garage it rests. Then from the morning the first bus takes, starts moving at 4 am or 5 am and then again comes here. Then again they go. Again they come here. So, basically what you want to say is at night there is some resting. Here what you are saying is there is 0 movement, 0 resting. Whatever goes comes out immediately. So this arc, this 7 to 1, this 7 to 1 basically takes care of all the vehicle movement that has happened through so many traffic signals. Now, if this route, so all the vehicles movements, so this route has to be maximized. So maximize this 7 to 1 route vehicle flow. Maximize the vehicle flow from 7 to 1. Maximize the vehicle flow from 7 to 1. This is our problem, nothing else. This is our problem. This is what we mentioned. We introduce a dummy road. The diagram is given here in very small figure here. We introduced a dummy road from node 7 to node 1. Since, no cars are created at node 7, the entire number of cars flowing out of node 7 must consist of entire number of cars that flowed into node 7, whatever cars are moving out must be equal to the cars that have come into node 7. Similarly, since no cars are consumed at node 1 the entire number of cars that enter node 1 through the node number 7 to 1 must consist of cars that originally flowed out of node 1. So, whatever car has come in is equal to the cars that had already moved out. So this now has to be maximized. So, we will see this is basically X15. If you take this as X1, yeah; if you take this as X1, sorry, just take X3, what are these? The maximum number of vehicles that should ply, X4, X5 you can write them on your own; X1, X2, X4, I am just writing down whatever I have written down here, so up to X14 and this route is X15 and our objective is to maximize this X15, our objective is to maximize this X15, so this is my model. And so this is the equation; max: X15. Now, here there is a question. What are the subjects, subject to, rather the constraints; X1 plus X2 plus X3 minus X15 is equal to 0. What does that mean? Remember X1, X2, X3 minus X15 is equal to 0. X1, X2, X3 minus X15 is equal to 0. Let us go back. What was the diagram? X1, X2, X3, X15, remember? What is happening here at node 1? What are we saying? Whatever vehicles are coming in are going out. It is like a traffic signal here at 2. This is at 1. At 2 what is happening? At node 2 or signal point 2 there is traffic signal. Whatever vehicles are standing, that is coming in at the traffic signal; after the signal becomes green, after the signal becomes green are moving out, agreed? So, at node 1 what is happening? How many vehicles are moving out? So what routes? X1 vehicles are moving along this route. X2 vehicles are moving along this route and X3 vehicles are moving along this route and what is coming in? X15 vehicles are coming in. What is coming in? X15 vehicles are coming in. So, X1 plus X2 plus X3 is equal to X15, agreed? This is at node 1. X1 plus X2 plus X3 is equal to X15. Take X15 another side, on the other side. X1 plus X2 plus X3 minus X15 is equal to 0. We need not do equal to 0. We have done it just for modelling purpose, no rocket science. So at each of the nodes whatever is coming in has to go out. Let us take X4. What is coming in? X3 is coming in. Look at the arrow. This was my X9. X9 is coming, what is going out? X10. So at node 4 what is happening? X3 plus X9 is coming in, should equal to X10; X3, X9, X10. So, at every node this will happen. Now let us go back. Yep, so you see this is what we did. Our objective was to maximize X15, that is node 7 to 1 and X1 plus X2 plus X3 is equal to X15; minus X15 we have done to put... X4, X5 is equal to X1 plus X6. That is two things coming in, two things going out. X10, X3 plus X7 is equal to X10. Let us go to node 4. At node 4 what has happened? Remember? X3, no there was X9 sorry, some X3, X9 whatever, X3, X9 we have mentioned, this is 7; X3, X7 and what is going out? X10. So, now what is the maximum capacity at node 1; that is X1? Maximum number of vehicles that can go is 5. How many vehicles are we planning? It should be less than equal to 5. Let us go back. If this is not understandable, let us go back and see, yep. X1 right, oh sorry, X1 right. What is the value of X1? We do not know, right? What is the maximum handling capacity of this road in 1 hour, handling capacity? 5. So what should X1 be, less than equal to 5? What is this one? This was X3, remember? This was X2, right? X3, what is the handling capacity of this particular road? 5. So how many vehicles can move at the max? Less than equal to 5, max is 5. How many vehicles should move, less than equal to 5? It cannot be greater than equal to. So, this is, so these are the other constraints. Let us take this one, X6 to X7, what was the variable? X14, so X14. What is the maximum possible? 7 units; so how many vehicles will move? Less than equal to 7, X14; so X14 less than... So, in this way, all the constraints are to be mapped. See last one, X14 is less than equal to 7. So, once you do that and once you use this particular software or Excel or whatever, once you use any mathematical optimization software you will get X15, you will get X15 sorry, you will get X15 is equal to 7. You will get X15 is equal to 7. This is my, X15 is equal to, sorry X15 will be equal to 14, solution. So, what does it mean? 14 equivalent size vehicles can pass origin to destination in 1 hour. If the load required to be sent to the destination is more than 14 vehicles then an alternate mode of transport is to be thought of. How did we...? So, 14 equivalent size vehicles can pass from the origin to the destination in 1 hour. If the load required to be sent to the destination is more than 1, then an alternate mode of transport is to be thought of. That is how basically you arrange your vehicles, clear? Now you can, I will show you. This is the result sheet from LIPS. X15 is equal to 14. That means this is the maximum number of vehicles that can move. And it is saying 3 vehicles should move in X1. What was the maximum capacity of X1, remember? X1 was 5. 5 vehicles can move. It is saying that 3 vehicles should move from signal 1 to signal 2. Maximum capacity is 5. It is saying 3 vehicles should move. In this way the number of vehicles that should move through these signal points are all given to you. So this is the way by which you can solve this problem. Now see this is the total number of vehicles that can move. You can use similar methods for; say you are having lot of small vehicles. Then it can enter the city during the daytime also. Large vehicles are only allowed after evening. So assume that you are having only small vehicles. So you can use this type of modelling to understand the product mix that means how many small vehicles you need and how many big vehicles you need. That also you can model. For example, let us take an example. What is the maximum value that we have got for X15, that is 14? That means we need 14 vehicles, or rather 14, in terms of city planning, 14 passenger car units, you need 14 passenger car units. And assume 1 passenger car unit consumes a space that is required by Tata Ace which is a small vehicle, and Tata Ace can carry, assume 100 kgs of material. So how many kgs can be transferred in 1 hour? 1400 kgs! If you are required to transport 1600 kgs so you have to look for alternate modes of transport. Now assume your factory is in such a location that no alternate mode is available. So what you can do? You know 1400 can be transported, another 200 is remaining, right. So, what you do, and each one has a 100 kg capacity. So you need 2 more, but where will you fit 2 more? Not possible. So, instead have 2 larger vehicles of 200 kgs capacity each. So, then that problem is taken care of. So, not only maximum flow but it can also, this model can be used for managing the size of the vehicles that you are having in your portfolio, which size vehicles to use. Now see another issue; then you will tell me that, “Sir, why shall I use 14 vehicles, 14 small vehicles. I will use 7 big vehicles and carry 200 kgs each.” Then what will happen? Your products will reach early and there will be storing problem. Where will you store? Because you have a JIT system; so you have a storing problem. And then what will happen? You will ask the vehicles to wait till 8 am or 9 am, till your production schedule starts. So, now what is happening? Your vehicles are waiting so vehicle waiting time is there. That is a cost. So your transport cost is increasing. So when you are operating in a JIT system you will have to be very-very careful about how you are synchronizing your transportation schedules, vehicle schedules, delivery schedules and that schedule is somewhere which now you are understanding, that schedule is somewhere linked with the network of roads that your vehicles are taking, the width of the road, whether national highway or state highway or local road which in an essence is basically the vehicle handling capacity of that road per hour. So, JIT system, in a nutshell what we want to say is JIT system is linked to the type of vehicles that you will hire, your vehicle scheduling system as also your distance and the vehicle handling capacity of the roads. So JIT system is to be linked to route planning and vehicle handling capacity also. So, this is the maximum flow problem. In the next module what we will do is we will take care of the minimum time or the minimum distance that needs to be travelled from place A to place B given that multiple routes are available, that is the shortest possible route. This we will take up in the next class. Thank you!