# Load to ship assignment problem

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?

• In a perfect matching, every load goes on exactly one ship and every ship carries exactly one load. Compare that to your problem statement.
– prubin
Apr 8 at 21:43
• @pubin I see, is it an "unbalanced" version of the assignment problem? In that case how should I formulate it? Because the number of vertices on the either side of the bipartite graph will not be the same. Apr 8 at 22:03

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.

• I think it should be something like $|\mathcal{L} - \mathcal{S}|$ extra imaginary "ships" if $\mathcal{S} < \mathcal{L}$ (and vise-versa), right? But how do I express this idea in a mathematical formula? Apr 9 at 0:24
• I was assuming an inequality constraint for the load allocated to the dummy "ship" and did not give the minimum workable capacity. The dummy "ship" needs a capacity of at least $max\lbrace 0, \vert \mathcal{L}\vert - \vert \mathcal{S}\vert\rbrace.$ If some loads have negative weights (you did not specify the sign of $w$), then you may need a larger capacity (to avoid forcing ships to take negative weight loads). Setting the capacity to $\vert \mathcal{L} \vert$ is a safe choice (assuming an inequality constraint on its load).
– prubin
Apr 9 at 16:32