4
$\begingroup$

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}$?

$\endgroup$

3 Answers 3

4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I don't disagree with you. My actual solution will likely be data processing: separating customers "too far" in the future into a separate set to be optimized. But I was hoping for an approach that would force such "future" customers into their own route due to time requirements. $\endgroup$
    – JBinggeli
    Jan 25, 2022 at 11:51
2
$\begingroup$

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.

$\endgroup$
0
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.