I'm working on a routing and scheduling problem in the home care services context. I consider a break as a dummy patient, so routing and scheduling are also implemented for the break node (with some conditions). For some reason, I need to determine whether a visit occurs before or after a break. I defined two binary variables "Zikt" which means if patient i is visited by doctor k on shift t before the break, and "Z'ikt" for after the break. I added 2 new constraints as follows:
S(b,k,t)-S(i,k,t) =l= M* Z(i,k,t)
Z(i,k,t) + Z'(i,k,t) =l= sum((j), X(i,j,k,t))
P.s: S(b,k,t) is the starting time of break by doctor k on shift t
S(i,k,t) is the starting time of visiting patient i by doctor k on shift t
X(i,j,k,t) is if doctor k on shift t goes from node i to node j (binary variable)
In the first constraint, if the left-hand side becomes positive, Z(i,k,t) will be 1.
The second one is guaranteeing that Z and Z' could get value if patient i was visited by doctor k on shift t.
By adding these 2 constraints to my model, the result of my S variables get wrong.
I think it's better to rewrite the first constraint so that it becomes related somehow to X(i,j,k,t), but I can not figure out how to do it.
I'd appreciate it if anyone could help me.
Thanks
Let's break down the problem and try to reframe the constraints to ensure they reflect the requirements accurately.
Firstly, your goal is to determine whether a visit to a patient \( i \) by doctor \( k \) on shift \( t \) occurs before or after a break.
Your variables:
- \( Z_{ikt} \): Binary, 1 if patient \( i \) is visited by doctor \( k \) on shift \( t \) before the break.
- \( Z'_{ikt} \): Binary, 1 if patient \( i \) is visited by doctor \( k \) on shift \( t \) after the break.
- \( S_{bkt} \): Starting time of break by doctor \( k \) on shift \( t \).
- \( S_{ikt} \): Starting time of visiting patient \( i \) by doctor \( k \) on shift \( t \).
- \( X_{ijkt} \): Binary, 1 if doctor \( k \) on shift \( t \) goes from node \( i \) to node \( j \).
Let's restate the constraints:
1. If \( S_{bkt} \) is greater than \( S_{ikt} \), then \( Z_{ikt} \) should be 1. This implies that the visit to patient \( i \) is before the break. You've used a large \( M \) to handle this condition. This is a big-M constraint and is often used in linear programming to model conditional constraints.
2. A visit can either be before the break or after the break, hence the summation of \( Z_{ikt} \) and \( Z'_{ikt} \) is 1 if patient \( i \) is visited by doctor \( k \) on shift \( t \). You've used the \( X \) variable to enforce this, which seems correct.
For the first constraint: the way you've modeled it assumes that if \( S_{bkt} - S_{ikt} \) is positive (i.e., \( S_{bkt} > S_{ikt} \)), \( Z_{ikt} \) will be 1. However, this doesn't enforce the converse (i.e., if \( S_{bkt} \leq S_{ikt} \), \( Z_{ikt} \) should be 0).
You can re-write this constraint using two inequalities to cover both scenarios:
\[
S_{bkt} - S_{ikt} \leq M(1 - Z_{ikt})
\]
\[
S_{ikt} - S_{bkt} \leq MZ_{ikt}
\]
The first equation ensures that if \( S_{bkt} \) is greater than \( S_{ikt} \), \( Z_{ikt} \) is forced to be 0. The second equation ensures the opposite.
The second constraint you provided seems to be correct. It ties the \( Z \) variables to the \( X \) variable, ensuring that \( Z \) and \( Z' \) can only be non-zero if there's a visit.
Lastly, ensure that the value of \( M \) is sufficiently large to avoid infeasibilities but not too large to cause numerical instability in the solver.
Try implementing these changes and see if they correct the issues with the \( S \) variables.