0

I have a problem in which there are 4 ships available to transport people from 3 different bases back to a main base.

1.Vehicle 1 has a capacity of 50, can make 6 round trips and is allowed to visit bases 1 and 2.

2.Vehicle 2 has a capacity of 75, can make 4 round trips and is allowed to visit bases 2 and 3.

3.Vehicle 3 has a capacity of 100, can make 4 round trips and is allowed to visit bases 1 and 3.

4.Vehicle 4 has a capacity of 150, can make 2 round trips and is allowed to visit all 3 bases.

There are 350, 400, 350 people to collect from the 3 bases respectively.

RobPratt
  • 45,619
  • 1
    "split delivery vehicle routing problem" – RobPratt Apr 07 '22 at 23:49
  • Does your given set of routes specify the number of passengers from each base? What are your decision variables? – RobPratt Apr 08 '22 at 01:07
  • That decision variable will not suffice because the numbers of people from each base can be different for each round trip of that same ship and route. – RobPratt Apr 08 '22 at 01:24

1 Answers1

1

Let $p_b$ be the number of people at base $b$. Let $c_i$ be the capacity of ship $i$.

Let binary decision variable $x_{ijk}$ indicate whether ship $i$ uses route $j$ in trip $k$. Let nonnegative integer decision variable $y_{ijkb}$ be the number of people served at base $b$ on that trip.

The problem is to minimize $\sum_{i,j,k} d_j x_{ijk}$ subject to \begin{align} \sum_{i,j,k} y_{ijkb} &\ge p_b &&\text{for all $b$} \tag1 \\ \sum_b y_{ijkb} &\le c_i x_{ijk} &&\text{for all $i,j,k$} \tag2 \\ \sum_j x_{ijk} &\le 1 &&\text{for all $i,k$} \tag3 \end{align}

Constraint $(1)$ covers all people at base $b$. Constraint $(2)$ enforces both the capacity of ship $i$ and the logical implication $y_{ijkb} > 0 \implies x_{ijk} = 1$. Constraint $(3)$ enforces at most one route per ship and trip.

RobPratt
  • 45,619