How to write a constraints on a first nodes for a courier-package problem?

Question

We have an employee whose job is to pick up and deliver some packages, and they have each a capacity of C. They can also pick up multiple packages in their route, and packages can be transferred between couriers. To solve this problem, we wish to use the following variables:

$x_{i,j,c}$ which is a binary that equals 1 if courier c travels between $(i,j)$

$a_{i,j,c,p}$ which is a binary that equals 1 if courier $c$ carries package $p$ on the route from $(i,j)$

$g_{i,c,p}$ which is a binary that equals 1 if courier $c$ gather up package p at $i$

$d_{i,c,p}$ which is a binary that equals 1 if courier $c$ drops off package p at $i$

We have some constraints, the one relating to these variables are:

$a_{i,j,c,p} \le x_{i,j,c} \qquad $ meaning that if courier $c$ passes $(i,j)$ then he can carry $p$ also.

$ g_{i,c,p} \le \sum_j a_{i,j,c,p} \qquad $ meaning that if package $p$ is gathered by $c$ at $i$ then they must travel to immediate place after $i$

$ \sum_i g_{i,c,p} = \sum_j d_{j,c,p} \qquad $ meaning that if package $p$ is gathered by $c$ it should also be dropp-off by $c$

What I'm thinking on how to write is this one:

How can we ensure that if a courier is carrying a package on a route (i.e. $\qquad a_{i,j,c,p} = 1, a_{j,j_1,c,p} = 1, ..., a_{j_k,j_{k+1},c,p} = 1 \qquad$, then they must have already picked it up at the first nodes i.e. $ \qquad g_{i,c,p}=1 $?

Answer 1

Try this (if route or arc A for $c,p$ is unique)
$ g_{i}^{cp} -1 \le \sum_{j:(i,j)\in A} a_{ij}^{cp} - \sum_{j:(i,j)\in A} a_{ji}^{cp} \le g_{i}^{cp} \quad \forall i \quad \forall c,p$
If route for employee $c$ and package $p$ isn't unique then M has to be used
$ M(g_{i}^{cp} -1) \le \sum_{j:(i,j)\in A} a_{ij}^{cp} - \sum_{j:(i,j)\in A} a_{ji}^{cp} \le Mg_{i}^{cp}$

Edit: if a similar constraint for $ d_{i}^{cp}$ is needed then the following may make sense
$ \sum_{j:(i,j)\in A} a_{ij}^{cp} - \sum_{j:(i,j)\in A} a_{ji}^{cp} = g_{i}^{cp}-d_{i}^{cp} $

$ \sum_c (g_{i}^{cp}+d_{i}^{cp}) \le 1 \quad \forall i \ \ \forall p$
The first constraint ensures (for 1-0: outgoing from node $i$), $g_i =1$, (for incoming:0-1 to node $i$), $ d_i =1$
Next constraint ensures same node $i$ may not be pickp/delivery for same package and also prevents $ g_i=d_i=1$ for 1-1 scenario in first constraint which implies just an edge on the path of pickup-delivery.

Answer 2

The following is only a partial answer, for a reason I'll explain at the end. Let $\sigma(p)$ and $\delta(p)$ denote the source (origin) and destination of package $p.$ Introduce binary variables $y_{i,j,p}$ taking value 1 if and only if package $p$ traverses the arc $(i,j).$ Set $y_{i,i,p} = 0$ for all $i$ and $p.$ Add the following constraints.

• Package $p$ crosses arc $(i,j)$ if and only if exactly one courier carries it across that arc: $$y_{i,j,p}=\sum_c a_{i,j,c,p}\quad \forall i,j,p.$$
• Package $p$ leaves its origin and arrives at its destination: $$\sum_j y_{\sigma(p), j, p} = 1 = \sum_j y_{j, \delta(p), p}\quad \forall p.$$
• Other than at its origin or destination, if package $p$ arrives it must depart: $$\sum_i y_{i,j,p} = \sum_k y_{j,k,p} \quad \forall j \notin \lbrace \sigma(p), \delta(p)\rbrace.$$

You will want similar flow continuity constraints for the couriers (other than where they start or finish, a courier must exit a node the same number of times they enter it).

Now, here is why I called this a partial answer: it lacks a time dimension. You allow packages to be transferred between couriers, and this approach will allow a package $p$ to enter node $j$ via courier $c$ and exit node $j$ via courier $c'.$ What the formulation does not do is ensure that courier $c$ arrives at $j$ (carrying $p$) before $c'$ leaves $j$ (carrying $p$). Dealing with the time element will add a whole new layer of complexity (and size) to the model.