Load to ship assignment problem

Question

Problem

We’d like to optimize the delivery of loads across a network using a fleet of ships. Assume there is a set of $\mathcal{S}$ ships that need to deliver the set of $\mathcal{L}$ loads in a single day. Let the profit of moving load $j ∈ \mathcal{L}$ with ship $i \in \mathcal{S}$ be given by $w_{ij}$.

• The ship can also chose to not move a load at all (and stay put) at $0$ profit.
• Assume we can only assign a ship to one load per day
• A load may be taken by at most one ship
• Not all loads necessarily need to be moved.

I need to make a model for optimizing profit by formulating the assignment problem for a single day as an integer program and a continuous LP version of it.

Here is my take:

We can model this problem as in a weighted bipartite graph, a matching of a given size, in which the sum of weights of the edges is maximum. Each edge $(i, j)$, where $i$ is in $\mathcal{S}$ and $j$ is in $\mathcal{L}$, has a profit $w_{ij}$. For each edge $(i, j)$ we have a variable $x_{ij}$. The variable is $1$ if the edge is contained in the matching and $0$ otherwise, so we set the domain constraints:

$$ x_{ij} = \{0, 1\} \quad \text{for} \quad i, j \in \mathcal{S},\mathcal{L} $$

The total weight of the matching is

$$ \sum_{(i,j) \in \mathcal{S} \times \mathcal{L}} x_{ij} w_{ij} $$

The goal is to find a perfect matching that maximizes the above objective function. To guarantee that the variables represent a perfect matching, we add constraints saying that each vertex is adjacent to exactly one edge in the matching, i.e,

$$ \sum_{j \in \mathcal{L}} x_{ij} = 1 \quad \text{for} \quad i \in \mathcal{S}\\ \sum_{i \in \mathcal{S}} x_{ij} = 1 \quad \text{for} \quad j \in \mathcal{L} $$

Therefore, the problem can be formulated as –

$$ \begin{eqnarray} \text{maximize} & \sum_{(i,j) \in \mathcal{S} \times \mathcal{L}} x_{ij}w_{ij}\\ \text{subject to} \\ & \sum_{j \in \mathcal{L}} x_{ij} = 1 \quad \text{for} \quad i \in \mathcal{S}\notag \\ & \sum_{i \in \mathcal{S}} x_{ij} = 1 \quad \text{for} \quad j \in \mathcal{L}\notag \\ \text{where,} \qquad & x_{ij} = \{0,1\} \quad \text{for} \quad i,j \in \mathcal{S},\mathcal{L} \notag \end{eqnarray} $$

LP version:

We can solve it without the integrality constraints, using standard methods for solving continuous linear programs. We can just use this constraint instead –

$$ \begin{eqnarray} 0 \leq x_{ij} \leq 1 \quad \text{for} \quad i,j \in \mathcal{S},\mathcal{L} \end{eqnarray} $$

Am I doing it right?

Answer 1

You can treat this as a generalized assignment problem, assigning loads to ships, with real ships having capacity one load each and with a dummy "ship" with capacity $\vert \mathcal{L} \vert$ representing loads that are not moved.