Linear Programming: Network Model Optimization

So I mentioned before that linear programming is simple, but can be used on complex problems for great results. Here’s a great example of linear programming being done on something that isn’t immediately recognizable as a linear structure:

Let’s say we have an airport that has one main terminal, two sub-terminals, three holding areas, and two baggage pickup locations. We have historical data of baggage movement by employees that gives us the maximum amount of bags we are able to transfer from one point to another, but only directly. However, we want to implement an automated baggage transportation system that optimizes the flow of luggage so that the most luggage can be brought from the main terminal to the two baggage pickup locations as possible through the system. Here is the graphical representation of the problem:

In this case, each location or area is represented by a node, and the node connections indicate maximum flow between the two nodes, as well as direction of the flow. The main terminal is node 1, the two sub terminals are nodes 2 and 3, the holding areas are nodes 4, 5, and 6, and lastly the baggage pickup locations are nodes 7 and 8.

As with all optimization problems, we need to identify the following things: our decision variables, our value function, and our constraints.

Our decision variable in this case is how much luggage flows from node to node. That’s a lot of decision variables: Flow from node 1 to node 2, flow from node 1 to node 3, etc, etc. At the end of the day, we can’t get our automated system up and running unless we can tell our employees and the system itself how much luggage to move from each node to each node.

Our value function is simple too, we just want to have the most bags flow through the system as possible. How we measure that is interesting, but we’ll get to that later.

Our constraints are mostly simple as well. We can’t have a node that sends more luggage than it’s maximum flow (represented by the number labels on each vector in the network. However, there’s another constraint. We can’t just send as much luggage down each node as the maximum is – if we do and a following node doesn’t have the exporting rate to keep up, the system will get clogged and everything fails. Therefore, we need a constraint that monitors each node’s inflow and outflow. In a linear programming structure, this would mean that every node’s inflow and outflow should be equal, or, (Inflow – Outflow) = 0.

But what about the first and last nodes? The main terminal and the two baggage pickup locations are missing an inflow or outflow constraint (inflow constraint for the main terminal, and an outflow constraint for the baggage pickup locations.

We can solve this problem, as well as our value function issue in one step: we pretend the final nodes are all capable of flowing back to the first node. In this way, we can measure the flow from the end of the network to the beginning of the network as our value function, AND we can use it to realistically constraint those nodes as well. This translates well in Excel. Below is the solved spreadsheet:

Again, our yellow cells represent our decision variables, in terms of how much luggage flows out from one node to another. Each also has a maximum flow cap.

In our inflow-outflow constraints we have cells that calculate a simple SUMIF() so that it can find all of the bags/minute that flow into their corresponding node, and all of the bags/minute that flow out of their corresponding node. Here is an example:

Our value function is simply the outflow from nodes 7 and 8 to node 1.

We give Excel Solver our inflow-outflow constraints, maximum cap constraints, non-negativity constraints, and then try to maximize the amount of baggage that can “flow back into node 1,” and we get a maximum flow of 400.

Just like in most business problems, the answer is anti-climactic. This is the maximum amount of luggage that our main terminal can export (150 to node 2, 150 to node 5, and 100 to node 3 for a total of 400). But this demonstrates the power of linear programming – it’s very simple to add or remove nodes from this model, change the maximum flow capabilities from each node, and gain a better understanding of the system to solve various business problems. For example, suppose your company proposes a construction project that would allow space for your system to increase the amount of luggage that can go out from node 1 to nodes 2, 3, and 5 by 200 bags. Is it a good idea? Without this model, it might take some time to figure out an acceptable solution. But with the model, you can easily set the parameters and find out what happens. In this case, we simulate an extra 50 bags/min to each sub-terminal, and then an extra 100 bags/min to the middle holding area:

And we find that anything past an exporting rate of 550 bags/min from the main terminal is useless – something else in the system is holding us back. From here you could either play around with the model, or run some sensitivity analysis, and you’d be able to help direct your company’s resources more efficiently.