Difference: AmericanSteelTransshipmentProblem (1 vs. 24)

Revision 242014-05-22 - MichaelOSullivan

Line: 1 to 1
 
META TOPICPARENT name="SubmitCaseStudy"
<-- Under Construction -->
Line: 88 to 88
 
FORM FIELD ApplicationAreas ApplicationAreas Logistics
|*FORM FIELD ProblemDescription*|ProblemDescription|American 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:

steel_network.jpg

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 cost per 1000 ton/month of shipping the steel. For example, the shipment from Youngstown to Kansas City is contracted out to a railroad company with a minimal shipping clause of 1000 tons/month. However, the railroad cannot ship more than 5000 tons/month due the shortage of rail cars.

Table 1 Arc Costs and Limits

From node To node Cost Minimum Maximum
Youngstown Albany 500 - 1000
Youngstown Cincinnati 350 - 3000
Youngstown Kansas City 450 1000 5000
Youngstown Chicago 375 - 5000
Pittsburgh Cincinnati 350 - 2000
Pittsburgh Kansas City 450 2000 3000
Pittsburgh Chicago 400 - 4000
Pittsburgh Gary 450 - 2000
Cincinnati Albany 350 1000 5000
Cincinnati Houston 550 - 6000
Kansas City Houston 375 - 4000
Kansas City Tempe 650 - 4000
Chicago Tempe 600 - 2000
Chicago Gary 120 - 4000

The current monthly demand at American Steel's four field warehouses is shown in Table 2.

Table 2 Monthly Demands

Field Warehouses Monthly Demand
Albany, N.Y. 3000
Houston 7000
Tempe 4000
Gary 6000

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.| |*FORM FIELD ProblemFormulation*|ProblemFormulation|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).

steel_formulation.jpg

|

Changed:
<
<
|*FORM FIELD ComputationalModel*|ComputationalModel|
<--/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 Kansas City must be enclosed in ' and ' because of the whitespace in the name.

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 ARCS:

set ARCS:   Cincinnati 'Kansas City' Chicago Albany Houston Tempe Gary :=
Youngstown         +          +         +      +       -      -    -
Pittsburgh         +          +         +      -       -      -    +
Cincinnati         -          -         -      +       +      -    -
'Kansas City'      -          -         -      -       +      +    -
Chicago            -          -         -      -       -      +    + ;

The NetDemand can be defined easily from the supply and demand. Since the default is 0 we don't need to define NetDemand for the transshipment nodes:

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 . for parameters where the defaults will suffice (e.g., Lower for Youngstown and Albany):

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-->
|
>
>
|*FORM FIELD ComputationalModel*|ComputationalModel|
<--/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 Kansas City must be enclosed in ' and ' because of the whitespace in the name.

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 ARCS:

set ARCS:   Cincinnati 'Kansas City' Chicago Albany Houston Tempe Gary :=
Youngstown         +          +         +      +       -      -    -
Pittsburgh         +          +         +      -       -      -    +
Cincinnati         -          -         -      +       +      -    -
'Kansas City'      -          -         -      -       +      +    -
Chicago            -          -         -      -       -      +    + ;

The NetDemand can be defined easily from the supply and demand. Since the default is 0 we don't need to define NetDemand for the transshipment nodes:

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 . for parameters where the defaults will suffice (e.g., Lower for Youngstown and Albany):

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-->
|
 |*FORM FIELD Results*|Results|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:

steel_solution.jpg

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 transshipment.mod we check that sum {n in NODES} NetDemand[n] <= 0 to ensure a problem is feasible before solving.

If total supply is less than demand (hence the problem is infeasible) we can add a dummy supply node (see with arcs to all the demand nodes. The optimal solution will show the "best" nodes to send the extra supply to. | |*FORM FIELD Conclusions*|Conclusions|In order to minimise the monthly shipment costs, American Steel should follow the shipment plan shown in Table 3.

Table 3 Optimal Shipment Plan

From/To Cincinnati Kansas City Chicago Albany Houston Tempe Gary
Youngstown 3000 3000 3000 1000      
Pittsburgh 2000 3000 3000       2000
Cincinnati       2000 3000    
Kansas City         4000 2000  
Chicago           2000 4000

As with many network problems, it can be illuminating to display the solution graphically as shown in Figure 1.

Figure 1 Optimal Shipment Plan

steel_graphical.jpg

|

FORM FIELD ExtraForExperts ExtraForExperts

Revision 232014-02-12 - MichaelOSullivan

Line: 1 to 1
 
META TOPICPARENT name="SubmitCaseStudy"
<-- Under Construction -->
Line: 88 to 88
 
FORM FIELD ApplicationAreas ApplicationAreas Logistics
|*FORM FIELD ProblemDescription*|ProblemDescription|American 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:

steel_network.jpg

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 cost per 1000 ton/month of shipping the steel. For example, the shipment from Youngstown to Kansas City is contracted out to a railroad company with a minimal shipping clause of 1000 tons/month. However, the railroad cannot ship more than 5000 tons/month due the shortage of rail cars.

Table 1 Arc Costs and Limits

From node To node Cost Minimum Maximum
Youngstown Albany 500 - 1000
Youngstown Cincinnati 350 - 3000
Youngstown Kansas City 450 1000 5000
Youngstown Chicago 375 - 5000
Pittsburgh Cincinnati 350 - 2000
Pittsburgh Kansas City 450 2000 3000
Pittsburgh Chicago 400 - 4000
Pittsburgh Gary 450 - 2000
Cincinnati Albany 350 1000 5000
Cincinnati Houston 550 - 6000
Kansas City Houston 375 - 4000
Kansas City Tempe 650 - 4000
Chicago Tempe 600 - 2000
Chicago Gary 120 - 4000

The current monthly demand at American Steel's four field warehouses is shown in Table 2.

Table 2 Monthly Demands

Field Warehouses Monthly Demand
Albany, N.Y. 3000
Houston 7000
Tempe 4000
Gary 6000

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.| |*FORM FIELD ProblemFormulation*|ProblemFormulation|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).

steel_formulation.jpg

|

Changed:
<
<
|*FORM FIELD ComputationalModel*|ComputationalModel|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 Kansas City must be enclosed in ' and ' because of the whitespace in the name.

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 ARCS:

set ARCS:   Cincinnati 'Kansas City' Chicago Albany Houston Tempe Gary :=
Youngstown         +          +         +      +       -      -    -
Pittsburgh         +          +         +      -       -      -    +
Cincinnati         -          -         -      +       +      -    -
'Kansas City'      -          -         -      -       +      +    -
Chicago            -          -         -      -       -      +    + ;

The NetDemand can be defined easily from the supply and demand. Since the default is 0 we don't need to define NetDemand for the transshipment nodes:

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 . for parameters where the defaults will suffice (e.g., Lower for Youngstown and Albany):

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;
|
>
>
|*FORM FIELD ComputationalModel*|ComputationalModel|
<--/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 Kansas City must be enclosed in ' and ' because of the whitespace in the name.

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 ARCS:

set ARCS:   Cincinnati 'Kansas City' Chicago Albany Houston Tempe Gary :=
Youngstown         +          +         +      +       -      -    -
Pittsburgh         +          +         +      -       -      -    +
Cincinnati         -          -         -      +       +      -    -
'Kansas City'      -          -         -      -       +      +    -
Chicago            -          -         -      -       -      +    + ;

The NetDemand can be defined easily from the supply and demand. Since the default is 0 we don't need to define NetDemand for the transshipment nodes:

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 . for parameters where the defaults will suffice (e.g., Lower for Youngstown and Albany):

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-->
|
 |*FORM FIELD Results*|Results|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:

steel_solution.jpg

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 transshipment.mod we check that sum {n in NODES} NetDemand[n] <= 0 to ensure a problem is feasible before solving.

If total supply is less than demand (hence the problem is infeasible) we can add a dummy supply node (see with arcs to all the demand nodes. The optimal solution will show the "best" nodes to send the extra supply to. | |*FORM FIELD Conclusions*|Conclusions|In order to minimise the monthly shipment costs, American Steel should follow the shipment plan shown in Table 3.

Table 3 Optimal Shipment Plan

From/To Cincinnati Kansas City Chicago Albany Houston Tempe Gary
Youngstown 3000 3000 3000 1000      
Pittsburgh 2000 3000 3000       2000
Cincinnati       2000 3000    
Kansas City         4000 2000  
Chicago           2000 4000

As with many network problems, it can be illuminating to display the solution graphically as shown in Figure 1.

Figure 1 Optimal Shipment Plan

steel_graphical.jpg

|

FORM FIELD ExtraForExperts ExtraForExperts

Revision 222009-10-06 - MichaelOSullivan

Line: 1 to 1
 
META TOPICPARENT name="SubmitCaseStudy"
<-- Under Construction -->
Line: 86 to 86
 
FORM FIELD CaseStudyType CaseStudyType TeachingCaseStudy
FORM FIELD OperationsResearchTopics OperationsResearchTopics LinearProgramming, IntegerProgramming, NetworkOptimisation, TransshipmentProblem
FORM FIELD ApplicationAreas ApplicationAreas Logistics
Changed:
<
<
|*FORM FIELD ProblemDescription*|ProblemDescription|American 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:

steel_network.jpg

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 cost per 1000 ton/month of shipping the steel. For example, the shipment from Youngstown to Kansas City is contracted out to a railroad company with a minimal shipping clause of 1000 tons/month. However, the railroad cannot ship more then 5000 tons/month due the shortage of rail cars.

Table 1 Arc Costs and Limits

From node To node Cost Minimum Maximum
Youngstown Albany 500 - 1000
Youngstown Cincinnati 350 - 3000
Youngstown Kansas City 450 1000 5000
Youngstown Chicago 375 - 5000
Pittsburgh Cincinnati 350 - 2000
Pittsburgh Kansas City 450 2000 3000
Pittsburgh Chicago 400 - 4000
Pittsburgh Gary 450 - 2000
Cincinnati Albany 350 1000 5000
Cincinnati Houston 550 - 6000
Kansas City Houston 375 - 4000
Kansas City Tempe 650 - 4000
Chicago Tempe 600 - 2000
Chicago Gary 120 - 4000

The current monthly demand at American Steel's four field warehouses is shown in Table 2.

Table 2 Monthly Demands

Field Warehouses Monthly Demand
Albany, N.Y. 3000
Houston 7000
Tempe 4000
Gary 6000

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.| |*FORM FIELD ProblemFormulation*|ProblemFormulation|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 repsectively. 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).

steel_formulation.jpg

|

>
>
|*FORM FIELD ProblemDescription*|ProblemDescription|American 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:

steel_network.jpg

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 cost per 1000 ton/month of shipping the steel. For example, the shipment from Youngstown to Kansas City is contracted out to a railroad company with a minimal shipping clause of 1000 tons/month. However, the railroad cannot ship more than 5000 tons/month due the shortage of rail cars.

Table 1 Arc Costs and Limits

From node To node Cost Minimum Maximum
Youngstown Albany 500 - 1000
Youngstown Cincinnati 350 - 3000
Youngstown Kansas City 450 1000 5000
Youngstown Chicago 375 - 5000
Pittsburgh Cincinnati 350 - 2000
Pittsburgh Kansas City 450 2000 3000
Pittsburgh Chicago 400 - 4000
Pittsburgh Gary 450 - 2000
Cincinnati Albany 350 1000 5000
Cincinnati Houston 550 - 6000
Kansas City Houston 375 - 4000
Kansas City Tempe 650 - 4000
Chicago Tempe 600 - 2000
Chicago Gary 120 - 4000

The current monthly demand at American Steel's four field warehouses is shown in Table 2.

Table 2 Monthly Demands

Field Warehouses Monthly Demand
Albany, N.Y. 3000
Houston 7000
Tempe 4000
Gary 6000

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.| |*FORM FIELD ProblemFormulation*|ProblemFormulation|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).

steel_formulation.jpg

|

 |*FORM FIELD ComputationalModel*|ComputationalModel|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 Kansas City must be enclosed in ' and ' because of the whitespace in the name.

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 ARCS:

set ARCS:   Cincinnati 'Kansas City' Chicago Albany Houston Tempe Gary :=
Youngstown         +          +         +      +       -      -    -
Pittsburgh         +          +         +      -       -      -    +
Cincinnati         -          -         -      +       +      -    -
'Kansas City'      -          -         -      -       +      +    -
Chicago            -          -         -      -       -      +    + ;

The NetDemand can be defined easily from the supply and demand. Since the default is 0 we don't need to define NetDemand for the transshipment nodes:

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 . for parameters where the defaults will suffice (e.g., Lower for Youngstown and Albany):

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;
| |*FORM FIELD Results*|Results|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:

steel_solution.jpg

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 transshipment.mod we check that sum {n in NODES} NetDemand[n] <= 0 to ensure a problem is feasible before solving.

If total supply is less than demand (hence the problem is infeasible) we can add a dummy supply node (see with arcs to all the demand nodes. The optimal solution will show the "best" nodes to send the extra supply to. | |*FORM FIELD Conclusions*|Conclusions|In order to minimise the monthly shipment costs, American Steel should follow the shipment plan shown in Table 3.

Table 3 Optimal Shipment Plan

From/To Cincinnati Kansas City Chicago Albany Houston Tempe Gary
Youngstown 3000 3000 3000 1000      
Pittsburgh 2000 3000 3000       2000
Cincinnati       2000 3000    
Kansas City         4000 2000  
Chicago           2000 4000

As with many network problems, it can be illuminating to display the solution graphically as shown in Figure 1.

Figure 1 Optimal Shipment Plan

steel_graphical.jpg

|

Revision 212008-04-29 - MichaelOSullivan

Line: 1 to 1
 
META TOPICPARENT name="SubmitCaseStudy"
<-- Under Construction -->
Line: 88 to 88
 
FORM FIELD ApplicationAreas ApplicationAreas Logistics
|*FORM FIELD ProblemDescription*|ProblemDescription|American 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:

steel_network.jpg

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 cost per 1000 ton/month of shipping the steel. For example, the shipment from Youngstown to Kansas City is contracted out to a railroad company with a minimal shipping clause of 1000 tons/month. However, the railroad cannot ship more then 5000 tons/month due the shortage of rail cars.

Table 1 Arc Costs and Limits

From node To node Cost Minimum Maximum
Youngstown Albany 500 - 1000
Youngstown Cincinnati 350 - 3000
Youngstown Kansas City 450 1000 5000
Youngstown Chicago 375 - 5000
Pittsburgh Cincinnati 350 - 2000
Pittsburgh Kansas City 450 2000 3000
Pittsburgh Chicago 400 - 4000
Pittsburgh Gary 450 - 2000
Cincinnati Albany 350 1000 5000
Cincinnati Houston 550 - 6000
Kansas City Houston 375 - 4000
Kansas City Tempe 650 - 4000
Chicago Tempe 600 - 2000
Chicago Gary 120 - 4000

The current monthly demand at American Steel's four field warehouses is shown in Table 2.

Table 2 Monthly Demands

Field Warehouses Monthly Demand
Albany, N.Y. 3000
Houston 7000
Tempe 4000
Gary 6000

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.| |*FORM FIELD ProblemFormulation*|ProblemFormulation|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 repsectively. 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).

steel_formulation.jpg

|

Changed:
<
<
|*FORM FIELD ComputationalModel*|ComputationalModel|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 Kansas City must be enclosed in ' and ' because of the whitespace in the name.

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 ARCS:

set ARCS:   Cincinnati 'Kansas City' Chicago Albany Houston Tempe Gary :=
Youngstown         +          +         +      +       -      -    -
Pittsburgh         +          +         +      -       -      -    +
Cincinnati         -          -         -      +       +      -    -
'Kansas City'      -          -         -      -       +      +    -
Chicago            -          -         -      -       -      +    + ;

The NetDemand can be defined easily from the supply and demand. Since the default is 0 we don't need to define NetDemand for the transshipment nodes:

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 . for parameters where the defaults will suffice (e.g., Lower for Youngstown and Albany):

param:                  	Cost    Lower  	Upper:=
Youngstown	Albany		500	.	1000
Youngstown	Cincinnati	350	.	3000
Youngstown	'Kansas City'	450	1000	5000
Youngstown	Chicago		375	.	5000
Pittsburgh 	Cincinnati	350	.	2000
Pittsburgh	'Kansas City'	450	2000	3000
Pittsburgh	Chicago		400	.	4000
Pittsburgh	Gary 		450	.	2000
Cincinnati	Albany		350	1000	5000
Cincinnati	Houston		550	.	6000
'Kansas City'	Houston		375	.	4000
'Kansas City'	Tempe		650	.	4000
Chicago		Tempe		600	.	2000
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;
|
>
>
|*FORM FIELD ComputationalModel*|ComputationalModel|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 Kansas City must be enclosed in ' and ' because of the whitespace in the name.

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 ARCS:

set ARCS:   Cincinnati 'Kansas City' Chicago Albany Houston Tempe Gary :=
Youngstown         +          +         +      +       -      -    -
Pittsburgh         +          +         +      -       -      -    +
Cincinnati         -          -         -      +       +      -    -
'Kansas City'      -          -         -      -       +      +    -
Chicago            -          -         -      -       -      +    + ;

The NetDemand can be defined easily from the supply and demand. Since the default is 0 we don't need to define NetDemand for the transshipment nodes:

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 . for parameters where the defaults will suffice (e.g., Lower for Youngstown and Albany):

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;
|
 |*FORM FIELD Results*|Results|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:

steel_solution.jpg

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 transshipment.mod we check that sum {n in NODES} NetDemand[n] <= 0 to ensure a problem is feasible before solving.

If total supply is less than demand (hence the problem is infeasible) we can add a dummy supply node (see with arcs to all the demand nodes. The optimal solution will show the "best" nodes to send the extra supply to. | |*FORM FIELD Conclusions*|Conclusions|In order to minimise the monthly shipment costs, American Steel should follow the shipment plan shown in Table 3.

Table 3 Optimal Shipment Plan

From/To Cincinnati Kansas City Chicago Albany Houston Tempe Gary
Youngstown 3000 3000 3000 1000      
Pittsburgh 2000 3000 3000       2000
Cincinnati       2000 3000    
Kansas City         4000 2000  
Chicago           2000 4000

As with many network problems, it can be illuminating to display the solution graphically as shown in Figure 1.

Figure 1 Optimal Shipment Plan

steel_graphical.jpg

|

FORM FIELD ExtraForExperts ExtraForExperts

Revision 202008-04-29 - MichaelOSullivan

Line: 1 to 1
 
META TOPICPARENT name="SubmitCaseStudy"
<-- Under Construction -->
Line: 80 to 80
 
Deleted:
<
<
  • steel_graphical.jpg:
    steel_graphical.jpg
 
META FORM name="OpsRes.CaseStudyForm"
FORM FIELD Title Title The American Steel Transshipment Problem
FORM FIELD DateSubmitted DateSubmitted 15 Feb 2008
Line: 93 to 90
 |*FORM FIELD ProblemFormulation*|ProblemFormulation|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 repsectively. 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).

steel_formulation.jpg

| |*FORM FIELD ComputationalModel*|ComputationalModel|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 Kansas City must be enclosed in ' and ' because of the whitespace in the name.

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 ARCS:

set ARCS:   Cincinnati 'Kansas City' Chicago Albany Houston Tempe Gary :=
Youngstown         +          +         +      +       -      -    -
Pittsburgh         +          +         +      -       -      -    +
Cincinnati         -          -         -      +       +      -    -
'Kansas City'      -          -         -      -       +      +    -
Chicago            -          -         -      -       -      +    + ;

The NetDemand can be defined easily from the supply and demand. Since the default is 0 we don't need to define NetDemand for the transshipment nodes:

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 . for parameters where the defaults will suffice (e.g., Lower for Youngstown and Albany):

param:                  	Cost    Lower  	Upper:=
Youngstown	Albany		500	.	1000
Youngstown	Cincinnati	350	.	3000
Youngstown	'Kansas City'	450	1000	5000
Youngstown	Chicago		375	.	5000
Pittsburgh 	Cincinnati	350	.	2000
Pittsburgh	'Kansas City'	450	2000	3000
Pittsburgh	Chicago		400	.	4000
Pittsburgh	Gary 		450	.	2000
Cincinnati	Albany		350	1000	5000
Cincinnati	Houston		550	.	6000
'Kansas City'	Houston		375	.	4000
'Kansas City'	Tempe		650	.	4000
Chicago		Tempe		600	.	2000
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;
| |*FORM FIELD Results*|Results|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:

steel_solution.jpg

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 transshipment.mod we check that sum {n in NODES} NetDemand[n] <= 0 to ensure a problem is feasible before solving.

If total supply is less than demand (hence the problem is infeasible) we can add a dummy supply node (see with arcs to all the demand nodes. The optimal solution will show the "best" nodes to send the extra supply to. |

Changed:
<
<
|*FORM FIELD Conclusions*|Conclusions|In order to minimise the monthly shipment costs, American Steel should follow the shipment plan shown in Table 3.

Table 3 Optimal Shipment Plan

From/To Cincinnati Kansas City Chicago Albany Houston Tempe Gary
Youngstown 3000 3000 3000 1000      
Pittsburgh 2000 3000 3000       2000
Cincinnati       2000 3000    
Kansas City         4000 2000  
Chicago           2000 4000

As with many network problems, it can be illuminating to display the solution graphically as shown in Figure 1.

Figure 1 Optimal Shipment Plan |

>
>
|*FORM FIELD Conclusions*|Conclusions|In order to minimise the monthly shipment costs, American Steel should follow the shipment plan shown in Table 3.

Table 3 Optimal Shipment Plan

From/To Cincinnati Kansas City Chicago Albany Houston Tempe Gary
Youngstown 3000 3000 3000 1000      
Pittsburgh 2000 3000 3000       2000
Cincinnati       2000 3000    
Kansas City         4000 2000  
Chicago           2000 4000

As with many network problems, it can be illuminating to display the solution graphically as shown in Figure 1.

Figure 1 Optimal Shipment Plan

steel_graphical.jpg

|

 
FORM FIELD ExtraForExperts ExtraForExperts
|*FORM FIELD StudentTasks*|StudentTasks|
  1. Solve the American Steel Transshipment Problem. Write a management summary of your solution.

    What to hand in Hand in your management summary.

|
META FILEATTACHMENT attachment="steel_formulation.jpg" attr="h" comment="" date="1203066411" name="steel_formulation.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_formulation.jpg" size="30991" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_formulation.jpg" tmpFilename="" user="BaseUserMapping_333" version="1"

Revision 192008-04-29 - MichaelOSullivan

Line: 1 to 1
 
META TOPICPARENT name="SubmitCaseStudy"
<-- Under Construction -->
Line: 80 to 80
 
Added:
>
>
  • steel_graphical.jpg:
    steel_graphical.jpg
 
META FORM name="OpsRes.CaseStudyForm"
FORM FIELD Title Title The American Steel Transshipment Problem
FORM FIELD DateSubmitted DateSubmitted 15 Feb 2008
Line: 90 to 93
 |*FORM FIELD ProblemFormulation*|ProblemFormulation|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 repsectively. 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).

steel_formulation.jpg

| |*FORM FIELD ComputationalModel*|ComputationalModel|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 Kansas City must be enclosed in ' and ' because of the whitespace in the name.

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 ARCS:

set ARCS:   Cincinnati 'Kansas City' Chicago Albany Houston Tempe Gary :=
Youngstown         +          +         +      +       -      -    -
Pittsburgh         +          +         +      -       -      -    +
Cincinnati         -          -         -      +       +      -    -
'Kansas City'      -          -         -      -       +      +    -
Chicago            -          -         -      -       -      +    + ;

The NetDemand can be defined easily from the supply and demand. Since the default is 0 we don't need to define NetDemand for the transshipment nodes:

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 . for parameters where the defaults will suffice (e.g., Lower for Youngstown and Albany):

