VRPTW: is there a way to prevent waiting at a node before starting service?

Question

In a typical VRPTW MIP formulation there are constraints that keep service at each node between node-specific lower and upper bounds. Using $x_{ijk}$ as a binary variable representing whether or not vehicle $k$ travels from node $i$ to node $j$, $w_{ik}$ is a variable representing the starting time at node $i$, $s_{i}$ is the service time at node $i$, $a_{i}$ and $b_{i}$ are the lower and upper bounds for service at node $i$, and $M_{ij}$ is a large scalar. The time-consistency constraints are: $$ \begin{array} \\ w_{ik} + s_{i} + t_{ij} - w_{jk} \leq (1 - x_{ijk})M_{ij} \\ w_{ik} \geq a_{i} \\ w_{ik} \leq b_{i} \end{array} $$

Such constraints keep service within the time windows. But if a vehicle arrives at the node before the lower bound, it waits at the node until it can start service. Can someone point me to constraints that will prevent a vehicle from going to the node if it will get there too early? For example, is there a way to constrain the system so that vehicle $k$ will not arrive at node $i$ until $a_{i}$?

Answer 1

IMHO, whether the vehicle arrives before $a_i$ and waits there or takes a break a block away and then shows up right on time is a matter of execution rather than something that should be explicitly enforced in the optimization model. Just tell the driver not to loiter at the node.

Answer 2

Have you tried considering it as a waiting_time_cost?

Take a look at this work by Cordeau et al. http://www.bernabe.dorronsoro.es/vrp/data/articles/VRPTW.pdf

On page 23, on the Time- and Load-Dependent Costs section, the authors explain how waiting_time / linear waiting cost can be taken into account. They also cite the work of Desaulniers, Lavigne, and Soumis from where they show their example.

Answer 3

While I agree with @RobPratt on this one, the following tweak to your model should work. Add a variable $z_i$ representing the combination of service time at $i$ and time spent loitering (somewhere) after serving location $i$. Change your first constraint to $$w_{ik} + z_{i} + t_{ij} - w_{jk} \leq (1 - x_{ijk})M_{ij}$$ and add the constraint $$w_{ik} + z_{i} + t_{ij} - w_{jk} \ge -(1 - x_{ijk})M_{ij},$$ so that service at $j$ starts exactly at arrival from $i$ when $j$ follows $i$. Finally, add the constraint $$z_i \ge s_i$$to preclude negative loitering time. I think this does what you asked in a technical sense, although in practice it may just change the problem from loitering at $j$ before service there to loitering at $i$ after service there.