Book Example: Transshipment problem#

net1.ipynb Open In Colab Kaggle Gradient Open In SageMaker Studio Lab Hits

Description: book example with general transshipment model (net1.mod)

Tags: ampl-only, ampl-book

Notebook author: Marcos Dominguez Velad <marcos@ampl.com>

Model author: N/A

# Install dependencies
%pip install -q amplpy

# Google Colab & Kaggle integration
from amplpy import AMPL, ampl_notebook

ampl = ampl_notebook(
    modules=["coin"],  # modules to install
    license_uuid="default",  # license to use
)  # instantiate AMPL object and register magics

General transshipment model#

This is a general formulation for shipments from city to city problems based on the Chapter 15 of the AMPL book. It will be modeled as a net, where nodes are cities and edges the roads/links between two cities.

  • Sets:

    • CITIES

    • LINKS within {CITIES cross CITIES} subset of the cartesian product CITIES\(\times\)CITIES

  • Parameters:

    • supply {CITIES}: supplied packages by each city

    • demand {CITIES}: demanded packages by each city

    • cost {LINKS}: cost when using a link between cities

    • capacity {LINKS}: capacity of a link (links are assumed to be independent)

  • Variables:

    • Ship {LINKS}

  • Objective: minimize total cost of shipping over all of the links.

\[ \sum \limits_{(i,j) \in LINKS} cost[i,j] \cdot Ship[i,j] \]

  • Constraints:

    • Balance {CITIES}: incoming and supplied packages are equal to outcoming and demanded packages. For each city k

\[ supply[k]+\sum \limits_{(i,k) \in LINKS} Ship[i,k] \ = \ demand[k]+\sum \limits_{(k,j) \in LINKS} Ship[k,j] \]
%%writefile net1.mod
set CITIES;
set LINKS within (CITIES cross CITIES);

param supply {CITIES} >= 0;   # amounts available at cities
param demand {CITIES} >= 0;   # amounts required at cities

check: sum {i in CITIES} supply[i] = sum {j in CITIES} demand[j];

param cost {LINKS} >= 0;      # shipment costs/1000 packages
param capacity {LINKS} >= 0;  # max packages that can be shipped

var Ship {(i,j) in LINKS} >= 0, <= capacity[i,j]; 
                              # packages to be shipped

minimize Total_Cost:
   sum {(i,j) in LINKS} cost[i,j] * Ship[i,j];

subject to Balance {k in CITIES}:
   supply[k] + sum {(i,k) in LINKS} Ship[i,k] 
      = demand[k] + sum {(k,j) in LINKS} Ship[k,j];

Writing net1.mod

%%writefile net1.dat
data;

set CITIES := PITT  NE SE  BOS EWR BWI ATL MCO ;

set LINKS := (PITT,NE) (PITT,SE)
             (NE,BOS) (NE,EWR) (NE,BWI)
             (SE,EWR) (SE,BWI) (SE,ATL) (SE,MCO);

param supply  default 0 := PITT 450 ;

param demand  default 0 :=
  BOS  90,  EWR 120,  BWI 120,  ATL  70,  MCO  50;

param:      cost  capacity  :=
  PITT NE    2.5    250
  PITT SE    3.5    250

  NE BOS     1.7    100
  NE EWR     0.7    100
  NE BWI     1.3    100

  SE EWR     1.3    100
  SE BWI     0.8    100
  SE ATL     0.2    100
  SE MCO     2.1    100 ;

Writing net1.dat

%%ampl_eval
model net1.mod;
data net1.dat;
option solver cbc;
solve;
display Ship;

CBC 2.10.5: CBC 2.10.5 optimal, objective 1819
1 iterations
Ship :=
NE   BOS    90
NE   BWI    60
NE   EWR   100
PITT NE    250
PITT SE    200
SE   ATL    70
SE   BWI    60
SE   EWR    20
SE   MCO    50
;