param:                  	Cost    Lower  	Upper:=
Youngstown	Albany		500	.	1000
Youngstown	Cincinnati	350	.	3000
Youngstown	'Kansas City'	450	1000	5000
Youngstown	Chicago		375	.	5000
Pittsburgh 	Cincinnati	350	.	2000
Pittsburgh	'Kansas City'	450	2000	3000
Pittsburgh	Chicago		400	.	4000
Pittsburgh	Gary 		450	.	2000
Cincinnati	Albany		350	1000	5000
Cincinnati	Houston		550	.	6000
'Kansas City'	Houston		375	.	4000
'Kansas City'	Tempe		650	.	4000
Chicago		Tempe		600	.	2000
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;
| |*FORM FIELD Results*|Results|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:

steel_solution.jpg

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 transshipment.mod we check that sum {n in NODES} NetDemand[n] <= 0 to ensure a problem is feasible before solving.

If total supply is less than demand (hence the problem is infeasible) we can add a dummy supply node (see with arcs to all the demand nodes. The optimal solution will show the "best" nodes to send the extra supply to. |

Changed:
<
<
|*FORM FIELD Conclusions*|Conclusions|In order to minimise the monthly shipment costs, American Steel should follow the shipment plan shown in Table 3.

Table 3 Optimal Shipment Plan

From/To Cincinnati Kansas City Chicago Albany Houston Tempe Gary
Youngstown 3000 3000 3000 1000      
Pittsburgh 2000 3000 3000       2000
Cincinnati       2000 3000    
Kansas City         4000 2000  
Chicago           2000 4000
>
>
|*FORM FIELD Conclusions*|Conclusions|In order to minimise the monthly shipment costs, American Steel should follow the shipment plan shown in Table 3.

Table 3 Optimal Shipment Plan

From/To Cincinnati Kansas City Chicago Albany Houston Tempe Gary
Youngstown 3000 3000 3000 1000      
Pittsburgh 2000 3000 3000       2000
Cincinnati       2000 3000    
Kansas City         4000 2000  
Chicago           2000 4000

As with many network problems, it can be illuminating to display the solution graphically as shown in Figure 1.

Figure 1 Optimal Shipment Plan |

 
FORM FIELD ExtraForExperts ExtraForExperts
|*FORM FIELD StudentTasks*|StudentTasks|
  1. Solve the American Steel Transshipment Problem. Write a management summary of your solution.

    What to hand in Hand in your management summary.

|
META FILEATTACHMENT attachment="steel_formulation.jpg" attr="h" comment="" date="1203066411" name="steel_formulation.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_formulation.jpg" size="30991" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_formulation.jpg" tmpFilename="" user="BaseUserMapping_333" version="1"
META FILEATTACHMENT attachment="steel_network.jpg" attr="h" comment="" date="1203066481" name="steel_network.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_network.jpg" size="25651" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_network.jpg" tmpFilename="" user="BaseUserMapping_333" version="1"
META FILEATTACHMENT attachment="steel_solution.jpg" attr="h" comment="" date="1209349430" name="steel_solution.jpg" path="steel_solution.jpg" size="75861" stream="steel_solution.jpg" tmpFilename="" user="BaseUserMapping_333" version="2"
Added:
>
>
META FILEATTACHMENT attachment="steel_graphical.jpg" attr="h" comment="" date="1209439527" name="steel_graphical.jpg" path="steel_graphical.jpg" size="128393" stream="steel_graphical.jpg" tmpFilename="" user="MichaelOSullivan" version="1"
 
META TOPICMOVED by="MichaelOSullivan" date="1204231417" from="OpsRes.ATransshipmentProblem" to="OpsRes.AmericanSteelTransshipmentProblem"

Revision 182008-04-29 - MichaelOSullivan

Line: 1 to 1
 
META TOPICPARENT name="SubmitCaseStudy"
<-- Under Construction -->
Line: 89 to 89
 |*FORM FIELD ProblemDescription*|ProblemDescription|American 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:

steel_network.jpg

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 cost per 1000 ton/month of shipping the steel. For example, the shipment from Youngstown to Kansas City is contracted out to a railroad company with a minimal shipping clause of 1000 tons/month. However, the railroad cannot ship more then 5000 tons/month due the shortage of rail cars.

Table 1 Arc Costs and Limits

From node To node Cost Minimum Maximum
Youngstown Albany 500 - 1000
Youngstown Cincinnati 350 - 3000
Youngstown Kansas City 450 1000 5000
Youngstown Chicago 375 - 5000
Pittsburgh Cincinnati 350 - 2000
Pittsburgh Kansas City 450 2000 3000
Pittsburgh Chicago 400 - 4000
Pittsburgh Gary 450 - 2000
Cincinnati Albany 350 1000 5000
Cincinnati Houston 550 - 6000
Kansas City Houston 375 - 4000
Kansas City Tempe 650 - 4000
Chicago Tempe 600 - 2000
Chicago Gary 120 - 4000

The current monthly demand at American Steel's four field warehouses is shown in Table 2.

Table 2 Monthly Demands

Field Warehouses Monthly Demand
Albany, N.Y. 3000
Houston 7000
Tempe 4000
Gary 6000

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.| |*FORM FIELD ProblemFormulation*|ProblemFormulation|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 repsectively. 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).

steel_formulation.jpg

| |*FORM FIELD ComputationalModel*|ComputationalModel|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 Kansas City must be enclosed in ' and ' because of the whitespace in the name.

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 ARCS:

set ARCS:   Cincinnati 'Kansas City' Chicago Albany Houston Tempe Gary :=
Youngstown         +          +         +      +       -      -    -
Pittsburgh         +          +         +      -       -      -    +
Cincinnati         -          -         -      +       +      -    -
'Kansas City'      -          -         -      -       +      +    -
Chicago            -          -         -      -       -      +    + ;

The NetDemand can be defined easily from the supply and demand. Since the default is 0 we don't need to define NetDemand for the transshipment nodes:

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 . for parameters where the defaults will suffice (e.g., Lower for Youngstown and Albany):

param:                  	Cost    Lower  	Upper:=
Youngstown	Albany		500	.	1000
Youngstown	Cincinnati	350	.	3000
Youngstown	'Kansas City'	450	1000	5000
Youngstown	Chicago		375	.	5000
Pittsburgh 	Cincinnati	350	.	2000
Pittsburgh	'Kansas City'	450	2000	3000
Pittsburgh	Chicago		400	.	4000
Pittsburgh	Gary 		450	.	2000
Cincinnati	Albany		350	1000	5000
Cincinnati	Houston		550	.	6000
'Kansas City'	Houston		375	.	4000
'Kansas City'	Tempe		650	.	4000
Chicago		Tempe		600	.	2000
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;
|
Changed:
<
<
|*FORM FIELD Results*|Results|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:

steel_solution.jpg

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 transshipment.mod we check that sum {n in NODES} NetDemand[n] <= 0 to ensure a problem is feasible before solving.

If total supply is less than demand (hence the problem is infeasible) we can add a dummy supply node (see with arcs to all the demand nodes. The optimal solution will show the "best" nodes to send the extra supply to. | |*FORM FIELD Conclusions*|Conclusions|In order to minimise the monthly shipment costs, American Steel should follow the shipment plan shown in Table 3.

Table 3 Optimal Shipment Plan

From/To Cincinnati Kansas City Chicago Albany Houston Tempe Gary
Youngstown 3000 3000 3000 1000      
Pittsburgh 2000 3000 3000       2000
Cincinnati       2000 3000    
Kansas City
Chicago
>
>
|*FORM FIELD Results*|Results|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:

steel_solution.jpg

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 transshipment.mod we check that sum {n in NODES} NetDemand[n] <= 0 to ensure a problem is feasible before solving.

If total supply is less than demand (hence the problem is infeasible) we can add a dummy supply node (see with arcs to all the demand nodes. The optimal solution will show the "best" nodes to send the extra supply to. | |*FORM FIELD Conclusions*|Conclusions|In order to minimise the monthly shipment costs, American Steel should follow the shipment plan shown in Table 3.

Table 3 Optimal Shipment Plan

From/To Cincinnati Kansas City Chicago Albany Houston Tempe Gary
Youngstown 3000 3000 3000 1000      
Pittsburgh 2000 3000 3000       2000
Cincinnati       2000 3000    
Kansas City         4000 2000  
Chicago           2000 4000
 
FORM FIELD ExtraForExperts ExtraForExperts
|*FORM FIELD StudentTasks*|StudentTasks|
  1. Solve the American Steel Transshipment Problem. Write a management summary of your solution.

    What to hand in Hand in your management summary.

|
META FILEATTACHMENT attachment="steel_formulation.jpg" attr="h" comment="" date="1203066411" name="steel_formulation.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_formulation.jpg" size="30991" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_formulation.jpg" tmpFilename="" user="BaseUserMapping_333" version="1"

Revision 172008-04-29 - MichaelOSullivan

Line: 1 to 1
 
META TOPICPARENT name="SubmitCaseStudy"
<-- Under Construction -->
Line: 90 to 90
 |*FORM FIELD ProblemFormulation*|ProblemFormulation|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 repsectively. 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).

steel_formulation.jpg

| |*FORM FIELD ComputationalModel*|ComputationalModel|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 Kansas City must be enclosed in ' and ' because of the whitespace in the name.

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 ARCS:

set ARCS:   Cincinnati 'Kansas City' Chicago Albany Houston Tempe Gary :=
Youngstown         +          +         +      +       -      -    -
Pittsburgh         +          +         +      -       -      -    +
Cincinnati         -          -         -      +       +      -    -
'Kansas City'      -          -         -      -       +      +    -
Chicago            -          -         -      -       -      +    + ;

The NetDemand can be defined easily from the supply and demand. Since the default is 0 we don't need to define NetDemand for the transshipment nodes:

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 . for parameters where the defaults will suffice (e.g., Lower for Youngstown and Albany):

param:                  	Cost    Lower  	Upper:=
Youngstown	Albany		500	.	1000
Youngstown	Cincinnati	350	.	3000
Youngstown	'Kansas City'	450	1000	5000
Youngstown	Chicago		375	.	5000
Pittsburgh 	Cincinnati	350	.	2000
Pittsburgh	'Kansas City'	450	2000	3000
Pittsburgh	Chicago		400	.	4000
Pittsburgh	Gary 		450	.	2000
Cincinnati	Albany		350	1000	5000
Cincinnati	Houston		550	.	6000
'Kansas City'	Houston		375	.	4000
'Kansas City'	Tempe		650	.	4000
Chicago		Tempe		600	.	2000
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;
| |*FORM FIELD Results*|Results|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:

steel_solution.jpg

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 transshipment.mod we check that sum {n in NODES} NetDemand[n] <= 0 to ensure a problem is feasible before solving.

If total supply is less than demand (hence the problem is infeasible) we can add a dummy supply node (see with arcs to all the demand nodes. The optimal solution will show the "best" nodes to send the extra supply to. |

Changed:
<
<
|*FORM FIELD Conclusions*|Conclusions|In order to minimise the monthly shipment costs, American Steel should follow the shipment plan shown in Table 3.

Table 3 Optimal Shipment Plan

From/To  
>
>
|*FORM FIELD Conclusions*|Conclusions|In order to minimise the monthly shipment costs, American Steel should follow the shipment plan shown in Table 3.

Table 3 Optimal Shipment Plan

From/To Cincinnati Kansas City Chicago Albany Houston Tempe Gary
Youngstown 3000 3000 3000 1000      
Pittsburgh 2000 3000 3000       2000
Cincinnati       2000 3000    
Kansas City
Chicago
 
FORM FIELD ExtraForExperts ExtraForExperts
|*FORM FIELD StudentTasks*|StudentTasks|
  1. Solve the American Steel Transshipment Problem. Write a management summary of your solution.

    What to hand in Hand in your management summary.

|
META FILEATTACHMENT attachment="steel_formulation.jpg" attr="h" comment="" date="1203066411" name="steel_formulation.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_formulation.jpg" size="30991" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_formulation.jpg" tmpFilename="" user="BaseUserMapping_333" version="1"

Revision 162008-04-28 - MichaelOSullivan

Line: 1 to 1
 
META TOPICPARENT name="SubmitCaseStudy"
<-- Under Construction -->
Line: 86 to 86
 
FORM FIELD CaseStudyType CaseStudyType TeachingCaseStudy
FORM FIELD OperationsResearchTopics OperationsResearchTopics LinearProgramming, IntegerProgramming, NetworkOptimisation, TransshipmentProblem
FORM FIELD ApplicationAreas ApplicationAreas Logistics
Changed:
<
<
|*FORM FIELD ProblemDescription*|ProblemDescription|American 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:

steel_network.jpg

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.

The table below presents the minimum and maximum flow amounts of steel that may be shipped between different cities along with the cost per 1000 ton/month of shipping the steel. For example, the shipment from Youngstown to Kansas City is contracted out to a railroad company with a minimal shipping clause of 1000 tons/month. However, the railroad cannot ship more then 5000 tons/month due the shortage of rail cars.

From node To node Cost Minimum Maximum
Youngstown Albany 500 - 1000
Youngstown Cincinnati 350 - 3000
Youngstown Kansas City 450 1000 5000
Youngstown Chicago 375 - 5000
Pittsburgh Cincinnati 350 - 2000
Pittsburgh Kansas City 450 2000 3000
Pittsburgh Chicago 400 - 4000
Pittsburgh Gary 450 - 2000
Cincinnati Albany 350 1000 5000
Cincinnati Houston 550 - 6000
Kansas City Houston 375 - 4000
Kansas City Tempe 650 - 4000
Chicago Tempe 600 - 2000
Chicago Gary 120 - 4000

The current monthly demand at American Steel's four field warehouses is as follows:

Field Warehouses Monthly Demand
Albany, N.Y. 3000
Houston 7000
Tempe 4000
Gary 6000

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.|

>
>
|*FORM FIELD ProblemDescription*|ProblemDescription|American 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:

steel_network.jpg

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 cost per 1000 ton/month of shipping the steel. For example, the shipment from Youngstown to Kansas City is contracted out to a railroad company with a minimal shipping clause of 1000 tons/month. However, the railroad cannot ship more then 5000 tons/month due the shortage of rail cars.

Table 1 Arc Costs and Limits

From node To node Cost Minimum Maximum
Youngstown Albany 500 - 1000
Youngstown Cincinnati 350 - 3000
Youngstown Kansas City 450 1000 5000
Youngstown Chicago 375 - 5000
Pittsburgh Cincinnati 350 - 2000
Pittsburgh Kansas City 450 2000 3000
Pittsburgh Chicago 400 - 4000
Pittsburgh Gary 450 - 2000
Cincinnati Albany 350 1000 5000
Cincinnati Houston 550 - 6000
Kansas City Houston 375 - 4000
Kansas City Tempe 650 - 4000
Chicago Tempe 600 - 2000
Chicago Gary 120 - 4000

The current monthly demand at American Steel's four field warehouses is shown in Table 2.

Table 2 Monthly Demands

Field Warehouses Monthly Demand
Albany, N.Y. 3000
Houston 7000
Tempe 4000
Gary 6000

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.|

 |*FORM FIELD ProblemFormulation*|ProblemFormulation|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 repsectively. 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).

steel_formulation.jpg

| |*FORM FIELD ComputationalModel*|ComputationalModel|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 Kansas City must be enclosed in ' and ' because of the whitespace in the name.

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 ARCS:

set ARCS:   Cincinnati 'Kansas City' Chicago Albany Houston Tempe Gary :=
Youngstown         +          +         +      +       -      -    -
Pittsburgh         +          +         +      -       -      -    +
Cincinnati         -          -         -      +       +      -    -
'Kansas City'      -          -         -      -       +      +    -
Chicago            -          -         -      -       -      +    + ;

The NetDemand can be defined easily from the supply and demand. Since the default is 0 we don't need to define NetDemand for the transshipment nodes:

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 . for parameters where the defaults will suffice (e.g., Lower for Youngstown and Albany):

param:                  	Cost    Lower  	Upper:=
Youngstown	Albany		500	.	1000
Youngstown	Cincinnati	350	.	3000
Youngstown	'Kansas City'	450	1000	5000
Youngstown	Chicago		375	.	5000
Pittsburgh 	Cincinnati	350	.	2000
Pittsburgh	'Kansas City'	450	2000	3000
Pittsburgh	Chicago		400	.	4000
Pittsburgh	Gary 		450	.	2000
Cincinnati	Albany		350	1000	5000
Cincinnati	Houston		550	.	6000
'Kansas City'	Houston		375	.	4000
'Kansas City'	Tempe		650	.	4000
Chicago		Tempe		600	.	2000
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;
|
Changed:
<
<
|*FORM FIELD Results*|Results|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:

steel_solution.jpg

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 transshipment.mod we check that sum {n in NODES} NetDemand[n] <= 0 to ensure a problem is feasible before solving.

If total supply is less than demand (hence the problem is infeasible) we can add a dummy supply node with arcs to all the demand nodes. ??? Up to here??? The optimal solution will show which nodes are "best" to get extra supply for to find the "best" nodes to t to get extrato see where we should , then the problem becomes infeasible! Even in the case of infeasibility, it is preferable to solve the transshipment problem using a dummy supply node so that we can analyse where there is a shortfall in demand. We can balance the problem by either adding a dummy supply node with arcs to all the demand nodes or adding a dummy demand node with arcs from all the supply nodes: balance_transshipment.mod

# The following parameters are needed to use balance_transshipment.run
param difference;
param dummyDemandCost {NODES};
param dummySupplyCost {NODES};
balance_transshipment.run
let difference := (sum {s in NODES} Supply[s])
                - (sum {d in NODES} Demand[d]);
             
let NODES := NODES union {'Dummy'};             
if difference > 0 then
{
  print "Total Supply > Total Demand";
  print "Solving with dummy supply node...";
  let Demand['Dummy'] := difference;
  for {n in NODES : Supply[n] > 0} {
    let ARCS := ARCS union {(n, 'Dummy')};
    let Cost[n, 'Dummy'] := dummyDemandCost[n];
  }
}
else if difference < 0 then
{
  print "WARNING: Total Supply < Total Demand, problem is infeasible!";
  print "Solving with dummy demand node...";
  let Demand['Dummy'] := - difference;
  for {n in NODES : Demand[n] > 0} {
    let ARCS := ARCS union {('Dummy', n)};
    let Cost['Dummy', n] := dummySupplyCost[n];
  }
}; # else the problem is balanced
steel.run
# steel.run
#
# Written by Mike O'Sullivan & Cameron Walker 2004
#
# This file contains a script for sensitivity analysis
# of the American Steel transshipment model.
#
# Last modified: 27/2/2004

reset;

model transshipment.mod;
model balance_transshipment.mod;

data steel.dat;

let {(m, n) in ARCS} Cost[m, n] := Cost[m, n] / 1000;

for {n in NODES} {
  let dummyDemandCost[n] := 0;
  let dummySupplyCost[n] := 0;  
}

include balance_transshipment.run;

option solver cplex;

solve;

display Flow;  
Note We also add a ???LINK??? check statement to our model file to ensure the problem is balanced:
check : sum {n in NODES} Supply[n] = sum {n in NODES} Demand[n];

Our solution now shows that there is 5000 ton of steel remaining at the Pittsburgh Mill, i.e., the flow from Pittsburgh to Dummy is 5000.

POST-OPTIMAL ANALYSIS

Validation For our solution to be valid we need it to be integer. Observing the Flow values shows that it is in fact integer. Moreover, no branch-and-bound nodes were required to make it integer. The transshipment problem is also naturally integer (like the transportation problem), so solving it as a linear programme will give integer solutions. In fact, any network flow problem with integer supplies, demands and arc capacities has naturally integer solutions.

Parametric Analysis If ???LINK??? sensitivity analysis shows that improvements to the objective function may be achieved by changing problem data, then we may use ???LINK??? parametric analysis to see the effect of these changes.

.
.
.
include balance_transshipment.run;

option presolve 0;
option solver cplex;
option cplex_options 'presolve 0 sensitivity';
solve;

display Flow;

display _varname, _var.down, _var.current, _var.up, _var.rc;
display _conname, _con.down, _con.current, _con.up, _con.dual;

steel_sensitivity.jpg

The sensitivity analysis shows that the solution is very sensitive to any changes in the constraint right-hand sides, with one exception ConserverFlow at Pittsburgh. However, we have variables on both sides of our constraints so we should expand our constraints to see what the right-hand side is:

steel_rhs.jpg

For the supply nodes the right-hand side is the negative of the supply, for the demand nodes the right-hand side is the demand and for the transshipment nodes the right-hand side is 0. Thus, any changes we make to the supply or demand at the nodes will affect our optimal solution. The only exception is that the right-hand side of the ConserveFlow['Pittsburgh'] can decrease without affecting our solution. Since Pittsburgh is a supply node (so the right-hand side is the negative of the supply) this means we can increase the supply at Pittsburgh without affecting our solution. This makes sense as Pittsburgh already has excess supply.

However, it seems like we can improve our objective the most by decreasing the demand at Tempe (the shadow price is 1.125), but the Allowable Minimum is such that we cannot discern what the change will be (the solution will change immediately). We can see the effect by using an ???LINK??? AMPL loop :

.
.
.
display TotalCost;

set CHANGES;
param Objective {CHANGES};

param OldDemand;

let OldDemand := Demand['Tempe'];

let CHANGES := {100..1000 by 100}; 
for {i in CHANGES} {
  
  let Demand['Tempe'] := OldDemand - i;
  display Demand['Tempe'];

  # Rebalance the problem  
  include balance_transshipment.run;
  
  solve;
  
  let Objective[i] := TotalCost;
}

steel_parametric.jpg

Note that we had to alter balance_transshipment.run to consider problems that have been balanced previously: balance_transshipment.run

let difference := (sum {s in NODES : s <> 'Dummy'} Supply[s])
                - (sum {d in NODES : d <> 'Dummy'} Demand[d]);
             
if 'Dummy' not in NODES then
  let NODES := NODES union {'Dummy'};
  
if difference > 0 then
{
  print "Total Supply > Total Demand";
  print "Solving with dummy supply node...";
  let Demand['Dummy'] := difference;
  for {n in NODES : Supply[n] > 0} {
    let ARCS := ARCS union {(n, 'Dummy')};
    let Cost[n, 'Dummy'] := dummyDemandCost[n];
  }
}
else if difference < 0 then
{
  print "WARNING: Total Supply < Total Demand, problem is infeasible!";
  print "Solving with dummy demand node...";
  let Demand['Dummy'] := - difference;
  for {n in NODES : Demand[n] > 0} {
    let ARCS := ARCS union {('Dummy', n)};
    let Cost['Dummy', n] := dummySupplyCost[n];
  }
}; # else the problem is balanced

The AMPL parametric analysis shows that, by decreasing the demand for steel at Tempe, we can get a consistent reduction in our objective function, even though this was not clear from our initial sensitivity analysis.

When we consider the sensitvity analysis for variable costs, we see that the only costs that affect our solution are the transportation costs from Pittsburgh and Youngstown to Chicago (all the other costs have Allowable Min and Allowable Max such that no "sensible" change would have any effect). Suppose American Steel are negotiating a new contract with the shipping company that takes their steel from Pittsburgh to Chicago. They estimate that they can get a reduction of around \$25/1000 ton of steel (taking the price from \$400/1000 ton to \$375/1000 ton), but want to know if they should negotiate for a lower price. The sensitivity analysis shows that below \$375/1000 ton the solution will change, so let's use parametric analysis to see what happens:

.
.
.
display TotalCost;

set CHANGES;
param Objective {CHANGES};

param OldCost;

let OldCost := Cost['Pittsburgh', 'Chicago'];

let CHANGES := {0..0.05 by 0.005}; 
for {i in CHANGES} {
  
  let Cost['Pittsburgh', 'Chicago'] := OldCost - i;
  display Cost['Pittsburgh', 'Chicago'];

  # Rebalance the problem  
  include balance_transshipment.run;
  
  solve;
  
  let Objective[i] := TotalCost;
}

The parametric analysis shows that the objective function decreases at a greater rate if the price drops below $375/1000 ton, so American Steel should try and negotiate the price down even further.

steel_cost_parametric.jpg| |*FORM FIELD Conclusions*|Conclusions|There is quite a bit of information to summarise and many ways to present it. Some suggestions include:

  1. Summarise the problem as usual and list the shipments that American Steel should make (similar to the transportation problem);
  2. Summarise the problem as usual and present a table of shipments that American Steel should make;
  3. Draw the network formulation for the problem (being sure to specify what the labels mean). Then draw the actual solution on top of the network formulation. You could colour code flows long arcs to show if they are at their bounds.

Implementation and Ongoing Monitoring

Given that the solution is very sensitive to the supply and demand amounts, careful consideration of the accuracy of these figures is important. Making sure that the bounds on the arcs are reliable is another concern.

Ongoing monitoring of the supply, demand and bounds will help American Steel to keep making good decisions. As shown in the parametric analysis, ongoing negotiation of transportation prices along important routes will help American Steel reduce their expenditure.|

>
>
|*FORM FIELD Results*|Results|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:

steel_solution.jpg

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 transshipment.mod we check that sum {n in NODES} NetDemand[n] <= 0 to ensure a problem is feasible before solving.

If total supply is less than demand (hence the problem is infeasible) we can add a dummy supply node (see with arcs to all the demand nodes. The optimal solution will show the "best" nodes to send the extra supply to. | |*FORM FIELD Conclusions*|Conclusions|In order to minimise the monthly shipment costs, American Steel should follow the shipment plan shown in Table 3.

Table 3 Optimal Shipment Plan

From/To  
 
FORM FIELD ExtraForExperts ExtraForExperts
|*FORM FIELD StudentTasks*|StudentTasks|
  1. Solve the American Steel Transshipment Problem. Write a management summary of your solution.

    What to hand in Hand in your management summary.

|
META FILEATTACHMENT attachment="steel_formulation.jpg" attr="h" comment="" date="1203066411" name="steel_formulation.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_formulation.jpg" size="30991" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_formulation.jpg" tmpFilename="" user="BaseUserMapping_333" version="1"

Revision 152008-04-28 - MichaelOSullivan

Line: 1 to 1
 
META TOPICPARENT name="SubmitCaseStudy"
<-- Under Construction -->
Line: 89 to 89
 |*FORM FIELD ProblemDescription*|ProblemDescription|American 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:

steel_network.jpg

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.

The table below presents the minimum and maximum flow amounts of steel that may be shipped between different cities along with the cost per 1000 ton/month of shipping the steel. For example, the shipment from Youngstown to Kansas City is contracted out to a railroad company with a minimal shipping clause of 1000 tons/month. However, the railroad cannot ship more then 5000 tons/month due the shortage of rail cars.

From node To node Cost Minimum Maximum
Youngstown Albany 500 - 1000
Youngstown Cincinnati 350 - 3000
Youngstown Kansas City 450 1000 5000
Youngstown Chicago 375 - 5000
Pittsburgh Cincinnati 350 - 2000
Pittsburgh Kansas City 450 2000 3000
Pittsburgh Chicago 400 - 4000
Pittsburgh Gary 450 - 2000
Cincinnati Albany 350 1000 5000
Cincinnati Houston 550 - 6000
Kansas City Houston 375 - 4000
Kansas City Tempe 650 - 4000
Chicago Tempe 600 - 2000
Chicago Gary 120 - 4000

The current monthly demand at American Steel's four field warehouses is as follows:

Field Warehouses Monthly Demand
Albany, N.Y. 3000
Houston 7000
Tempe 4000
Gary 6000

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.| |*FORM FIELD ProblemFormulation*|ProblemFormulation|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 repsectively. 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).

steel_formulation.jpg

| |*FORM FIELD ComputationalModel*|ComputationalModel|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 Kansas City must be enclosed in ' and ' because of the whitespace in the name.

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 ARCS:

set ARCS:   Cincinnati 'Kansas City' Chicago Albany Houston Tempe Gary :=
Youngstown         +          +         +      +       -      -    -
Pittsburgh         +          +         +      -       -      -    +
Cincinnati         -          -         -      +       +      -    -
'Kansas City'      -          -         -      -       +      +    -
Chicago            -          -         -      -       -      +    + ;

The NetDemand can be defined easily from the supply and demand. Since the default is 0 we don't need to define NetDemand for the transshipment nodes:

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 . for parameters where the defaults will suffice (e.g., Lower for Youngstown and Albany):

param:                  	Cost    Lower  	Upper:=
Youngstown	Albany		500	.	1000
Youngstown	Cincinnati	350	.	3000
Youngstown	'Kansas City'	450	1000	5000
Youngstown	Chicago		375	.	5000
Pittsburgh 	Cincinnati	350	.	2000
Pittsburgh	'Kansas City'	450	2000	3000
Pittsburgh	Chicago		400	.	4000
Pittsburgh	Gary 		450	.	2000
Cincinnati	Albany		350	1000	5000
Cincinnati	Houston		550	.	6000
'Kansas City'	Houston		375	.	4000
'Kansas City'	Tempe		650	.	4000
Chicago		Tempe		600	.	2000
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;
|
Changed:
<
<
|*FORM FIELD Results*|Results|Implementing the usual script file with transshipment.mod and steel.dat (with the Cost modification) gives us the optimal Flow variables:

steel_solution.jpg

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). If total supply is less than demand, then the problem becomes infeasible! Even in the case of infeasibility, it is preferable to solve the transshipment problem using a dummy supply node so that we can analyse where there is a shortfall in demand. We can balance the problem by either adding a dummy supply node with arcs to all the demand nodes or adding a dummy demand node with arcs from all the supply nodes: balance_transshipment.mod

