Difference: AmericanSteelTransshipmentProblem (7 vs. 8)

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

 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2021 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback