I have a problem in which there are 4 vessels available to transport people from 3 different bases back to a main base.
- Vessel 1 has a capacity of 50, can make 6 round trips, and is allowed to visit bases 1 and 2.
- Vessel 2 has a capacity of 75, can make 4 round trips, and is allowed to visit bases 2 and 3.
- Vessel 3 has a capacity of 100, can make 4 round trips, and is allowed to visit bases 1 and 3.
- Vessel 4 has a capacity of 150, can make 2 round trips, and is allowed to visit all three bases.
There are 350, 400, 350 people to collect from the 3 bases respectively.
I then also have a distance matrix, indicating distance between the bases and starting base.
I have deduced that I must minimize the total distance travelled in order to provide the optimal solution.
I am struggling with the formulation of constraints - I am not sure how to mathematically represent the number of available trips and the allowed bases.
I have tried to use binary variables, to no avail, as I just can't figure out how to define them.
Any pointers would be greatly appreciated.
Thanks.
You didn't specify whether or not it is allowed for vessel to visit several bases in a round before returning to the main base. I assumed this was probably not the case. Otherwise, some minor modifications have to be made to the answer.
Let $d_j$ denote the distance from base $j$ to the main base. Moreover, let $p_{ijk}$ denote the number of people taken from base $j$ in round $k$ by vessel $i$. We first introduce binary indicator variables $x_{ijk}:$ $$x_{ijk}=\begin{cases} 1, \text{ if vessel $i$ travels to base $j$ in round $k$,}\\0, \text{ otherwise}\end{cases},$$ where $i \in\{1,2,3,4\},~j\in\{1,2,3\},~k\in \{1,2,3,4,5,6\}$.
The objective is to minimize the distances traveled by the vessels, i.e.
$$\min \sum_{i=1}^4 \sum_{j=1}^3\sum_{k=1}^6 x_{ijk}\cdot d_j$$
In case you don't only want to know how to coordinate the vessels but also want to know the total distance traveled, you have to multiply the objective function by 2 since a vessel goes back and forth if it does take a tour.
Now we have to add constraints to our program. In each run, vessel 1 can take a maximum of 50 people. We thus have to add the constraint $\sum_{j=1}^3\sum_{k=1}^6 x_{1jk}p_{1jk} \leq 50$. Accordingly, the constraints for the other two vessels are $$\sum_{j=1}^3\sum_{k=1}^6 x_{2jk}p_{2jk} \leq 75$$ $$\sum_{j=1}^3\sum_{k=1}^6 x_{3jk}p_{3jk} \leq 100$$ $$\sum_{j=1}^3\sum_{k=1}^6 x_{4jk}p_{4jk} \leq 150$$
Since each vessel can only make a given number of rounds, we have to add further constraints. Vessel 1 can make 6 runs, so we have $\sum_{j=1}^3\sum_{k=1}^6 x_{1jk} \leq 6$. Accordingly, we obtain $$\sum_{j=1}^3\sum_{k=1}^6 x_{2jk} \leq 4,$$ $$\sum_{j=1}^3\sum_{k=1}^6 x_{3jk} \leq 4$$ and $$\sum_{j=1}^3\sum_{k=1}^6 x_{4jk} \leq 2.$$
We ensure that in each round, a vessel only visits one base before returning to the main base. Here you have to make modifications if this was to be allowed (to make it possible for vessel 1 to pick up 30 people at base 1, travel to base 2, pick up 20 people there and return to main base, for example). For each vessel $i$ and for each round $k$ we add the constraint $\sum_{j=1}^3 x_{ijk}\leq 1$.
Since each vessel can only visit certain bases, we have to include this in our model. Vessel 1 can visit bases 1 and 2 but not base 3. Thus, we have $\sum_{k=1}^6 x_{13k} =0$. Accordingly, we obtain $\sum_{k=1}^6 x_{21k} =0$ and $\sum_{k=1}^6 x_{32k} =0$. There is no such constraint for vessel 4 since it can travel to all bases.
Lastly, we have to make sure that everyone gets picked up. From base 1 we have to pick up 350 people. We, hence, add the constraint $\sum_{i=1}^4 \sum_{k=1}^6 x_{i1k}\cdot p_{i1k} =350$. Accordingly, we obtain $\sum_{i=1}^4 \sum_{k=1}^6 x_{i2k}\cdot p_{i2k} =400$ and $\sum_{i=1}^4 \sum_{k=1}^6 x_{i3k}\cdot p_{i3k} =350$.
The whole problem is:
$$\min \sum_{i=1}^4 \sum_{j=1}^3\sum_{k=1}^6 x_{ijk}\cdot d_j$$ $$\sum_{j=1}^3\sum_{k=1}^6 x_{1jk}p_{1jk} \leq 50$$ $$\sum_{j=1}^3\sum_{k=1}^6 x_{2jk}p_{2jk} \leq 75$$ $$\sum_{j=1}^3\sum_{k=1}^6 x_{3jk}p_{3jk} \leq 100$$ $$\sum_{j=1}^3\sum_{k=1}^6 x_{4jk}p_{4jk} \leq 150$$ $$\sum_{j=1}^3\sum_{k=1}^6 x_{1jk} \leq 6$$ $$\sum_{j=1}^3\sum_{k=1}^6 x_{2jk} \leq 4$$ $$\sum_{j=1}^3\sum_{k=1}^6 x_{3jk} \leq 4$$ $$\sum_{j=1}^3\sum_{k=1}^6 x_{4jk} \leq 2$$ $$\sum_{j=1}^3 x_{ijk}\leq 1 ~~\forall i\in\{1,2,3,4\} \forall k\in\{1,\ldots,6\}$$ $$\sum_{k=1}^6 x_{13k} =0$$ $$\sum_{k=1}^6 x_{21k} =0$$ $$\sum_{k=1}^6 x_{32k} =0$$ $$\sum_{i=1}^4 \sum_{k=1}^6 x_{i1k}\cdot p_{i1k} =350$$ $$\sum_{i=1}^4 \sum_{k=1}^6 x_{i2k}\cdot p_{i2k} =400$$ $$\sum_{i=1}^4 \sum_{k=1}^6 x_{i3k}\cdot p_{i3k} =350$$ $$x_{ijk} \in\{0,1\} \forall i \in\{1,2,3,4\} \forall j\in\{1,2,3\} \forall k\in \{1,2,3,4,5,6\}$$ $$ p_{ijk} \in \mathbb{Z}_+ \forall i \in\{1,2,3,4\} \forall j\in\{1,2,3\} \forall k\in \{1,2,3,4,5,6\}$$