# The following parameters are needed to use balance_transshipment.run
param difference;
param dummyDemandCost {NODES};
param dummySupplyCost {NODES};
balance_transshipment.run
let difference := (sum {s in NODES} Supply[s])
                - (sum {d in NODES} Demand[d]);
             
let NODES := NODES union {'Dummy'};             
if difference > 0 then
{
  print "Total Supply > Total Demand";
  print "Solving with dummy supply node...";
  let Demand['Dummy'] := difference;
  for {n in NODES : Supply[n] > 0} {
    let ARCS := ARCS union {(n, 'Dummy')};
    let Cost[n, 'Dummy'] := dummyDemandCost[n];
  }
}
else if difference < 0 then
{
  print "WARNING: Total Supply < Total Demand, problem is infeasible!";
  print "Solving with dummy demand node...";
  let Demand['Dummy'] := - difference;
  for {n in NODES : Demand[n] > 0} {
    let ARCS := ARCS union {('Dummy', n)};
    let Cost['Dummy', n] := dummySupplyCost[n];
  }
}; # else the problem is balanced
steel.run
# steel.run
#
# Written by Mike O'Sullivan & Cameron Walker 2004
#
# This file contains a script for sensitivity analysis
# of the American Steel transshipment model.
#
# Last modified: 27/2/2004

reset;

model transshipment.mod;
model balance_transshipment.mod;

data steel.dat;

let {(m, n) in ARCS} Cost[m, n] := Cost[m, n] / 1000;

for {n in NODES} {
  let dummyDemandCost[n] := 0;
  let dummySupplyCost[n] := 0;  
}

include balance_transshipment.run;

option solver cplex;

solve;

display Flow;  
Note We also add a ???LINK??? check statement to our model file to ensure the problem is balanced:
check : sum {n in NODES} Supply[n] = sum {n in NODES} Demand[n];

Our solution now shows that there is 5000 ton of steel remaining at the Pittsburgh Mill, i.e., the flow from Pittsburgh to Dummy is 5000.

POST-OPTIMAL ANALYSIS

Validation For our solution to be valid we need it to be integer. Observing the Flow values shows that it is in fact integer. Moreover, no branch-and-bound nodes were required to make it integer. The transshipment problem is also naturally integer (like the transportation problem), so solving it as a linear programme will give integer solutions. In fact, any network flow problem with integer supplies, demands and arc capacities has naturally integer solutions.

Parametric Analysis If ???LINK??? sensitivity analysis shows that improvements to the objective function may be achieved by changing problem data, then we may use ???LINK??? parametric analysis to see the effect of these changes.

.
.
.
include balance_transshipment.run;

option presolve 0;
option solver cplex;
option cplex_options 'presolve 0 sensitivity';
solve;

display Flow;

display _varname, _var.down, _var.current, _var.up, _var.rc;
display _conname, _con.down, _con.current, _con.up, _con.dual;

steel_sensitivity.jpg

The sensitivity analysis shows that the solution is very sensitive to any changes in the constraint right-hand sides, with one exception ConserverFlow at Pittsburgh. However, we have variables on both sides of our constraints so we should expand our constraints to see what the right-hand side is:

steel_rhs.jpg

For the supply nodes the right-hand side is the negative of the supply, for the demand nodes the right-hand side is the demand and for the transshipment nodes the right-hand side is 0. Thus, any changes we make to the supply or demand at the nodes will affect our optimal solution. The only exception is that the right-hand side of the ConserveFlow['Pittsburgh'] can decrease without affecting our solution. Since Pittsburgh is a supply node (so the right-hand side is the negative of the supply) this means we can increase the supply at Pittsburgh without affecting our solution. This makes sense as Pittsburgh already has excess supply.

However, it seems like we can improve our objective the most by decreasing the demand at Tempe (the shadow price is 1.125), but the Allowable Minimum is such that we cannot discern what the change will be (the solution will change immediately). We can see the effect by using an ???LINK??? AMPL loop :

.
.
.
display TotalCost;

set CHANGES;
param Objective {CHANGES};

param OldDemand;

let OldDemand := Demand['Tempe'];

let CHANGES := {100..1000 by 100}; 
for {i in CHANGES} {
  
  let Demand['Tempe'] := OldDemand - i;
  display Demand['Tempe'];

  # Rebalance the problem  
  include balance_transshipment.run;
  
  solve;
  
  let Objective[i] := TotalCost;
}

steel_parametric.jpg

Note that we had to alter balance_transshipment.run to consider problems that have been balanced previously: balance_transshipment.run

let difference := (sum {s in NODES : s <> 'Dummy'} Supply[s])
                - (sum {d in NODES : d <> 'Dummy'} Demand[d]);
             
if 'Dummy' not in NODES then
  let NODES := NODES union {'Dummy'};
  
if difference > 0 then
{
  print "Total Supply > Total Demand";
  print "Solving with dummy supply node...";
  let Demand['Dummy'] := difference;
  for {n in NODES : Supply[n] > 0} {
    let ARCS := ARCS union {(n, 'Dummy')};
    let Cost[n, 'Dummy'] := dummyDemandCost[n];
  }
}
else if difference < 0 then
{
  print "WARNING: Total Supply < Total Demand, problem is infeasible!";
  print "Solving with dummy demand node...";
  let Demand['Dummy'] := - difference;
  for {n in NODES : Demand[n] > 0} {
    let ARCS := ARCS union {('Dummy', n)};
    let Cost['Dummy', n] := dummySupplyCost[n];
  }
}; # else the problem is balanced

The AMPL parametric analysis shows that, by decreasing the demand for steel at Tempe, we can get a consistent reduction in our objective function, even though this was not clear from our initial sensitivity analysis.

When we consider the sensitvity analysis for variable costs, we see that the only costs that affect our solution are the transportation costs from Pittsburgh and Youngstown to Chicago (all the other costs have Allowable Min and Allowable Max such that no "sensible" change would have any effect). Suppose American Steel are negotiating a new contract with the shipping company that takes their steel from Pittsburgh to Chicago. They estimate that they can get a reduction of around \$25/1000 ton of steel (taking the price from \$400/1000 ton to \$375/1000 ton), but want to know if they should negotiate for a lower price. The sensitivity analysis shows that below \$375/1000 ton the solution will change, so let's use parametric analysis to see what happens:

.
.
.
display TotalCost;

set CHANGES;
param Objective {CHANGES};

param OldCost;

let OldCost := Cost['Pittsburgh', 'Chicago'];

let CHANGES := {0..0.05 by 0.005}; 
for {i in CHANGES} {
  
  let Cost['Pittsburgh', 'Chicago'] := OldCost - i;
  display Cost['Pittsburgh', 'Chicago'];

  # Rebalance the problem  
  include balance_transshipment.run;
  
  solve;
  
  let Objective[i] := TotalCost;
}

The parametric analysis shows that the objective function decreases at a greater rate if the price drops below $375/1000 ton, so American Steel should try and negotiate the price down even further.

steel_cost_parametric.jpg|

>
>
|*FORM FIELD Results*|Results|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:

steel_solution.jpg

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 transshipment.mod we check that sum {n in NODES} NetDemand[n] <= 0 to ensure a problem is feasible before solving.

If total supply is less than demand (hence the problem is infeasible) we can add a dummy supply node with arcs to all the demand nodes. ??? Up to here??? The optimal solution will show which nodes are "best" to get extra supply for to find the "best" nodes to t to get extrato see where we should , then the problem becomes infeasible! Even in the case of infeasibility, it is preferable to solve the transshipment problem using a dummy supply node so that we can analyse where there is a shortfall in demand. We can balance the problem by either adding a dummy supply node with arcs to all the demand nodes or adding a dummy demand node with arcs from all the supply nodes: balance_transshipment.mod

# The following parameters are needed to use balance_transshipment.run
param difference;
param dummyDemandCost {NODES};
param dummySupplyCost {NODES};
balance_transshipment.run
let difference := (sum {s in NODES} Supply[s])
                - (sum {d in NODES} Demand[d]);
             
let NODES := NODES union {'Dummy'};             
if difference > 0 then
{
  print "Total Supply > Total Demand";
  print "Solving with dummy supply node...";
  let Demand['Dummy'] := difference;
  for {n in NODES : Supply[n] > 0} {
    let ARCS := ARCS union {(n, 'Dummy')};
    let Cost[n, 'Dummy'] := dummyDemandCost[n];
  }
}
else if difference < 0 then
{
  print "WARNING: Total Supply < Total Demand, problem is infeasible!";
  print "Solving with dummy demand node...";
  let Demand['Dummy'] := - difference;
  for {n in NODES : Demand[n] > 0} {
    let ARCS := ARCS union {('Dummy', n)};
    let Cost['Dummy', n] := dummySupplyCost[n];
  }
}; # else the problem is balanced
steel.run
# steel.run
#
# Written by Mike O'Sullivan & Cameron Walker 2004
#
# This file contains a script for sensitivity analysis
# of the American Steel transshipment model.
#
# Last modified: 27/2/2004

reset;

model transshipment.mod;
model balance_transshipment.mod;

data steel.dat;

let {(m, n) in ARCS} Cost[m, n] := Cost[m, n] / 1000;

for {n in NODES} {
  let dummyDemandCost[n] := 0;
  let dummySupplyCost[n] := 0;  
}

include balance_transshipment.run;

option solver cplex;

solve;

display Flow;  
Note We also add a ???LINK??? check statement to our model file to ensure the problem is balanced:
check : sum {n in NODES} Supply[n] = sum {n in NODES} Demand[n];

Our solution now shows that there is 5000 ton of steel remaining at the Pittsburgh Mill, i.e., the flow from Pittsburgh to Dummy is 5000.

POST-OPTIMAL ANALYSIS

Validation For our solution to be valid we need it to be integer. Observing the Flow values shows that it is in fact integer. Moreover, no branch-and-bound nodes were required to make it integer. The transshipment problem is also naturally integer (like the transportation problem), so solving it as a linear programme will give integer solutions. In fact, any network flow problem with integer supplies, demands and arc capacities has naturally integer solutions.

Parametric Analysis If ???LINK??? sensitivity analysis shows that improvements to the objective function may be achieved by changing problem data, then we may use ???LINK??? parametric analysis to see the effect of these changes.

.
.
.
include balance_transshipment.run;

option presolve 0;
option solver cplex;
option cplex_options 'presolve 0 sensitivity';
solve;

display Flow;

display _varname, _var.down, _var.current, _var.up, _var.rc;
display _conname, _con.down, _con.current, _con.up, _con.dual;

steel_sensitivity.jpg

The sensitivity analysis shows that the solution is very sensitive to any changes in the constraint right-hand sides, with one exception ConserverFlow at Pittsburgh. However, we have variables on both sides of our constraints so we should expand our constraints to see what the right-hand side is:

steel_rhs.jpg

For the supply nodes the right-hand side is the negative of the supply, for the demand nodes the right-hand side is the demand and for the transshipment nodes the right-hand side is 0. Thus, any changes we make to the supply or demand at the nodes will affect our optimal solution. The only exception is that the right-hand side of the ConserveFlow['Pittsburgh'] can decrease without affecting our solution. Since Pittsburgh is a supply node (so the right-hand side is the negative of the supply) this means we can increase the supply at Pittsburgh without affecting our solution. This makes sense as Pittsburgh already has excess supply.

However, it seems like we can improve our objective the most by decreasing the demand at Tempe (the shadow price is 1.125), but the Allowable Minimum is such that we cannot discern what the change will be (the solution will change immediately). We can see the effect by using an ???LINK??? AMPL loop :

.
.
.
display TotalCost;

set CHANGES;
param Objective {CHANGES};

param OldDemand;

let OldDemand := Demand['Tempe'];

let CHANGES := {100..1000 by 100}; 
for {i in CHANGES} {
  
  let Demand['Tempe'] := OldDemand - i;
  display Demand['Tempe'];

  # Rebalance the problem  
  include balance_transshipment.run;
  
  solve;
  
  let Objective[i] := TotalCost;
}

steel_parametric.jpg

Note that we had to alter balance_transshipment.run to consider problems that have been balanced previously: balance_transshipment.run

let difference := (sum {s in NODES : s <> 'Dummy'} Supply[s])
                - (sum {d in NODES : d <> 'Dummy'} Demand[d]);
             
if 'Dummy' not in NODES then
  let NODES := NODES union {'Dummy'};
  
if difference > 0 then
{
  print "Total Supply > Total Demand";
  print "Solving with dummy supply node...";
  let Demand['Dummy'] := difference;
  for {n in NODES : Supply[n] > 0} {
    let ARCS := ARCS union {(n, 'Dummy')};
    let Cost[n, 'Dummy'] := dummyDemandCost[n];
  }
}
else if difference < 0 then
{
  print "WARNING: Total Supply < Total Demand, problem is infeasible!";
  print "Solving with dummy demand node...";
  let Demand['Dummy'] := - difference;
  for {n in NODES : Demand[n] > 0} {
    let ARCS := ARCS union {('Dummy', n)};
    let Cost['Dummy', n] := dummySupplyCost[n];
  }
}; # else the problem is balanced

The AMPL parametric analysis shows that, by decreasing the demand for steel at Tempe, we can get a consistent reduction in our objective function, even though this was not clear from our initial sensitivity analysis.

When we consider the sensitvity analysis for variable costs, we see that the only costs that affect our solution are the transportation costs from Pittsburgh and Youngstown to Chicago (all the other costs have Allowable Min and Allowable Max such that no "sensible" change would have any effect). Suppose American Steel are negotiating a new contract with the shipping company that takes their steel from Pittsburgh to Chicago. They estimate that they can get a reduction of around \$25/1000 ton of steel (taking the price from \$400/1000 ton to \$375/1000 ton), but want to know if they should negotiate for a lower price. The sensitivity analysis shows that below \$375/1000 ton the solution will change, so let's use parametric analysis to see what happens:

.
.
.
display TotalCost;

set CHANGES;
param Objective {CHANGES};

param OldCost;

let OldCost := Cost['Pittsburgh', 'Chicago'];

let CHANGES := {0..0.05 by 0.005}; 
for {i in CHANGES} {
  
  let Cost['Pittsburgh', 'Chicago'] := OldCost - i;
  display Cost['Pittsburgh', 'Chicago'];

  # Rebalance the problem  
  include balance_transshipment.run;
  
  solve;
  
  let Objective[i] := TotalCost;
}

The parametric analysis shows that the objective function decreases at a greater rate if the price drops below $375/1000 ton, so American Steel should try and negotiate the price down even further.

steel_cost_parametric.jpg|

 |*FORM FIELD Conclusions*|Conclusions|There is quite a bit of information to summarise and many ways to present it. Some suggestions include:
  1. Summarise the problem as usual and list the shipments that American Steel should make (similar to the transportation problem);
  2. Summarise the problem as usual and present a table of shipments that American Steel should make;
  3. Draw the network formulation for the problem (being sure to specify what the labels mean). Then draw the actual solution on top of the network formulation. You could colour code flows long arcs to show if they are at their bounds.

Implementation and Ongoing Monitoring

Given that the solution is very sensitive to the supply and demand amounts, careful consideration of the accuracy of these figures is important. Making sure that the bounds on the arcs are reliable is another concern.

Ongoing monitoring of the supply, demand and bounds will help American Steel to keep making good decisions. As shown in the parametric analysis, ongoing negotiation of transportation prices along important routes will help American Steel reduce their expenditure.|

Changed:
<
<
|*FORM FIELD ExtraForExperts*|ExtraForExperts|Another common network flow problem that uses almost the same model as transshipment is the maximum flow problem. The objective of this problem is to maximise flow through the network. The only changes to transshipment.mod are:
  1. A new variable FlowOut is introduced at each node;
  2. FlowOut has lower and upper bounds, often the upper bound is set to as the Demand at the nodes;
  3. FlowOut replaces Demand in the ConserveFlow constraints;
  4. The ConserveFlow constraint becomes an equality constraint as all flow must be accounted for (no storage at the nodes);
  5. Cost of transshipment is ignored;
  6. The objective is to maximise the total flow out of the network sum {n in NODES} FlowOut[n];
  7. The problem no longer needs to be balanced.

Maxflow.mod ???ATTACH MAXFLOW.MOD HERE???

If we set MaxOut to Demand for all nodes:

let {n in NODES} MaxOut[n] := Demand[n];
then we see that currently all the demands are being met via the American Steel distribution network (the total flow out = the total demand):

steel_maxflow_solution.jpg| |*FORM FIELD StudentTasks*|StudentTasks| 1 Solve The American Steel Problem. Write a management summary of your solution.

What to hand in Hand in your management summary.

EXTRA FOR EXPERTS' TASKS

  1. American Steel are planning a marketing campaign to increase demand in their four markets Albany, Tempe, Houston and Gary. However, they would like to know the maximum demand their distribution network can handle (in each market) before they proceed. Write a script file that uses maxflow.mod and steel.dat to find the maximum demand they can supply in each market.

What to hand in Hand in your script file and a management summary of your solution.|

>
>
FORM FIELD ExtraForExperts ExtraForExperts
|*FORM FIELD StudentTasks*|StudentTasks|
  1. Solve the American Steel Transshipment Problem. Write a management summary of your solution.

    What to hand in Hand in your management summary.

|
 
META FILEATTACHMENT attachment="steel_formulation.jpg" attr="h" comment="" date="1203066411" name="steel_formulation.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_formulation.jpg" size="30991" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_formulation.jpg" tmpFilename="" user="BaseUserMapping_333" version="1"
META FILEATTACHMENT attachment="steel_network.jpg" attr="h" comment="" date="1203066481" name="steel_network.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_network.jpg" size="25651" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_network.jpg" tmpFilename="" user="BaseUserMapping_333" version="1"
META FILEATTACHMENT attachment="steel_solution.jpg" attr="h" comment="" date="1209349430" name="steel_solution.jpg" path="steel_solution.jpg" size="75861" stream="steel_solution.jpg" tmpFilename="" user="BaseUserMapping_333" version="2"

Revision 142008-04-28 - TWikiAdminUser

Line: 1 to 1
 
META TOPICPARENT name="SubmitCaseStudy"
<-- Under Construction -->
Line: 93 to 93
 |*FORM FIELD Conclusions*|Conclusions|There is quite a bit of information to summarise and many ways to present it. Some suggestions include:
  1. Summarise the problem as usual and list the shipments that American Steel should make (similar to the transportation problem);
  2. Summarise the problem as usual and present a table of shipments that American Steel should make;
  3. Draw the network formulation for the problem (being sure to specify what the labels mean). Then draw the actual solution on top of the network formulation. You could colour code flows long arcs to show if they are at their bounds.

Implementation and Ongoing Monitoring

Given that the solution is very sensitive to the supply and demand amounts, careful consideration of the accuracy of these figures is important. Making sure that the bounds on the arcs are reliable is another concern.

Ongoing monitoring of the supply, demand and bounds will help American Steel to keep making good decisions. As shown in the parametric analysis, ongoing negotiation of transportation prices along important routes will help American Steel reduce their expenditure.| |*FORM FIELD ExtraForExperts*|ExtraForExperts|Another common network flow problem that uses almost the same model as transshipment is the maximum flow problem. The objective of this problem is to maximise flow through the network. The only changes to transshipment.mod are:

  1. A new variable FlowOut is introduced at each node;
  2. FlowOut has lower and upper bounds, often the upper bound is set to as the Demand at the nodes;
  3. FlowOut replaces Demand in the ConserveFlow constraints;
  4. The ConserveFlow constraint becomes an equality constraint as all flow must be accounted for (no storage at the nodes);
  5. Cost of transshipment is ignored;
  6. The objective is to maximise the total flow out of the network sum {n in NODES} FlowOut[n];
  7. The problem no longer needs to be balanced.

Maxflow.mod ???ATTACH MAXFLOW.MOD HERE???

If we set MaxOut to Demand for all nodes:

let {n in NODES} MaxOut[n] := Demand[n];
then we see that currently all the demands are being met via the American Steel distribution network (the total flow out = the total demand):

steel_maxflow_solution.jpg| |*FORM FIELD StudentTasks*|StudentTasks| 1 Solve The American Steel Problem. Write a management summary of your solution.

What to hand in Hand in your management summary.

EXTRA FOR EXPERTS' TASKS

  1. American Steel are planning a marketing campaign to increase demand in their four markets Albany, Tempe, Houston and Gary. However, they would like to know the maximum demand their distribution network can handle (in each market) before they proceed. Write a script file that uses maxflow.mod and steel.dat to find the maximum demand they can supply in each market.

What to hand in Hand in your script file and a management summary of your solution.|

Changed:
<
<
META FILEATTACHMENT attachment="conserve_flow.jpg" attr="" comment="" date="1203066350" name="conserve_flow.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\conserve_flow.jpg" size="119214" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\conserve_flow.jpg" tmpFilename="" user="BaseUserMapping_333" version="1"
META FILEATTACHMENT attachment="steel_cost_parametric.jpg" attr="" comment="" date="1203066378" name="steel_cost_parametric.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_cost_parametric.jpg" size="21242" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_cost_parametric.jpg" tmpFilename="" user="BaseUserMapping_333" version="1"
META FILEATTACHMENT attachment="steel_formulation.jpg" attr="" comment="" date="1203066411" name="steel_formulation.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_formulation.jpg" size="30991" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_formulation.jpg" tmpFilename="" user="BaseUserMapping_333" version="1"
META FILEATTACHMENT attachment="steel_maxflow_solution.jpg" attr="" comment="" date="1203066451" name="steel_maxflow_solution.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_maxflow_solution.jpg" size="40059" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_maxflow_solution.jpg" tmpFilename="" user="BaseUserMapping_333" version="1"
META FILEATTACHMENT attachment="steel_network.jpg" attr="" comment="" date="1203066481" name="steel_network.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_network.jpg" size="25651" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_network.jpg" tmpFilename="" user="BaseUserMapping_333" version="1"
META FILEATTACHMENT attachment="steel_parametric.jpg" attr="" comment="" date="1203066537" name="steel_parametric.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_parametric.jpg" size="69672" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_parametric.jpg" tmpFilename="" user="BaseUserMapping_333" version="1"
META FILEATTACHMENT attachment="steel_rhs.jpg" attr="" comment="" date="1203066590" name="steel_rhs.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_rhs.jpg" size="93278" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_rhs.jpg" tmpFilename="" user="BaseUserMapping_333" version="1"
META FILEATTACHMENT attachment="steel_sensitivity.jpg" attr="" comment="" date="1203066683" name="steel_sensitivity.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_sensitivity.jpg" size="93137" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_sensitivity.jpg" tmpFilename="" user="BaseUserMapping_333" version="1"
META FILEATTACHMENT attachment="steel_solution.jpg" attr="" comment="" date="1203066761" name="steel_solution.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_solution.jpg" size="38501" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_solution.jpg" tmpFilename="" user="BaseUserMapping_333" version="1"
>
>
META FILEATTACHMENT attachment="steel_formulation.jpg" attr="h" comment="" date="1203066411" name="steel_formulation.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_formulation.jpg" size="30991" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_formulation.jpg" tmpFilename="" user="BaseUserMapping_333" version="1"
META FILEATTACHMENT attachment="steel_network.jpg" attr="h" comment="" date="1203066481" name="steel_network.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_network.jpg" size="25651" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_network.jpg" tmpFilename="" user="BaseUserMapping_333" version="1"
META FILEATTACHMENT attachment="steel_solution.jpg" attr="h" comment="" date="1209349430" name="steel_solution.jpg" path="steel_solution.jpg" size="75861" stream="steel_solution.jpg" tmpFilename="" user="BaseUserMapping_333" version="2"
 
META TOPICMOVED by="MichaelOSullivan" date="1204231417" from="OpsRes.ATransshipmentProblem" to="OpsRes.AmericanSteelTransshipmentProblem"

Revision 132008-04-28 - MichaelOSullivan

Line: 1 to 1
 
META TOPICPARENT name="SubmitCaseStudy"
<-- Under Construction -->
Line: 88 to 88
 
FORM FIELD ApplicationAreas ApplicationAreas Logistics
|*FORM FIELD ProblemDescription*|ProblemDescription|American 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:

steel_network.jpg

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.

The table below presents the minimum and maximum flow amounts of steel that may be shipped between different cities along with the cost per 1000 ton/month of shipping the steel. For example, the shipment from Youngstown to Kansas City is contracted out to a railroad company with a minimal shipping clause of 1000 tons/month. However, the railroad cannot ship more then 5000 tons/month due the shortage of rail cars.

From node To node Cost Minimum Maximum
Youngstown Albany 500 - 1000
Youngstown Cincinnati 350 - 3000
Youngstown Kansas City 450 1000 5000
Youngstown Chicago 375 - 5000
Pittsburgh Cincinnati 350 - 2000
Pittsburgh Kansas City 450 2000 3000
Pittsburgh Chicago 400 - 4000
Pittsburgh Gary 450 - 2000
Cincinnati Albany 350 1000 5000
Cincinnati Houston 550 - 6000
Kansas City Houston 375 - 4000
Kansas City Tempe 650 - 4000
Chicago Tempe 600 - 2000
Chicago Gary 120 - 4000

The current monthly demand at American Steel's four field warehouses is as follows:

Field Warehouses Monthly Demand
Albany, N.Y. 3000
Houston 7000
Tempe 4000
Gary 6000

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.| |*FORM FIELD ProblemFormulation*|ProblemFormulation|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 repsectively. 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).

steel_formulation.jpg

|

Changed:
<
<
|*FORM FIELD ComputationalModel*|ComputationalModel|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 Kansas City must be enclosed in ' and ' because of the whitespace in the name.

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 ARCS:

set ARCS:   Cincinnati 'Kansas City' Chicago Albany Houston Tempe Gary :=
Youngstown         +          +         +      +       -      -    -
Pittsburgh         +          +         +      -       -      -    +
Cincinnati         -          -         -      +       +      -    -
'Kansas City'      -          -         -      -       +      +    -
Chicago            -          -         -      -       -      +    + ;

The NetDemand can be defined easily from the supply and demand. Since the default is 0 we don't need to define NetDemand for the transshipment nodes:

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 . for parameters where the defaults will suffice (e.g., Lower for Youngstown and Albany):

param:                  	Cost    Lower  	Upper:=
Youngstown	Albany		500	.	1000
Youngstown	Cincinnati	350	.	3000
Youngstown	'Kansas City'	450	1000	5000
Youngstown	Chicago		375	.	5000
Pittsburgh 	Cincinnati	350	.	2000
Pittsburgh	'Kansas City'	450	2000	3000
Pittsburgh	Chicago		400	.	4000
Pittsburgh	Gary 		450	.	2000
Cincinnati	Albany		350	1000	5000
Cincinnati	Houston		550	.	6000
'Kansas City'	Houston		375	.	4000
'Kansas City'	Tempe		650	.	4000
Chicago		Tempe		600	.	2000
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;
|
>
>
|*FORM FIELD ComputationalModel*|ComputationalModel|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 Kansas City must be enclosed in ' and ' because of the whitespace in the name.

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 ARCS:

set ARCS:   Cincinnati 'Kansas City' Chicago Albany Houston Tempe Gary :=
Youngstown         +          +         +      +       -      -    -
Pittsburgh         +          +         +      -       -      -    +
Cincinnati         -          -         -      +       +      -    -
'Kansas City'      -          -         -      -       +      +    -
Chicago            -          -         -      -       -      +    + ;

The NetDemand can be defined easily from the supply and demand. Since the default is 0 we don't need to define NetDemand for the transshipment nodes:

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 . for parameters where the defaults will suffice (e.g., Lower for Youngstown and Albany):

param:                  	Cost    Lower  	Upper:=
Youngstown	Albany		500	.	1000
Youngstown	Cincinnati	350	.	3000
Youngstown	'Kansas City'	450	1000	5000
Youngstown	Chicago		375	.	5000
Pittsburgh 	Cincinnati	350	.	2000
Pittsburgh	'Kansas City'	450	2000	3000
Pittsburgh	Chicago		400	.	4000
Pittsburgh	Gary 		450	.	2000
Cincinnati	Albany		350	1000	5000
Cincinnati	Houston		550	.	6000
'Kansas City'	Houston		375	.	4000
'Kansas City'	Tempe		650	.	4000
Chicago		Tempe		600	.	2000
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;
|
 |*FORM FIELD Results*|Results|Implementing the usual script file with transshipment.mod and steel.dat (with the Cost modification) gives us the optimal Flow variables:

steel_solution.jpg

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). If total supply is less than demand, then the problem becomes infeasible! Even in the case of infeasibility, it is preferable to solve the transshipment problem using a dummy supply node so that we can analyse where there is a shortfall in demand. We can balance the problem by either adding a dummy supply node with arcs to all the demand nodes or adding a dummy demand node with arcs from all the supply nodes: balance_transshipment.mod

# The following parameters are needed to use balance_transshipment.run
param difference;
param dummyDemandCost {NODES};
param dummySupplyCost {NODES};
balance_transshipment.run
let difference := (sum {s in NODES} Supply[s])
                - (sum {d in NODES} Demand[d]);
             
let NODES := NODES union {'Dummy'};             
if difference > 0 then
{
  print "Total Supply > Total Demand";
  print "Solving with dummy supply node...";
  let Demand['Dummy'] := difference;
  for {n in NODES : Supply[n] > 0} {
    let ARCS := ARCS union {(n, 'Dummy')};
    let Cost[n, 'Dummy'] := dummyDemandCost[n];
  }
}
else if difference < 0 then
{
  print "WARNING: Total Supply < Total Demand, problem is infeasible!";
  print "Solving with dummy demand node...";
  let Demand['Dummy'] := - difference;
  for {n in NODES : Demand[n] > 0} {
    let ARCS := ARCS union {('Dummy', n)};
    let Cost['Dummy', n] := dummySupplyCost[n];
  }
}; # else the problem is balanced
steel.run
# steel.run
#
# Written by Mike O'Sullivan & Cameron Walker 2004
#
# This file contains a script for sensitivity analysis
# of the American Steel transshipment model.
#
# Last modified: 27/2/2004

reset;

model transshipment.mod;
model balance_transshipment.mod;

data steel.dat;

let {(m, n) in ARCS} Cost[m, n] := Cost[m, n] / 1000;

for {n in NODES} {
  let dummyDemandCost[n] := 0;
  let dummySupplyCost[n] := 0;  
}

include balance_transshipment.run;

option solver cplex;

solve;

display Flow;  
Note We also add a ???LINK??? check statement to our model file to ensure the problem is balanced:
check : sum {n in NODES} Supply[n] = sum {n in NODES} Demand[n];

Our solution now shows that there is 5000 ton of steel remaining at the Pittsburgh Mill, i.e., the flow from Pittsburgh to Dummy is 5000.

POST-OPTIMAL ANALYSIS

Validation For our solution to be valid we need it to be integer. Observing the Flow values shows that it is in fact integer. Moreover, no branch-and-bound nodes were required to make it integer. The transshipment problem is also naturally integer (like the transportation problem), so solving it as a linear programme will give integer solutions. In fact, any network flow problem with integer supplies, demands and arc capacities has naturally integer solutions.

Parametric Analysis If ???LINK??? sensitivity analysis shows that improvements to the objective function may be achieved by changing problem data, then we may use ???LINK??? parametric analysis to see the effect of these changes.

.
.
.
include balance_transshipment.run;

option presolve 0;
option solver cplex;
option cplex_options 'presolve 0 sensitivity';
solve;

display Flow;

display _varname, _var.down, _var.current, _var.up, _var.rc;
display _conname, _con.down, _con.current, _con.up, _con.dual;

steel_sensitivity.jpg

The sensitivity analysis shows that the solution is very sensitive to any changes in the constraint right-hand sides, with one exception ConserverFlow at Pittsburgh. However, we have variables on both sides of our constraints so we should expand our constraints to see what the right-hand side is:

steel_rhs.jpg

For the supply nodes the right-hand side is the negative of the supply, for the demand nodes the right-hand side is the demand and for the transshipment nodes the right-hand side is 0. Thus, any changes we make to the supply or demand at the nodes will affect our optimal solution. The only exception is that the right-hand side of the ConserveFlow['Pittsburgh'] can decrease without affecting our solution. Since Pittsburgh is a supply node (so the right-hand side is the negative of the supply) this means we can increase the supply at Pittsburgh without affecting our solution. This makes sense as Pittsburgh already has excess supply.

However, it seems like we can improve our objective the most by decreasing the demand at Tempe (the shadow price is 1.125), but the Allowable Minimum is such that we cannot discern what the change will be (the solution will change immediately). We can see the effect by using an ???LINK??? AMPL loop :

.
.
.
display TotalCost;

set CHANGES;
param Objective {CHANGES};

param OldDemand;

let OldDemand := Demand['Tempe'];

let CHANGES := {100..1000 by 100}; 
for {i in CHANGES} {
  
  let Demand['Tempe'] := OldDemand - i;
  display Demand['Tempe'];

  # Rebalance the problem  
  include balance_transshipment.run;
  
  solve;
  
  let Objective[i] := TotalCost;
}

steel_parametric.jpg

Note that we had to alter balance_transshipment.run to consider problems that have been balanced previously: balance_transshipment.run

let difference := (sum {s in NODES : s <> 'Dummy'} Supply[s])
                - (sum {d in NODES : d <> 'Dummy'} Demand[d]);
             
if 'Dummy' not in NODES then
  let NODES := NODES union {'Dummy'};
  
if difference > 0 then
{
  print "Total Supply > Total Demand";
  print "Solving with dummy supply node...";
  let Demand['Dummy'] := difference;
  for {n in NODES : Supply[n] > 0} {
    let ARCS := ARCS union {(n, 'Dummy')};
    let Cost[n, 'Dummy'] := dummyDemandCost[n];
  }
}
else if difference < 0 then
{
  print "WARNING: Total Supply < Total Demand, problem is infeasible!";
  print "Solving with dummy demand node...";
  let Demand['Dummy'] := - difference;
  for {n in NODES : Demand[n] > 0} {
    let ARCS := ARCS union {('Dummy', n)};
    let Cost['Dummy', n] := dummySupplyCost[n];
  }
}; # else the problem is balanced

The AMPL parametric analysis shows that, by decreasing the demand for steel at Tempe, we can get a consistent reduction in our objective function, even though this was not clear from our initial sensitivity analysis.

When we consider the sensitvity analysis for variable costs, we see that the only costs that affect our solution are the transportation costs from Pittsburgh and Youngstown to Chicago (all the other costs have Allowable Min and Allowable Max such that no "sensible" change would have any effect). Suppose American Steel are negotiating a new contract with the shipping company that takes their steel from Pittsburgh to Chicago. They estimate that they can get a reduction of around \$25/1000 ton of steel (taking the price from \$400/1000 ton to \$375/1000 ton), but want to know if they should negotiate for a lower price. The sensitivity analysis shows that below \$375/1000 ton the solution will change, so let's use parametric analysis to see what happens:

.
.
.
display TotalCost;

set CHANGES;
param Objective {CHANGES};

param OldCost;

let OldCost := Cost['Pittsburgh', 'Chicago'];

let CHANGES := {0..0.05 by 0.005}; 
for {i in CHANGES} {
  
  let Cost['Pittsburgh', 'Chicago'] := OldCost - i;
  display Cost['Pittsburgh', 'Chicago'];

  # Rebalance the problem  
  include balance_transshipment.run;
  
  solve;
  
  let Objective[i] := TotalCost;
}

The parametric analysis shows that the objective function decreases at a greater rate if the price drops below $375/1000 ton, so American Steel should try and negotiate the price down even further.

steel_cost_parametric.jpg| |*FORM FIELD Conclusions*|Conclusions|There is quite a bit of information to summarise and many ways to present it. Some suggestions include:

  1. Summarise the problem as usual and list the shipments that American Steel should make (similar to the transportation problem);
  2. Summarise the problem as usual and present a table of shipments that American Steel should make;
  3. Draw the network formulation for the problem (being sure to specify what the labels mean). Then draw the actual solution on top of the network formulation. You could colour code flows long arcs to show if they are at their bounds.

Implementation and Ongoing Monitoring

Given that the solution is very sensitive to the supply and demand amounts, careful consideration of the accuracy of these figures is important. Making sure that the bounds on the arcs are reliable is another concern.

Ongoing monitoring of the supply, demand and bounds will help American Steel to keep making good decisions. As shown in the parametric analysis, ongoing negotiation of transportation prices along important routes will help American Steel reduce their expenditure.| |*FORM FIELD ExtraForExperts*|ExtraForExperts|Another common network flow problem that uses almost the same model as transshipment is the maximum flow problem. The objective of this problem is to maximise flow through the network. The only changes to transshipment.mod are:

  1. A new variable FlowOut is introduced at each node;
  2. FlowOut has lower and upper bounds, often the upper bound is set to as the Demand at the nodes;
  3. FlowOut replaces Demand in the ConserveFlow constraints;
  4. The ConserveFlow constraint becomes an equality constraint as all flow must be accounted for (no storage at the nodes);
  5. Cost of transshipment is ignored;
  6. The objective is to maximise the total flow out of the network sum {n in NODES} FlowOut[n];
  7. The problem no longer needs to be balanced.

Maxflow.mod ???ATTACH MAXFLOW.MOD HERE???

If we set MaxOut to Demand for all nodes:

let {n in NODES} MaxOut[n] := Demand[n];
then we see that currently all the demands are being met via the American Steel distribution network (the total flow out = the total demand):

steel_maxflow_solution.jpg|

Revision 122008-04-28 - MichaelOSullivan

Line: 1 to 1
 
META TOPICPARENT name="SubmitCaseStudy"
<-- Under Construction -->
Line: 87 to 87
 
FORM FIELD OperationsResearchTopics OperationsResearchTopics LinearProgramming, IntegerProgramming, NetworkOptimisation, TransshipmentProblem
FORM FIELD ApplicationAreas ApplicationAreas Logistics
|*FORM FIELD ProblemDescription*|ProblemDescription|American 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:

steel_network.jpg

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.

The table below presents the minimum and maximum flow amounts of steel that may be shipped between different cities along with the cost per 1000 ton/month of shipping the steel. For example, the shipment from Youngstown to Kansas City is contracted out to a railroad company with a minimal shipping clause of 1000 tons/month. However, the railroad cannot ship more then 5000 tons/month due the shortage of rail cars.

From node To node Cost Minimum Maximum
Youngstown Albany 500 - 1000
Youngstown Cincinnati 350 - 3000
Youngstown Kansas City 450 1000 5000
Youngstown Chicago 375 - 5000
Pittsburgh Cincinnati 350 - 2000
Pittsburgh Kansas City 450 2000 3000
Pittsburgh Chicago 400 - 4000
Pittsburgh Gary 450 - 2000
Cincinnati Albany 350 1000 5000
Cincinnati Houston 550 - 6000
Kansas City Houston 375 - 4000
Kansas City Tempe 650 - 4000
Chicago Tempe 600 - 2000
Chicago Gary 120 - 4000

The current monthly demand at American Steel's four field warehouses is as follows:

Field Warehouses Monthly Demand
Albany, N.Y. 3000
Houston 7000
Tempe 4000
Gary 6000

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.|

Changed:
<
<
|*FORM FIELD ProblemFormulation*|ProblemFormulation|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 repsectively. 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). | |*FORM FIELD ComputationalModel*|ComputationalModel|nodes and arcs are shown in the network and the net demand is given in [[tab1][Table 1].

Table 1 Net Demand Amounts

Node Net Demand
Youngstown  
Pittsburgh  
Cincinnati 0
Kansas City  
Chicago  
| 1. IDENTIFY THE DECISION VARIABLES*

The decision variables for this problem are the same as for the transportation problem, the Flow of goods (cases of beer in The Beer Distribution Problem, tons of steels here) through the network. In ???LINK??? A Transportation Problem all arcs from the supply nodes to the demand nodes existed (although in ???LINK??? Forestry Management we used upper bounds to removes some arcs). In The American Steel Problem, the network has transshipment nodes and arcs don't exist between all nodes. However, arcs must travel from one node to another. In AMPL we ???LINK??? declare the set of NODES and the set of ARCS between nodes:

# The set of all nodes in the network
set NODES;

# The set of arcs in the network
set ARCS within NODES cross NODES;
Now we define bounds on the flow (of our goods) along each arc:
# The minimum and maximum flow allowed along the arcs
param Min {ARCS} integer, default 0;
param Max {(m, n) in ARCS} integer, >= Min[m, n], default Infinity;
and finally declare our Flow variables:
# The flow of goods to be sent across an arc
var Flow {(m, n) in ARCS} >= Min[m, n], <= Max[m, n], integer;

2. FORMULATE THE OBJECTIVE FUNCTION

The objective of transshipment problems in general and The American Steel Problem in particular is to minimise the cost of shipping goods through the network:

# The cost of shipping 1 unit of goods (per time unit)
param Cost {ARCS};

# Minimise the total shipping cost
minimize TotalCost:
  sum {(m, n) in ARCS} Cost[m, n] * Flow[m, n];

3. FORMULATE THE CONSTRAINTS

All the nodes have supply and demand, demand = 0 for supply nodes, supply = 0 for demand nodes and supply = demand = 0 for transshipment nodes. Also, the supply and demand amounts must be integer to ensure a naturally integer solution (i.e., linear programming will provide an integer optimal solution).

# Each node has a (non-negative, integer) supply and a (non-negative, integer) demand
# Note. supply nodes have demand = 0 and vice versa,
# transshipment nodes have supply = demand = 0
param Supply {NODES} >= 0, integer, default 0;
param Demand {NODES} >= 0, integer, default 0;

The only constraints in the transshipment problem are flow conservation constraints. These constraints simply state that the flow of goods into a node must be greater than the flow of goods out of a node.

# Must conserve flow in the network (goods cannot disappear!)
subject to ConserveFlow {n in NODES}:
  sum {m in NODES: (m, n) in ARCS} Flow[m, n] + Supply[n] =>
  sum {p in NODES: (n, p) in ARCS} Flow[n, p] + Demand[n];

For example, if a node has a supply of 10 units and has 10 units flowing in, then it can have no more than 20 units flowing out:

conserve_flow.jpg

Transshipment problems are often presented as a network formulation:

steel_formulation.jpg

4. IDENTIFY THE DATA

The nodes of The American Steel Problem can be easily ???LINK??? defined using a list :

set NODES := Youngstown  Pittsburgh
             Cincinnati 'Kansas City' Chicago
             Albany      Houston      Tempe   Gary ;
Note that Kansas City must be enclosed in ' and ' because of the whitespace in the name.

The arc set is 2-dimensional and can be ???LINK??? 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         +          +         +      -       -      -    +
Cincinnati         -          -         -      +       +      -    -
'Kansas City'      -          -         -      -       +      +    -
Chicago            -          -         -      -       -      +    + ;
# Array of arcs
set ARCS :=
(Youngstown, *)    Cincinnati 'Kansas City' Chicago Albany
(Pittsburgh, *)    Cincinnati 'Kansas City' Chicago Gary
.
.
.
(Chicago, *)       Tempe       Gary
 ;

We can choose lists, tables or arrays to define the parameters for The American Steel Problem, but in this case we will use a list and ???LINK??? define multiple parameters at once. This allows us to "cut-and-paste" the parameters from the problem description. Note the use of . for parameters where the defaults will suffice (e.g., Min['Youngstown', 'Albany']):

param:                          Cost    Min     Max:=
Youngstown      Albany          500     .       1000
Youngstown      Cincinnati      350     .       3000
Youngstown     'Kansas City'    450     1000    5000
Youngstown      Chicago         375     .       5000
Pittsburgh      Cincinnati      350     .       2000
Pittsburgh     'Kansas City'    450     2000    3000
Pittsburgh      Chicago         400     .       4000
Pittsburgh      Gary            450     .       2000
Cincinnati      Albany          350     1000    5000
Cincinnati      Houston         550     .       6000
'Kansas City'   Houston         375     .       4000
'Kansas City'   Tempe           650     .       4000
Chicago         Tempe           600     .       2000
Chicago         Gary            120     .       4000
 ;
Note that the cost is in $/1000 ton, so we must divide the cost by 1000 before solving:
let {(m, n) in ARCS} Cost[m, n] := Cost[m, n] / 1000;
|
>
>
|*FORM FIELD ProblemFormulation*|ProblemFormulation|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 repsectively. 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).

steel_formulation.jpg

| |*FORM FIELD ComputationalModel*|ComputationalModel|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 Kansas City must be enclosed in ' and ' because of the whitespace in the name.

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 ARCS:

set ARCS:   Cincinnati 'Kansas City' Chicago Albany Houston Tempe Gary :=
Youngstown         +          +         +      +       -      -    -
Pittsburgh         +          +         +      -       -      -    +
Cincinnati         -          -         -      +       +      -    -
'Kansas City'      -          -         -      -       +      +    -
Chicago            -          -         -      -       -      +    + ;

The NetDemand can be defined easily from the supply and demand. Since the default is 0 we don't need to define NetDemand for the transshipment nodes:

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 . for parameters where the defaults will suffice (e.g., Lower for Youngstown and Albany):

param:                  	Cost    Lower  	Upper:=
Youngstown	Albany		500	.	1000
Youngstown	Cincinnati	350	.	3000
Youngstown	'Kansas City'	450	1000	5000
Youngstown	Chicago		375	.	5000
Pittsburgh 	Cincinnati	350	.	2000
Pittsburgh	'Kansas City'	450	2000	3000
Pittsburgh	Chicago		400	.	4000
Pittsburgh	Gary 		450	.	2000
Cincinnati	Albany		350	1000	5000
Cincinnati	Houston		550	.	6000
'Kansas City'	Houston		375	.	4000
'Kansas City'	Tempe		650	.	4000
Chicago		Tempe		600	.	2000
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;
|
 |*FORM FIELD Results*|Results|Implementing the usual script file with transshipment.mod and steel.dat (with the Cost modification) gives us the optimal Flow variables:

steel_solution.jpg

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). If total supply is less than demand, then the problem becomes infeasible! Even in the case of infeasibility, it is preferable to solve the transshipment problem using a dummy supply node so that we can analyse where there is a shortfall in demand. We can balance the problem by either adding a dummy supply node with arcs to all the demand nodes or adding a dummy demand node with arcs from all the supply nodes: balance_transshipment.mod

# The following parameters are needed to use balance_transshipment.run
param difference;
param dummyDemandCost {NODES};
param dummySupplyCost {NODES};
balance_transshipment.run
let difference := (sum {s in NODES} Supply[s])
                - (sum {d in NODES} Demand[d]);
             
let NODES := NODES union {'Dummy'};             
if difference > 0 then
{
  print "Total Supply > Total Demand";
  print "Solving with dummy supply node...";
  let Demand['Dummy'] := difference;
  for {n in NODES : Supply[n] > 0} {
    let ARCS := ARCS union {(n, 'Dummy')};
    let Cost[n, 'Dummy'] := dummyDemandCost[n];
  }
}
else if difference < 0 then
{
  print "WARNING: Total Supply < Total Demand, problem is infeasible!";
  print "Solving with dummy demand node...";
  let Demand['Dummy'] := - difference;
  for {n in NODES : Demand[n] > 0} {
    let ARCS := ARCS union {('Dummy', n)};
    let Cost['Dummy', n] := dummySupplyCost[n];
  }
}; # else the problem is balanced
steel.run
# steel.run
#
# Written by Mike O'Sullivan & Cameron Walker 2004
#
# This file contains a script for sensitivity analysis
# of the American Steel transshipment model.
#
# Last modified: 27/2/2004

reset;

model transshipment.mod;
model balance_transshipment.mod;

data steel.dat;

let {(m, n) in ARCS} Cost[m, n] := Cost[m, n] / 1000;

for {n in NODES} {
  let dummyDemandCost[n] := 0;
  let dummySupplyCost[n] := 0;  
}

include balance_transshipment.run;

option solver cplex;

solve;

display Flow;  
Note We also add a ???LINK??? check statement to our model file to ensure the problem is balanced:
check : sum {n in NODES} Supply[n] = sum {n in NODES} Demand[n];

Our solution now shows that there is 5000 ton of steel remaining at the Pittsburgh Mill, i.e., the flow from Pittsburgh to Dummy is 5000.

POST-OPTIMAL ANALYSIS

Validation For our solution to be valid we need it to be integer. Observing the Flow values shows that it is in fact integer. Moreover, no branch-and-bound nodes were required to make it integer. The transshipment problem is also naturally integer (like the transportation problem), so solving it as a linear programme will give integer solutions. In fact, any network flow problem with integer supplies, demands and arc capacities has naturally integer solutions.

Parametric Analysis If ???LINK??? sensitivity analysis shows that improvements to the objective function may be achieved by changing problem data, then we may use ???LINK??? parametric analysis to see the effect of these changes.

.
.
.
include balance_transshipment.run;

option presolve 0;
option solver cplex;
option cplex_options 'presolve 0 sensitivity';
solve;

display Flow;

display _varname, _var.down, _var.current, _var.up, _var.rc;
display _conname, _con.down, _con.current, _con.up, _con.dual;

steel_sensitivity.jpg

The sensitivity analysis shows that the solution is very sensitive to any changes in the constraint right-hand sides, with one exception ConserverFlow at Pittsburgh. However, we have variables on both sides of our constraints so we should expand our constraints to see what the right-hand side is:

steel_rhs.jpg

For the supply nodes the right-hand side is the negative of the supply, for the demand nodes the right-hand side is the demand and for the transshipment nodes the right-hand side is 0. Thus, any changes we make to the supply or demand at the nodes will affect our optimal solution. The only exception is that the right-hand side of the ConserveFlow['Pittsburgh'] can decrease without affecting our solution. Since Pittsburgh is a supply node (so the right-hand side is the negative of the supply) this means we can increase the supply at Pittsburgh without affecting our solution. This makes sense as Pittsburgh already has excess supply.

However, it seems like we can improve our objective the most by decreasing the demand at Tempe (the shadow price is 1.125), but the Allowable Minimum is such that we cannot discern what the change will be (the solution will change immediately). We can see the effect by using an ???LINK??? AMPL loop :

.
.
.
display TotalCost;

set CHANGES;
param Objective {CHANGES};

param OldDemand;

let OldDemand := Demand['Tempe'];

let CHANGES := {100..1000 by 100}; 
for {i in CHANGES} {
  
  let Demand['Tempe'] := OldDemand - i;
  display Demand['Tempe'];

  # Rebalance the problem  
  include balance_transshipment.run;
  
  solve;
  
  let Objective[i] := TotalCost;
}

steel_parametric.jpg

Note that we had to alter balance_transshipment.run to consider problems that have been balanced previously: balance_transshipment.run

let difference := (sum {s in NODES : s <> 'Dummy'} Supply[s])
                - (sum {d in NODES : d <> 'Dummy'} Demand[d]);
             
if 'Dummy' not in NODES then
  let NODES := NODES union {'Dummy'};
  
if difference > 0 then
{
  print "Total Supply > Total Demand";
  print "Solving with dummy supply node...";
  let Demand['Dummy'] := difference;
  for {n in NODES : Supply[n] > 0} {
    let ARCS := ARCS union {(n, 'Dummy')};
    let Cost[n, 'Dummy'] := dummyDemandCost[n];
  }
}
else if difference < 0 then
{
  print "WARNING: Total Supply < Total Demand, problem is infeasible!";
  print "Solving with dummy demand node...";
  let Demand['Dummy'] := - difference;
  for {n in NODES : Demand[n] > 0} {
    let ARCS := ARCS union {('Dummy', n)};
    let Cost['Dummy', n] := dummySupplyCost[n];
  }
}; # else the problem is balanced

The AMPL parametric analysis shows that, by decreasing the demand for steel at Tempe, we can get a consistent reduction in our objective function, even though this was not clear from our initial sensitivity analysis.

When we consider the sensitvity analysis for variable costs, we see that the only costs that affect our solution are the transportation costs from Pittsburgh and Youngstown to Chicago (all the other costs have Allowable Min and Allowable Max such that no "sensible" change would have any effect). Suppose American Steel are negotiating a new contract with the shipping company that takes their steel from Pittsburgh to Chicago. They estimate that they can get a reduction of around \$25/1000 ton of steel (taking the price from \$400/1000 ton to \$375/1000 ton), but want to know if they should negotiate for a lower price. The sensitivity analysis shows that below \$375/1000 ton the solution will change, so let's use parametric analysis to see what happens:

.
.
.
display TotalCost;

set CHANGES;
param Objective {CHANGES};

param OldCost;

let OldCost := Cost['Pittsburgh', 'Chicago'];

let CHANGES := {0..0.05 by 0.005}; 
for {i in CHANGES} {
  
  let Cost['Pittsburgh', 'Chicago'] := OldCost - i;
  display Cost['Pittsburgh', 'Chicago'];

  # Rebalance the problem  
  include balance_transshipment.run;
  
  solve;
  
  let Objective[i] := TotalCost;
}

The parametric analysis shows that the objective function decreases at a greater rate if the price drops below $375/1000 ton, so American Steel should try and negotiate the price down even further.

steel_cost_parametric.jpg| |*FORM FIELD Conclusions*|Conclusions|There is quite a bit of information to summarise and many ways to present it. Some suggestions include:

  1. Summarise the problem as usual and list the shipments that American Steel should make (similar to the transportation problem);
  2. Summarise the problem as usual and present a table of shipments that American Steel should make;
  3. Draw the network formulation for the problem (being sure to specify what the labels mean). Then draw the actual solution on top of the network formulation. You could colour code flows long arcs to show if they are at their bounds.

Implementation and Ongoing Monitoring

Given that the solution is very sensitive to the supply and demand amounts, careful consideration of the accuracy of these figures is important. Making sure that the bounds on the arcs are reliable is another concern.

Ongoing monitoring of the supply, demand and bounds will help American Steel to keep making good decisions. As shown in the parametric analysis, ongoing negotiation of transportation prices along important routes will help American Steel reduce their expenditure.| |*FORM FIELD ExtraForExperts*|ExtraForExperts|Another common network flow problem that uses almost the same model as transshipment is the maximum flow problem. The objective of this problem is to maximise flow through the network. The only changes to transshipment.mod are:

  1. A new variable FlowOut is introduced at each node;
  2. FlowOut has lower and upper bounds, often the upper bound is set to as the Demand at the nodes;
  3. FlowOut replaces Demand in the ConserveFlow constraints;
  4. The ConserveFlow constraint becomes an equality constraint as all flow must be accounted for (no storage at the nodes);
  5. Cost of transshipment is ignored;
  6. The objective is to maximise the total flow out of the network sum {n in NODES} FlowOut[n];
  7. The problem no longer needs to be balanced.

Maxflow.mod ???ATTACH MAXFLOW.MOD HERE???

If we set MaxOut to Demand for all nodes:

let {n in NODES} MaxOut[n] := Demand[n];
then we see that currently all the demands are being met via the American Steel distribution network (the total flow out = the total demand):

steel_maxflow_solution.jpg|

Revision 112008-04-28 - MichaelOSullivan

Line: 1 to 1
 
META TOPICPARENT name="SubmitCaseStudy"
<-- Under Construction -->
Line: 86 to 86
 
FORM FIELD CaseStudyType CaseStudyType TeachingCaseStudy
FORM FIELD OperationsResearchTopics OperationsResearchTopics LinearProgramming, IntegerProgramming, NetworkOptimisation, TransshipmentProblem
FORM FIELD ApplicationAreas ApplicationAreas Logistics
Changed:
<
<
|*FORM FIELD ProblemDescription*|ProblemDescription|*THE AMERICAN STEEL PROBLEM*

American 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:

steel_network.jpg

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.

The table below presents the minimum and maximum flow amounts of steel that may be shipped between different cities along with the cost per 1000 ton/month of shipping the steel. For example, the shipment from Youngstown to Kansas City is contracted out to a railroad company with a minimal shipping clause of 1000 tons/month. However, the railroad cannot ship more then 5000 tons/month due the shortage of rail cars.

From node To node Cost Minimum Maximum
Youngstown Albany 500 - 1000
Youngstown Cincinnati 350 - 3000
Youngstown Kansas City 450 1000 5000
Youngstown Chicago 375 - 5000
Pittsburgh Cincinnati 350 - 2000
Pittsburgh Kansas City 450 2000 3000
Pittsburgh Chicago 400 - 4000
Pittsburgh Gary 450 - 2000
Cincinnati Albany 350 1000 5000
Cincinnati Houston 550 - 6000
Kansas City Houston 375 - 4000
Kansas City Tempe 650 - 4000
Chicago Tempe 600 - 2000
Chicago Gary 120 - 4000

The current monthly demand at American Steel’s four field warehouses is as follows:

Field Warehouses Monthly Demand
Albany, N.Y. 3000
Houston 7000
Tempe 4000
Gary 6000

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.| |*FORM FIELD ProblemFormulation*|ProblemFormulation|*1. IDENTIFY THE DECISION VARIABLES*

The decision variables for this problem are the same as for the transportation problem, the Flow of goods (cases of beer in The Beer Distribution Problem, tons of steels here) through the network. In ???LINK??? A Transportation Problem all arcs from the supply nodes to the demand nodes existed (although in ???LINK??? Forestry Management we used upper bounds to removes some arcs). In The American Steel Problem, the network has transshipment nodes and arcs don't exist between all nodes. However, arcs must travel from one node to another. In AMPL we ???LINK??? declare the set of NODES and the set of ARCS between nodes:

# The set of all nodes in the network
set NODES;

# The set of arcs in the network
set ARCS within NODES cross NODES;
Now we define bounds on the flow (of our goods) along each arc:
# The minimum and maximum flow allowed along the arcs
param Min {ARCS} integer, default 0;
param Max {(m, n) in ARCS} integer, >= Min[m, n], default Infinity;
and finally declare our Flow variables:
# The flow of goods to be sent across an arc
var Flow {(m, n) in ARCS} >= Min[m, n], <= Max[m, n], integer;

2. FORMULATE THE OBJECTIVE FUNCTION

The objective of transshipment problems in general and The American Steel Problem in particular is to minimise the cost of shipping goods through the network:

# The cost of shipping 1 unit of goods (per time unit)
param Cost {ARCS};

# Minimise the total shipping cost
minimize TotalCost:
  sum {(m, n) in ARCS} Cost[m, n] * Flow[m, n];

3. FORMULATE THE CONSTRAINTS

All the nodes have supply and demand, demand = 0 for supply nodes, supply = 0 for demand nodes and supply = demand = 0 for transshipment nodes. Also, the supply and demand amounts must be integer to ensure a naturally integer solution (i.e., linear programming will provide an integer optimal solution).

# Each node has a (non-negative, integer) supply and a (non-negative, integer) demand
# Note. supply nodes have demand = 0 and vice versa,
# transshipment nodes have supply = demand = 0
param Supply {NODES} >= 0, integer, default 0;
param Demand {NODES} >= 0, integer, default 0;

The only constraints in the transshipment problem are flow conservation constraints. These constraints simply state that the flow of goods into a node must be greater than the flow of goods out of a node.

# Must conserve flow in the network (goods cannot disappear!)
subject to ConserveFlow {n in NODES}:
  sum {m in NODES: (m, n) in ARCS} Flow[m, n] + Supply[n] =>
  sum {p in NODES: (n, p) in ARCS} Flow[n, p] + Demand[n];

For example, if a node has a supply of 10 units and has 10 units flowing in, then it can have no more than 20 units flowing out:

conserve_flow.jpg

Transshipment problems are often presented as a network formulation:

steel_formulation.jpg

4. IDENTIFY THE DATA

The nodes of The American Steel Problem can be easily ???LINK??? defined using a list :

set NODES := Youngstown  Pittsburgh
             Cincinnati 'Kansas City' Chicago
             Albany      Houston      Tempe   Gary ;
Note that Kansas City must be enclosed in ' and ' because of the whitespace in the name.

The arc set is 2-dimensional and can be ???LINK??? 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         +          +         +      -       -      -    +
Cincinnati         -          -         -      +       +      -    -
'Kansas City'      -          -         -      -       +      +    -
Chicago            -          -         -      -       -      +    + ;
# Array of arcs
set ARCS :=
(Youngstown, *)    Cincinnati 'Kansas City' Chicago Albany
(Pittsburgh, *)    Cincinnati 'Kansas City' Chicago Gary
.
.
.
(Chicago, *)       Tempe       Gary
 ;

We can choose lists, tables or arrays to define the parameters for The American Steel Problem, but in this case we will use a list and ???LINK??? define multiple parameters at once. This allows us to "cut-and-paste" the parameters from the problem description. Note the use of . for parameters where the defaults will suffice (e.g., Min['Youngstown', 'Albany']):

param:                          Cost    Min     Max:=
Youngstown      Albany          500     .       1000
Youngstown      Cincinnati      350     .       3000
Youngstown     'Kansas City'    450     1000    5000
Youngstown      Chicago         375     .       5000
Pittsburgh      Cincinnati      350     .       2000
Pittsburgh     'Kansas City'    450     2000    3000
Pittsburgh      Chicago         400     .       4000
Pittsburgh      Gary            450     .       2000
Cincinnati      Albany          350     1000    5000
Cincinnati      Houston         550     .       6000
'Kansas City'   Houston         375     .       4000
'Kansas City'   Tempe           650     .       4000
Chicago         Tempe           600     .       2000
Chicago         Gary            120     .       4000
 ;
Note that the cost is in $/1000 ton, so we must divide the cost by 1000 before solving:
let {(m, n) in ARCS} Cost[m, n] := Cost[m, n] / 1000;
|
FORM FIELD ComputationalModel ComputationalModel The computational model...
>
>
|*FORM FIELD ProblemDescription*|ProblemDescription|American 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:

steel_network.jpg

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.

The table below presents the minimum and maximum flow amounts of steel that may be shipped between different cities along with the cost per 1000 ton/month of shipping the steel. For example, the shipment from Youngstown to Kansas City is contracted out to a railroad company with a minimal shipping clause of 1000 tons/month. However, the railroad cannot ship more then 5000 tons/month due the shortage of rail cars.

From node To node Cost Minimum Maximum
Youngstown Albany 500 - 1000
Youngstown Cincinnati 350 - 3000
Youngstown Kansas City 450 1000 5000
Youngstown Chicago 375 - 5000
Pittsburgh Cincinnati 350 - 2000
Pittsburgh Kansas City 450 2000 3000
Pittsburgh Chicago 400 - 4000
Pittsburgh Gary 450 - 2000
Cincinnati Albany 350 1000 5000
Cincinnati Houston 550 - 6000
Kansas City Houston 375 - 4000
Kansas City Tempe 650 - 4000
Chicago Tempe 600 - 2000
Chicago Gary 120 - 4000

The current monthly demand at American Steel's four field warehouses is as follows:

