1
$\begingroup$

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: $Z(i,k,t)$ which means if patient i is visited by doctor k on shift t before the break, and $Z'(i,k,t)$ 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)$

$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 (starting time) 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.

$\endgroup$
1

2 Answers 2

0
$\begingroup$

I'd use binary $x_{i,j}^{k,t}=1$ if $k$ visits any node (patient or break node) basically the connecting edge (between patient -break and break-patient) and just one set of binary $z_{i}^{k,t}$ to indicate if doctor has visited patient $i$ or break $b$
Let $P$ is set of patients & $B$ is set of break nodes with $I = P \cup B$ set of all nodes

Constraints
$ s_{i}^{k,t} \le Mz_i^{k,t}$

$ z_i^{k,t} \le \sum_jx_{i,j}^{k,t}+\sum_i x_{j,i}^{k,t} - 1$

$ \sum_i x_{i,j}^{k,t} \le Mz_i^{k,t}$

$ \sum_jx_{i,j}^{k,t} - \sum_i x_{i,j}^{k,t} = 0$

$ M(x_{i,j}^{k,t}-1) \le s_{j}^{k,t} - s_{i}^{k,t} \le Mx_{i,j}^{k,t}$

$\endgroup$
0
$\begingroup$

Is there a reason why you want to adjust your model? I would try to not add complexity to your mathematical model, as the solution to your initial problem should already include all the information you need, so I would rather see it as an information extraction issue. For example, if you use the Miller-Tucker-Zemlin formulation for subtour elimination purposes, you could use it to determine if a patient is visited before a break or afterward. I.e., you could simply look at the auxiliary variables (often referred to as $u_i$). If $u_i < u_j$, $i$ is visited before $j$.

$\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.