This is possible with LP but it isn't entirely straightforward.
Right out the gate, ignore n_pickers = 7
. Your objective is only on total distance and not total time, which is a very different creature; so we can imagine that an optimal system smells the same regardless of whether you have one picker or 700.
With
- picker capacity $c = 25$,
- node count $n = 19$, and
- node demand $d_i > c \; \forall i$,
There is an important pre-solve step - run a fixed number of visits to each node at full capacity equal to $$ \lfloor\frac {d_i} c \rfloor $$
After these fixed visits, we can guarantee that the remaining $0 \le d_i < c \; \forall i$.
Then you'll need distinct circuits. It's easy to prove that the maximum number of non-degenerate circuits is $n$.
With
- graph edges $e_{ijk}$ (source $i$, dest $j$ and circuit $k$),
- graph node visit assignments $a_{ik}$,
- units picked up per node visit $u_{ik}$, and
- distances $\delta_{ij}$:
Care must be taken when defining $e$. No $(i, i)$ is allowed, but some matrix transposition must be allowed. The only situation where we permit an edge to be traversed twice is if it's from the depot to a node and directly back again; so a sample solution could end up looking like
node_b 0 1 2 3 4 5 6 7 8 9 10
node_a
0 NaN 0.0 1.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0
1 0.0 NaN 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0
2 1.0 NaN NaN 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0
3 0.0 NaN NaN NaN 1.0 1.0 0.0 0.0 0.0 0.0 0.0
4 0.0 NaN NaN NaN NaN 0.0 0.0 0.0 1.0 0.0 0.0
5 0.0 NaN NaN NaN NaN NaN 0.0 0.0 0.0 0.0 1.0
6 0.0 NaN NaN NaN NaN NaN NaN 0.0 0.0 0.0 0.0
7 0.0 NaN NaN NaN NaN NaN NaN NaN 0.0 0.0 0.0
8 0.0 NaN NaN NaN NaN NaN NaN NaN NaN 0.0 1.0
9 0.0 NaN NaN NaN NaN NaN NaN NaN NaN NaN 0.0
10 0.0 NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN
with NaN
where there is no edge assignment defined. (Notice the subtrip in the above - more on that in a minute.)
Minimize the distance objective:
$$\sum_{ijk} e_{ijk} \delta_{ij}$$
Subject to the following.
The sum of visit units for each circuit must not exceed capacity:
$$\sum_i u_{ik} \le c \; \forall k$$
The sum of visit units over all circuits for each node must equal the node's demand left over from after the unconditional trips:
$$\sum_k u_{ik} = d_i \; \forall i$$
If the visit is assigned, at least one unit must be picked up, and vice versa; here a suitable $M > d_i$:
$$a_{ik} \le u_{ik} \le M a_{ik}$$
Within each circuit, for each node, the number of associated edges must either be 2 if the visit is assigned (one ingress edge, one egress edge), or 0 otherwise (notably this is conditional whereas traditional TSP is unconditional):
$$\sum_{j} e_{ijk} = 2 a_{ik} \; \forall i,k $$
Specific to the depot, for each circuit, the number of egress (and, separately, ingress) edges must be 1 if there is any visit assigned in the circuit, or 0 otherwise:
$$\frac 1 n \sum_i a_{ik} \le \sum_i e_{i0k} \le \sum_i a_{ik} \; \forall k$$
$$\frac 1 n \sum_j a_{jk} \le \sum_j e_{0jk} \le \sum_j a_{jk} \; \forall k$$
All of this will not be enough; you need subtrip elimination. Read e.g. Dantzig cutting-plane.