Field Warehouses Monthly Demand
Albany, N.Y. 3000
Houston 7000
Tempe 4000
Gary 6000

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.| |*FORM FIELD ProblemFormulation*|ProblemFormulation|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 repsectively. 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). | |*FORM FIELD ComputationalModel*|ComputationalModel|nodes and arcs are shown in the network and the net demand is given in [[tab1][Table 1].

Table 1 Net Demand Amounts

Node Net Demand
Youngstown  
Pittsburgh  
Cincinnati 0
Kansas City  
Chicago  
| 1. IDENTIFY THE DECISION VARIABLES*

The decision variables for this problem are the same as for the transportation problem, the Flow of goods (cases of beer in The Beer Distribution Problem, tons of steels here) through the network. In ???LINK??? A Transportation Problem all arcs from the supply nodes to the demand nodes existed (although in ???LINK??? Forestry Management we used upper bounds to removes some arcs). In The American Steel Problem, the network has transshipment nodes and arcs don't exist between all nodes. However, arcs must travel from one node to another. In AMPL we ???LINK??? declare the set of NODES and the set of ARCS between nodes:

# The set of all nodes in the network
set NODES;

# The set of arcs in the network
set ARCS within NODES cross NODES;
Now we define bounds on the flow (of our goods) along each arc:
# The minimum and maximum flow allowed along the arcs
param Min {ARCS} integer, default 0;
param Max {(m, n) in ARCS} integer, >= Min[m, n], default Infinity;
and finally declare our Flow variables:
# The flow of goods to be sent across an arc
var Flow {(m, n) in ARCS} >= Min[m, n], <= Max[m, n], integer;

2. FORMULATE THE OBJECTIVE FUNCTION

The objective of transshipment problems in general and The American Steel Problem in particular is to minimise the cost of shipping goods through the network:

# The cost of shipping 1 unit of goods (per time unit)
param Cost {ARCS};

# Minimise the total shipping cost
minimize TotalCost:
  sum {(m, n) in ARCS} Cost[m, n] * Flow[m, n];

3. FORMULATE THE CONSTRAINTS

All the nodes have supply and demand, demand = 0 for supply nodes, supply = 0 for demand nodes and supply = demand = 0 for transshipment nodes. Also, the supply and demand amounts must be integer to ensure a naturally integer solution (i.e., linear programming will provide an integer optimal solution).

# Each node has a (non-negative, integer) supply and a (non-negative, integer) demand
# Note. supply nodes have demand = 0 and vice versa,
# transshipment nodes have supply = demand = 0
param Supply {NODES} >= 0, integer, default 0;
param Demand {NODES} >= 0, integer, default 0;

The only constraints in the transshipment problem are flow conservation constraints. These constraints simply state that the flow of goods into a node must be greater than the flow of goods out of a node.

# Must conserve flow in the network (goods cannot disappear!)
subject to ConserveFlow {n in NODES}:
  sum {m in NODES: (m, n) in ARCS} Flow[m, n] + Supply[n] =>
  sum {p in NODES: (n, p) in ARCS} Flow[n, p] + Demand[n];

For example, if a node has a supply of 10 units and has 10 units flowing in, then it can have no more than 20 units flowing out:

conserve_flow.jpg

Transshipment problems are often presented as a network formulation:

steel_formulation.jpg

4. IDENTIFY THE DATA

The nodes of The American Steel Problem can be easily ???LINK??? defined using a list :

set NODES := Youngstown  Pittsburgh
             Cincinnati 'Kansas City' Chicago
             Albany      Houston      Tempe   Gary ;
Note that Kansas City must be enclosed in ' and ' because of the whitespace in the name.

The arc set is 2-dimensional and can be ???LINK??? 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         +          +         +      -       -      -    +
Cincinnati         -          -         -      +       +      -    -
'Kansas City'      -          -         -      -       +      +    -
Chicago            -          -         -      -       -      +    + ;
# Array of arcs
set ARCS :=
(Youngstown, *)    Cincinnati 'Kansas City' Chicago Albany
(Pittsburgh, *)    Cincinnati 'Kansas City' Chicago Gary
.
.
.
(Chicago, *)       Tempe       Gary
 ;

We can choose lists, tables or arrays to define the parameters for The American Steel Problem, but in this case we will use a list and ???LINK??? define multiple parameters at once. This allows us to "cut-and-paste" the parameters from the problem description. Note the use of . for parameters where the defaults will suffice (e.g., Min['Youngstown', 'Albany']):

param:                          Cost    Min     Max:=
Youngstown      Albany          500     .       1000
Youngstown      Cincinnati      350     .       3000
Youngstown     'Kansas City'    450     1000    5000
Youngstown      Chicago         375     .       5000
Pittsburgh      Cincinnati      350     .       2000
Pittsburgh     'Kansas City'    450     2000    3000
Pittsburgh      Chicago         400     .       4000
Pittsburgh      Gary            450     .       2000
Cincinnati      Albany          350     1000    5000
Cincinnati      Houston         550     .       6000
'Kansas City'   Houston         375     .       4000
'Kansas City'   Tempe           650     .       4000
Chicago         Tempe           600     .       2000
Chicago         Gary            120     .       4000
 ;
Note that the cost is in $/1000 ton, so we must divide the cost by 1000 before solving:
let {(m, n) in ARCS} Cost[m, n] := Cost[m, n] / 1000;
|
 |*FORM FIELD Results*|Results|Implementing the usual script file with transshipment.mod and steel.dat (with the Cost modification) gives us the optimal Flow variables:

steel_solution.jpg

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). If total supply is less than demand, then the problem becomes infeasible! Even in the case of infeasibility, it is preferable to solve the transshipment problem using a dummy supply node so that we can analyse where there is a shortfall in demand. We can balance the problem by either adding a dummy supply node with arcs to all the demand nodes or adding a dummy demand node with arcs from all the supply nodes: balance_transshipment.mod

# The following parameters are needed to use balance_transshipment.run
param difference;
param dummyDemandCost {NODES};
param dummySupplyCost {NODES};
balance_transshipment.run
let difference := (sum {s in NODES} Supply[s])
                - (sum {d in NODES} Demand[d]);
             
let NODES := NODES union {'Dummy'};             
if difference > 0 then
{
  print "Total Supply > Total Demand";
  print "Solving with dummy supply node...";
  let Demand['Dummy'] := difference;
  for {n in NODES : Supply[n] > 0} {
    let ARCS := ARCS union {(n, 'Dummy')};
    let Cost[n, 'Dummy'] := dummyDemandCost[n];
  }
}
else if difference < 0 then
{
  print "WARNING: Total Supply < Total Demand, problem is infeasible!";
  print "Solving with dummy demand node...";
  let Demand['Dummy'] := - difference;
  for {n in NODES : Demand[n] > 0} {
    let ARCS := ARCS union {('Dummy', n)};
    let Cost['Dummy', n] := dummySupplyCost[n];
  }
}; # else the problem is balanced
steel.run
# steel.run
#
# Written by Mike O'Sullivan & Cameron Walker 2004
#
# This file contains a script for sensitivity analysis
# of the American Steel transshipment model.
#
# Last modified: 27/2/2004

reset;

model transshipment.mod;
model balance_transshipment.mod;

data steel.dat;

let {(m, n) in ARCS} Cost[m, n] := Cost[m, n] / 1000;

for {n in NODES} {
  let dummyDemandCost[n] := 0;
  let dummySupplyCost[n] := 0;  
}

include balance_transshipment.run;

option solver cplex;

solve;

display Flow;  
Note We also add a ???LINK??? check statement to our model file to ensure the problem is balanced:
check : sum {n in NODES} Supply[n] = sum {n in NODES} Demand[n];

Our solution now shows that there is 5000 ton of steel remaining at the Pittsburgh Mill, i.e., the flow from Pittsburgh to Dummy is 5000.

POST-OPTIMAL ANALYSIS

Validation For our solution to be valid we need it to be integer. Observing the Flow values shows that it is in fact integer. Moreover, no branch-and-bound nodes were required to make it integer. The transshipment problem is also naturally integer (like the transportation problem), so solving it as a linear programme will give integer solutions. In fact, any network flow problem with integer supplies, demands and arc capacities has naturally integer solutions.

Parametric Analysis If ???LINK??? sensitivity analysis shows that improvements to the objective function may be achieved by changing problem data, then we may use ???LINK??? parametric analysis to see the effect of these changes.

.
.
.
include balance_transshipment.run;

option presolve 0;
option solver cplex;
option cplex_options 'presolve 0 sensitivity';
solve;

display Flow;

display _varname, _var.down, _var.current, _var.up, _var.rc;
display _conname, _con.down, _con.current, _con.up, _con.dual;

steel_sensitivity.jpg

The sensitivity analysis shows that the solution is very sensitive to any changes in the constraint right-hand sides, with one exception ConserverFlow at Pittsburgh. However, we have variables on both sides of our constraints so we should expand our constraints to see what the right-hand side is:

steel_rhs.jpg

For the supply nodes the right-hand side is the negative of the supply, for the demand nodes the right-hand side is the demand and for the transshipment nodes the right-hand side is 0. Thus, any changes we make to the supply or demand at the nodes will affect our optimal solution. The only exception is that the right-hand side of the ConserveFlow['Pittsburgh'] can decrease without affecting our solution. Since Pittsburgh is a supply node (so the right-hand side is the negative of the supply) this means we can increase the supply at Pittsburgh without affecting our solution. This makes sense as Pittsburgh already has excess supply.

However, it seems like we can improve our objective the most by decreasing the demand at Tempe (the shadow price is 1.125), but the Allowable Minimum is such that we cannot discern what the change will be (the solution will change immediately). We can see the effect by using an ???LINK??? AMPL loop :

.
.
.
display TotalCost;

set CHANGES;
param Objective {CHANGES};

param OldDemand;

let OldDemand := Demand['Tempe'];

let CHANGES := {100..1000 by 100}; 
for {i in CHANGES} {
  
  let Demand['Tempe'] := OldDemand - i;
  display Demand['Tempe'];

  # Rebalance the problem  
  include balance_transshipment.run;
  
  solve;
  
  let Objective[i] := TotalCost;
}

steel_parametric.jpg

Note that we had to alter balance_transshipment.run to consider problems that have been balanced previously: balance_transshipment.run

let difference := (sum {s in NODES : s <> 'Dummy'} Supply[s])
                - (sum {d in NODES : d <> 'Dummy'} Demand[d]);
             
if 'Dummy' not in NODES then
  let NODES := NODES union {'Dummy'};
  
if difference > 0 then
{
  print "Total Supply > Total Demand";
  print "Solving with dummy supply node...";
  let Demand['Dummy'] := difference;
  for {n in NODES : Supply[n] > 0} {
    let ARCS := ARCS union {(n, 'Dummy')};
    let Cost[n, 'Dummy'] := dummyDemandCost[n];
  }
}
else if difference < 0 then
{
  print "WARNING: Total Supply < Total Demand, problem is infeasible!";
  print "Solving with dummy demand node...";
  let Demand['Dummy'] := - difference;
  for {n in NODES : Demand[n] > 0} {
    let ARCS := ARCS union {('Dummy', n)};
    let Cost['Dummy', n] := dummySupplyCost[n];
  }
}; # else the problem is balanced

The AMPL parametric analysis shows that, by decreasing the demand for steel at Tempe, we can get a consistent reduction in our objective function, even though this was not clear from our initial sensitivity analysis.

When we consider the sensitvity analysis for variable costs, we see that the only costs that affect our solution are the transportation costs from Pittsburgh and Youngstown to Chicago (all the other costs have Allowable Min and Allowable Max such that no "sensible" change would have any effect). Suppose American Steel are negotiating a new contract with the shipping company that takes their steel from Pittsburgh to Chicago. They estimate that they can get a reduction of around \$25/1000 ton of steel (taking the price from \$400/1000 ton to \$375/1000 ton), but want to know if they should negotiate for a lower price. The sensitivity analysis shows that below \$375/1000 ton the solution will change, so let's use parametric analysis to see what happens:

.
.
.
display TotalCost;

set CHANGES;
param Objective {CHANGES};

param OldCost;

let OldCost := Cost['Pittsburgh', 'Chicago'];

let CHANGES := {0..0.05 by 0.005}; 
for {i in CHANGES} {
  
  let Cost['Pittsburgh', 'Chicago'] := OldCost - i;
  display Cost['Pittsburgh', 'Chicago'];

  # Rebalance the problem  
  include balance_transshipment.run;
  
  solve;
  
  let Objective[i] := TotalCost;
}

The parametric analysis shows that the objective function decreases at a greater rate if the price drops below $375/1000 ton, so American Steel should try and negotiate the price down even further.

steel_cost_parametric.jpg| |*FORM FIELD Conclusions*|Conclusions|There is quite a bit of information to summarise and many ways to present it. Some suggestions include:

  1. Summarise the problem as usual and list the shipments that American Steel should make (similar to the transportation problem);
  2. Summarise the problem as usual and present a table of shipments that American Steel should make;
  3. Draw the network formulation for the problem (being sure to specify what the labels mean). Then draw the actual solution on top of the network formulation. You could colour code flows long arcs to show if they are at their bounds.

Implementation and Ongoing Monitoring

Given that the solution is very sensitive to the supply and demand amounts, careful consideration of the accuracy of these figures is important. Making sure that the bounds on the arcs are reliable is another concern.

Ongoing monitoring of the supply, demand and bounds will help American Steel to keep making good decisions. As shown in the parametric analysis, ongoing negotiation of transportation prices along important routes will help American Steel reduce their expenditure.| |*FORM FIELD ExtraForExperts*|ExtraForExperts|Another common network flow problem that uses almost the same model as transshipment is the maximum flow problem. The objective of this problem is to maximise flow through the network. The only changes to transshipment.mod are:

  1. A new variable FlowOut is introduced at each node;
  2. FlowOut has lower and upper bounds, often the upper bound is set to as the Demand at the nodes;
  3. FlowOut replaces Demand in the ConserveFlow constraints;
  4. The ConserveFlow constraint becomes an equality constraint as all flow must be accounted for (no storage at the nodes);
  5. Cost of transshipment is ignored;
  6. The objective is to maximise the total flow out of the network sum {n in NODES} FlowOut[n];
  7. The problem no longer needs to be balanced.

Maxflow.mod ???ATTACH MAXFLOW.MOD HERE???

If we set MaxOut to Demand for all nodes:

let {n in NODES} MaxOut[n] := Demand[n];
then we see that currently all the demands are being met via the American Steel distribution network (the total flow out = the total demand):

steel_maxflow_solution.jpg|

Revision 102008-04-21 - TWikiAdminUser

Line: 1 to 1
 
META TOPICPARENT name="SubmitCaseStudy"
<-- Under Construction -->
Line: 84 to 84
 
FORM FIELD Title Title The American Steel Transshipment Problem
FORM FIELD DateSubmitted DateSubmitted 15 Feb 2008
FORM FIELD CaseStudyType CaseStudyType TeachingCaseStudy
Changed:
<
<
FORM FIELD OperationsResearchTopics OperationsResearchTopics LinearProgramming, IntegerProgramming, NetworkOptimisation
>
>
FORM FIELD OperationsResearchTopics OperationsResearchTopics LinearProgramming, IntegerProgramming, NetworkOptimisation, TransshipmentProblem
 
FORM FIELD ApplicationAreas ApplicationAreas Logistics
|*FORM FIELD ProblemDescription*|ProblemDescription|*THE AMERICAN STEEL PROBLEM*

American 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:

steel_network.jpg

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.

The table below presents the minimum and maximum flow amounts of steel that may be shipped between different cities along with the cost per 1000 ton/month of shipping the steel. For example, the shipment from Youngstown to Kansas City is contracted out to a railroad company with a minimal shipping clause of 1000 tons/month. However, the railroad cannot ship more then 5000 tons/month due the shortage of rail cars.

From node To node Cost Minimum Maximum
Youngstown Albany 500 - 1000
Youngstown Cincinnati 350 - 3000
Youngstown Kansas City 450 1000 5000
Youngstown Chicago 375 - 5000
Pittsburgh Cincinnati 350 - 2000
Pittsburgh Kansas City 450 2000 3000
Pittsburgh Chicago 400 - 4000
Pittsburgh Gary 450 - 2000
Cincinnati Albany 350 1000 5000
Cincinnati Houston 550 - 6000
Kansas City Houston 375 - 4000
Kansas City Tempe 650 - 4000
Chicago Tempe 600 - 2000
Chicago Gary 120 - 4000

The current monthly demand at American Steel’s four field warehouses is as follows:

Field Warehouses Monthly Demand
Albany, N.Y. 3000
Houston 7000
Tempe 4000
Gary 6000

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.| |*FORM FIELD ProblemFormulation*|ProblemFormulation|*1. IDENTIFY THE DECISION VARIABLES*

The decision variables for this problem are the same as for the transportation problem, the Flow of goods (cases of beer in The Beer Distribution Problem, tons of steels here) through the network. In ???LINK??? A Transportation Problem all arcs from the supply nodes to the demand nodes existed (although in ???LINK??? Forestry Management we used upper bounds to removes some arcs). In The American Steel Problem, the network has transshipment nodes and arcs don't exist between all nodes. However, arcs must travel from one node to another. In AMPL we ???LINK??? declare the set of NODES and the set of ARCS between nodes:

# The set of all nodes in the network
set NODES;

# The set of arcs in the network
set ARCS within NODES cross NODES;
Now we define bounds on the flow (of our goods) along each arc:
# The minimum and maximum flow allowed along the arcs
param Min {ARCS} integer, default 0;
param Max {(m, n) in ARCS} integer, >= Min[m, n], default Infinity;
and finally declare our Flow variables:
# The flow of goods to be sent across an arc
var Flow {(m, n) in ARCS} >= Min[m, n], <= Max[m, n], integer;

2. FORMULATE THE OBJECTIVE FUNCTION

The objective of transshipment problems in general and The American Steel Problem in particular is to minimise the cost of shipping goods through the network:

# The cost of shipping 1 unit of goods (per time unit)
param Cost {ARCS};

# Minimise the total shipping cost
minimize TotalCost:
  sum {(m, n) in ARCS} Cost[m, n] * Flow[m, n];

3. FORMULATE THE CONSTRAINTS

All the nodes have supply and demand, demand = 0 for supply nodes, supply = 0 for demand nodes and supply = demand = 0 for transshipment nodes. Also, the supply and demand amounts must be integer to ensure a naturally integer solution (i.e., linear programming will provide an integer optimal solution).

# Each node has a (non-negative, integer) supply and a (non-negative, integer) demand
# Note. supply nodes have demand = 0 and vice versa,
# transshipment nodes have supply = demand = 0
param Supply {NODES} >= 0, integer, default 0;
param Demand {NODES} >= 0, integer, default 0;

The only constraints in the transshipment problem are flow conservation constraints. These constraints simply state that the flow of goods into a node must be greater than the flow of goods out of a node.

# Must conserve flow in the network (goods cannot disappear!)
subject to ConserveFlow {n in NODES}:
  sum {m in NODES: (m, n) in ARCS} Flow[m, n] + Supply[n] =>
  sum {p in NODES: (n, p) in ARCS} Flow[n, p] + Demand[n];

For example, if a node has a supply of 10 units and has 10 units flowing in, then it can have no more than 20 units flowing out:

conserve_flow.jpg

Transshipment problems are often presented as a network formulation:

steel_formulation.jpg

4. IDENTIFY THE DATA

The nodes of The American Steel Problem can be easily ???LINK??? defined using a list :

set NODES := Youngstown  Pittsburgh
             Cincinnati 'Kansas City' Chicago
             Albany      Houston      Tempe   Gary ;
Note that Kansas City must be enclosed in ' and ' because of the whitespace in the name.

The arc set is 2-dimensional and can be ???LINK??? 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         +          +         +      -       -      -    +
Cincinnati         -          -         -      +       +      -    -
'Kansas City'      -          -         -      -       +      +    -
Chicago            -          -         -      -       -      +    + ;
# Array of arcs
set ARCS :=
(Youngstown, *)    Cincinnati 'Kansas City' Chicago Albany
(Pittsburgh, *)    Cincinnati 'Kansas City' Chicago Gary
.
.
.
(Chicago, *)       Tempe       Gary
 ;

We can choose lists, tables or arrays to define the parameters for The American Steel Problem, but in this case we will use a list and ???LINK??? define multiple parameters at once. This allows us to "cut-and-paste" the parameters from the problem description. Note the use of . for parameters where the defaults will suffice (e.g., Min['Youngstown', 'Albany']):

param:                          Cost    Min     Max:=
Youngstown      Albany          500     .       1000
Youngstown      Cincinnati      350     .       3000
Youngstown     'Kansas City'    450     1000    5000
Youngstown      Chicago         375     .       5000
Pittsburgh      Cincinnati      350     .       2000
Pittsburgh     'Kansas City'    450     2000    3000
Pittsburgh      Chicago         400     .       4000
Pittsburgh      Gary            450     .       2000
Cincinnati      Albany          350     1000    5000
Cincinnati      Houston         550     .       6000
'Kansas City'   Houston         375     .       4000
'Kansas City'   Tempe           650     .       4000
Chicago         Tempe           600     .       2000
Chicago         Gary            120     .       4000
 ;
Note that the cost is in $/1000 ton, so we must divide the cost by 1000 before solving:
let {(m, n) in ARCS} Cost[m, n] := Cost[m, n] / 1000;
|

Revision 92008-04-08 - MichaelOSullivan

Line: 1 to 1
 
META TOPICPARENT name="SubmitCaseStudy"
<-- Under Construction -->
Line: 84 to 84
 
FORM FIELD Title Title The American Steel Transshipment Problem
FORM FIELD DateSubmitted DateSubmitted 15 Feb 2008
FORM FIELD CaseStudyType CaseStudyType TeachingCaseStudy
Changed:
<
<
FORM FIELD OperationsResearchTopics OperationsResearchTopics
>
>
FORM FIELD OperationsResearchTopics OperationsResearchTopics LinearProgramming, IntegerProgramming, NetworkOptimisation
 
FORM FIELD ApplicationAreas ApplicationAreas Logistics
|*FORM FIELD ProblemDescription*|ProblemDescription|*THE AMERICAN STEEL PROBLEM*

American 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:

steel_network.jpg

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.

The table below presents the minimum and maximum flow amounts of steel that may be shipped between different cities along with the cost per 1000 ton/month of shipping the steel. For example, the shipment from Youngstown to Kansas City is contracted out to a railroad company with a minimal shipping clause of 1000 tons/month. However, the railroad cannot ship more then 5000 tons/month due the shortage of rail cars.

From node To node Cost Minimum Maximum
Youngstown Albany 500 - 1000
Youngstown Cincinnati 350 - 3000
Youngstown Kansas City 450 1000 5000
Youngstown Chicago 375 - 5000
Pittsburgh Cincinnati 350 - 2000
Pittsburgh Kansas City 450 2000 3000
Pittsburgh Chicago 400 - 4000
Pittsburgh Gary 450 - 2000
Cincinnati Albany 350 1000 5000
Cincinnati Houston 550 - 6000
Kansas City Houston 375 - 4000
Kansas City Tempe 650 - 4000
Chicago Tempe 600 - 2000
Chicago Gary 120 - 4000

The current monthly demand at American Steel’s four field warehouses is as follows:

Field Warehouses Monthly Demand
Albany, N.Y. 3000
Houston 7000
Tempe 4000
Gary 6000

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.| |*FORM FIELD ProblemFormulation*|ProblemFormulation|*1. IDENTIFY THE DECISION VARIABLES*

The decision variables for this problem are the same as for the transportation problem, the Flow of goods (cases of beer in The Beer Distribution Problem, tons of steels here) through the network. In ???LINK??? A Transportation Problem all arcs from the supply nodes to the demand nodes existed (although in ???LINK??? Forestry Management we used upper bounds to removes some arcs). In The American Steel Problem, the network has transshipment nodes and arcs don't exist between all nodes. However, arcs must travel from one node to another. In AMPL we ???LINK??? declare the set of NODES and the set of ARCS between nodes:

# The set of all nodes in the network
set NODES;

# The set of arcs in the network
set ARCS within NODES cross NODES;
Now we define bounds on the flow (of our goods) along each arc:
# The minimum and maximum flow allowed along the arcs
param Min {ARCS} integer, default 0;
param Max {(m, n) in ARCS} integer, >= Min[m, n], default Infinity;
and finally declare our Flow variables:
# The flow of goods to be sent across an arc
var Flow {(m, n) in ARCS} >= Min[m, n], <= Max[m, n], integer;

2. FORMULATE THE OBJECTIVE FUNCTION

The objective of transshipment problems in general and The American Steel Problem in particular is to minimise the cost of shipping goods through the network:

# The cost of shipping 1 unit of goods (per time unit)
param Cost {ARCS};

# Minimise the total shipping cost
minimize TotalCost:
  sum {(m, n) in ARCS} Cost[m, n] * Flow[m, n];

3. FORMULATE THE CONSTRAINTS

All the nodes have supply and demand, demand = 0 for supply nodes, supply = 0 for demand nodes and supply = demand = 0 for transshipment nodes. Also, the supply and demand amounts must be integer to ensure a naturally integer solution (i.e., linear programming will provide an integer optimal solution).

# Each node has a (non-negative, integer) supply and a (non-negative, integer) demand
# Note. supply nodes have demand = 0 and vice versa,
# transshipment nodes have supply = demand = 0
param Supply {NODES} >= 0, integer, default 0;
param Demand {NODES} >= 0, integer, default 0;

The only constraints in the transshipment problem are flow conservation constraints. These constraints simply state that the flow of goods into a node must be greater than the flow of goods out of a node.

# Must conserve flow in the network (goods cannot disappear!)
subject to ConserveFlow {n in NODES}:
  sum {m in NODES: (m, n) in ARCS} Flow[m, n] + Supply[n] =>
  sum {p in NODES: (n, p) in ARCS} Flow[n, p] + Demand[n];

For example, if a node has a supply of 10 units and has 10 units flowing in, then it can have no more than 20 units flowing out:

conserve_flow.jpg

Transshipment problems are often presented as a network formulation:

steel_formulation.jpg

4. IDENTIFY THE DATA

The nodes of The American Steel Problem can be easily ???LINK??? defined using a list :

set NODES := Youngstown  Pittsburgh
             Cincinnati 'Kansas City' Chicago
             Albany      Houston      Tempe   Gary ;
Note that Kansas City must be enclosed in ' and ' because of the whitespace in the name.

