Enforcing Simultaneous Arrivals

I'm recapping here an answer to a modeling question that I just posted on a help forum. (Since it will now appear in two different places, let's hope it's correct!)

The original poster (OP) was working on a routing model, in which vehicles (for which I will use $v$ and if needed $v'$ as indices) are assigned to visit customers (index $c$) at various (strictly positive) times. Different customers need different numbers of vehicles. We'll assume, for simplicity, that each customer is visited only once (or at most once, if you're allowed to blow off customers). If customers can be revisited, we can finesse it by creating clones of the customers (so $c$ and $c'$ are actually the same customer at different times).

I'll skip much of the formulation, which is irrelevant to the issue here. The problem confounding the OP was that if multiple vehicles serve the same customer, they must arrive at the same time. I suggested two ways to formulate this, described below.

Discrete time approach

Let's assume that the time frame (call it 0 to $T$) can be adequately approximated by a discrete sequence $$0=t_0 \lt t_1 \lt \dots \lt t_N=T.$$ Define a set of binary variables $x_{cvn}$ to be 1 if vehicle $v$ serves customer $c$ at time $t_n$ and 0 otherwise. To enforce the simultaneity requirement, we add the constraints $$x_{cvn} = x_{cv'n}$$for all combinations of $c$, $n$ and $v\neq v'$. The good news is that it's relatively easy to do and numerically stable. The bad news is that it requires a ton of binary variables ($C\times V\times N$, where $C$ is the number of  customers, $V$ the number of vehicles and $N$, as noted, the number of time epochs) and constraints ($C\times N \times \frac{V\times (V-1)}{2}$). The constraints could hypothetically be added "lazily" via callbacks, but I'm not sure that whether that would help or hurt performance.

Big $M$ approach

Let's stipulate, for convenience, that a vehicle is assigned arrival time 0 at a customer if the vehicle does not serve that customer. The alternative approach relies on the fact that the absolute difference between any two arrival times cannot exceed $T$. We can use a "big $M$" model with $T$ serving as our value for the infamous coefficient $M$.

Let $y_{cv}$ denote the time at which vehicle $v$ arrives at customer $c$ (or 0 if the assignment of $v$ to $c$ is not made). The $y$ variables can be considered continuous, and we do not need to discretize time. We will also need binary variables $z_{cv}$ taking the value 1 if vehicle $v$ services customer $c$ and 0 if not. We add the constraints $$y_{cv}-y_{cv'} \le T(2 - z_{cv} - z_{cv'})$$and $$y_{cv'}-y_{cv} \le T(2 - z_{cv} - z_{cv'})$$for all combinations of $c$ and $v\neq v'$. We'll also need constraints to tie $y$ and $z$ together, namely $$y_{cv}\le Tz_{cv}$$for all combinations of $c$ and $v$. If serving a customer at time 0 is not legal, and $\tau \gt 0$ is the earliest possible service time, throw in$$y_{cv}\ge \tau z_{cv}$$for all $c, v$ pairs. Using the previous notation, this requires $C\times V$ binary variables (the continuous variables are harmless) and at worst $C\times V\times (V-1)+2\times C\times V$ constraints, which is considerably more compact than the previous approach. Two possible downsides -- the only ones I see off the top of my head -- are that if $T$ is large, it may create numerical stability issues and/or cause LP relaxations to be loose (for both of which "big $M$" models are infamous).