Help with Mathematical Formulation for VRP with Specific Constraints

Question

I am currently working on a Vehicle Routing Problem (VRP) with a set of specific constraints. I have a total of 19 nodes, each representing a customer location, and a depot. There are also 7 pickers available to fulfill the pick up requirements. The problem has the following characteristics:

I have a distance matrix between all 19 nodes and the depot. Each node has an associated demand representing the amount to be picked up. The pickers have a limited capacity of 25 units each. The capacity of each picker is less than the demand at every node, necessitating multiple trips.

I am seeking assistance in formulating this problem mathematically. Specifically, I need help defining the constraints to ensure that the pickers efficiently complete their tasks while considering capacity limitations and multiple trips necessity.

Data:

• Distance matrix: A 20x20 matrix representing distances between nodes and the depot.
• Demand: A list of 19 demand values, one for each node.
• Picker capacity: 25 units for each picker.
• Number of pickers: 7.

Goal:
Minimize the total distance traveled by the pickers while satisfying the pick up demands and capacity constraints.

Answer 1

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.

Answer 2

In Timefold (open source, java), start from the capacitated VRP quickstarts (see this video).

One not-very-sophisticated way to solve it:

1. If a visit has 40 units, split it up into 40 visits at the same location.
2. Create a src/main/resources/solverConfig.xml (see vaccination quickstart how) and configure ListChangeMoveSelector and ListSwapMoveSelector together with the normal change, swap and tailSwap moves. See docs.

---

A much more sophisticated way would be to not split up the demands, to drop capacity as a constraint and instead introduce a shadow variable "Visit.unitsCollectedThisFar" (and Visit.arrivalTime like in VRPTW) to force the pickers to go back-and-forth to the depot in the middle of a picking. This would scale much better in case you want to handle thousands of pickers.