Line: 1 to 1 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

<-- Under Construction --> | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Line: 26 to 26 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

## Operations Research Topics: LinearProgramming, IntegerProgramming, NetworkOptimisation, TransshipmentProblem## Application Areas: Logistics## Contents | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Changed: | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

< < | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

> > | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

## Problem DescriptionAmerican Steel, an Ohio-based steel manufacturing company, produces steel at its two steel mills located at Youngstown and Pittsburgh. The company distributes finished steel to its retail customers through the distribution network of regional and field warehouses shown below:
The network represents shipment of finished steel from American Steel's two steel mills located at Youngstown (node 1) and Pittsburgh (node 2) to their field warehouses at Albany, Houston, Tempe, and Gary (nodes 6, 7, 8 and 9) through three regional warehouses located at Cincinnati, Kansas City, and Chicago (nodes 3, 4 and 5). Also, some field warehouses can be directly supplied from the steel mills.
Table 1 presents the minimum and maximum flow amounts of steel that may be shipped between different cities along with the
The current monthly demand at American Steel's four field warehouses is shown in Table 2.
The Youngstown and Pittsburgh mills can produce up to 10,000 tons and 15,000 tons of steel per month, respectively. The management wants to know the least cost monthly shipment plan. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Line: 36 to 34 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Return to top
## Problem Formulation | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Changed: | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

< < | The American Steel Problem can be solved as a transshipment problem. The supply at the supply nodes is the maximum production at the steel mills, i.e., 10,000 and 15,000 for Youngstown and Pittsburgh respectively. The demand at demand nodes in given by the demand at the field warehouses and the other nodes are transshipment nodes. The costs and bounds on flow through the network are also given. The most compact formulation for this problem is a network formulation (see The Transshipment Problem for details).
<img width= | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

> > |
The American Steel Problem can be solved as a transshipment problem. The supply at the supply nodes is the maximum production at the steel mills, i.e., 10,000 and 15,000 for Youngstown and Pittsburgh respectively. The demand at demand nodes in given by the demand at the field warehouses and the other nodes are transshipment nodes. The costs and bounds on flow through the network are also given. The most compact formulation for this problem is a network formulation (see The Transshipment Problem for details).
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Return to top
## Computational Model | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Changed: | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

< < | <div class= | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

> > |
<--/twistyPlugin twikiMakeVisibleInline-->
We can use the AMPL model file `transshipment.mod` (see The Transshipment Problem in AMPL for details) to solve the American Steel Transshipment Problem. We need a data file to describe the nodes, arcs, costs and bounds. The node set is simply a list of the node names:
set NODES := Youngstown Pittsburgh Cincinnati 'Kansas City' Chicago Albany Houston Tempe Gary ;
Note that The arc set is 2-dimensional and can be defined in a number of different ways: # List of arcs set ARCS := (Youngstown, Albany), (Youngstown, Cincinnati), ... , (Chicago, Gary) ; # Table of arcs set ARCS: Cincinnati 'Kansas City' Chicago Albany Houston Tempe Gary := Youngstown + + + + - - - Pittsburgh + + + - - - + . . . # Array of arcs set ARCS := (Youngstown, *) Cincinnati 'Kansas City' Chicago Albany (Pittsburgh, *) Cincinnati 'Kansas City' Chicago Gary . . . (Chicago, *) Tempe Gary ;
Since the node set is small and the arc set is "dense", i.e., many of the node pairs are represented in the arc set, we choose a table to define set ARCS: Cincinnati 'Kansas City' Chicago Albany Houston Tempe Gary := Youngstown + + + + - - - Pittsburgh + + + - - - + Cincinnati - - - + + - - 'Kansas City' - - - - + + - Chicago - - - - - + + ;
The param NetDemand := Youngstown -10000 Pittsburgh -15000 Albany 3000 Houston 7000 Tempe 4000 Gary 6000 ;
We can use lists, tables or arrays to define the parameters for the American Steel Transhippment Problem,
but in this case we will use a list and define multiple parameters at once. This allows us to "cut-and-paste" the parameters from the problem description. Note the use of
param: Cost Lower Upper:= Youngstown Albany 500 . 1000 Youngstown Cincinnati 350 . 3000 Youngstown 'Kansas City' 450 1000 5000 Youngstown Chicago 375 . 5000 . . . Chicago Gary 120 . 4000 ; Note that the cost is in $/1000 ton, so we must divide the cost by 1000 in our script file before solving: reset; model transshipment.mod; data steel.dat; let {(m, n) in ARCS} Cost[m, n] := Cost[m, n] / 1000; option solver cplex; solve; display Flow; <--/twistyPlugin--> <--/twistyPlugin twikiMakeVisibleInline-->
We can define the PuLP/Dippy model using functions in `transshipment_funcy.py`
<--/twistyPlugin--> | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Return to top
## Results | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Changed: | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

< < | Using `transshipment.mod` , and the data and script files defined in Computational Model we can solve the American Steel Transshipment Problem to get the optimal `Flow` variables:
<img width= | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

> > |
Using `transshipment.mod` , and the data and script files defined in Computational Model we can solve the American Steel Transshipment Problem to get the optimal `Flow` variables:
If the total supply is greater than the total demand, the transshipment problem will solve, but flow may be left in the network (in this case at the Pittsburgh node). In
If total supply is less than demand (hence the problem is infeasible) we can add a | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Return to top
## Conclusions | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Changed: | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

< < | In order to minimise the monthly shipment costs, American Steel should follow the shipment plan shown in Table 3.
<a name= | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

> > |
In order to minimise the monthly shipment costs, American Steel should follow the shipment plan shown in Table 3.
As with many network problems, it can be illuminating to display the solution graphically as shown in Figure 1.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Return to top | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Changed: | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

< < | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

> > | <-- | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Changed: | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

< < | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

> > | <-- | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

View topic | History: r24 < r23 < r22 < r21 | More topic actions...

Copyright © 2008-2021 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.

Ideas, requests, problems regarding TWiki? Send feedback

Ideas, requests, problems regarding TWiki? Send feedback