Book Example: Transshipment problem#

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

Tags: ampl-book, cbc, transportation

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

Model author: N/A

# Install dependencies
%pip install -q amplpy pandas

# 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 default 0;   # amounts available at cities
param demand {CITIES} >= 0 default 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];

Overwriting net1.mod

import pandas as pd

# Set of cities
cities = ["PITT", "NE", "SE", "BOS", "EWR", "BWI", "ATL", "MCO"]

# Set of links (edges between cities)
links = [
    ("PITT", "NE"),
    ("PITT", "SE"),
    ("NE", "BOS"),
    ("NE", "EWR"),
    ("NE", "BWI"),
    ("SE", "EWR"),
    ("SE", "BWI"),
    ("SE", "ATL"),
    ("SE", "MCO"),
]

supply = {}
supply["PITT"] = 450

demand = {"BOS": 90, "EWR": 120, "BWI": 120, "ATL": 70, "MCO": 50}

# Cost and capacity per link
cost_capacity_data = {
    ("PITT", "NE"): {"cost": 2.5, "capacity": 250},
    ("PITT", "SE"): {"cost": 3.5, "capacity": 250},
    ("NE", "BOS"): {"cost": 1.7, "capacity": 100},
    ("NE", "EWR"): {"cost": 0.7, "capacity": 100},
    ("NE", "BWI"): {"cost": 1.3, "capacity": 100},
    ("SE", "EWR"): {"cost": 1.3, "capacity": 100},
    ("SE", "BWI"): {"cost": 0.8, "capacity": 100},
    ("SE", "ATL"): {"cost": 0.2, "capacity": 100},
    ("SE", "MCO"): {"cost": 2.1, "capacity": 100},
}

# Convert cost and capacity into a DataFrame
cost_capacity_df = pd.DataFrame.from_dict(cost_capacity_data, orient="index")
cost_capacity_df.index = pd.MultiIndex.from_tuples(
    cost_capacity_df.index, names=["from", "to"]
)

# Read the model
ampl.read("net1.mod")

# Load data
ampl.set["CITIES"] = cities
ampl.set["LINKS"] = links

ampl.param["supply"] = supply
ampl.param["demand"] = demand
ampl.param["cost"] = cost_capacity_df["cost"]
ampl.param["capacity"] = cost_capacity_df["capacity"]

# Solve problem
ampl.solve(solver="cbc")

# Display solution
ampl.display("Ship")

cbc 2.10.12: cbc 2.10.12: optimal solution; objective 1819
0 simplex 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
;

assert ampl.solve_result == "solved", ampl.solve_result