The arc set is 2-dimensional and can be ???LINK??? 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         +          +         +      -       -      -    +
Cincinnati         -          -         -      +       +      -    -
'Kansas City'      -          -         -      -       +      +    -
Chicago            -          -         -      -       -      +    + ;
# Array of arcs
set ARCS :=
(Youngstown, *)    Cincinnati 'Kansas City' Chicago Albany
(Pittsburgh, *)    Cincinnati 'Kansas City' Chicago Gary
.
.
.
(Chicago, *)       Tempe       Gary
 ;

We can choose lists, tables or arrays to define the parameters for The American Steel Problem, but in this case we will use a list and ???LINK??? define multiple parameters at once. This allows us to "cut-and-paste" the parameters from the problem description. Note the use of . for parameters where the defaults will suffice (e.g., Min['Youngstown', 'Albany']):

param:                          Cost    Min     Max:=
Youngstown      Albany          500     .       1000
Youngstown      Cincinnati      350     .       3000
Youngstown     'Kansas City'    450     1000    5000
Youngstown      Chicago         375     .       5000
Pittsburgh      Cincinnati      350     .       2000
Pittsburgh     'Kansas City'    450     2000    3000
Pittsburgh      Chicago         400     .       4000
Pittsburgh      Gary            450     .       2000
Cincinnati      Albany          350     1000    5000
Cincinnati      Houston         550     .       6000
'Kansas City'   Houston         375     .       4000
'Kansas City'   Tempe           650     .       4000
Chicago         Tempe           600     .       2000
Chicago         Gary            120     .       4000
 ;
Note that the cost is in $/1000 ton, so we must divide the cost by 1000 before solving:
let {(m, n) in ARCS} Cost[m, n] := Cost[m, n] / 1000;
|

Revision 82008-04-02 - TWikiAdminUser

Line: 1 to 1
 
META TOPICPARENT name="SubmitCaseStudy"
<-- Under Construction -->
Line: 40 to 40
  Return to top
Changed:
<
<

Computational Model

>
>

Computational Model

 

<--/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 Kansas City must be enclosed in ' and ' because of the whitespace in the name.

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 ARCS:

set ARCS:   Cincinnati 'Kansas City' Chicago Albany Houston Tempe Gary :=
Youngstown         +          +         +      +       -      -    -
Pittsburgh         +          +         +      -       -      -    +
Cincinnati         -          -         -      +       +      -    -
'Kansas City'      -          -         -      -       +      +    -
Chicago            -          -         -      -       -      +    + ;

The NetDemand can be defined easily from the supply and demand. Since the default is 0 we don't need to define NetDemand for the transshipment nodes:

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 . for parameters where the defaults will suffice (e.g., Lower for Youngstown and Albany):

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-->
Line: 48 to 48
  Return to top
Changed:
<
<

Results

>
>

Results

 

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:

steel_solution.jpg

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 transshipment.mod we check that sum {n in NODES} NetDemand[n] <= 0 to ensure a problem is feasible before solving.

If total supply is less than demand (hence the problem is infeasible) we can add a dummy supply node (see with arcs to all the demand nodes. The optimal solution will show the "best" nodes to send the extra supply to.

Line: 56 to 56
  Return to top
Changed:
<
<

Conclusions

>
>

Conclusions

 

In order to minimise the monthly shipment costs, American Steel should follow the shipment plan shown in Table 3.

Table 3 Optimal Shipment Plan

From/To Cincinnati Kansas City Chicago Albany Houston Tempe Gary
Youngstown 3000 3000 3000 1000      
Pittsburgh 2000 3000 3000       2000
Cincinnati       2000 3000    
Kansas City         4000 2000  
Chicago           2000 4000

As with many network problems, it can be illuminating to display the solution graphically as shown in Figure 1.

Figure 1 Optimal Shipment Plan

steel_graphical.jpg

Revision 72008-03-01 - TWikiAdminUser

Line: 1 to 1
 
META TOPICPARENT name="SubmitCaseStudy"
<-- Under Construction -->
Line: 26 to 26
 

Operations Research Topics: LinearProgramming, IntegerProgramming, NetworkOptimisation, TransshipmentProblem

Application Areas: Logistics

Contents

Changed:
<
<
>
>
 

Problem Description

American 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:

steel_network.jpg

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 cost per 1000 ton/month of shipping the steel. For example, the shipment from Youngstown to Kansas City is contracted out to a railroad company with a minimal shipping clause of 1000 tons/month. However, the railroad cannot ship more than 5000 tons/month due the shortage of rail cars.

Table 1 Arc Costs and Limits

From node To node Cost Minimum Maximum
Youngstown Albany 500 - 1000
Youngstown Cincinnati 350 - 3000
Youngstown Kansas City 450 1000 5000
Youngstown Chicago 375 - 5000
Pittsburgh Cincinnati 350 - 2000
Pittsburgh Kansas City 450 2000 3000
Pittsburgh Chicago 400 - 4000
Pittsburgh Gary 450 - 2000
Cincinnati Albany 350 1000 5000
Cincinnati Houston 550 - 6000
Kansas City Houston 375 - 4000
Kansas City Tempe 650 - 4000
Chicago Tempe 600 - 2000
Chicago Gary 120 - 4000

The current monthly demand at American Steel's four field warehouses is shown in Table 2.

Table 2 Monthly Demands

Field Warehouses Monthly Demand
Albany, N.Y. 3000
Houston 7000
Tempe 4000
Gary 6000

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).

steel_formulation.jpg

  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 Kansas City must be enclosed in ' and ' because of the whitespace in the name.

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 ARCS:

set ARCS:   Cincinnati 'Kansas City' Chicago Albany Houston Tempe Gary :=
Youngstown         +          +         +      +       -      -    -
Pittsburgh         +          +         +      -       -      -    +
Cincinnati         -          -         -      +       +      -    -
'Kansas City'      -          -         -      -       +      +    -
Chicago            -          -         -      -       -      +    + ;

The NetDemand can be defined easily from the supply and demand. Since the default is 0 we don't need to define NetDemand for the transshipment nodes:

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 . for parameters where the defaults will suffice (e.g., Lower for Youngstown and Albany):

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:

steel_solution.jpg

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 transshipment.mod we check that sum {n in NODES} NetDemand[n] <= 0 to ensure a problem is feasible before solving.

If total supply is less than demand (hence the problem is infeasible) we can add a dummy supply node (see with arcs to all the demand nodes. The optimal solution will show the "best" nodes to send the extra supply to.

  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.

Table 3 Optimal Shipment Plan

From/To Cincinnati Kansas City Chicago Albany Houston Tempe Gary
Youngstown 3000 3000 3000 1000      
Pittsburgh 2000 3000 3000       2000
Cincinnati       2000 3000    
Kansas City         4000 2000  
Chicago           2000 4000

As with many network problems, it can be illuminating to display the solution graphically as shown in Figure 1.

Figure 1 Optimal Shipment Plan

steel_graphical.jpg

  Return to top

Changed:
<
<
>
>
<--

-->

 

Changed:
<
<
>
>
<--
  1. Solve the American Steel Transshipment Problem. Write a management summary of your solution.

    What to hand in Hand in your management summary.

-->
 

Revision 62008-03-01 - TWikiAdminUser

Line: 1 to 1
 
META TOPICPARENT name="SubmitCaseStudy"
<-- Under Construction -->
Line: 26 to 26
 

Operations Research Topics: LinearProgramming, IntegerProgramming, NetworkOptimisation, TransshipmentProblem

Application Areas: Logistics

Contents

Changed:
<
<

>
>
 

Problem Description

American 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:

steel_network.jpg

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 cost per 1000 ton/month of shipping the steel. For example, the shipment from Youngstown to Kansas City is contracted out to a railroad company with a minimal shipping clause of 1000 tons/month. However, the railroad cannot ship more than 5000 tons/month due the shortage of rail cars.

Table 1 Arc Costs and Limits

From node To node Cost Minimum Maximum
Youngstown Albany 500 - 1000
Youngstown Cincinnati 350 - 3000
Youngstown Kansas City 450 1000 5000
Youngstown Chicago 375 - 5000
Pittsburgh Cincinnati 350 - 2000
Pittsburgh Kansas City 450 2000 3000
Pittsburgh Chicago 400 - 4000
Pittsburgh Gary 450 - 2000
Cincinnati Albany 350 1000 5000
Cincinnati Houston 550 - 6000
Kansas City Houston 375 - 4000
Kansas City Tempe 650 - 4000
Chicago Tempe 600 - 2000
Chicago Gary 120 - 4000

The current monthly demand at American Steel's four field warehouses is shown in Table 2.

Table 2 Monthly Demands

Field Warehouses Monthly Demand
Albany, N.Y. 3000
Houston 7000
Tempe 4000
Gary 6000

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.

Return to top

Changed:
<
<

Problem Formulation

>
>

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).

steel_formulation.jpg

>
>
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=

 
Changed:
<
<
Return to top

Computational Model

>
>
Return to top
 
Changed:
<
<
<--/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 Kansas City must be enclosed in ' and ' because of the whitespace in the name.

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 ARCS:

set ARCS:   Cincinnati 'Kansas City' Chicago Albany Houston Tempe Gary :=
Youngstown         +          +         +      +       -      -    -
Pittsburgh         +          +         +      -       -      -    +
Cincinnati         -          -         -      +       +      -    -
'Kansas City'      -          -         -      -       +      +    -
Chicago            -          -         -      -       -      +    + ;

The NetDemand can be defined easily from the supply and demand. Since the default is 0 we don't need to define NetDemand for the transshipment nodes:

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 . for parameters where the defaults will suffice (e.g., Lower for Youngstown and Albany):

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-->
>
>

Computational Model

 
Changed:
<
<
Return to top

Results

>
>
<div class=
 
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:

steel_solution.jpg

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 transshipment.mod we check that sum {n in NODES} NetDemand[n] <= 0 to ensure a problem is feasible before solving.

If total supply is less than demand (hence the problem is infeasible) we can add a dummy supply node (see with arcs to all the demand nodes. The optimal solution will show the "best" nodes to send the extra supply to.

>
>
Return to top
 
Changed:
<
<
Return to top

Conclusions

>
>

Results

 
Changed:
<
<
In order to minimise the monthly shipment costs, American Steel should follow the shipment plan shown in Table 3.

Table 3 Optimal Shipment Plan

From/To Cincinnati Kansas City Chicago Albany Houston Tempe Gary
Youngstown 3000 3000 3000 1000      
Pittsburgh 2000 3000 3000       2000
Cincinnati       2000 3000    
Kansas City         4000 2000  
Chicago           2000 4000

As with many network problems, it can be illuminating to display the solution graphically as shown in Figure 1.

Figure 1 Optimal Shipment Plan

steel_graphical.jpg

>
>
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=

 
Changed:
<
<
Return to top
>
>
Return to top

Conclusions

In order to minimise the monthly shipment costs, American Steel should follow the shipment plan shown in Table 3.

<a name=

Return to top

 
Changed:
<
<
>
>
 
Changed:
<
<
>
>
 
Changed:
<
<
>
>
 
Changed:
<
<

Student Tasks

>
>
 
Changed:
<
<
  1. Solve the American Steel Transshipment Problem. Write a management summary of your solution.

    What to hand in Hand in your management summary.

>
>
 
Changed:
<
<
Return to top
>
>
 
META FORM name="OpsRes.CaseStudyForm"
FORM FIELD Title Title The American Steel Transshipment Problem
FORM FIELD DateSubmitted DateSubmitted 15 Feb 2008
Added:
>
>
FORM FIELD CaseStudyType CaseStudyType TeachingCaseStudy
 
FORM FIELD OperationsResearchTopics OperationsResearchTopics
FORM FIELD ApplicationAreas ApplicationAreas Logistics
|*FORM FIELD ProblemDescription*|ProblemDescription|*THE AMERICAN STEEL PROBLEM*

American 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:

steel_network.jpg

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.

The table below presents the minimum and maximum flow amounts of steel that may be shipped between different cities along with the cost per 1000 ton/month of shipping the steel. For example, the shipment from Youngstown to Kansas City is contracted out to a railroad company with a minimal shipping clause of 1000 tons/month. However, the railroad cannot ship more then 5000 tons/month due the shortage of rail cars.

From node To node Cost Minimum Maximum
Youngstown Albany 500 - 1000
Youngstown Cincinnati 350 - 3000
Youngstown Kansas City 450 1000 5000
Youngstown Chicago 375 - 5000
Pittsburgh Cincinnati 350 - 2000
Pittsburgh Kansas City 450 2000 3000
Pittsburgh Chicago 400 - 4000
Pittsburgh Gary 450 - 2000
Cincinnati Albany 350 1000 5000
Cincinnati Houston 550 - 6000
Kansas City Houston 375 - 4000
Kansas City Tempe 650 - 4000
Chicago Tempe 600 - 2000
Chicago Gary 120 - 4000

The current monthly demand at American Steel’s four field warehouses is as follows:

Field Warehouses Monthly Demand
Albany, N.Y. 3000
Houston 7000
Tempe 4000
Gary 6000

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.|

Revision 52008-02-28 - MichaelOSullivan

Line: 1 to 1
 
META TOPICPARENT name="SubmitCaseStudy"
<-- Under Construction -->
Line: 73 to 73
 Return to top

META FORM name="OpsRes.CaseStudyForm"
Changed:
<
<
FORM FIELD Title Title ATransshipmentProblem
>
>
FORM FIELD Title Title The American Steel Transshipment Problem
 
FORM FIELD DateSubmitted DateSubmitted 15 Feb 2008
FORM FIELD OperationsResearchTopics OperationsResearchTopics
FORM FIELD ApplicationAreas ApplicationAreas Logistics
Line: 93 to 93
 
META FILEATTACHMENT attachment="steel_rhs.jpg" attr="" comment="" date="1203066590" name="steel_rhs.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_rhs.jpg" size="93278" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_rhs.jpg" tmpFilename="" user="BaseUserMapping_333" version="1"
META FILEATTACHMENT attachment="steel_sensitivity.jpg" attr="" comment="" date="1203066683" name="steel_sensitivity.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_sensitivity.jpg" size="93137" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_sensitivity.jpg" tmpFilename="" user="BaseUserMapping_333" version="1"
META FILEATTACHMENT attachment="steel_solution.jpg" attr="" comment="" date="1203066761" name="steel_solution.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_solution.jpg" size="38501" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_solution.jpg" tmpFilename="" user="BaseUserMapping_333" version="1"
Added:
>
>
META TOPICMOVED by="MichaelOSullivan" date="1204231417" from="OpsRes.ATransshipmentProblem" to="OpsRes.AmericanSteelTransshipmentProblem"

Revision 42008-02-23 - MichaelOSullivan

Line: 1 to 1
 
META TOPICPARENT name="SubmitCaseStudy"
Added:
>
>
<-- Under Construction -->
 
Changed:
<
<
%BEGINLATEXPREAMBLE% \usepackage{amsmath}
>
>
%BEGINLATEXPREAMBLE% \usepackage{amsmath}
 %ENDLATEXPREAMBLE%

Case Study: The American Steel Transshipment Problem

Revision 32008-02-16 - TWikiAdminUser

Line: 1 to 1
 
META TOPICPARENT name="SubmitCaseStudy"
Deleted:
<
<

<--
This topic can only be changed by:  
-->
 
Changed:
<
<

The American Steel Transshipment Problem

>
>
<--
This topic can only be changed by:  
-->

Case Study: The American Steel Transshipment Problem

 

Submitted: 15 Feb 2008

Changed:
<
<

Operations Research Areas:

>
>

Operations Research Topics: LinearProgramming, IntegerProgramming, NetworkOptimisation, TransshipmentProblem

 

Application Areas: Logistics

Changed:
<
<

Problem Description

>
>

Contents

Problem Description

 American 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:

steel_network.jpg

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 cost per 1000 ton/month of shipping the steel. For example, the shipment from Youngstown to Kansas City is contracted out to a railroad company with a minimal shipping clause of 1000 tons/month. However, the railroad cannot ship more than 5000 tons/month due the shortage of rail cars.

Table 1 Arc Costs and Limits

From node To node Cost Minimum Maximum
Youngstown Albany 500 - 1000
Youngstown Cincinnati 350 - 3000
Youngstown Kansas City 450 1000 5000
Youngstown Chicago 375 - 5000
Pittsburgh Cincinnati 350 - 2000
Pittsburgh Kansas City 450 2000 3000
Pittsburgh Chicago 400 - 4000
Pittsburgh Gary 450 - 2000
Cincinnati Albany 350 1000 5000
Cincinnati Houston 550 - 6000
Kansas City Houston 375 - 4000
Kansas City Tempe 650 - 4000
Chicago Tempe 600 - 2000
Chicago Gary 120 - 4000

The current monthly demand at American Steel's four field warehouses is shown in Table 2.

Table 2 Monthly Demands

Field Warehouses Monthly Demand
Albany, N.Y. 3000
Houston 7000
Tempe 4000
Gary 6000

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.

Changed:
<
<

Problem Formulation

>
>
Return to top

Problem Formulation

  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).

steel_formulation.jpg

Changed:
<
<

Computational Model

>
>
Return to top

Computational Model

 
<--/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 Kansas City must be enclosed in ' and ' because of the whitespace in the name.

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 ARCS:

set ARCS:   Cincinnati 'Kansas City' Chicago Albany Houston Tempe Gary :=
Youngstown         +          +         +      +       -      -    -
Pittsburgh         +          +         +      -       -      -    +
Cincinnati         -          -         -      +       +      -    -
'Kansas City'      -          -         -      -       +      +    -
Chicago            -          -         -      -       -      +    + ;

The NetDemand can be defined easily from the supply and demand. Since the default is 0 we don't need to define NetDemand for the transshipment nodes:

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 . for parameters where the defaults will suffice (e.g., Lower for Youngstown and Albany):

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-->
Changed:
<
<

Results

>
>
Return to top

Results

 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:

steel_solution.jpg

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 transshipment.mod we check that sum {n in NODES} NetDemand[n] <= 0 to ensure a problem is feasible before solving.

If total supply is less than demand (hence the problem is infeasible) we can add a dummy supply node (see with arcs to all the demand nodes. The optimal solution will show the "best" nodes to send the extra supply to.

Changed:
<
<

Conclusions

>
>
Return to top

Conclusions

  In order to minimise the monthly shipment costs, American Steel should follow the shipment plan shown in Table 3.

Table 3 Optimal Shipment Plan

From/To Cincinnati Kansas City Chicago Albany Houston Tempe Gary
Youngstown 3000 3000 3000 1000      
Pittsburgh 2000 3000 3000       2000
Cincinnati       2000 3000    
Kansas City         4000 2000  
Chicago           2000 4000

As with many network problems, it can be illuminating to display the solution graphically as shown in Figure 1.

Figure 1 Optimal Shipment Plan

steel_graphical.jpg

Changed:
<
<
>
>
Return to top
 
Changed:
<
<

Student Tasks

>
>

Student Tasks

 
  1. Solve the American Steel Transshipment Problem. Write a management summary of your solution.

    What to hand in Hand in your management summary.

Added:
>
>
Return to top
 
META FORM name="OpsRes.CaseStudyForm"
FORM FIELD Title Title ATransshipmentProblem
FORM FIELD DateSubmitted DateSubmitted 15 Feb 2008
Changed:
<
<
FORM FIELD OperationsResearchAreas OperationsResearchAreas Linear Programming, Integer Programming
>
>
FORM FIELD OperationsResearchTopics OperationsResearchTopics
 
FORM FIELD ApplicationAreas ApplicationAreas Logistics
|*FORM FIELD ProblemDescription*|ProblemDescription|*THE AMERICAN STEEL PROBLEM*

American 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:

steel_network.jpg

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.

The table below presents the minimum and maximum flow amounts of steel that may be shipped between different cities along with the cost per 1000 ton/month of shipping the steel. For example, the shipment from Youngstown to Kansas City is contracted out to a railroad company with a minimal shipping clause of 1000 tons/month. However, the railroad cannot ship more then 5000 tons/month due the shortage of rail cars.

From node To node Cost Minimum Maximum
Youngstown Albany 500 - 1000
Youngstown Cincinnati 350 - 3000
Youngstown Kansas City 450 1000 5000
Youngstown Chicago 375 - 5000
Pittsburgh Cincinnati 350 - 2000
Pittsburgh Kansas City 450 2000 3000
Pittsburgh Chicago 400 - 4000
Pittsburgh Gary 450 - 2000
Cincinnati Albany 350 1000 5000
Cincinnati Houston 550 - 6000
Kansas City Houston 375 - 4000
Kansas City Tempe 650 - 4000
Chicago Tempe 600 - 2000
Chicago Gary 120 - 4000

The current monthly demand at American Steel’s four field warehouses is as follows:

Field Warehouses Monthly Demand
Albany, N.Y. 3000
Houston 7000
Tempe 4000
Gary 6000

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.| |*FORM FIELD ProblemFormulation*|ProblemFormulation|*1. IDENTIFY THE DECISION VARIABLES*

The decision variables for this problem are the same as for the transportation problem, the Flow of goods (cases of beer in The Beer Distribution Problem, tons of steels here) through the network. In ???LINK??? A Transportation Problem all arcs from the supply nodes to the demand nodes existed (although in ???LINK??? Forestry Management we used upper bounds to removes some arcs). In The American Steel Problem, the network has transshipment nodes and arcs don't exist between all nodes. However, arcs must travel from one node to another. In AMPL we ???LINK??? declare the set of NODES and the set of ARCS between nodes:

# The set of all nodes in the network
set NODES;

# The set of arcs in the network
set ARCS within NODES cross NODES;
Now we define bounds on the flow (of our goods) along each arc:
# The minimum and maximum flow allowed along the arcs
param Min {ARCS} integer, default 0;
param Max {(m, n) in ARCS} integer, >= Min[m, n], default Infinity;
and finally declare our Flow variables:
# The flow of goods to be sent across an arc
var Flow {(m, n) in ARCS} >= Min[m, n], <= Max[m, n], integer;

2. FORMULATE THE OBJECTIVE FUNCTION

The objective of transshipment problems in general and The American Steel Problem in particular is to minimise the cost of shipping goods through the network:

# The cost of shipping 1 unit of goods (per time unit)
param Cost {ARCS};

# Minimise the total shipping cost
minimize TotalCost:
  sum {(m, n) in ARCS} Cost[m, n] * Flow[m, n];

3. FORMULATE THE CONSTRAINTS

All the nodes have supply and demand, demand = 0 for supply nodes, supply = 0 for demand nodes and supply = demand = 0 for transshipment nodes. Also, the supply and demand amounts must be integer to ensure a naturally integer solution (i.e., linear programming will provide an integer optimal solution).

# Each node has a (non-negative, integer) supply and a (non-negative, integer) demand
# Note. supply nodes have demand = 0 and vice versa,
# transshipment nodes have supply = demand = 0
param Supply {NODES} >= 0, integer, default 0;
param Demand {NODES} >= 0, integer, default 0;

The only constraints in the transshipment problem are flow conservation constraints. These constraints simply state that the flow of goods into a node must be greater than the flow of goods out of a node.

# Must conserve flow in the network (goods cannot disappear!)
subject to ConserveFlow {n in NODES}:
  sum {m in NODES: (m, n) in ARCS} Flow[m, n] + Supply[n] =>
  sum {p in NODES: (n, p) in ARCS} Flow[n, p] + Demand[n];

For example, if a node has a supply of 10 units and has 10 units flowing in, then it can have no more than 20 units flowing out:

conserve_flow.jpg

Transshipment problems are often presented as a network formulation:

steel_formulation.jpg

4. IDENTIFY THE DATA

The nodes of The American Steel Problem can be easily ???LINK??? defined using a list :

set NODES := Youngstown  Pittsburgh
             Cincinnati 'Kansas City' Chicago
             Albany      Houston      Tempe   Gary ;
Note that Kansas City must be enclosed in ' and ' because of the whitespace in the name.

The arc set is 2-dimensional and can be ???LINK??? 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         +          +         +      -       -      -    +
Cincinnati         -          -         -      +       +      -    -
'Kansas City'      -          -         -      -       +      +    -
Chicago            -          -         -      -       -      +    + ;
# Array of arcs
set ARCS :=
(Youngstown, *)    Cincinnati 'Kansas City' Chicago Albany
(Pittsburgh, *)    Cincinnati 'Kansas City' Chicago Gary
.
.
.
(Chicago, *)       Tempe       Gary
 ;

We can choose lists, tables or arrays to define the parameters for The American Steel Problem, but in this case we will use a list and ???LINK??? define multiple parameters at once. This allows us to "cut-and-paste" the parameters from the problem description. Note the use of . for parameters where the defaults will suffice (e.g., Min['Youngstown', 'Albany']):

param:                          Cost    Min     Max:=
Youngstown      Albany          500     .       1000
Youngstown      Cincinnati      350     .       3000
Youngstown     'Kansas City'    450     1000    5000
Youngstown      Chicago         375     .       5000
Pittsburgh      Cincinnati      350     .       2000
Pittsburgh     'Kansas City'    450     2000    3000
Pittsburgh      Chicago         400     .       4000
Pittsburgh      Gary            450     .       2000
Cincinnati      Albany          350     1000    5000
Cincinnati      Houston         550     .       6000
'Kansas City'   Houston         375     .       4000
'Kansas City'   Tempe           650     .       4000
Chicago         Tempe           600     .       2000
Chicago         Gary            120     .       4000
 ;
Note that the cost is in $/1000 ton, so we must divide the cost by 1000 before solving:
let {(m, n) in ARCS} Cost[m, n] := Cost[m, n] / 1000;
|

Revision 22008-02-15 - TWikiAdminUser

Line: 1 to 1
 
META TOPICPARENT name="SubmitCaseStudy"

Revision 12008-02-15 - TWikiAdminUser

Line: 1 to 1
Added:
>
>
META TOPICPARENT name="SubmitCaseStudy"

<--
This topic can only be changed by:  
-->

<--
This template controls both the look and functionality of case study topics.
You should not need to alter the layout, only edit the data using the form above.

Set the view and edit templates: Comment out the next line to use the TWiki default view

Comment out the next line to use the TWiki default edit -->

The American Steel Transshipment Problem

Submitted: 15 Feb 2008

Operations Research Areas:

Application Areas: Logistics

Problem Description

American 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:

steel_network.jpg

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 cost per 1000 ton/month of shipping the steel. For example, the shipment from Youngstown to Kansas City is contracted out to a railroad company with a minimal shipping clause of 1000 tons/month. However, the railroad cannot ship more than 5000 tons/month due the shortage of rail cars.

Table 1 Arc Costs and Limits

From node To node Cost Minimum Maximum
Youngstown Albany 500 - 1000
Youngstown Cincinnati 350 - 3000
Youngstown Kansas City 450 1000 5000
Youngstown Chicago 375 - 5000
Pittsburgh Cincinnati 350 - 2000
Pittsburgh Kansas City 450 2000 3000
Pittsburgh Chicago 400 - 4000
Pittsburgh Gary 450 - 2000
Cincinnati Albany 350 1000 5000
Cincinnati Houston 550 - 6000
Kansas City Houston 375 - 4000
Kansas City Tempe 650 - 4000
Chicago Tempe 600 - 2000
Chicago Gary 120 - 4000

The current monthly demand at American Steel's four field warehouses is shown in Table 2.

Table 2 Monthly Demands

Field Warehouses Monthly Demand
Albany, N.Y. 3000
Houston 7000
Tempe 4000
Gary 6000

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.

Problem Formulation

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).

steel_formulation.jpg

Computational Model

<--/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 Kansas City must be enclosed in ' and ' because of the whitespace in the name.

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 ARCS:

set ARCS:   Cincinnati 'Kansas City' Chicago Albany Houston Tempe Gary :=
Youngstown         +          +         +      +       -      -    -
Pittsburgh         +          +         +      -       -      -    +
Cincinnati         -          -         -      +       +      -    -
'Kansas City'      -          -         -      -       +      +    -
Chicago            -          -         -      -       -      +    + ;

The NetDemand can be defined easily from the supply and demand. Since the default is 0 we don't need to define NetDemand for the transshipment nodes:

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 . for parameters where the defaults will suffice (e.g., Lower for Youngstown and Albany):

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-->

Results

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:

steel_solution.jpg

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 transshipment.mod we check that sum {n in NODES} NetDemand[n] <= 0 to ensure a problem is feasible before solving.

If total supply is less than demand (hence the problem is infeasible) we can add a dummy supply node (see with arcs to all the demand nodes. The optimal solution will show the "best" nodes to send the extra supply to.

Conclusions

In order to minimise the monthly shipment costs, American Steel should follow the shipment plan shown in Table 3.

Table 3 Optimal Shipment Plan

From/To Cincinnati Kansas City Chicago Albany Houston Tempe Gary
Youngstown 3000 3000 3000 1000      
Pittsburgh 2000 3000 3000       2000
Cincinnati       2000 3000    
Kansas City         4000 2000  
Chicago           2000 4000

As with many network problems, it can be illuminating to display the solution graphically as shown in Figure 1.

Figure 1 Optimal Shipment Plan

steel_graphical.jpg

Student Tasks

  1. Solve the American Steel Transshipment Problem. Write a management summary of your solution.

    What to hand in Hand in your management summary.

META FORM name="OpsRes.CaseStudyForm"
FORM FIELD Title Title ATransshipmentProblem
FORM FIELD DateSubmitted DateSubmitted 15 Feb 2008
FORM FIELD OperationsResearchAreas OperationsResearchAreas Linear Programming, Integer Programming
FORM FIELD ApplicationAreas ApplicationAreas Logistics
|*FORM FIELD ProblemDescription*|ProblemDescription|*THE AMERICAN STEEL PROBLEM*

American 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:

steel_network.jpg

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.

The table below presents the minimum and maximum flow amounts of steel that may be shipped between different cities along with the cost per 1000 ton/month of shipping the steel. For example, the shipment from Youngstown to Kansas City is contracted out to a railroad company with a minimal shipping clause of 1000 tons/month. However, the railroad cannot ship more then 5000 tons/month due the shortage of rail cars.

From node To node Cost Minimum Maximum
Youngstown Albany 500 - 1000
Youngstown Cincinnati 350 - 3000
Youngstown Kansas City 450 1000 5000
Youngstown Chicago 375 - 5000
Pittsburgh Cincinnati 350 - 2000
Pittsburgh Kansas City 450 2000 3000
Pittsburgh Chicago 400 - 4000
Pittsburgh Gary 450 - 2000
Cincinnati Albany 350 1000 5000
Cincinnati Houston 550 - 6000
Kansas City Houston 375 - 4000
Kansas City Tempe 650 - 4000
Chicago Tempe 600 - 2000
Chicago Gary 120 - 4000

The current monthly demand at American Steel’s four field warehouses is as follows:

Field Warehouses Monthly Demand
Albany, N.Y. 3000
Houston 7000
Tempe 4000
Gary 6000

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.| |*FORM FIELD ProblemFormulation*|ProblemFormulation|*1. IDENTIFY THE DECISION VARIABLES*

The decision variables for this problem are the same as for the transportation problem, the Flow of goods (cases of beer in The Beer Distribution Problem, tons of steels here) through the network. In ???LINK??? A Transportation Problem all arcs from the supply nodes to the demand nodes existed (although in ???LINK??? Forestry Management we used upper bounds to removes some arcs). In The American Steel Problem, the network has transshipment nodes and arcs don't exist between all nodes. However, arcs must travel from one node to another. In AMPL we ???LINK??? declare the set of NODES and the set of ARCS between nodes:

# The set of all nodes in the network
set NODES;

# The set of arcs in the network
set ARCS within NODES cross NODES;
Now we define bounds on the flow (of our goods) along each arc:
# The minimum and maximum flow allowed along the arcs
param Min {ARCS} integer, default 0;
param Max {(m, n) in ARCS} integer, >= Min[m, n], default Infinity;
and finally declare our Flow variables:
# The flow of goods to be sent across an arc
var Flow {(m, n) in ARCS} >= Min[m, n], <= Max[m, n], integer;

2. FORMULATE THE OBJECTIVE FUNCTION

The objective of transshipment problems in general and The American Steel Problem in particular is to minimise the cost of shipping goods through the network:

# The cost of shipping 1 unit of goods (per time unit)
param Cost {ARCS};

# Minimise the total shipping cost
minimize TotalCost:
  sum {(m, n) in ARCS} Cost[m, n] * Flow[m, n];

3. FORMULATE THE CONSTRAINTS

All the nodes have supply and demand, demand = 0 for supply nodes, supply = 0 for demand nodes and supply = demand = 0 for transshipment nodes. Also, the supply and demand amounts must be integer to ensure a naturally integer solution (i.e., linear programming will provide an integer optimal solution).

# Each node has a (non-negative, integer) supply and a (non-negative, integer) demand
# Note. supply nodes have demand = 0 and vice versa,
# transshipment nodes have supply = demand = 0
param Supply {NODES} >= 0, integer, default 0;
param Demand {NODES} >= 0, integer, default 0;

The only constraints in the transshipment problem are flow conservation constraints. These constraints simply state that the flow of goods into a node must be greater than the flow of goods out of a node.

# Must conserve flow in the network (goods cannot disappear!)
subject to ConserveFlow {n in NODES}:
  sum {m in NODES: (m, n) in ARCS} Flow[m, n] + Supply[n] =>
  sum {p in NODES: (n, p) in ARCS} Flow[n, p] + Demand[n];

For example, if a node has a supply of 10 units and has 10 units flowing in, then it can have no more than 20 units flowing out:

conserve_flow.jpg

Transshipment problems are often presented as a network formulation:

steel_formulation.jpg

4. IDENTIFY THE DATA

The nodes of The American Steel Problem can be easily ???LINK??? defined using a list :

set NODES := Youngstown  Pittsburgh
             Cincinnati 'Kansas City' Chicago
             Albany      Houston      Tempe   Gary ;
Note that Kansas City must be enclosed in ' and ' because of the whitespace in the name.

The arc set is 2-dimensional and can be ???LINK??? 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         +          +         +      -       -      -    +
Cincinnati         -          -         -      +       +      -    -
'Kansas City'      -          -         -      -       +      +    -
Chicago            -          -         -      -       -      +    + ;
# Array of arcs
set ARCS :=
(Youngstown, *)    Cincinnati 'Kansas City' Chicago Albany
(Pittsburgh, *)    Cincinnati 'Kansas City' Chicago Gary
.
.
.
(Chicago, *)       Tempe       Gary
 ;

We can choose lists, tables or arrays to define the parameters for The American Steel Problem, but in this case we will use a list and ???LINK??? define multiple parameters at once. This allows us to "cut-and-paste" the parameters from the problem description. Note the use of . for parameters where the defaults will suffice (e.g., Min['Youngstown', 'Albany']):

param:                          Cost    Min     Max:=
Youngstown      Albany          500     .       1000
Youngstown      Cincinnati      350     .       3000
Youngstown     'Kansas City'    450     1000    5000
Youngstown      Chicago         375     .       5000
Pittsburgh      Cincinnati      350     .       2000
Pittsburgh     'Kansas City'    450     2000    3000
Pittsburgh      Chicago         400     .       4000
Pittsburgh      Gary            450     .       2000
Cincinnati      Albany          350     1000    5000
Cincinnati      Houston         550     .       6000
'Kansas City'   Houston         375     .       4000
'Kansas City'   Tempe           650     .       4000
Chicago         Tempe           600     .       2000
Chicago         Gary            120     .       4000
 ;
Note that the cost is in $/1000 ton, so we must divide the cost by 1000 before solving:
let {(m, n) in ARCS} Cost[m, n] := Cost[m, n] / 1000;
|
FORM FIELD ComputationalModel ComputationalModel The computational model...
|*FORM FIELD Results*|Results|Implementing the usual script file with transshipment.mod and steel.dat (with the Cost modification) gives us the optimal Flow variables:

steel_solution.jpg

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). If total supply is less than demand, then the problem becomes infeasible! Even in the case of infeasibility, it is preferable to solve the transshipment problem using a dummy supply node so that we can analyse where there is a shortfall in demand. We can balance the problem by either adding a dummy supply node with arcs to all the demand nodes or adding a dummy demand node with arcs from all the supply nodes: balance_transshipment.mod

# The following parameters are needed to use balance_transshipment.run
param difference;
param dummyDemandCost {NODES};
param dummySupplyCost {NODES};
balance_transshipment.run
let difference := (sum {s in NODES} Supply[s])
                - (sum {d in NODES} Demand[d]);
             
let NODES := NODES union {'Dummy'};             
if difference > 0 then
{
  print "Total Supply > Total Demand";
  print "Solving with dummy supply node...";
  let Demand['Dummy'] := difference;
  for {n in NODES : Supply[n] > 0} {
    let ARCS := ARCS union {(n, 'Dummy')};
    let Cost[n, 'Dummy'] := dummyDemandCost[n];
  }
}
else if difference < 0 then
{
  print "WARNING: Total Supply < Total Demand, problem is infeasible!";
  print "Solving with dummy demand node...";
  let Demand['Dummy'] := - difference;
  for {n in NODES : Demand[n] > 0} {
    let ARCS := ARCS union {('Dummy', n)};
    let Cost['Dummy', n] := dummySupplyCost[n];
  }
}; # else the problem is balanced
steel.run
# steel.run
#
# Written by Mike O'Sullivan & Cameron Walker 2004
#
# This file contains a script for sensitivity analysis
# of the American Steel transshipment model.
#
# Last modified: 27/2/2004

reset;

model transshipment.mod;
model balance_transshipment.mod;

data steel.dat;

let {(m, n) in ARCS} Cost[m, n] := Cost[m, n] / 1000;

for {n in NODES} {
  let dummyDemandCost[n] := 0;
  let dummySupplyCost[n] := 0;  
}

include balance_transshipment.run;

option solver cplex;

solve;

display Flow;  
Note We also add a ???LINK??? check statement to our model file to ensure the problem is balanced:
check : sum {n in NODES} Supply[n] = sum {n in NODES} Demand[n];

Our solution now shows that there is 5000 ton of steel remaining at the Pittsburgh Mill, i.e., the flow from Pittsburgh to Dummy is 5000.

POST-OPTIMAL ANALYSIS

Validation For our solution to be valid we need it to be integer. Observing the Flow values shows that it is in fact integer. Moreover, no branch-and-bound nodes were required to make it integer. The transshipment problem is also naturally integer (like the transportation problem), so solving it as a linear programme will give integer solutions. In fact, any network flow problem with integer supplies, demands and arc capacities has naturally integer solutions.

Parametric Analysis If ???LINK??? sensitivity analysis shows that improvements to the objective function may be achieved by changing problem data, then we may use ???LINK??? parametric analysis to see the effect of these changes.

.
.
.
include balance_transshipment.run;

option presolve 0;
option solver cplex;
option cplex_options 'presolve 0 sensitivity';
solve;

display Flow;

display _varname, _var.down, _var.current, _var.up, _var.rc;
display _conname, _con.down, _con.current, _con.up, _con.dual;

steel_sensitivity.jpg

The sensitivity analysis shows that the solution is very sensitive to any changes in the constraint right-hand sides, with one exception ConserverFlow at Pittsburgh. However, we have variables on both sides of our constraints so we should expand our constraints to see what the right-hand side is:

steel_rhs.jpg

For the supply nodes the right-hand side is the negative of the supply, for the demand nodes the right-hand side is the demand and for the transshipment nodes the right-hand side is 0. Thus, any changes we make to the supply or demand at the nodes will affect our optimal solution. The only exception is that the right-hand side of the ConserveFlow['Pittsburgh'] can decrease without affecting our solution. Since Pittsburgh is a supply node (so the right-hand side is the negative of the supply) this means we can increase the supply at Pittsburgh without affecting our solution. This makes sense as Pittsburgh already has excess supply.

However, it seems like we can improve our objective the most by decreasing the demand at Tempe (the shadow price is 1.125), but the Allowable Minimum is such that we cannot discern what the change will be (the solution will change immediately). We can see the effect by using an ???LINK??? AMPL loop :

.
.
.
display TotalCost;

set CHANGES;
param Objective {CHANGES};

param OldDemand;

let OldDemand := Demand['Tempe'];

let CHANGES := {100..1000 by 100}; 
for {i in CHANGES} {
  
  let Demand['Tempe'] := OldDemand - i;
  display Demand['Tempe'];

  # Rebalance the problem  
  include balance_transshipment.run;
  
  solve;
  
  let Objective[i] := TotalCost;
}

steel_parametric.jpg

Note that we had to alter balance_transshipment.run to consider problems that have been balanced previously: balance_transshipment.run

let difference := (sum {s in NODES : s <> 'Dummy'} Supply[s])
                - (sum {d in NODES : d <> 'Dummy'} Demand[d]);
             
if 'Dummy' not in NODES then
  let NODES := NODES union {'Dummy'};
  
if difference > 0 then
{
  print "Total Supply > Total Demand";
  print "Solving with dummy supply node...";
  let Demand['Dummy'] := difference;
  for {n in NODES : Supply[n] > 0} {
    let ARCS := ARCS union {(n, 'Dummy')};
    let Cost[n, 'Dummy'] := dummyDemandCost[n];
  }
}
else if difference < 0 then
{
  print "WARNING: Total Supply < Total Demand, problem is infeasible!";
  print "Solving with dummy demand node...";
  let Demand['Dummy'] := - difference;
  for {n in NODES : Demand[n] > 0} {
    let ARCS := ARCS union {('Dummy', n)};
    let Cost['Dummy', n] := dummySupplyCost[n];
  }
}; # else the problem is balanced

The AMPL parametric analysis shows that, by decreasing the demand for steel at Tempe, we can get a consistent reduction in our objective function, even though this was not clear from our initial sensitivity analysis.

When we consider the sensitvity analysis for variable costs, we see that the only costs that affect our solution are the transportation costs from Pittsburgh and Youngstown to Chicago (all the other costs have Allowable Min and Allowable Max such that no "sensible" change would have any effect). Suppose American Steel are negotiating a new contract with the shipping company that takes their steel from Pittsburgh to Chicago. They estimate that they can get a reduction of around \$25/1000 ton of steel (taking the price from \$400/1000 ton to \$375/1000 ton), but want to know if they should negotiate for a lower price. The sensitivity analysis shows that below \$375/1000 ton the solution will change, so let's use parametric analysis to see what happens:

.
.
.
display TotalCost;

set CHANGES;
param Objective {CHANGES};

param OldCost;

let OldCost := Cost['Pittsburgh', 'Chicago'];

let CHANGES := {0..0.05 by 0.005}; 
for {i in CHANGES} {
  
  let Cost['Pittsburgh', 'Chicago'] := OldCost - i;
  display Cost['Pittsburgh', 'Chicago'];

  # Rebalance the problem  
  include balance_transshipment.run;
  
  solve;
  
  let Objective[i] := TotalCost;
}

The parametric analysis shows that the objective function decreases at a greater rate if the price drops below $375/1000 ton, so American Steel should try and negotiate the price down even further.

steel_cost_parametric.jpg| |*FORM FIELD Conclusions*|Conclusions|There is quite a bit of information to summarise and many ways to present it. Some suggestions include:

  1. Summarise the problem as usual and list the shipments that American Steel should make (similar to the transportation problem);
  2. Summarise the problem as usual and present a table of shipments that American Steel should make;
  3. Draw the network formulation for the problem (being sure to specify what the labels mean). Then draw the actual solution on top of the network formulation. You could colour code flows long arcs to show if they are at their bounds.

Implementation and Ongoing Monitoring

Given that the solution is very sensitive to the supply and demand amounts, careful consideration of the accuracy of these figures is important. Making sure that the bounds on the arcs are reliable is another concern.

Ongoing monitoring of the supply, demand and bounds will help American Steel to keep making good decisions. As shown in the parametric analysis, ongoing negotiation of transportation prices along important routes will help American Steel reduce their expenditure.| |*FORM FIELD ExtraForExperts*|ExtraForExperts|Another common network flow problem that uses almost the same model as transshipment is the maximum flow problem. The objective of this problem is to maximise flow through the network. The only changes to transshipment.mod are:

  1. A new variable FlowOut is introduced at each node;
  2. FlowOut has lower and upper bounds, often the upper bound is set to as the Demand at the nodes;
  3. FlowOut replaces Demand in the ConserveFlow constraints;
  4. The ConserveFlow constraint becomes an equality constraint as all flow must be accounted for (no storage at the nodes);
  5. Cost of transshipment is ignored;
  6. The objective is to maximise the total flow out of the network sum {n in NODES} FlowOut[n];
  7. The problem no longer needs to be balanced.

Maxflow.mod ???ATTACH MAXFLOW.MOD HERE???

If we set MaxOut to Demand for all nodes:

let {n in NODES} MaxOut[n] := Demand[n];
then we see that currently all the demands are being met via the American Steel distribution network (the total flow out = the total demand):

steel_maxflow_solution.jpg| |*FORM FIELD StudentTasks*|StudentTasks| 1 Solve The American Steel Problem. Write a management summary of your solution.

What to hand in Hand in your management summary.

EXTRA FOR EXPERTS' TASKS

  1. American Steel are planning a marketing campaign to increase demand in their four markets Albany, Tempe, Houston and Gary. However, they would like to know the maximum demand their distribution network can handle (in each market) before they proceed. Write a script file that uses maxflow.mod and steel.dat to find the maximum demand they can supply in each market.

What to hand in Hand in your script file and a management summary of your solution.|

META FILEATTACHMENT attachment="conserve_flow.jpg" attr="" comment="" date="1203066350" name="conserve_flow.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\conserve_flow.jpg" size="119214" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\conserve_flow.jpg" tmpFilename="" user="BaseUserMapping_333" version="1"
META FILEATTACHMENT attachment="steel_cost_parametric.jpg" attr="" comment="" date="1203066378" name="steel_cost_parametric.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_cost_parametric.jpg" size="21242" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_cost_parametric.jpg" tmpFilename="" user="BaseUserMapping_333" version="1"
META FILEATTACHMENT attachment="steel_formulation.jpg" attr="" comment="" date="1203066411" name="steel_formulation.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_formulation.jpg" size="30991" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_formulation.jpg" tmpFilename="" user="BaseUserMapping_333" version="1"
META FILEATTACHMENT attachment="steel_maxflow_solution.jpg" attr="" comment="" date="1203066451" name="steel_maxflow_solution.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_maxflow_solution.jpg" size="40059" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_maxflow_solution.jpg" tmpFilename="" user="BaseUserMapping_333" version="1"
META FILEATTACHMENT attachment="steel_network.jpg" attr="" comment="" date="1203066481" name="steel_network.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_network.jpg" size="25651" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_network.jpg" tmpFilename="" user="BaseUserMapping_333" version="1"
META FILEATTACHMENT attachment="steel_parametric.jpg" attr="" comment="" date="1203066537" name="steel_parametric.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_parametric.jpg" size="69672" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_parametric.jpg" tmpFilename="" user="BaseUserMapping_333" version="1"
META FILEATTACHMENT attachment="steel_rhs.jpg" attr="" comment="" date="1203066590" name="steel_rhs.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_rhs.jpg" size="93278" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_rhs.jpg" tmpFilename="" user="BaseUserMapping_333" version="1"
META FILEATTACHMENT attachment="steel_sensitivity.jpg" attr="" comment="" date="1203066683" name="steel_sensitivity.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_sensitivity.jpg" size="93137" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_sensitivity.jpg" tmpFilename="" user="BaseUserMapping_333" version="1"
META FILEATTACHMENT attachment="steel_solution.jpg" attr="" comment="" date="1203066761" name="steel_solution.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_solution.jpg" size="38501" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\ATransshipProb\steel_solution.jpg" tmpFilename="" user="BaseUserMapping_333" version="1"
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2020 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback